g*******4
发帖数: 155 | 1 找工作有点时间了，被拒也是已经成为习惯。今天的google电面感觉就不理想，约定45
分钟时间谈了半个多小时对方就挂了。
刨去简历上的问题和其他无聊的对话，两个题目如下：
1. 两个等长数组，如何判断里面的元素是不是完全一样，只是次序不对而已。
我先给的答案是两个数组排序，然后一个一个比，有点耗时，是吧？
然后要求优化，我就把一个数组放进HashSet，另外一个数组去取。对方说你这有点费
空间。
要求不费时间也不费空间，我没给出个合理的方案。
2. 这个题我完全Lost了，对方也是费了很大劲才让我明白。假设一个无穷无尽的流，
里面都是整数，每次里面随便每10个每10个取样。当然了，每次取到的样本都不一样。
要求只保留10个数字作为数组，而且这10个在整个流的出现概率和在这个数组里面出现
的概率是一样的。
哪位大侠有好的解决方案，贴上来让我看看把，也算我没白打字。 |
b*****n
发帖数: 221 | 2 第二题精华区有答案。取样有weight去参与新的sampling,这样就uniform了。
第一题估计用bitset,这样比较省空间。 |
h*******x
发帖数: 12808 | 3 恩，第一题我也没有什么好的办法。
如果是数字的话，bitset正好，不是数字的话，hash成数字就再用bitset也行，还有更
好的办法吗？
【在 b*****n 的大作中提到】
: 第二题精华区有答案。取样有weight去参与新的sampling,这样就uniform了。
: 第一题估计用bitset,这样比较省空间。
|
g*******4
发帖数: 155 | 4
第二题我也提到类似的解法，对方恩了一声就说你有啥问题了……
bitset怎么做呢？
【在 b*****n 的大作中提到】
: 第二题精华区有答案。取样有weight去参与新的sampling,这样就uniform了。
: 第一题估计用bitset,这样比较省空间。
|
d**a
发帖数: 84 | 5 1.可不可以先给整个数组算个hash值，例如就是和，然后如果不一样再排序比较？
2. 就是reservoir sampling吧
45
【在 g*******4 的大作中提到】
: 找工作有点时间了，被拒也是已经成为习惯。今天的google电面感觉就不理想，约定45
: 分钟时间谈了半个多小时对方就挂了。
: 刨去简历上的问题和其他无聊的对话，两个题目如下：
: 1. 两个等长数组，如何判断里面的元素是不是完全一样，只是次序不对而已。
: 我先给的答案是两个数组排序，然后一个一个比，有点耗时，是吧？
: 然后要求优化，我就把一个数组放进HashSet，另外一个数组去取。对方说你这有点费
: 空间。
: 要求不费时间也不费空间，我没给出个合理的方案。
: 2. 这个题我完全Lost了，对方也是费了很大劲才让我明白。假设一个无穷无尽的流，
: 里面都是整数，每次里面随便每10个每10个取样。当然了，每次取到的样本都不一样。
|
m****n
发帖数: 589 | 6 第一个，求第两组数的 sum 和 平方和，比较行不？ 平方和不行就求 三字方的和，
想加
比较，应该不会出现一样的吧
第二个，不知道哦啊
45
【在 g*******4 的大作中提到】
: 找工作有点时间了，被拒也是已经成为习惯。今天的google电面感觉就不理想，约定45
: 分钟时间谈了半个多小时对方就挂了。
: 刨去简历上的问题和其他无聊的对话，两个题目如下：
: 1. 两个等长数组，如何判断里面的元素是不是完全一样，只是次序不对而已。
: 我先给的答案是两个数组排序，然后一个一个比，有点耗时，是吧？
: 然后要求优化，我就把一个数组放进HashSet，另外一个数组去取。对方说你这有点费
: 空间。
: 要求不费时间也不费空间，我没给出个合理的方案。
: 2. 这个题我完全Lost了，对方也是费了很大劲才让我明白。假设一个无穷无尽的流，
: 里面都是整数，每次里面随便每10个每10个取样。当然了，每次取到的样本都不一样。
|
c*m
发帖数: 1114 | 7 第一题可以用对两个数组combine进行一次插入排序，碰到一样的对消，看最后是不是都
对消掉了。
时间复杂度O(n*n)虽然和冒泡排序一样，但比冒泡排序快2倍。
45
【在 g*******4 的大作中提到】
: 找工作有点时间了，被拒也是已经成为习惯。今天的google电面感觉就不理想，约定45
: 分钟时间谈了半个多小时对方就挂了。
: 刨去简历上的问题和其他无聊的对话，两个题目如下：
: 1. 两个等长数组，如何判断里面的元素是不是完全一样，只是次序不对而已。
: 我先给的答案是两个数组排序，然后一个一个比，有点耗时，是吧？
: 然后要求优化，我就把一个数组放进HashSet，另外一个数组去取。对方说你这有点费
: 空间。
: 要求不费时间也不费空间，我没给出个合理的方案。
: 2. 这个题我完全Lost了，对方也是费了很大劲才让我明白。假设一个无穷无尽的流，
: 里面都是整数，每次里面随便每10个每10个取样。当然了，每次取到的样本都不一样。
|
c*******d
发帖数: 255 | 8 cmft
我要是碰见这两题，估计也挂了
45
【在 g*******4 的大作中提到】
: 找工作有点时间了，被拒也是已经成为习惯。今天的google电面感觉就不理想，约定45
: 分钟时间谈了半个多小时对方就挂了。
: 刨去简历上的问题和其他无聊的对话，两个题目如下：
: 1. 两个等长数组，如何判断里面的元素是不是完全一样，只是次序不对而已。
: 我先给的答案是两个数组排序，然后一个一个比，有点耗时，是吧？
: 然后要求优化，我就把一个数组放进HashSet，另外一个数组去取。对方说你这有点费
: 空间。
: 要求不费时间也不费空间，我没给出个合理的方案。
: 2. 这个题我完全Lost了，对方也是费了很大劲才让我明白。假设一个无穷无尽的流，
: 里面都是整数，每次里面随便每10个每10个取样。当然了，每次取到的样本都不一样。
|
s**********h
发帖数: 19 | 9 第一题为什么不能用XOR,最后结果是0就是相等... |
H*M
发帖数: 1268 | 10 如果一个数组里面自己就XOR为0呢
【在 s**********h 的大作中提到】
: 第一题为什么不能用XOR,最后结果是0就是相等...
|
|
|
m****u
发帖数: 3915 | 11 第一题为什么要求两个等长数组？
用bitset的话怎么区分aaab和aabb？ |
r********g
发帖数: 1351 | 12 因为不等长肯定不相等啊 。。。
【在 m****u 的大作中提到】
: 第一题为什么要求两个等长数组？
: 用bitset的话怎么区分aaab和aabb？
|
r********g
发帖数: 1351 | 13 如果没有重复元素，我的idea：是不是可以用quicksort那样的，比如根据某个random值分两段，
然后比较两边长度是不是相等，然后再分。。。直到剩下一个为止，这样的好处是中间就可以
return了。
为什么我的mit格式这么奇怪，都改两回了。。
45
【在 g*******4 的大作中提到】
: 找工作有点时间了，被拒也是已经成为习惯。今天的google电面感觉就不理想，约定45
: 分钟时间谈了半个多小时对方就挂了。
: 刨去简历上的问题和其他无聊的对话，两个题目如下：
: 1. 两个等长数组，如何判断里面的元素是不是完全一样，只是次序不对而已。
: 我先给的答案是两个数组排序，然后一个一个比，有点耗时，是吧？
: 然后要求优化，我就把一个数组放进HashSet，另外一个数组去取。对方说你这有点费
: 空间。
: 要求不费时间也不费空间，我没给出个合理的方案。
: 2. 这个题我完全Lost了，对方也是费了很大劲才让我明白。假设一个无穷无尽的流，
: 里面都是整数，每次里面随便每10个每10个取样。当然了，每次取到的样本都不一样。
|
l***i
发帖数: 1309 | 14 sort and merge already achieves O(nlogn), so there is no point to post new
solution unless you have O(n) time and O(1) space. |
h********0
发帖数: 440 | 15 agree...
any trick can be used here?
【在 l***i 的大作中提到】
: sort and merge already achieves O(nlogn), so there is no point to post new
: solution unless you have O(n) time and O(1) space.
|
b******r
发帖数: 79 | 16 got the same question as the first one, but kindly allowed to use extra
space and asked to deal with special cases (i.e., duplicates)...
45
【在 g*******4 的大作中提到】
: 找工作有点时间了，被拒也是已经成为习惯。今天的google电面感觉就不理想，约定45
: 分钟时间谈了半个多小时对方就挂了。
: 刨去简历上的问题和其他无聊的对话，两个题目如下：
: 1. 两个等长数组，如何判断里面的元素是不是完全一样，只是次序不对而已。
: 我先给的答案是两个数组排序，然后一个一个比，有点耗时，是吧？
: 然后要求优化，我就把一个数组放进HashSet，另外一个数组去取。对方说你这有点费
: 空间。
: 要求不费时间也不费空间，我没给出个合理的方案。
: 2. 这个题我完全Lost了，对方也是费了很大劲才让我明白。假设一个无穷无尽的流，
: 里面都是整数，每次里面随便每10个每10个取样。当然了，每次取到的样本都不一样。
|
s*********a
发帖数: 418 | 17 在精华区哪片啊？google区？probability区？
麻烦给指一些吧
【在 b*****n 的大作中提到】
: 第二题精华区有答案。取样有weight去参与新的sampling,这样就uniform了。
: 第一题估计用bitset,这样比较省空间。
|
s********f
发帖数: 510 | 18 排序可以nlogn，比n^2快啊。
是都
【在 c*m 的大作中提到】
: 第一题可以用对两个数组combine进行一次插入排序，碰到一样的对消，看最后是不是都
: 对消掉了。
: 时间复杂度O(n*n)虽然和冒泡排序一样，但比冒泡排序快2倍。
:
: 45
|
s********f
发帖数: 510 | 19 1 知道range可以用bitmap，不知道range如果spaceO(1)最快也就是nlogn了吧？
2 第一次取样就是是头10个，第二次就是两个10的取样各50%几率再取样，
第三次就是已有的10个有2/3的几率被取，新的10个有1/3的几率被取，再取样。
第n次就是以后的按(n-1)/n的几率，新的按1/n的几率取。
45
【在 g*******4 的大作中提到】
: 找工作有点时间了，被拒也是已经成为习惯。今天的google电面感觉就不理想，约定45
: 分钟时间谈了半个多小时对方就挂了。
: 刨去简历上的问题和其他无聊的对话，两个题目如下：
: 1. 两个等长数组，如何判断里面的元素是不是完全一样，只是次序不对而已。
: 我先给的答案是两个数组排序，然后一个一个比，有点耗时，是吧？
: 然后要求优化，我就把一个数组放进HashSet，另外一个数组去取。对方说你这有点费
: 空间。
: 要求不费时间也不费空间，我没给出个合理的方案。
: 2. 这个题我完全Lost了，对方也是费了很大劲才让我明白。假设一个无穷无尽的流，
: 里面都是整数，每次里面随便每10个每10个取样。当然了，每次取到的样本都不一样。
|
g*******4
发帖数: 155 | 20 我说了排序可以这个速度，人觉得两次排序慢么……
【在 s********f 的大作中提到】
: 排序可以nlogn，比n^2快啊。
:
: 是都
|
|
|
m****u
发帖数: 3915 | 21 老大，没有不相等阿
如果有重复元素，bitset不行吧
就像aaab和aabb这两个数组，你需要记录a和b出现的次数
如果没有重复元素，用bitset可以
【在 r********g 的大作中提到】
: 因为不等长肯定不相等啊 。。。
|
m****u
发帖数: 3915 | 22 1题有重复元素的话，没法用bitmap吧
【在 s********f 的大作中提到】
: 1 知道range可以用bitmap，不知道range如果spaceO(1)最快也就是nlogn了吧？
: 2 第一次取样就是是头10个，第二次就是两个10的取样各50%几率再取样，
: 第三次就是已有的10个有2/3的几率被取，新的10个有1/3的几率被取，再取样。
: 第n次就是以后的按(n-1)/n的几率，新的按1/n的几率取。
:
: 45
|
c*m
发帖数: 1114 | 23 其实插入法虽然是n^2,很可能大多数情况下比nlog(n)的堆排序都要更有效率。
1. 大多数情况下它不需要排序完就知道结果了。
2. 排序过程中可以配合相同元素(分别在不同数组里时才执行)消去的操作,导致n比较
小。
3. Implement比较简单。
【在 s********f 的大作中提到】
: 排序可以nlogn，比n^2快啊。
:
: 是都
|
g*******y
发帖数: 1930 | 24 第一题krone电面时遇到过有很好的解法，他最后也顺利拿到google的offer
【在 m****u 的大作中提到】
: 老大，没有不相等阿
: 如果有重复元素，bitset不行吧
: 就像aaab和aabb这两个数组，你需要记录a和b出现的次数
: 如果没有重复元素，用bitset可以
|
t**********t
发帖数: 364 | 25 which is..?
【在 g*******y 的大作中提到】
: 第一题krone电面时遇到过有很好的解法，他最后也顺利拿到google的offer
|
g*******y
发帖数: 1930 | 26 等krone来解答吧，我没答案的版权的，呵呵
【在 t**********t 的大作中提到】
: which is..?
|
k***e
发帖数: 556 | 27 get some statistics i.e. moments
【在 t**********t 的大作中提到】
: which is..?
|
k***e
发帖数: 556 | 28 ft 授权你了
【在 g*******y 的大作中提到】
: 等krone来解答吧，我没答案的版权的，呵呵
|
g*******y
发帖数: 1930 | 29 赞，这么快就来罗！
【在 k***e 的大作中提到】
: get some statistics i.e. moments
|
t********1
发帖数: 266 | 30 non-CS guy's solution:
Given same length A, B python lists.
Steps:
1, turn A, B lists into associated arrays A1, B1, keys are the uniq numbers,
values are counts of the particular uniq numbers.
2, quicksort A1, B1 arrays' key space lists, so the KA1, KB1 arrays' keys
are in order.
3 compare the sorted keys sequentially (which are lists themselves), stop at:
3.1: the lengths of KA1, KB1 key lists differ.
3.2: At the same list position i, KA1[i], KB1[i] keys differ.
3.3, at the same list pos |
|
|
h*******x
发帖数: 12808 | 31 可是人间排序才是（nlogn）啊。。
是都
点费
流，
样。
【在 c*m 的大作中提到】
: 第一题可以用对两个数组combine进行一次插入排序，碰到一样的对消，看最后是不是都
: 对消掉了。
: 时间复杂度O(n*n)虽然和冒泡排序一样，但比冒泡排序快2倍。
:
: 45
|
h*******x
发帖数: 13 | 32 i think u can use an array to count the # of occurence of each number in the
first list
once that done, scan the second list to decrement the count, so finally all
array elements should be zero if two list are equal even though will
different orders.
this only causes two scan of n elements, so it is O(N), and the memeories
size is also limited to the size of yr original arrays
45
【在 g*******4 的大作中提到】
: 找工作有点时间了，被拒也是已经成为习惯。今天的google电面感觉就不理想，约定45
: 分钟时间谈了半个多小时对方就挂了。
: 刨去简历上的问题和其他无聊的对话，两个题目如下：
: 1. 两个等长数组，如何判断里面的元素是不是完全一样，只是次序不对而已。
: 我先给的答案是两个数组排序，然后一个一个比，有点耗时，是吧？
: 然后要求优化，我就把一个数组放进HashSet，另外一个数组去取。对方说你这有点费
: 空间。
: 要求不费时间也不费空间，我没给出个合理的方案。
: 2. 这个题我完全Lost了，对方也是费了很大劲才让我明白。假设一个无穷无尽的流，
: 里面都是整数，每次里面随便每10个每10个取样。当然了，每次取到的样本都不一样。
|
t********1
发帖数: 266 | 33 I mean O(nlogn) ...
numbers,
at:
【在 t********1 的大作中提到】
: non-CS guy's solution:
: Given same length A, B python lists.
: Steps:
: 1, turn A, B lists into associated arrays A1, B1, keys are the uniq numbers,
: values are counts of the particular uniq numbers.
: 2, quicksort A1, B1 arrays' key space lists, so the KA1, KB1 arrays' keys
: are in order.
: 3 compare the sorted keys sequentially (which are lists themselves), stop at:
: 3.1: the lengths of KA1, KB1 key lists differ.
: 3.2: At the same list position i, KA1[i], KB1[i] keys differ.
|
k*******s
发帖数: 134 | 34 把array里的element作为hashmap的key,key每出现一次value加1，最后比较一下两个
hashmap。O(n) |
h*******x
发帖数: 12808 | 35 第一题，用基数排序的方便行不？
45
【在 g*******4 的大作中提到】
: 找工作有点时间了，被拒也是已经成为习惯。今天的google电面感觉就不理想，约定45
: 分钟时间谈了半个多小时对方就挂了。
: 刨去简历上的问题和其他无聊的对话，两个题目如下：
: 1. 两个等长数组，如何判断里面的元素是不是完全一样，只是次序不对而已。
: 我先给的答案是两个数组排序，然后一个一个比，有点耗时，是吧？
: 然后要求优化，我就把一个数组放进HashSet，另外一个数组去取。对方说你这有点费
: 空间。
: 要求不费时间也不费空间，我没给出个合理的方案。
: 2. 这个题我完全Lost了，对方也是费了很大劲才让我明白。假设一个无穷无尽的流，
: 里面都是整数，每次里面随便每10个每10个取样。当然了，每次取到的样本都不一样。
|
r****o
发帖数: 1950 | 36 Could you give some detailed information? Hehe.
【在 k***e 的大作中提到】
: get some statistics i.e. moments
|
M***D
发帖数: 1130 | |
v****s
发帖数: 1112 | 38 what if collision?
【在 k*******s 的大作中提到】
: 把array里的element作为hashmap的key,key每出现一次value加1，最后比较一下两个
: hashmap。O(n)
|
y******0
发帖数: 80 | 39 A=[a,b,c,a]; rankA = 1+10+100+1 = 112
B=[b,c,a,a]; rankB = 10+100+1+1 = 112 |
k*******s
发帖数: 134 | 40 和collision有什么关系。如果有duplicate就加1.
当然这个方法需要space，如果space restrict就不能这样。
【在 v****s 的大作中提到】
: what if collision?
|
|
|
m****n
发帖数: 589 | 41 这个算法当字母种类多的时候,怎么分weight呀?
【在 y******0 的大作中提到】
: A=[a,b,c,a]; rankA = 1+10+100+1 = 112
: B=[b,c,a,a]; rankB = 10+100+1+1 = 112
|
a***u
发帖数: 168 | 42 一个hashmap就可以...一边加一边减. 最后走一遍看value是不是都是0
【在 k*******s 的大作中提到】
: 把array里的element作为hashmap的key,key每出现一次value加1，最后比较一下两个
: hashmap。O(n)
|
a******t
发帖数: 34 | 43 第2题10是一个整体，还是要求10个里面每一个的要单独算？
45
【在 g*******4 的大作中提到】
: 找工作有点时间了，被拒也是已经成为习惯。今天的google电面感觉就不理想，约定45
: 分钟时间谈了半个多小时对方就挂了。
: 刨去简历上的问题和其他无聊的对话，两个题目如下：
: 1. 两个等长数组，如何判断里面的元素是不是完全一样，只是次序不对而已。
: 我先给的答案是两个数组排序，然后一个一个比，有点耗时，是吧？
: 然后要求优化，我就把一个数组放进HashSet，另外一个数组去取。对方说你这有点费
: 空间。
: 要求不费时间也不费空间，我没给出个合理的方案。
: 2. 这个题我完全Lost了，对方也是费了很大劲才让我明白。假设一个无穷无尽的流，
: 里面都是整数，每次里面随便每10个每10个取样。当然了，每次取到的样本都不一样。
|
h***s
发帖数: 1716 | 44 第一题时间O(N),空间O(1).答案就是 XXX*捞个(XXX) 之类的小聪明. 第二题估计也就
是玩点基本统计的小聪明.想想当年还把收狗当那摸回事. 其实一天到晚做这种程序员
的"算法"很浪费人生...
45
【在 g*******4 的大作中提到】
: 找工作有点时间了，被拒也是已经成为习惯。今天的google电面感觉就不理想，约定45
: 分钟时间谈了半个多小时对方就挂了。
: 刨去简历上的问题和其他无聊的对话，两个题目如下：
: 1. 两个等长数组，如何判断里面的元素是不是完全一样，只是次序不对而已。
: 我先给的答案是两个数组排序，然后一个一个比，有点耗时，是吧？
: 然后要求优化，我就把一个数组放进HashSet，另外一个数组去取。对方说你这有点费
: 空间。
: 要求不费时间也不费空间，我没给出个合理的方案。
: 2. 这个题我完全Lost了，对方也是费了很大劲才让我明白。假设一个无穷无尽的流，
: 里面都是整数，每次里面随便每10个每10个取样。当然了，每次取到的样本都不一样。
|
r****o
发帖数: 1950 | 45 XXX*捞个(XXX) 是什么意思啊？
【在 h***s 的大作中提到】
: 第一题时间O(N),空间O(1).答案就是 XXX*捞个(XXX) 之类的小聪明. 第二题估计也就
: 是玩点基本统计的小聪明.想想当年还把收狗当那摸回事. 其实一天到晚做这种程序员
: 的"算法"很浪费人生...
:
: 45
|
m****n
发帖数: 589 | 46 n*log(n)?
【在 r****o 的大作中提到】
: XXX*捞个(XXX) 是什么意思啊？
|
d****j
发帖数: 293 | 47 这个主意貌似可行哦
不过首先需要直接sum和 也相等，再平方和，立方和，4次方和？
不过需要理论证明？
【在 m****n 的大作中提到】
: 第一个，求第两组数的 sum 和 平方和，比较行不？ 平方和不行就求 三字方的和，
: 想加
: 比较，应该不会出现一样的吧
: 第二个，不知道哦啊
:
: 45
|
h***s
发帖数: 1716 | 48 我随便猜猜而已, 不一定对, 就是书本上shannon entropy之类的无聊玩意. 别浪费时
间了, 人生苦短啊... 而且都是给别人打工...
【在 r****o 的大作中提到】
: XXX*捞个(XXX) 是什么意思啊？
|
m****n
发帖数: 589 | 49 x^n + y^n = z^n
在n大于2时就没有整数解?
就是不知道
x1^n+y1^n = x2^n + y2^n这种有没有
不过另外有人说用什么xxx*log(***)的方法可以
【在 d****j 的大作中提到】
: 这个主意貌似可行哦
: 不过首先需要直接sum和 也相等，再平方和，立方和，4次方和？
: 不过需要理论证明？
|
s**********y
发帖数: 1 | 50 第一题：
等长数组：A-B 等于数组C， 然后数组C内所有元素求和，如果和为零，那么说明
A=B ，否则A不等于B。
不知道对不对？ |
|
|
m****n
发帖数: 589 | 51 太模糊了....
【在 h***s 的大作中提到】
: 我随便猜猜而已, 不一定对, 就是书本上shannon entropy之类的无聊玩意. 别浪费时
: 间了, 人生苦短啊... 而且都是给别人打工...
|
m****n
发帖数: 589 | 52 不对
这个相当于求A的和，和B的和，然后和相减
【在 s**********y 的大作中提到】
: 第一题：
: 等长数组：A-B 等于数组C， 然后数组C内所有元素求和，如果和为零，那么说明
: A=B ，否则A不等于B。
: 不知道对不对？
|
h***s
发帖数: 1716 | 53 那张图挺清楚的啊...
【在 m****n 的大作中提到】
: 太模糊了....
|
m****n
发帖数: 589 | 54 哦，我Fterm下看，底色是黑的，比较模糊
换了web还蛮清楚
【在 h***s 的大作中提到】
: 那张图挺清楚的啊...
|
h***s
发帖数: 1716 | 55 其实挺好的. 要瘦狗的问我,我就折磨答他. 哈... |
l****u
发帖数: 2778 | 56 美国面试这么难啊，哎，还是回国工作吧，面试贼简单。你知道为什么么？国内谁招人
，都是招自己好管的人就行，当初我们小组招了个傻蛋说话都结巴的人，人是老实，别
人1个小时的工作量他估计一天能搞定就不错了，只要老实服管就好。 |
h***s
发帖数: 1716 | 57 我朋友自己国内开公司, 招人喜欢既聪明,又好管的...
【在 l****u 的大作中提到】
: 美国面试这么难啊，哎，还是回国工作吧，面试贼简单。你知道为什么么？国内谁招人
: ，都是招自己好管的人就行，当初我们小组招了个傻蛋说话都结巴的人，人是老实，别
: 人1个小时的工作量他估计一天能搞定就不错了，只要老实服管就好。
|
h*******x
发帖数: 12808 | 58 你这个算法是平方的，比楼主的还慢。
点费
流，
样。 |
l*e
发帖数: 187 | 59 Even if I am totally non-IT people, I am pretty sure the first one is to sum
up each group and compare the totals - based on my recollection with a
Google employee. |
b***u
发帖数: 12010 | 60 第一题用programming pearl中的in space heap sort吧，空间1时间nlogn
45
【在 g*******4 的大作中提到】
: 找工作有点时间了，被拒也是已经成为习惯。今天的google电面感觉就不理想，约定45
: 分钟时间谈了半个多小时对方就挂了。
: 刨去简历上的问题和其他无聊的对话，两个题目如下：
: 1. 两个等长数组，如何判断里面的元素是不是完全一样，只是次序不对而已。
: 我先给的答案是两个数组排序，然后一个一个比，有点耗时，是吧？
: 然后要求优化，我就把一个数组放进HashSet，另外一个数组去取。对方说你这有点费
: 空间。
: 要求不费时间也不费空间，我没给出个合理的方案。
: 2. 这个题我完全Lost了，对方也是费了很大劲才让我明白。假设一个无穷无尽的流，
: 里面都是整数，每次里面随便每10个每10个取样。当然了，每次取到的样本都不一样。
|
|
|
g*m
发帖数: 70 | 61 geniusxsy and Krone, 说说答案吧。
【在 g*******y 的大作中提到】
: 等krone来解答吧，我没答案的版权的，呵呵
|
t***t
发帖数: 6066 | |
t***t
发帖数: 6066 | 63 如果都是，用如下解法：
first let AA = 1;
assume A[i] = n, and get the nth prime number X, and AA = AA * X
do same to array B, see if AA = BB
【在 t***t 的大作中提到】
: 数组元素都是整数么？
|
w*********m
发帖数: 4740 | 64 2. reservoir sampling
45
【在 g*******4 的大作中提到】
: 找工作有点时间了，被拒也是已经成为习惯。今天的google电面感觉就不理想，约定45
: 分钟时间谈了半个多小时对方就挂了。
: 刨去简历上的问题和其他无聊的对话，两个题目如下：
: 1. 两个等长数组，如何判断里面的元素是不是完全一样，只是次序不对而已。
: 我先给的答案是两个数组排序，然后一个一个比，有点耗时，是吧？
: 然后要求优化，我就把一个数组放进HashSet，另外一个数组去取。对方说你这有点费
: 空间。
: 要求不费时间也不费空间，我没给出个合理的方案。
: 2. 这个题我完全Lost了，对方也是费了很大劲才让我明白。假设一个无穷无尽的流，
: 里面都是整数，每次里面随便每10个每10个取样。当然了，每次取到的样本都不一样。
|
d*****9
发帖数: 147 | 65 第一题，参看josh bloch的effective java里面讲到的比较通用的算hashCode 的方法。
result = 17 ;
for each element in the array {
result = 31 * result + a[i]
}
see if resultA = result B. |
t******t
发帖数: 2404 | 66 range小才行. 否则bitmap比hash还大.
【在 s********f 的大作中提到】
: 1 知道range可以用bitmap，不知道range如果spaceO(1)最快也就是nlogn了吧？
: 2 第一次取样就是是头10个，第二次就是两个10的取样各50%几率再取样，
: 第三次就是已有的10个有2/3的几率被取，新的10个有1/3的几率被取，再取样。
: 第n次就是以后的按(n-1)/n的几率，新的按1/n的几率取。
:
: 45
|
h********e
发帖数: 1972 | 67 第一题。。也许是多项式fingerprinting算法 |
c**********r
发帖数: 472 | 68 第一题前面不是有人给出最优解了么，还讨论啥。。
对两列数分统计元素的出现次数，然后比较。O（n）就搞定了，肯定没有比这个更快的
了，因为把数组看一遍就已经O（n）了，没法再快了。
第二题不太清楚，不知道是不是只允许储存10个数在内存里？？ |
t******t
发帖数: 2404 | 69 负数怎么办. get the nth prime number也很费时吧.
【在 t***t 的大作中提到】
: 如果都是，用如下解法：
: first let AA = 1;
: assume A[i] = n, and get the nth prime number X, and AA = AA * X
: do same to array B, see if AA = BB
|
c**********r
发帖数: 472 | 70 哦，我搞错了，那个解法用c#编看起来很快，但是value-key pair的查找是。net
framework提供的，效率也得算进去。 |
|
|
s********f
发帖数: 510 | 71 如果重复的不多,可以用多个bitmap
【在 m****u 的大作中提到】
: 1题有重复元素的话，没法用bitmap吧
|
j****a
发帖数: 55 | 72 我对第一题的想法是：
LZ的方法是2*n log(n) + n,最后那个n是因为两个list要比较一下。
我的想法是: 只要sort一个list，n log(n)，然后拿另外一个list的每一个数字去
sorted list里面找。这样是：n * log(n)。所以最后是2*n log(n)。
虽说两个方法都是O(nlog(n)),可是少一个n在practical programming的时候还是有可
能挺重要的... |
t******t
发帖数: 2404 | 73 怎么统计元素的出现次数?
【在 c**********r 的大作中提到】
: 第一题前面不是有人给出最优解了么，还讨论啥。。
: 对两列数分统计元素的出现次数，然后比较。O（n）就搞定了，肯定没有比这个更快的
: 了，因为把数组看一遍就已经O（n）了，没法再快了。
: 第二题不太清楚，不知道是不是只允许储存10个数在内存里？？
|
c**********r
发帖数: 472 | |
m****n
发帖数: 589 | 75 拿个数组计数？
【在 t******t 的大作中提到】
: 怎么统计元素的出现次数?
|
c**********r
发帖数: 472 | 76 数组计数的时候得查找，如果元素不是数字的话每个查找都是O(n)...
所以得用hashtable，但有hash的overhead。而且如果输入范围不确定的话，hashtable
的效率也下降。
【在 m****n 的大作中提到】
: 拿个数组计数？
|
m****n
发帖数: 589 | 77 对哦
hashtable
【在 c**********r 的大作中提到】
: 数组计数的时候得查找，如果元素不是数字的话每个查找都是O(n)...
: 所以得用hashtable，但有hash的overhead。而且如果输入范围不确定的话，hashtable
: 的效率也下降。
|
s********f
发帖数: 510 | 78 比hashtable强
the
all
【在 h*******x 的大作中提到】
: i think u can use an array to count the # of occurence of each number in the
: first list
: once that done, scan the second list to decrement the count, so finally all
: array elements should be zero if two list are equal even though will
: different orders.
: this only causes two scan of n elements, so it is O(N), and the memeories
: size is also limited to the size of yr original arrays
:
: 45
|
f*****r
发帖数: 229 | 79 看了一圈，好像quicksort的方法靠谱一些：拿一个element
来divide two arrays, then first count the numbers of each part. If they are
same, then go ahead.
Hash based methods should be also ok.
如果两个数组不一样的概率很大的话，前面提到的一些方法可以快速检测很多不一样的情况，such as, hash code, bloom filter, fingerprinting, or even moments, etc. 但是这些方法都有false positive.
【在 m****n 的大作中提到】
: 对哦
:
: hashtable
|
d******d
发帖数: 74 | 80 第一题是不是可以这样，貌似我们知道数组的大小，假设为N
每个元素看作是数字，即使是字母也当作数字好了
然后像下面这样计算每个数组：
例如数组
A: 1，7，4，4，5，6 N=6
sum(A) = 6^1+6^7+6^4+6^4+6^5+6^6 = 1112001(六进制)
这样的话只有两个数组的数字完全一样 他们的sum才会相等
时间复杂度O(N) 不需要额外的空间 |
|
|
m****0
发帖数: 30 | 81 这个..是要额外空间的,worst case
假设1，2....M (共N个，M为最大数）
按照你的算法，和>M^N
至少额外需要MlgN bit去存这个阶乘求和的结果
另外，大数做阶乘.....你的时间复杂度就不是O(N)可以搞定的了。
【在 d******d 的大作中提到】
: 第一题是不是可以这样，貌似我们知道数组的大小，假设为N
: 每个元素看作是数字，即使是字母也当作数字好了
: 然后像下面这样计算每个数组：
: 例如数组
: A: 1，7，4，4，5，6 N=6
: sum(A) = 6^1+6^7+6^4+6^4+6^5+6^6 = 1112001(六进制)
: 这样的话只有两个数组的数字完全一样 他们的sum才会相等
: 时间复杂度O(N) 不需要额外的空间
|
c****p
发帖数: 6474 | 82 4 5 vs 3 6
【在 s**********y 的大作中提到】
: 第一题：
: 等长数组：A-B 等于数组C， 然后数组C内所有元素求和，如果和为零，那么说明
: A=B ，否则A不等于B。
: 不知道对不对？
|
r**u
发帖数: 1567 | 83 You can easily get overflow.
Bitmap won't work either. Think about how much space you need for bitmap.
For unsigned int, 2^32 / 8bits/byte = 2^29 = 512MB and bitmap can't handle
duplicates. Even hash is better.
【在 d******d 的大作中提到】
: 第一题是不是可以这样，貌似我们知道数组的大小，假设为N
: 每个元素看作是数字，即使是字母也当作数字好了
: 然后像下面这样计算每个数组：
: 例如数组
: A: 1，7，4，4，5，6 N=6
: sum(A) = 6^1+6^7+6^4+6^4+6^5+6^6 = 1112001(六进制)
: 这样的话只有两个数组的数字完全一样 他们的sum才会相等
: 时间复杂度O(N) 不需要额外的空间
|
n******7
发帖数: 5678 | |
v****s
发帖数: 1112 | 85 版上牛人发散性思维真多，Fermat theorem都出来了，鼓掌！
【在 m****n 的大作中提到】
: x^n + y^n = z^n
: 在n大于2时就没有整数解?
: 就是不知道
: x1^n+y1^n = x2^n + y2^n这种有没有
: 不过另外有人说用什么xxx*log(***)的方法可以
|
s****e
发帖数: 43 | 86 but is it a sufficient condition for the equality of two arrays?
【在 k***e 的大作中提到】
: get some statistics i.e. moments
|
c********t
发帖数: 1756 | 87 数组A: 2,2,6
数组B: 3,3,4
这个算法不对；
要将Ａ，Ｂ数组中的元素hash成prime number 后求和才可以比较！
法。
【在 d*****9 的大作中提到】
: 第一题，参看josh bloch的effective java里面讲到的比较通用的算hashCode 的方法。
: result = 17 ;
: for each element in the array {
: result = 31 * result + a[i]
: }
: see if resultA = result B.
|
h*******x
发帖数: 12808 | 88 第一个怎么做到O（n）？
【在 c**********r 的大作中提到】
: 第一题前面不是有人给出最优解了么，还讨论啥。。
: 对两列数分统计元素的出现次数，然后比较。O（n）就搞定了，肯定没有比这个更快的
: 了，因为把数组看一遍就已经O（n）了，没法再快了。
: 第二题不太清楚，不知道是不是只允许储存10个数在内存里？？
|
h*******x
发帖数: 12808 | 89 最后比较hashtable的时候，就不是O（n)。
取决于hashtable的长度。
hashtable
【在 c**********r 的大作中提到】
: 数组计数的时候得查找，如果元素不是数字的话每个查找都是O(n)...
: 所以得用hashtable，但有hash的overhead。而且如果输入范围不确定的话，hashtable
: 的效率也下降。
|
F**p
发帖数: 1046 | 90 你这是浪费面试机会。
现在你不把几个书搞输，坐上几百道题目，千万别去面试。肯定死。
很简单，面试的人，都假设你做过这些事情的。就是看看你的反应。
这些题目，去找学校的教授们做，我估计没几个通过的。 |
|
|
s*****m
发帖数: 8094 | 91 那就用“天堂排序”
【在 h*******x 的大作中提到】
: 可是人间排序才是（nlogn）啊。。
:
: 是都
: 点费
: 流，
: 样。
|
s*****m
发帖数: 8094 | 92 He will get fired soon...
sum
【在 l*e 的大作中提到】
: Even if I am totally non-IT people, I am pretty sure the first one is to sum
: up each group and compare the totals - based on my recollection with a
: Google employee.
|
s*****m
发帖数: 8094 | 93 You are joking right?
prime numbers: 2,3,5,7...
the first one has 1 element: 2
the second one has 1 element: 3
【在 t***t 的大作中提到】
: 如果都是，用如下解法：
: first let AA = 1;
: assume A[i] = n, and get the nth prime number X, and AA = AA * X
: do same to array B, see if AA = BB
|
s*****m
发帖数: 8094 | 94 If only 2 elements i,j
Then result = 31*(31*17+i) + j = 31*31*17 + 31*i + j
And you mean there's no such two (i,j) can could result in the same results?
I think you are kidding as well, try i=0,j=31 and i=1,j=0
法。
【在 d*****9 的大作中提到】
: 第一题，参看josh bloch的effective java里面讲到的比较通用的算hashCode 的方法。
: result = 17 ;
: for each element in the array {
: result = 31 * result + a[i]
: }
: see if resultA = result B.
|
s*****m
发帖数: 8094 | 95 空间呢？人不是要又快又省么？
【在 c**********r 的大作中提到】
: 第一题前面不是有人给出最优解了么，还讨论啥。。
: 对两列数分统计元素的出现次数，然后比较。O（n）就搞定了，肯定没有比这个更快的
: 了，因为把数组看一遍就已经O（n）了，没法再快了。
: 第二题不太清楚，不知道是不是只允许储存10个数在内存里？？
|
s*****m
发帖数: 8094 | 96 这种divide and conquer 好像比较符合狗狗的口味，谁叫人机器多呢，不过不好弄吧
，不知道MR有
没有帮助
are
的情况，such
as, hash code, bloom filter, fingerprinting, or even moments, etc. 但是这些
方法
都有false positive.
【在 f*****r 的大作中提到】
: 看了一圈，好像quicksort的方法靠谱一些：拿一个element
: 来divide two arrays, then first count the numbers of each part. If they are
: same, then go ahead.
: Hash based methods should be also ok.
: 如果两个数组不一样的概率很大的话，前面提到的一些方法可以快速检测很多不一样的情况，such as, hash code, bloom filter, fingerprinting, or even moments, etc. 但是这些方法都有false positive.
|
s*****m
发帖数: 8094 | 97 byebye
【在 d******d 的大作中提到】
: 第一题是不是可以这样，貌似我们知道数组的大小，假设为N
: 每个元素看作是数字，即使是字母也当作数字好了
: 然后像下面这样计算每个数组：
: 例如数组
: A: 1，7，4，4，5，6 N=6
: sum(A) = 6^1+6^7+6^4+6^4+6^5+6^6 = 1112001(六进制)
: 这样的话只有两个数组的数字完全一样 他们的sum才会相等
: 时间复杂度O(N) 不需要额外的空间
|
J**i
发帖数: 166 | 98 第一题，假定都是正数，产生(0,1)之间的随机数a, 则
P(x1^a+...+xn^a == y1^a+...+yn^a | x1,...,xn != y1,...,yn) = 0
理论上这个算法是O(n)时间，O(1)空间的。
45
【在 g*******4 的大作中提到】
: 找工作有点时间了，被拒也是已经成为习惯。今天的google电面感觉就不理想，约定45
: 分钟时间谈了半个多小时对方就挂了。
: 刨去简历上的问题和其他无聊的对话，两个题目如下：
: 1. 两个等长数组，如何判断里面的元素是不是完全一样，只是次序不对而已。
: 我先给的答案是两个数组排序，然后一个一个比，有点耗时，是吧？
: 然后要求优化，我就把一个数组放进HashSet，另外一个数组去取。对方说你这有点费
: 空间。
: 要求不费时间也不费空间，我没给出个合理的方案。
: 2. 这个题我完全Lost了，对方也是费了很大劲才让我明白。假设一个无穷无尽的流，
: 里面都是整数，每次里面随便每10个每10个取样。当然了，每次取到的样本都不一样。
|
s******8
发帖数: 4192 | 99 “有点耗时，是吧？”，如果是对方问的，就是在试探你。你这个时候应该坚持，如果
用quicksort，这是最快的算法了。我觉得这才是正确答案。
当然对于这个题目，可以在quicksort第二个数组的时候做一些优化,或者用binary
search。可能快一点点，但是相对于编程工作量来说，得不偿失。
45
【在 g*******4 的大作中提到】
: 找工作有点时间了，被拒也是已经成为习惯。今天的google电面感觉就不理想，约定45
: 分钟时间谈了半个多小时对方就挂了。
: 刨去简历上的问题和其他无聊的对话，两个题目如下：
: 1. 两个等长数组，如何判断里面的元素是不是完全一样，只是次序不对而已。
: 我先给的答案是两个数组排序，然后一个一个比，有点耗时，是吧？
: 然后要求优化，我就把一个数组放进HashSet，另外一个数组去取。对方说你这有点费
: 空间。
: 要求不费时间也不费空间，我没给出个合理的方案。
: 2. 这个题我完全Lost了，对方也是费了很大劲才让我明白。假设一个无穷无尽的流，
: 里面都是整数，每次里面随便每10个每10个取样。当然了，每次取到的样本都不一样。
|
r********g
发帖数: 1351 | 100 我也觉得说“耗时”并不是说O(nlgn)的复杂度不够好，可能是，比如两次sort，然后
还有一对一的比较，如果字符串很长，这样就比较耗时，或者是这种情况必须完全sort
完了比较才能知道结果，可能有办法提前知道结果的，或者是不用具体比较数字的值，
只比较数字的多少就行了，虽然没有改变复杂度的量级，但还是应该节省了一点时间吧
；还有preprocessing阿，比如如果知道不一样的数字可能比较多，可以加起来mod一个
素数之类的...
【在 s******8 的大作中提到】
: “有点耗时，是吧？”，如果是对方问的，就是在试探你。你这个时候应该坚持，如果
: 用quicksort，这是最快的算法了。我觉得这才是正确答案。
: 当然对于这个题目，可以在quicksort第二个数组的时候做一些优化,或者用binary
: search。可能快一点点，但是相对于编程工作量来说，得不偿失。
:
: 45
|
|
|
w*********l
发帖数: 1337 | 101 你的bitset其实还是一个hash啊
【在 h*******x 的大作中提到】
: 恩，第一题我也没有什么好的办法。
: 如果是数字的话，bitset正好，不是数字的话，hash成数字就再用bitset也行，还有更
: 好的办法吗？
|
f*****r
发帖数: 229 | 102 Quick sort has some nice featurse for this question:
1) You can find if the pivot element is in both arrays. If not, then stop and return false.
2) After you divide an array o two parts based on a pivot element's value, you can count each part's element numbers. Only when those numbers are same for two arrays, you do another iteration. Otherwise, stop and return false.
Thus if two arrays are different, you have better chance to find that before you do more work.
【在 s*****m 的大作中提到】
: 这种divide and conquer 好像比较符合狗狗的口味，谁叫人机器多呢，不过不好弄吧
: ，不知道MR有
: 没有帮助
:
: are
: 的情况，such
: as, hash code, bloom filter, fingerprinting, or even moments, etc. 但是这些
: 方法
: 都有false positive.
|
t***t
发帖数: 6066 | 103 what do you mean?
in your example, AA will be 2, BB will be 3, AA != BB, so array A not equals
array B
【在 s*****m 的大作中提到】
: You are joking right?
: prime numbers: 2,3,5,7...
: the first one has 1 element: 2
: the second one has 1 element: 3
|
A*********l
发帖数: 2005 | 104 you don't really know the range of the data, right?
Suppose the array size is 1000, but the data in the array can be from 1 to 2
^30 (just an example), even counting the occurance of the elements are going
to use huge memory for the additional array to do the counting, if you want
your algorithm's run time to be O(n).
【在 s********f 的大作中提到】
: 比hashtable强
:
: the
: all
|
m********i
发帖数: 298 | 105 Solve Problem 1:
1. Sort to continuous memory block.
2. !memcmp(a,b) (which is much faster than you do element compare).
or even faster:
3. http://www-igm.univ-mlv.fr/~lecroq/string/index.html
check for Boyer-Moore algorithm
in terms of performance:
a.memcmp 530ms
b.bm algo 70ms |
s******8
发帖数: 4192 | 106 It totally depends on how the "equal" is defined for the elements.
【在 m********i 的大作中提到】
: Solve Problem 1:
: 1. Sort to continuous memory block.
: 2. !memcmp(a,b) (which is much faster than you do element compare).
: or even faster:
: 3. http://www-igm.univ-mlv.fr/~lecroq/string/index.html
: check for Boyer-Moore algorithm
: in terms of performance:
: a.memcmp 530ms
: b.bm algo 70ms
|
s*****m
发帖数: 8094 | 107 """
first let AA = 1;
assume A[i] = n, and get the nth prime number X, and AA = AA * X
do same to array B, see if AA = BB
"""
忘了，估计是看错了，不过你也错了，aa=3(p2=3)，bb=5(p3=5)
你这个会死得很难看，还得事先存一大堆素数，还不如直接count呢，还不overflow.
equals
【在 t***t 的大作中提到】
: what do you mean?
: in your example, AA will be 2, BB will be 3, AA != BB, so array A not equals
: array B
|
d********2
发帖数: 135 | 108 感觉第一题要用数学方法另辟蹊径，而非从数据结构、算法入手。六楼那意思。。。。 |
k***e
发帖数: 556 | 109 just randomly takes an integer value, say k,
then check whether \sigma_{i}X_i^k is euqal for both arrays
thus, we will choose some const c, and randomly pick c numbers, for each one
of the c numbers we do the preceding check.
Sure there are false positive, because that is an monte carlo algorithm. if
we want to bound the success probability, we need to make some assumptions
about input distribution. then we assume the inputs are randomly pick up
from the distribution and use the idea in proving
【在 k***e 的大作中提到】
: get some statistics i.e. moments
|
d******a
发帖数: 238 | 110 这种无聊的题目真是没啥意思，就跟小学参加什么个辅导班似的，知道几个trick就好
像数学学得很好似的。你让这边教授过来答，没见过的话，很多照样不知道。。。
45
【在 g*******4 的大作中提到】
: 找工作有点时间了，被拒也是已经成为习惯。今天的google电面感觉就不理想，约定45
: 分钟时间谈了半个多小时对方就挂了。
: 刨去简历上的问题和其他无聊的对话，两个题目如下：
: 1. 两个等长数组，如何判断里面的元素是不是完全一样，只是次序不对而已。
: 我先给的答案是两个数组排序，然后一个一个比，有点耗时，是吧？
: 然后要求优化，我就把一个数组放进HashSet，另外一个数组去取。对方说你这有点费
: 空间。
: 要求不费时间也不费空间，我没给出个合理的方案。
: 2. 这个题我完全Lost了，对方也是费了很大劲才让我明白。假设一个无穷无尽的流，
: 里面都是整数，每次里面随便每10个每10个取样。当然了，每次取到的样本都不一样。
|
|
|
r****o
发帖数: 1950 | 111 请问一下，你说的每次10个有p的几率被取样是这10个元素里面，每个元素被再取样的
几率是p，还是这10个元素作为整体被取样的几率是p?
比如说第2次，a1,a2,...,a10 和 a11,a12,..., a20 各50%几率被取样，是说a1到a20
每个元素都有50%被取样，还是说要么取a1,a2,...,a10或者取a11,a12,...,a20?
【在 s********f 的大作中提到】
: 1 知道range可以用bitmap，不知道range如果spaceO(1)最快也就是nlogn了吧？
: 2 第一次取样就是是头10个，第二次就是两个10的取样各50%几率再取样，
: 第三次就是已有的10个有2/3的几率被取，新的10个有1/3的几率被取，再取样。
: 第n次就是以后的按(n-1)/n的几率，新的按1/n的几率取。
:
: 45
|
h***s
发帖数: 1716 | 112 昨晚回家查了关于entropy的书,我猜的应该可以.
two-lists-of-values-are-same (array1 array2)
loop array1 and array2:
collect sum1, sum2, minimum1, minimum2, N
if NOT (sum1==sum2 & minimum1==minimum2):
return false.
initialize:
sucker1=0, sucker2=0,
normalization=sum1-N*minimum1
loop array1 and array2:
p1 = (element1 - minimum1) / normalization
p2 = (element2 - minimum2) / normalization
sum p1*捞个(p1) into sucker1
sum p2*捞个(p2) into sucker2
if (sucker1==sucker2):
return true;
else
return false.
显然计算时间循
【在 g*******4 的大作中提到】
: 找工作有点时间了，被拒也是已经成为习惯。今天的google电面感觉就不理想，约定45
: 分钟时间谈了半个多小时对方就挂了。
: 刨去简历上的问题和其他无聊的对话，两个题目如下：
: 1. 两个等长数组，如何判断里面的元素是不是完全一样，只是次序不对而已。
: 我先给的答案是两个数组排序，然后一个一个比，有点耗时，是吧？
: 然后要求优化，我就把一个数组放进HashSet，另外一个数组去取。对方说你这有点费
: 空间。
: 要求不费时间也不费空间，我没给出个合理的方案。
: 2. 这个题我完全Lost了，对方也是费了很大劲才让我明白。假设一个无穷无尽的流，
: 里面都是整数，每次里面随便每10个每10个取样。当然了，每次取到的样本都不一样。
|
h***s
发帖数: 1716 | 113 说得好... 下次狗狗来电,就回她说今天没兴趣,改日子谈. 要求面世题和算法无关, 否
则面谈.
【在 n******7 的大作中提到】
: goog 不去也罢。乱公司。
|
s********f
发帖数: 510 | 114 这和check 和相等并且平方和相等不是一个意思么.
点费
流，
样。
【在 h***s 的大作中提到】
: 昨晚回家查了关于entropy的书,我猜的应该可以.
: two-lists-of-values-are-same (array1 array2)
: loop array1 and array2:
: collect sum1, sum2, minimum1, minimum2, N
: if NOT (sum1==sum2 & minimum1==minimum2):
: return false.
: initialize:
: sucker1=0, sucker2=0,
: normalization=sum1-N*minimum1
: loop array1 and array2:
|
h***s
发帖数: 1716 | 115 如果你能证明是一个意思, 那就是一个意思. 我只想到了XXX捞个XXX, 而且这个众所周
知严格数学上成立.
【在 s********f 的大作中提到】
: 这和check 和相等并且平方和相等不是一个意思么.
:
: 点费
: 流，
: 样。
|
f*****r
发帖数: 229 | 116 Can someone explain more about the magic of XXX捞个XXX? Don't understand it.
Some naive question:
If the array has multiple minimum values, how does the method handle that? (
log(min - min) = log0).
【在 h***s 的大作中提到】
: 如果你能证明是一个意思, 那就是一个意思. 我只想到了XXX捞个XXX, 而且这个众所周
: 知严格数学上成立.
|
k*n
发帖数: 150 | 117 -1, -1, 2
1 1 -2
【在 d****j 的大作中提到】
: 这个主意貌似可行哦
: 不过首先需要直接sum和 也相等，再平方和，立方和，4次方和？
: 不过需要理论证明？
|
h***s
发帖数: 1716 | 118 0*log0 == 0 is an analytic result. So handle it when you code.
it.
(
【在 f*****r 的大作中提到】
: Can someone explain more about the magic of XXX捞个XXX? Don't understand it.
: Some naive question:
: If the array has multiple minimum values, how does the method handle that? (
: log(min - min) = log0).
|
r****k
发帖数: 173 | 119
你的解法是第一题的正解 O(n)时间，O(1)空间，
楼下那个不理解的哥们可以看看补充资料：wiki的 information Entropy
http://en.wikipedia.org/wiki/Information_Entropy
【在 h***s 的大作中提到】
: 如果你能证明是一个意思, 那就是一个意思. 我只想到了XXX捞个XXX, 而且这个众所周
: 知严格数学上成立.
|
r****k
发帖数: 173 | 120
还有一个问题，那个Entropy的加和有没有可能overflow呢？
一个极端的例子，假设有两个n个integer的数列相同元素乱序存放，n是最大的integer
。要使他们的
加和最大，数列里的数也都取最大值，没有重复的情况下Shannon entropy=1×log1+2
×log2+...n×logn，怎样知道n是最大integer的时候，shannon entropy
用一个long整型可以保存呢？
【在 h***s 的大作中提到】
: 0*log0 == 0 is an analytic result. So handle it when you code.
:
: it.
: (
|
|
|
r****k
发帖数: 173 | 121
哦，我想明白了，sum(n*logn)
两个最大integer的平方也不会overflow 一个long。。。这个解法确实好。
【在 h***s 的大作中提到】
: 0*log0 == 0 is an analytic result. So handle it when you code.
:
: it.
: (
|
h***s
发帖数: 1716 | 122 其实这种不叫算法, 就叫编程优化技巧. 如果在实际工作中需要的话, 谁都自然会慢慢
琢磨出来. 如果不需要的话, 折磨做纯属吃饱了撑的...
【在 r****k 的大作中提到】
:
: 哦，我想明白了，sum(n*logn): 两个最大integer的平方也不会overflow 一个long。。。这个解法确实好。
|
t**n
发帖数: 272 | 123 第二题是resevoir sampling? 第一批10个数字进数组,第二批10个以1/2概率替换数组,
第三批1/3概率... 但是这样连续10个的命运就联系在一起了,不知道是否符合题意
第一题难道要计算数组的和和平方和? |
y**i
发帖数: 1112 | 124 如果有重复元素的话，查找的时候会出问题吧：一个数在数组1中重复2次，数组2中重
复3次，另一个数正好相反，查找法应该区分不出来吧。
【在 j****a 的大作中提到】
: 我对第一题的想法是：
: LZ的方法是2*n log(n) + n,最后那个n是因为两个list要比较一下。
: 我的想法是: 只要sort一个list，n log(n)，然后拿另外一个list的每一个数字去
: sorted list里面找。这样是：n * log(n)。所以最后是2*n log(n)。
: 虽说两个方法都是O(nlog(n)),可是少一个n在practical programming的时候还是有可
: 能挺重要的...
|
t****t
发帖数: 6806 | 125 其实大家说的求和, 求平方和, 求XOR都是一个意思, 就是用一个hash function或者说
signature, 只是这里要求invariant to element order
普通的signature很常见的, 比如说CRC32, MD5之类, 不是invariant to element
order, 可以做一些诸如验证下载是否正确的事情. 这是一个快速的方法, 特别是正确
序列的signature已知的情况. 它不能保证检测正确, 但是它能保证检测错误, 在随机
错误的情况下, 检测正确的成功率也很高.
我觉得你要能答出这些, 就差不多了. 关键是given random error pattern, it has
high probability of successful. 如果是人为forged error pattern, 那么再另说. |
