h**t
发帖数: 1678 | 1 两种方法底下有很多人都做出来了。最简单的方法是求array的和，求1-1000的和，求两者差。面试的人给我的algorithm是，假设原来的arry是a，另创一个array b， 把a中的element作b 的index: 例如a10的数是3，那末在b3里存1。每次存入1到b里时都check，如果已经有1存入就是重复的那个了。第二题同理可作。
还是希望能拿到on site...
——————————————————————————
应该算很简单的，我实在是比较水，学艺不精：
1) a big array with a thousand elements storing integers from 1 to 1000, not
sorted. One number is duplicated. How do you find the duplicated number
most efficiently.
2) an array with 1000-1 elements storing integers from 1 to 1000, not sorted
. one number is missing in the array. How do you find that missing number in
the most efficient way.
想听听大家的法子，学习学习。晚些时候我来更新interviewer 给我的答案。 |
f***g
发帖数: 214 | 2 确实经典。
不过第一题是不是描述的有点问题：
既然1000个elements，储存了1-1000，一个重复，那还有一个misssing？ |
r*****l
发帖数: 2859 | 3 这个这个：全加起来再和sum(1:999)比。
In the 2nd problem, looks like 1000-2 elements, or 1000 is stored.
not
sorted
in
【在 h**t 的大作中提到】
: 两种方法底下有很多人都做出来了。最简单的方法是求array的和，求1-1000的和，求两者差。面试的人给我的algorithm是，假设原来的arry是a，另创一个array b， 把a中的element作b 的index: 例如a10的数是3，那末在b3里存1。每次存入1到b里时都check，如果已经有1存入就是重复的那个了。第二题同理可作。
: 还是希望能拿到on site...
: ——————————————————————————
: 应该算很简单的，我实在是比较水，学艺不精：
: 1) a big array with a thousand elements storing integers from 1 to 1000, not
: sorted. One number is duplicated. How do you find the duplicated number
: most efficiently.
: 2) an array with 1000-1 elements storing integers from 1 to 1000, not sorted
: . one number is missing in the array. How do you find that missing number in
: the most efficient way.
|
h**t
发帖数: 1678 | 4 这两个题分开来看的，第一个题只是要找出重复的那个数
【在 f***g 的大作中提到】
: 确实经典。
: 不过第一题是不是描述的有点问题：
: 既然1000个elements，储存了1-1000，一个重复，那还有一个misssing？
|
h**t
发帖数: 1678 | 5 赞！他给了我一个algorithm去做，但是他说其实最简单的方法就是加和求差。果然是
redBull啊。。。是cs,ee背景的？
第二个题我理解就是1000个数存在999个位置里，自然会漏掉一个，求如何找到那个数
的间接方法...
【在 r*****l 的大作中提到】
: 这个这个：全加起来再和sum(1:999)比。
: In the 2nd problem, looks like 1000-2 elements, or 1000 is stored.
:
: not
: sorted
: in
|
s*****n
发帖数: 231 | |
r*****l
发帖数: 2859 | 7 第二道题也是一样的做法。
其实我想很多人都知道答案的。只不过他们没时间回答或还没看到你的贴子。
【在 h**t 的大作中提到】
: 赞！他给了我一个algorithm去做，但是他说其实最简单的方法就是加和求差。果然是
: redBull啊。。。是cs,ee背景的？
: 第二个题我理解就是1000个数存在999个位置里，自然会漏掉一个，求如何找到那个数
: 的间接方法...
|
A*********n
发帖数: 637 | 8 N年以前的面世题了,换了下.
全加起来,然后跟1~1000加起来的对比,就找出了.
not
sorted
in
【在 h**t 的大作中提到】
: 赞！他给了我一个algorithm去做，但是他说其实最简单的方法就是加和求差。果然是
: redBull啊。。。是cs,ee背景的？
: 第二个题我理解就是1000个数存在999个位置里，自然会漏掉一个，求如何找到那个数
: 的间接方法...
|
s*****y
发帖数: 897 | 9 N年以前的面世题了,换了下.
全加起来,然后跟1~1000加起来的对比,就找出了. |
s*****y
发帖数: 897 | 10 第2题，careercup 150上面有，把1000 pack到1024个number
就是pack 1001， 1002 。。。1024 number上去
然后做xor，如果没有缺少number结果应该是0，如果不为0，结果就是缺少的数。 |
|
|
h**t
发帖数: 1678 | 11 很谦虚阿。。。
【在 r*****l 的大作中提到】
: 第二道题也是一样的做法。
: 其实我想很多人都知道答案的。只不过他们没时间回答或还没看到你的贴子。
|
h**t
发帖数: 1678 | 12 我一会儿的。。。先看看大家的做法
【在 s*****n 的大作中提到】
: 楼主,把他给你的algorithm分享一下吧?
|
h**t
发帖数: 1678 | 13 看来是我复习的不到家。。。嗯哪里能找到这些面试题？精华区？careercup?
【在 A*********n 的大作中提到】
: N年以前的面世题了,换了下.
: 全加起来,然后跟1~1000加起来的对比,就找出了.
:
: not
: sorted
: in
|
h**t
发帖数: 1678 | 14 你的做法根面试的人给我的方法有些像，他给我的更好理解些。
【在 s*****y 的大作中提到】
: N年以前的面世题了,换了下.
: 全加起来,然后跟1~1000加起来的对比,就找出了.
|
r********r
发帖数: 2912 | 15 这个方法还挺巧的，相当于不用额外空间记录了各个数都出现过没有
【在 s*****y 的大作中提到】
: N年以前的面世题了,换了下.
: 全加起来,然后跟1~1000加起来的对比,就找出了.
|
h**t
发帖数: 1678 | 16 我。。。不明白。。。什莫是xor?
【在 s*****y 的大作中提到】
: 第2题，careercup 150上面有，把1000 pack到1024个number
: 就是pack 1001， 1002 。。。1024 number上去
: 然后做xor，如果没有缺少number结果应该是0，如果不为0，结果就是缺少的数。
|
i*********d
发帖数: 2739 | 17 这样做worst cast cost是多少？
【在 s*****y 的大作中提到】
: N年以前的面世题了,换了下.
: 全加起来,然后跟1~1000加起来的对比,就找出了.
|
r***y
发帖数: 4379 | 18 异或 ^
半路出家的?
【在 h**t 的大作中提到】
: 我。。。不明白。。。什莫是xor?
|
s*****y
发帖数: 897 | 19 worst case is walk through the whole array.
O(n)
【在 i*********d 的大作中提到】
: 这样做worst cast cost是多少？
|
h**t
发帖数: 1678 | 20 受鄙视了〉_<
【在 r***y 的大作中提到】
: 异或 ^
: 半路出家的?
|
|
|
r***y
发帖数: 4379 | 21 木有, 随手一问
【在 h**t 的大作中提到】
: 受鄙视了〉_<
|
r*****l
发帖数: 2859 | 22 You need to do more homework. XOR is exclusive OR.
for binary:
0 xor 0 = 1 xor 1 = 0
0 xor 1 = 1 xor 0 = 1
For any number a: a xor a = 0.
For any number a, b: a xor b xor b = a
Basically, as long as you see a variable appears even # of times in a xor
relationship, you can ignore it.
Very useful during interview.
【在 h**t 的大作中提到】
: 我。。。不明白。。。什莫是xor?
|
s*****y
发帖数: 1974 | 23 是啊，这题一般都是刚开始的开胃小菜吧
【在 s*****y 的大作中提到】
: 第2题，careercup 150上面有，把1000 pack到1024个number
: 就是pack 1001， 1002 。。。1024 number上去
: 然后做xor，如果没有缺少number结果应该是0，如果不为0，结果就是缺少的数。
|
b*******g
发帖数: 355 | 24 我想第一题应该是1001个elements
【在 f***g 的大作中提到】
: 确实经典。
: 不过第一题是不是描述的有点问题：
: 既然1000个elements，储存了1-1000，一个重复，那还有一个misssing？
|
n*******t
发帖数: 77 | 25 我觉得也是
【在 b*******g 的大作中提到】
: 我想第一题应该是1001个elements
|
p*********9
发帖数: 277 | 26 should classify them as brainteaser problem, not algorithm problem. |
y***m
发帖数: 7027 | 27 俺觉得考这种题对一个训练有数的人很简单吧？ 对第一次碰到的人就要考量考量。
结论：这种题没有太多区分度....
求两者差。面试的人给我的algorithm是，假设原来的arry是a，另创一个array b， 把
a中的element作b 的index: 例如a10的数是3，那末在b3里存1。每次存入1到b里时都
check，如果已经有1存入就
not
sorted
in
【在 h**t 的大作中提到】
: 两种方法底下有很多人都做出来了。最简单的方法是求array的和，求1-1000的和，求两者差。面试的人给我的algorithm是，假设原来的arry是a，另创一个array b， 把a中的element作b 的index: 例如a10的数是3，那末在b3里存1。每次存入1到b里时都check，如果已经有1存入就是重复的那个了。第二题同理可作。
: 还是希望能拿到on site...
: ——————————————————————————
: 应该算很简单的，我实在是比较水，学艺不精：
: 1) a big array with a thousand elements storing integers from 1 to 1000, not
: sorted. One number is duplicated. How do you find the duplicated number
: most efficiently.
: 2) an array with 1000-1 elements storing integers from 1 to 1000, not sorted
: . one number is missing in the array. How do you find that missing number in
: the most efficient way.
|
s****z
发帖数: 37 | 28 这道题正是我用来面试人的算法题啊. 可是面试了那么多人, 没有一个给出这个XOR算
法的. 对于高速ASIC设计来说, XOR算法最好, 没有CARRY-CHAIN, 可以并行处理, 而且
不需要额外的STORAGE. |
b*******8
发帖数: 37364 | 29 先看看异或，再看看加。不行再问问，哈希、位图这些行不行，额外空间有多少，到这
里基本就出来了。实在不行就In Place排序了。这套思路可以解决不少题目，至少有的
跟他扯蛋半天，不会哑场。 |
h**t
发帖数: 1678 | 30 两种方法底下有很多人都做出来了。最简单的方法是求array的和，求1-1000的和，求两者差。面试的人给我的algorithm是，假设原来的arry是a，另创一个array b， 把a中的element作b 的index: 例如a10的数是3，那末在b3里存1。每次存入1到b里时都check，如果已经有1存入就是重复的那个了。第二题同理可作。
还是希望能拿到on site...
——————————————————————————
应该算很简单的，我实在是比较水，学艺不精：
1) a big array with a thousand elements storing integers from 1 to 1000, not
sorted. One number is duplicated. How do you find the duplicated number
most efficiently.
2) an array with 1000-1 elements storing integers from 1 to 1000, not sorted
. one number is missing in the array. How do you find that missing number in
the most efficient way.
想听听大家的法子，学习学习。晚些时候我来更新interviewer 给我的答案。 |
|
|
f***g
发帖数: 214 | 31 确实经典。
不过第一题是不是描述的有点问题：
既然1000个elements，储存了1-1000，一个重复，那还有一个misssing？ |
r*****l
发帖数: 2859 | 32 这个这个：全加起来再和sum(1:999)比。
In the 2nd problem, looks like 1000-2 elements, or 1000 is stored.
not
sorted
in
【在 h**t 的大作中提到】
: 两种方法底下有很多人都做出来了。最简单的方法是求array的和，求1-1000的和，求两者差。面试的人给我的algorithm是，假设原来的arry是a，另创一个array b， 把a中的element作b 的index: 例如a10的数是3，那末在b3里存1。每次存入1到b里时都check，如果已经有1存入就是重复的那个了。第二题同理可作。
: 还是希望能拿到on site...
: ——————————————————————————
: 应该算很简单的，我实在是比较水，学艺不精：
: 1) a big array with a thousand elements storing integers from 1 to 1000, not
: sorted. One number is duplicated. How do you find the duplicated number
: most efficiently.
: 2) an array with 1000-1 elements storing integers from 1 to 1000, not sorted
: . one number is missing in the array. How do you find that missing number in
: the most efficient way.
|
h**t
发帖数: 1678 | 33 这两个题分开来看的，第一个题只是要找出重复的那个数
【在 f***g 的大作中提到】
: 确实经典。
: 不过第一题是不是描述的有点问题：
: 既然1000个elements，储存了1-1000，一个重复，那还有一个misssing？
|
h**t
发帖数: 1678 | 34 赞！他给了我一个algorithm去做，但是他说其实最简单的方法就是加和求差。果然是
redBull啊。。。是cs,ee背景的？
第二个题我理解就是1000个数存在999个位置里，自然会漏掉一个，求如何找到那个数
的间接方法...
【在 r*****l 的大作中提到】
: 这个这个：全加起来再和sum(1:999)比。
: In the 2nd problem, looks like 1000-2 elements, or 1000 is stored.
:
: not
: sorted
: in
|
s*****n
发帖数: 231 | 35 楼主,把他给你的algorithm分享一下吧? |
r*****l
发帖数: 2859 | 36 第二道题也是一样的做法。
其实我想很多人都知道答案的。只不过他们没时间回答或还没看到你的贴子。
【在 h**t 的大作中提到】
: 赞！他给了我一个algorithm去做，但是他说其实最简单的方法就是加和求差。果然是
: redBull啊。。。是cs,ee背景的？
: 第二个题我理解就是1000个数存在999个位置里，自然会漏掉一个，求如何找到那个数
: 的间接方法...
|
A*********n
发帖数: 637 | 37 N年以前的面世题了,换了下.
全加起来,然后跟1~1000加起来的对比,就找出了.
not
sorted
in
【在 h**t 的大作中提到】
: 赞！他给了我一个algorithm去做，但是他说其实最简单的方法就是加和求差。果然是
: redBull啊。。。是cs,ee背景的？
: 第二个题我理解就是1000个数存在999个位置里，自然会漏掉一个，求如何找到那个数
: 的间接方法...
|
s*****y
发帖数: 897 | 38 N年以前的面世题了,换了下.
全加起来,然后跟1~1000加起来的对比,就找出了.
---------------------------------
你这样子就是一定要遍历n个element，我记得经典做法是
假设array是A[0]----A[5]
array是 2，1，1，0，4，3
A[0] = 2， 把A[0]和A[2]换，array变成 1， 1， 2， 0， 4， 3
如何A[i]=i，就可以跳过，继续看A[0]， A[0]=1， detect到A[1]已经有1了，
找到Duplicate是1。
我这里number从0开始，从1开始的数稍微改动一下。 |
s*****y
发帖数: 897 | 39 第2题，careercup 150上面有，把1000 pack到1024个number
就是pack 1001， 1002 。。。1024 number上去
然后做xor，如果没有缺少number结果应该是0，如果不为0，结果就是缺少的数。 |
h**t
发帖数: 1678 | 40 很谦虚阿。。。
【在 r*****l 的大作中提到】
: 第二道题也是一样的做法。
: 其实我想很多人都知道答案的。只不过他们没时间回答或还没看到你的贴子。
|
|
|
h**t
发帖数: 1678 | 41 我一会儿的。。。先看看大家的做法
【在 s*****n 的大作中提到】
: 楼主,把他给你的algorithm分享一下吧?
|
h**t
发帖数: 1678 | 42 看来是我复习的不到家。。。嗯哪里能找到这些面试题？精华区？careercup?
【在 A*********n 的大作中提到】
: N年以前的面世题了,换了下.
: 全加起来,然后跟1~1000加起来的对比,就找出了.
:
: not
: sorted
: in
|
h**t
发帖数: 1678 | 43 你的做法根面试的人给我的方法有些像，他给我的更好理解些。
【在 s*****y 的大作中提到】
: N年以前的面世题了,换了下.
: 全加起来,然后跟1~1000加起来的对比,就找出了.
: ---------------------------------
: 你这样子就是一定要遍历n个element，我记得经典做法是
: 假设array是A[0]----A[5]
: array是 2，1，1，0，4，3
: A[0] = 2， 把A[0]和A[2]换，array变成 1， 1， 2， 0， 4， 3
: 如何A[i]=i，就可以跳过，继续看A[0]， A[0]=1， detect到A[1]已经有1了，
: 找到Duplicate是1。
: 我这里number从0开始，从1开始的数稍微改动一下。
|
r********r
发帖数: 2912 | 44 这个方法还挺巧的，相当于不用额外空间记录了各个数都出现过没有
【在 s*****y 的大作中提到】
: N年以前的面世题了,换了下.
: 全加起来,然后跟1~1000加起来的对比,就找出了.
: ---------------------------------
: 你这样子就是一定要遍历n个element，我记得经典做法是
: 假设array是A[0]----A[5]
: array是 2，1，1，0，4，3
: A[0] = 2， 把A[0]和A[2]换，array变成 1， 1， 2， 0， 4， 3
: 如何A[i]=i，就可以跳过，继续看A[0]， A[0]=1， detect到A[1]已经有1了，
: 找到Duplicate是1。
: 我这里number从0开始，从1开始的数稍微改动一下。
|
h**t
发帖数: 1678 | 45 我。。。不明白。。。什莫是xor?
【在 s*****y 的大作中提到】
: 第2题，careercup 150上面有，把1000 pack到1024个number
: 就是pack 1001， 1002 。。。1024 number上去
: 然后做xor，如果没有缺少number结果应该是0，如果不为0，结果就是缺少的数。
|
i*********d
发帖数: 2739 | 46 这样做worst cast cost是多少？
【在 s*****y 的大作中提到】
: N年以前的面世题了,换了下.
: 全加起来,然后跟1~1000加起来的对比,就找出了.
: ---------------------------------
: 你这样子就是一定要遍历n个element，我记得经典做法是
: 假设array是A[0]----A[5]
: array是 2，1，1，0，4，3
: A[0] = 2， 把A[0]和A[2]换，array变成 1， 1， 2， 0， 4， 3
: 如何A[i]=i，就可以跳过，继续看A[0]， A[0]=1， detect到A[1]已经有1了，
: 找到Duplicate是1。
: 我这里number从0开始，从1开始的数稍微改动一下。
|
r***y
发帖数: 4379 | 47 异或 ^
半路出家的?
【在 h**t 的大作中提到】
: 我。。。不明白。。。什莫是xor?
|
s*****y
发帖数: 897 | 48 worst case is walk through the whole array.
O(n)
【在 i*********d 的大作中提到】
: 这样做worst cast cost是多少？
|
h**t
发帖数: 1678 | 49 受鄙视了〉_<
【在 r***y 的大作中提到】
: 异或 ^
: 半路出家的?
|
r***y
发帖数: 4379 | 50 木有, 随手一问
【在 h**t 的大作中提到】
: 受鄙视了〉_<
|
|
|
r*****l
发帖数: 2859 | 51 You need to do more homework. XOR is exclusive OR.
for binary:
0 xor 0 = 1 xor 1 = 0
0 xor 1 = 1 xor 0 = 1
For any number a: a xor a = 0.
For any number a, b: a xor b xor b = a
Basically, as long as you see a variable appears even # of times in a xor
relationship, you can ignore it.
Very useful during interview.
【在 h**t 的大作中提到】
: 我。。。不明白。。。什莫是xor?
|
s*****y
发帖数: 1974 | 52 是啊，这题一般都是刚开始的开胃小菜吧
【在 s*****y 的大作中提到】
: 第2题，careercup 150上面有，把1000 pack到1024个number
: 就是pack 1001， 1002 。。。1024 number上去
: 然后做xor，如果没有缺少number结果应该是0，如果不为0，结果就是缺少的数。
|
b*******g
发帖数: 355 | 53 我想第一题应该是1001个elements
【在 f***g 的大作中提到】
: 确实经典。
: 不过第一题是不是描述的有点问题：
: 既然1000个elements，储存了1-1000，一个重复，那还有一个misssing？
|
n*******t
发帖数: 77 | 54 我觉得也是
【在 b*******g 的大作中提到】
: 我想第一题应该是1001个elements
|
p*********9
发帖数: 277 | 55 should classify them as brainteaser problem, not algorithm problem. |
y***m
发帖数: 7027 | 56 俺觉得考这种题对一个训练有数的人很简单吧？ 对第一次碰到的人就要考量考量。
结论：这种题没有太多区分度....
求两者差。面试的人给我的algorithm是，假设原来的arry是a，另创一个array b， 把
a中的element作b 的index: 例如a10的数是3，那末在b3里存1。每次存入1到b里时都
check，如果已经有1存入就是br />
not
sorted
in
【在 h**t 的大作中提到】
: 两种方法底下有很多人都做出来了。最简单的方法是求array的和，求1-1000的和，求两者差。面试的人给我的algorithm是，假设原来的arry是a，另创一个array b， 把a中的element作b 的index: 例如a10的数是3，那末在b3里存1。每次存入1到b里时都check，如果已经有1存入就是重复的那个了。第二题同理可作。
: 还是希望能拿到on site...
: ——————————————————————————
: 应该算很简单的，我实在是比较水，学艺不精：
: 1) a big array with a thousand elements storing integers from 1 to 1000, not
: sorted. One number is duplicated. How do you find the duplicated number
: most efficiently.
: 2) an array with 1000-1 elements storing integers from 1 to 1000, not sorted
: . one number is missing in the array. How do you find that missing number in
: the most efficient way.
|
s****z
发帖数: 37 | 57 这道题正是我用来面试人的算法题啊. 可是面试了那么多人, 没有一个给出这个XOR算
法的. 对于高速ASIC设计来说, XOR算法最好, 没有CARRY-CHAIN, 可以并行处理, 而且
不需要额外的STORAGE. |
b*******8
发帖数: 37364 | 58 先看看异或，再看看加。不行再问问，哈希、位图这些行不行，额外空间有多少，到这
里基本就出来了。实在不行就In Place排序了。这套思路可以解决不少题目，至少有的
跟他扯蛋半天，不会哑场。 |
Y**B
发帖数: 144 | 59 如果第一题按照原题意，1000个元素有一个是重复的，那么你们的加加减减的方法根本
不好使。面试管的答案才是他的题目的正解。
注意审题！！ |
a********n
发帖数: 1287 | 60 同样有这个问题i,如果是这样的话，就不能用求和的方法做了吧。
【在 f***g 的大作中提到】
: 确实经典。
: 不过第一题是不是描述的有点问题：
: 既然1000个elements，储存了1-1000，一个重复，那还有一个misssing？
|
|
|
k****n
发帖数: 369 | 61 这题做法很多，只知道一种显然是不够的
【在 s*****y 的大作中提到】
: N年以前的面世题了,换了下.
: 全加起来,然后跟1~1000加起来的对比,就找出了.
: ---------------------------------
: 你这样子就是一定要遍历n个element，我记得经典做法是
: 假设array是A[0]----A[5]
: array是 2，1，1，0，4，3
: A[0] = 2， 把A[0]和A[2]换，array变成 1， 1， 2， 0， 4， 3
: 如何A[i]=i，就可以跳过，继续看A[0]， A[0]=1， detect到A[1]已经有1了，
: 找到Duplicate是1。
: 我这里number从0开始，从1开始的数稍微改动一下。
|
