z**a
发帖数: 69 | 1 两轮店面。第一轮看面试官的名字，应该是以前在本版被抱怨的很多回的华裔面试官。
不过个人感觉真人却不像很多人抱怨的那样糟糕，其实我觉得他还挺不错的。面试题只
有一道，怎么查找一个数组中缺省的那一个整数，是的，不难找到方法。他会不停改变
条件，然后我给出不同的方法。最后一点是数据很大，而且数组不可变，如何找。给我
的提示用二分，不过到最后我都没做出来。其实在编程珠玑上有类似的题，可惜我没看
过。。。出乎意料，我最后拿到了二面。二面的题目也不难，数独valid，实现vector
类。当天拿到了Onsite。
Onsite签了NDA所以不透题了，其实也没什么必要透题，题目真心不难，可以说是在
leetcode平均水平，甚至以下，什么树啊，图啊，dp啊根本没有，链表都没。不过面试
官会追问很多细节的地方，比如代码的效率和改进，数据的overflow，进程空间等基础
概念，一个二分查找搞了我40分钟。三轮coding，我觉得我死在第三轮了，题目没听清
。。。写到最后才知道会错意了，当场就要崩溃。第四轮是design，我觉得不难，面试
官引导的很好，我也算是把自己能说得上的都表达出来了。最后看起来面试官也比较满
意。
第二天得到消息，挂了，HR说是slightly under the bar，可能也是客套话吧。
总体来说，题目都不是很难。以我的经验来看，编程之美和编程珠玑很重要。我所被问
到的coding题几乎都可以在这两本书上看到。
Onsite除了机票旅店，只给报$100，打车都不够啊。 |
y***n
发帖数: 1594 | |
h*******e
发帖数: 1377 | 3 也是一个比赛。
【在 y***n 的大作中提到】
: 编程之美第一次听说。。
|
h*******e
发帖数: 1377 | 4 讨论一下first missing postive integer吧。。比如最后一问不能swap那么
unordered_set让用不呢。 |
z**a
发帖数: 69 | 5 是value [1, n]中的n-1长数组缺省的值，并非first missing value。时间复杂度O(
nlogn)。
【在 h*******e 的大作中提到】
: 讨论一下first missing postive integer吧。。比如最后一问不能swap那么
: unordered_set让用不呢。
|
h*******e
发帖数: 1377 | 6 还有楼主关于vmware。。。求公共祖先 它让你用tarjan 算法么,如果用，不光要记住
大体算法，还要写个并查集类哦。。。。 |
h*******e
发帖数: 1377 | 7 http://segmentfault.com/q/1010000000359749
类似这个？
【在 z**a 的大作中提到】
: 是value [1, n]中的n-1长数组缺省的值，并非first missing value。时间复杂度O(
: nlogn)。
|
z**a
发帖数: 69 | 8 没听说过。。。应该没这么高级吧，说实话，面了公司也不少了，还真没碰到过要求特
别高级方法的题。dp碰到过一次而已。感觉还是细节更重要。
【在 h*******e 的大作中提到】
: 还有楼主关于vmware。。。求公共祖先 它让你用tarjan 算法么,如果用，不光要记住
: 大体算法，还要写个并查集类哦。。。。
|
z**a
发帖数: 69 | 9 不是这个，这个我答上来了。。。不对。 mid=highValue-(highValue-lowValue)/2(二
分要这么写）。 然后算多少比mid小，多少比mid大，update highValue和lowValue，
找到target Value，这就是缺省的值了。
【在 h*******e 的大作中提到】
: http://segmentfault.com/q/1010000000359749
: 类似这个？
|
h*******e
发帖数: 1377 | 10 确实细节很重要啊。
【在 z**a 的大作中提到】
: 没听说过。。。应该没这么高级吧，说实话，面了公司也不少了，还真没碰到过要求特
: 别高级方法的题。dp碰到过一次而已。感觉还是细节更重要。
|
|
|
q********c
发帖数: 1774 | 11 数组是sorted的吗？
【在 z**a 的大作中提到】
: 是value [1, n]中的n-1长数组缺省的值，并非first missing value。时间复杂度O(
: nlogn)。
|
z**a
发帖数: 69 | 12 当然不是。。。
【在 q********c 的大作中提到】
: 数组是sorted的吗？
|
h*******e
发帖数: 1377 | 13 我把缺省理解成缺少了， 我还是没明白题意哦。什么样的数组（排过序的？随机的数
组？ 数组大小多少 （n-1? n?)， 怎么数组是１开头呢）找什么样的值哦,给定的
值么，还是中值，还是top k（第k大的值）呢。
【在 z**a 的大作中提到】
: 不是这个，这个我答上来了。。。不对。 mid=highValue-(highValue-lowValue)/2(二
: 分要这么写）。 然后算多少比mid小，多少比mid大，update highValue和lowValue，
: 找到target Value，这就是缺省的值了。
|
z**a
发帖数: 69 | 14 长n-1的正整数数组，值的范围是1~n，不重复，所以有且有一个值缺省。无序，要求O
（1）空间，O(nlogn）时间。不允许改动原数组。找到那个缺省的值。
【在 h*******e 的大作中提到】
: 我把缺省理解成缺少了， 我还是没明白题意哦。什么样的数组（排过序的？随机的数
: 组？ 数组大小多少 （n-1? n?)， 怎么数组是１开头呢）找什么样的值哦,给定的
: 值么，还是中值，还是top k（第k大的值）呢。
|
h*******e
发帖数: 1377 | 15 明白了
O
【在 z**a 的大作中提到】
: 长n-1的正整数数组，值的范围是1~n，不重复，所以有且有一个值缺省。无序，要求O
: （1）空间，O(nlogn）时间。不允许改动原数组。找到那个缺省的值。
|
v***o
发帖数: 287 | 16 简单啊。。。
vector
【在 z**a 的大作中提到】
: 两轮店面。第一轮看面试官的名字，应该是以前在本版被抱怨的很多回的华裔面试官。
: 不过个人感觉真人却不像很多人抱怨的那样糟糕，其实我觉得他还挺不错的。面试题只
: 有一道，怎么查找一个数组中缺省的那一个整数，是的，不难找到方法。他会不停改变
: 条件，然后我给出不同的方法。最后一点是数据很大，而且数组不可变，如何找。给我
: 的提示用二分，不过到最后我都没做出来。其实在编程珠玑上有类似的题，可惜我没看
: 过。。。出乎意料，我最后拿到了二面。二面的题目也不难，数独valid，实现vector
: 类。当天拿到了Onsite。
: Onsite签了NDA所以不透题了，其实也没什么必要透题，题目真心不难，可以说是在
: leetcode平均水平，甚至以下，什么树啊，图啊，dp啊根本没有，链表都没。不过面试
: 官会追问很多细节的地方，比如代码的效率和改进，数据的overflow，进程空间等基础
|
l***s
发帖数: 15 | 17 是不是 用 counting sort 类似，
1. scan through the whole array; count # of 1 ~ n/2
2. then decide to count half of (1～n/2) or half of (n/2 - n)
3. repeat logn times.
O
【在 z**a 的大作中提到】
: 长n-1的正整数数组，值的范围是1~n，不重复，所以有且有一个值缺省。无序，要求O
: （1）空间，O(nlogn）时间。不允许改动原数组。找到那个缺省的值。
|
q********c
发帖数: 1774 | 18 到底是O(nlogn)时间还是log(n)时间?
O
【在 z**a 的大作中提到】
: 长n-1的正整数数组，值的范围是1~n，不重复，所以有且有一个值缺省。无序，要求O
: （1）空间，O(nlogn）时间。不允许改动原数组。找到那个缺省的值。
|
l*****7
发帖数: 55 | 19 无序，怎么O(logn)?
【在 q********c 的大作中提到】
: 到底是O(nlogn)时间还是log(n)时间?
:
: O
|
z**a
发帖数: 69 | 20 不错，虽然我不认为这和counting sort类似
【在 l***s 的大作中提到】
: 是不是 用 counting sort 类似，
: 1. scan through the whole array; count # of 1 ~ n/2
: 2. then decide to count half of (1～n/2) or half of (n/2 - n)
: 3. repeat logn times.
:
: O
|
|
|
z**a
发帖数: 69 | 21 我似乎没说过logn吧
【在 q********c 的大作中提到】
: 到底是O(nlogn)时间还是log(n)时间?
:
: O
|
w******e
发帖数: 1621 | 22 缺省是default的意思吧 lz是说缺少的值么 |
h*******e
发帖数: 1377 | 23 你的二分方法我懂了，那么n*(n + 1)/2 对于1-n求和, 再减数组里面所有的数的和得出
missing的数呢？ O(1)空间，O(n)时间,不改原数组的。
O
【在 z**a 的大作中提到】
: 长n-1的正整数数组，值的范围是1~n，不重复，所以有且有一个值缺省。无序，要求O
: （1）空间，O(nlogn）时间。不允许改动原数组。找到那个缺省的值。
|
n*********d
发帖数: 1603 | 24 对啊 这个方法很赞啊，不过有点类似脑筋急转弯，纯粹数学而不是coding问题了
而且n稍微大一点就得溢出了，得边求和边减
得出
【在 h*******e 的大作中提到】
: 你的二分方法我懂了，那么n*(n + 1)/2 对于1-n求和, 再减数组里面所有的数的和得出
: missing的数呢？ O(1)空间，O(n)时间,不改原数组的。
:
: O
|
z**a
发帖数: 69 | 25 这方法挺好，如果不是我题目表述有错，那就是我们两个当时都SB了。。。
得出
【在 h*******e 的大作中提到】
: 你的二分方法我懂了，那么n*(n + 1)/2 对于1-n求和, 再减数组里面所有的数的和得出
: missing的数呢？ O(1)空间，O(n)时间,不改原数组的。
:
: O
|
h*******e
发帖数: 1377 | 26 也可能面试官题意没太说清。
【在 z**a 的大作中提到】
: 这方法挺好，如果不是我题目表述有错，那就是我们两个当时都SB了。。。
:
: 得出
|
m*****k
发帖数: 731 | 27 this is the math solution, 马工面试要考虑溢出。
就像2分查找算mid一样，不是直接(low+high)/2的。
得出
【在 h*******e 的大作中提到】
: 你的二分方法我懂了，那么n*(n + 1)/2 对于1-n求和, 再减数组里面所有的数的和得出
: missing的数呢？ O(1)空间，O(n)时间,不改原数组的。
:
: O
|
J***u
发帖数: 18 | |
h*******e
发帖数: 1377 | 29 可不可以事先估算n*(n+1)/2的范围如果比较大的话用 java big integer 或者 c++
string 算乘法。
如果数再大存不下， 存在外存上，比如 硬盘文件阿神马的
【在 m*****k 的大作中提到】
: this is the math solution, 马工面试要考虑溢出。
: 就像2分查找算mid一样，不是直接(low+high)/2的。
:
: 得出
|
h*******e
发帖数: 1377 | 30 你后来说得xor不错的。 加加减减也会溢出的 n^2 级别的数 当数组是递减情况。
【在 m*****k 的大作中提到】
: this is the math solution, 马工面试要考虑溢出。
: 就像2分查找算mid一样，不是直接(low+high)/2的。
:
: 得出
|
|
|
h*******e
发帖数: 1377 | 31 恩，以前以为xor光可以用在数组有只一个元素出现一次其他元素两次用xor， 现在发
现数组里面如果2个元素出现一次， 其它元素出现两次，或者数组n个连续数 少了一个
都可以用xor阿， xor真是用途多哦。
【在 J***u 的大作中提到】
: xor
|
t*******y
发帖数: 22 | 32 how to use xor for this question?
int findMissingNumber(int a[], int len, int minNum, int maxNum){
int middle = minNum + (maxNum-minNum)/2;
int count_smaller = 0;
int count_greater = 0;
for(int i=0; i
if(a[i]>=minNum && a[i]<=middle) count_smaller++;
else if(a[i]>middle && a[i]<=maxNum) count_greater++;
}
if(count_smaller < (middle-minNum+1)){
if(middle==minNum) return middle;
else return findMissingNumber(a,len,minNum,middle);
}else{
if(middle==minNum) return middle+1;
else return findMissingNumber(a,len,middle+1,maxNum);
}
}
【在 h*******e 的大作中提到】
: 恩，以前以为xor光可以用在数组有只一个元素出现一次其他元素两次用xor， 现在发
: 现数组里面如果2个元素出现一次， 其它元素出现两次，或者数组n个连续数 少了一个
: 都可以用xor阿， xor真是用途多哦。
|
h*******e
发帖数: 1377 | 33 1 xor 2 xor3 xor 4....xor n n个数 xor 出的结果 xor arr[0]...arr[n-1] n-1个
数 得到了一个最后结果 这样只有一个元素在这个表达式中算了一遍，其他元素在这个
表达式中计算了两遍为0， 这样最后的结果就是这个missing 的元素。
【在 t*******y 的大作中提到】
: how to use xor for this question?
: int findMissingNumber(int a[], int len, int minNum, int maxNum){
: int middle = minNum + (maxNum-minNum)/2;
: int count_smaller = 0;
: int count_greater = 0;
: for(int i=0; i: if(a[i]>=minNum && a[i]<=middle) count_smaller++;
: else if(a[i]>middle && a[i]<=maxNum) count_greater++;
: }
:
|
t*******y
发帖数: 22 | 34 cool
【在 h*******e 的大作中提到】
: 1 xor 2 xor3 xor 4....xor n n个数 xor 出的结果 xor arr[0]...arr[n-1] n-1个
: 数 得到了一个最后结果 这样只有一个元素在这个表达式中算了一遍，其他元素在这个
: 表达式中计算了两遍为0， 这样最后的结果就是这个missing 的元素。
|
l*****a
发帖数: 14598 | 35 微软培训班的阿
vector
【在 z**a 的大作中提到】
: 两轮店面。第一轮看面试官的名字，应该是以前在本版被抱怨的很多回的华裔面试官。
: 不过个人感觉真人却不像很多人抱怨的那样糟糕，其实我觉得他还挺不错的。面试题只
: 有一道，怎么查找一个数组中缺省的那一个整数，是的，不难找到方法。他会不停改变
: 条件，然后我给出不同的方法。最后一点是数据很大，而且数组不可变，如何找。给我
: 的提示用二分，不过到最后我都没做出来。其实在编程珠玑上有类似的题，可惜我没看
: 过。。。出乎意料，我最后拿到了二面。二面的题目也不难，数独valid，实现vector
: 类。当天拿到了Onsite。
: Onsite签了NDA所以不透题了，其实也没什么必要透题，题目真心不难，可以说是在
: leetcode平均水平，甚至以下，什么树啊，图啊，dp啊根本没有，链表都没。不过面试
: 官会追问很多细节的地方，比如代码的效率和改进，数据的overflow，进程空间等基础
|
r****n
发帖数: 63 | 36 咦，不是MS出的那本书么？
【在 h*******e 的大作中提到】
: 也是一个比赛。
|
c****l
发帖数: 1280 | 37 "现在发
现数组里面如果2个元素出现一次， 其它元素出现两次，" 这种情况是什么意思? 用
xor
【在 h*******e 的大作中提到】
: 恩，以前以为xor光可以用在数组有只一个元素出现一次其他元素两次用xor， 现在发
: 现数组里面如果2个元素出现一次， 其它元素出现两次，或者数组n个连续数 少了一个
: 都可以用xor阿， xor真是用途多哦。
|
d*l
发帖数: 1810 | 38 还是没有弄明白啥叫一个数“缺省”?
看题目说是n-1个不重复正整数，范围从1~n，那必须有一个“缺少”的数啊。这里的缺
省和缺少是啥关系? |
m*******i
发帖数: 34 | 39 数组没有排序过的， 你这样二分法可以吗？
【在 t*******y 的大作中提到】
: how to use xor for this question?
: int findMissingNumber(int a[], int len, int minNum, int maxNum){
: int middle = minNum + (maxNum-minNum)/2;
: int count_smaller = 0;
: int count_greater = 0;
: for(int i=0; i: if(a[i]>=minNum && a[i]<=middle) count_smaller++;
: else if(a[i]>middle && a[i]<=maxNum) count_greater++;
: }
:
|
s******t
发帖数: 229 | 40
这方法应该行
【在 h*******e 的大作中提到】
: 1 xor 2 xor3 xor 4....xor n n个数 xor 出的结果 xor arr[0]...arr[n-1] n-1个
: 数 得到了一个最后结果 这样只有一个元素在这个表达式中算了一遍，其他元素在这个
: 表达式中计算了两遍为0， 这样最后的结果就是这个missing 的元素。
|
|
|
z**a
发帖数: 69 | 41 两轮店面。第一轮看面试官的名字，应该是以前在本版被抱怨的很多回的华裔面试官。
不过个人感觉真人却不像很多人抱怨的那样糟糕，其实我觉得他还挺不错的。面试题只
有一道，怎么查找一个数组中缺省的那一个整数，是的，不难找到方法。他会不停改变
条件，然后我给出不同的方法。最后一点是数据很大，而且数组不可变，如何找。给我
的提示用二分，不过到最后我都没做出来。其实在编程珠玑上有类似的题，可惜我没看
过。。。出乎意料，我最后拿到了二面。二面的题目也不难，数独valid，实现vector
类。当天拿到了Onsite。
Onsite签了NDA所以不透题了，其实也没什么必要透题，题目真心不难，可以说是在
leetcode平均水平，甚至以下，什么树啊，图啊，dp啊根本没有，链表都没。不过面试
官会追问很多细节的地方，比如代码的效率和改进，数据的overflow，进程空间等基础
概念，一个二分查找搞了我40分钟。三轮coding，我觉得我死在第三轮了，题目没听清
。。。写到最后才知道会错意了，当场就要崩溃。第四轮是design，我觉得不难，面试
官引导的很好，我也算是把自己能说得上的都表达出来了。最后看起来面试官也比较满
意。
第二天得到消息，挂了，HR说是slightly under the bar，可能也是客套话吧。
总体来说，题目都不是很难。以我的经验来看，编程之美和编程珠玑很重要。我所被问
到的coding题几乎都可以在这两本书上看到。
Onsite除了机票旅店，只给报$100，打车都不够啊。 |
y***n
发帖数: 1594 | |
h*******e
发帖数: 1377 | 43 也是一个比赛。
【在 y***n 的大作中提到】
: 编程之美第一次听说。。
|
h*******e
发帖数: 1377 | 44 讨论一下first missing postive integer吧。。比如最后一问不能swap那么
unordered_set让用不呢。 |
z**a
发帖数: 69 | 45 是value [1, n]中的n-1长数组缺省的值，并非first missing value。时间复杂度O(
nlogn)。
【在 h*******e 的大作中提到】
: 讨论一下first missing postive integer吧。。比如最后一问不能swap那么
: unordered_set让用不呢。
|
h*******e
发帖数: 1377 | 46 还有楼主关于vmware。。。求公共祖先 它让你用tarjan 算法么,如果用，不光要记住
大体算法，还要写个并查集类哦。。。。 |
h*******e
发帖数: 1377 | 47 http://segmentfault.com/q/1010000000359749
类似这个？
【在 z**a 的大作中提到】
: 是value [1, n]中的n-1长数组缺省的值，并非first missing value。时间复杂度O(
: nlogn)。
|
z**a
发帖数: 69 | 48 没听说过。。。应该没这么高级吧，说实话，面了公司也不少了，还真没碰到过要求特
别高级方法的题。dp碰到过一次而已。感觉还是细节更重要。
【在 h*******e 的大作中提到】
: 还有楼主关于vmware。。。求公共祖先 它让你用tarjan 算法么,如果用，不光要记住
: 大体算法，还要写个并查集类哦。。。。
|
z**a
发帖数: 69 | 49 不是这个，这个我答上来了。。。不对。 mid=highValue-(highValue-lowValue)/2(二
分要这么写）。 然后算多少比mid小，多少比mid大，update highValue和lowValue，
找到target Value，这就是缺省的值了。
【在 h*******e 的大作中提到】
: http://segmentfault.com/q/1010000000359749
: 类似这个？
|
h*******e
发帖数: 1377 | 50 确实细节很重要啊。
【在 z**a 的大作中提到】
: 没听说过。。。应该没这么高级吧，说实话，面了公司也不少了，还真没碰到过要求特
: 别高级方法的题。dp碰到过一次而已。感觉还是细节更重要。
|
|
|
q********c
发帖数: 1774 | 51 数组是sorted的吗？
【在 z**a 的大作中提到】
: 是value [1, n]中的n-1长数组缺省的值，并非first missing value。时间复杂度O(
: nlogn)。
|
z**a
发帖数: 69 | 52 当然不是。。。
【在 q********c 的大作中提到】
: 数组是sorted的吗？
|
h*******e
发帖数: 1377 | 53 我把缺省理解成缺少了， 我还是没明白题意哦。什么样的数组（排过序的？随机的数
组？ 数组大小多少 （n-1? n?)， 怎么数组是１开头呢）找什么样的值哦,给定的
值么，还是中值，还是top k（第k大的值）呢。
【在 z**a 的大作中提到】
: 不是这个，这个我答上来了。。。不对。 mid=highValue-(highValue-lowValue)/2(二
: 分要这么写）。 然后算多少比mid小，多少比mid大，update highValue和lowValue，
: 找到target Value，这就是缺省的值了。
|
z**a
发帖数: 69 | 54 长n-1的正整数数组，值的范围是1~n，不重复，所以有且有一个值缺省。无序，要求O
（1）空间，O(nlogn）时间。不允许改动原数组。找到那个缺省的值。
【在 h*******e 的大作中提到】
: 我把缺省理解成缺少了， 我还是没明白题意哦。什么样的数组（排过序的？随机的数
: 组？ 数组大小多少 （n-1? n?)， 怎么数组是１开头呢）找什么样的值哦,给定的
: 值么，还是中值，还是top k（第k大的值）呢。
|
h*******e
发帖数: 1377 | 55 明白了
O
【在 z**a 的大作中提到】
: 长n-1的正整数数组，值的范围是1~n，不重复，所以有且有一个值缺省。无序，要求O
: （1）空间，O(nlogn）时间。不允许改动原数组。找到那个缺省的值。
|
v***o
发帖数: 287 | 56 简单啊。。。
vector
【在 z**a 的大作中提到】
: 两轮店面。第一轮看面试官的名字，应该是以前在本版被抱怨的很多回的华裔面试官。
: 不过个人感觉真人却不像很多人抱怨的那样糟糕，其实我觉得他还挺不错的。面试题只
: 有一道，怎么查找一个数组中缺省的那一个整数，是的，不难找到方法。他会不停改变
: 条件，然后我给出不同的方法。最后一点是数据很大，而且数组不可变，如何找。给我
: 的提示用二分，不过到最后我都没做出来。其实在编程珠玑上有类似的题，可惜我没看
: 过。。。出乎意料，我最后拿到了二面。二面的题目也不难，数独valid，实现vector
: 类。当天拿到了Onsite。
: Onsite签了NDA所以不透题了，其实也没什么必要透题，题目真心不难，可以说是在
: leetcode平均水平，甚至以下，什么树啊，图啊，dp啊根本没有，链表都没。不过面试
: 官会追问很多细节的地方，比如代码的效率和改进，数据的overflow，进程空间等基础
|
l***s
发帖数: 15 | 57 是不是 用 counting sort 类似，
1. scan through the whole array; count # of 1 ~ n/2
2. then decide to count half of (1～n/2) or half of (n/2 - n)
3. repeat logn times.
O
【在 z**a 的大作中提到】
: 长n-1的正整数数组，值的范围是1~n，不重复，所以有且有一个值缺省。无序，要求O
: （1）空间，O(nlogn）时间。不允许改动原数组。找到那个缺省的值。
|
q********c
发帖数: 1774 | 58 到底是O(nlogn)时间还是log(n)时间?
O
【在 z**a 的大作中提到】
: 长n-1的正整数数组，值的范围是1~n，不重复，所以有且有一个值缺省。无序，要求O
: （1）空间，O(nlogn）时间。不允许改动原数组。找到那个缺省的值。
|
l*****7
发帖数: 55 | 59 无序，怎么O(logn)?
【在 q********c 的大作中提到】
: 到底是O(nlogn)时间还是log(n)时间?
:
: O
|
z**a
发帖数: 69 | 60 不错，虽然我不认为这和counting sort类似
【在 l***s 的大作中提到】
: 是不是 用 counting sort 类似，
: 1. scan through the whole array; count # of 1 ~ n/2
: 2. then decide to count half of (1～n/2) or half of (n/2 - n)
: 3. repeat logn times.
:
: O
|
|
|
z**a
发帖数: 69 | 61 我似乎没说过logn吧
【在 q********c 的大作中提到】
: 到底是O(nlogn)时间还是log(n)时间?
:
: O
|
w******e
发帖数: 1621 | 62 缺省是default的意思吧 lz是说缺少的值么 |
h*******e
发帖数: 1377 | 63 你的二分方法我懂了，那么n*(n + 1)/2 对于1-n求和, 再减数组里面所有的数的和得出
missing的数呢？ O(1)空间，O(n)时间,不改原数组的。
O
【在 z**a 的大作中提到】
: 长n-1的正整数数组，值的范围是1~n，不重复，所以有且有一个值缺省。无序，要求O
: （1）空间，O(nlogn）时间。不允许改动原数组。找到那个缺省的值。
|
n*********d
发帖数: 1603 | 64 对啊 这个方法很赞啊，不过有点类似脑筋急转弯，纯粹数学而不是coding问题了
而且n稍微大一点就得溢出了，得边求和边减
得出
【在 h*******e 的大作中提到】
: 你的二分方法我懂了，那么n*(n + 1)/2 对于1-n求和, 再减数组里面所有的数的和得出
: missing的数呢？ O(1)空间，O(n)时间,不改原数组的。
:
: O
|
z**a
发帖数: 69 | 65 这方法挺好，如果不是我题目表述有错，那就是我们两个当时都SB了。。。
得出
【在 h*******e 的大作中提到】
: 你的二分方法我懂了，那么n*(n + 1)/2 对于1-n求和, 再减数组里面所有的数的和得出
: missing的数呢？ O(1)空间，O(n)时间,不改原数组的。
:
: O
|
h*******e
发帖数: 1377 | 66 也可能面试官题意没太说清。
【在 z**a 的大作中提到】
: 这方法挺好，如果不是我题目表述有错，那就是我们两个当时都SB了。。。
:
: 得出
|
m*****k
发帖数: 731 | 67 this is the math solution, 马工面试要考虑溢出。
就像2分查找算mid一样，不是直接(low+high)/2的。
得出
【在 h*******e 的大作中提到】
: 你的二分方法我懂了，那么n*(n + 1)/2 对于1-n求和, 再减数组里面所有的数的和得出
: missing的数呢？ O(1)空间，O(n)时间,不改原数组的。
:
: O
|
J***u
发帖数: 18 | |
h*******e
发帖数: 1377 | 69 可不可以事先估算n*(n+1)/2的范围如果比较大的话用 java big integer 或者 c++
string 算乘法。
如果数再大存不下， 存在外存上，比如 硬盘文件阿神马的
【在 m*****k 的大作中提到】
: this is the math solution, 马工面试要考虑溢出。
: 就像2分查找算mid一样，不是直接(low+high)/2的。
:
: 得出
|
h*******e
发帖数: 1377 | 70 你后来说得xor不错的。 加加减减也会溢出的 n^2 级别的数 当数组是递减情况。
【在 m*****k 的大作中提到】
: this is the math solution, 马工面试要考虑溢出。
: 就像2分查找算mid一样，不是直接(low+high)/2的。
:
: 得出
|
|
|
h*******e
发帖数: 1377 | 71 恩，以前以为xor光可以用在数组有只一个元素出现一次其他元素两次用xor， 现在发
现数组里面如果2个元素出现一次， 其它元素出现两次，或者数组n个连续数 少了一个
都可以用xor阿， xor真是用途多哦。
【在 J***u 的大作中提到】
: xor
|
t*******y
发帖数: 22 | 72 how to use xor for this question?
int findMissingNumber(int a[], int len, int minNum, int maxNum){
int middle = minNum + (maxNum-minNum)/2;
int count_smaller = 0;
int count_greater = 0;
for(int i=0; i
if(a[i]>=minNum && a[i]<=middle) count_smaller++;
else if(a[i]>middle && a[i]<=maxNum) count_greater++;
}
if(count_smaller < (middle-minNum+1)){
if(middle==minNum) return middle;
else return findMissingNumber(a,len,minNum,middle);
}else{
if(middle==minNum) return middle+1;
else return findMissingNumber(a,len,middle+1,maxNum);
}
}
【在 h*******e 的大作中提到】
: 恩，以前以为xor光可以用在数组有只一个元素出现一次其他元素两次用xor， 现在发
: 现数组里面如果2个元素出现一次， 其它元素出现两次，或者数组n个连续数 少了一个
: 都可以用xor阿， xor真是用途多哦。
|
h*******e
发帖数: 1377 | 73 1 xor 2 xor3 xor 4....xor n n个数 xor 出的结果 xor arr[0]...arr[n-1] n-1个
数 得到了一个最后结果 这样只有一个元素在这个表达式中算了一遍，其他元素在这个
表达式中计算了两遍为0， 这样最后的结果就是这个missing 的元素。
【在 t*******y 的大作中提到】
: how to use xor for this question?
: int findMissingNumber(int a[], int len, int minNum, int maxNum){
: int middle = minNum + (maxNum-minNum)/2;
: int count_smaller = 0;
: int count_greater = 0;
: for(int i=0; i: if(a[i]>=minNum && a[i]<=middle) count_smaller++;
: else if(a[i]>middle && a[i]<=maxNum) count_greater++;
: }
:
|
t*******y
发帖数: 22 | 74 cool
【在 h*******e 的大作中提到】
: 1 xor 2 xor3 xor 4....xor n n个数 xor 出的结果 xor arr[0]...arr[n-1] n-1个
: 数 得到了一个最后结果 这样只有一个元素在这个表达式中算了一遍，其他元素在这个
: 表达式中计算了两遍为0， 这样最后的结果就是这个missing 的元素。
|
l*****a
发帖数: 14598 | 75 微软培训班的阿
vector
【在 z**a 的大作中提到】
: 两轮店面。第一轮看面试官的名字，应该是以前在本版被抱怨的很多回的华裔面试官。
: 不过个人感觉真人却不像很多人抱怨的那样糟糕，其实我觉得他还挺不错的。面试题只
: 有一道，怎么查找一个数组中缺省的那一个整数，是的，不难找到方法。他会不停改变
: 条件，然后我给出不同的方法。最后一点是数据很大，而且数组不可变，如何找。给我
: 的提示用二分，不过到最后我都没做出来。其实在编程珠玑上有类似的题，可惜我没看
: 过。。。出乎意料，我最后拿到了二面。二面的题目也不难，数独valid，实现vector
: 类。当天拿到了Onsite。
: Onsite签了NDA所以不透题了，其实也没什么必要透题，题目真心不难，可以说是在
: leetcode平均水平，甚至以下，什么树啊，图啊，dp啊根本没有，链表都没。不过面试
: 官会追问很多细节的地方，比如代码的效率和改进，数据的overflow，进程空间等基础
|
r****n
发帖数: 63 | 76 咦，不是MS出的那本书么？
【在 h*******e 的大作中提到】
: 也是一个比赛。
|
c****l
发帖数: 1280 | 77 "现在发
现数组里面如果2个元素出现一次， 其它元素出现两次，" 这种情况是什么意思? 用
xor
【在 h*******e 的大作中提到】
: 恩，以前以为xor光可以用在数组有只一个元素出现一次其他元素两次用xor， 现在发
: 现数组里面如果2个元素出现一次， 其它元素出现两次，或者数组n个连续数 少了一个
: 都可以用xor阿， xor真是用途多哦。
|
d*l
发帖数: 1810 | 78 还是没有弄明白啥叫一个数“缺省”?
看题目说是n-1个不重复正整数，范围从1~n，那必须有一个“缺少”的数啊。这里的缺
省和缺少是啥关系? |
m*******i
发帖数: 34 | 79 数组没有排序过的， 你这样二分法可以吗？
【在 t*******y 的大作中提到】
: how to use xor for this question?
: int findMissingNumber(int a[], int len, int minNum, int maxNum){
: int middle = minNum + (maxNum-minNum)/2;
: int count_smaller = 0;
: int count_greater = 0;
: for(int i=0; i: if(a[i]>=minNum && a[i]<=middle) count_smaller++;
: else if(a[i]>middle && a[i]<=maxNum) count_greater++;
: }
:
|
s******t
发帖数: 229 | 80
这方法应该行
【在 h*******e 的大作中提到】
: 1 xor 2 xor3 xor 4....xor n n个数 xor 出的结果 xor arr[0]...arr[n-1] n-1个
: 数 得到了一个最后结果 这样只有一个元素在这个表达式中算了一遍，其他元素在这个
: 表达式中计算了两遍为0， 这样最后的结果就是这个missing 的元素。
|
|
|
i*****o
发帖数: 105 | 81 how about:
x = (1+n)*n/2 - SUM(A[1]...A[n-1])
using big number for large array |
i*****o
发帖数: 105 | 82 how about:
x = (1+n)*n/2 - SUM(A[1]...A[n-1])
using big number for large array |
i*****o
发帖数: 105 | 83 how about:
x = (1+n)*n/2 - SUM(A[1]...A[n-1])
using big number for large array |
i*****o
发帖数: 105 | 84 how about:
x = (1+n)*n/2 - SUM(A[1]...A[n-1])
using big number for large array |
j****1
发帖数: 99 | 85 could you PLS share the design question? OOD or system design ? thanks |
