Google的这一道题的最优解？继续求助@! - 未名空间MITBBS历史存档

Google的这一道题的最优解？继续求助@!# JobHunting - 待字闺中

G*s2012-03-15 07:03

1 楼

Q: Given two arrays of numbers, find if each of the two arrays have the same set of integers ? Suggest an algo which can run faster than nlogn without extra space?
我已经把这个题出现的老帖的所有回复查阅了一边，貌似第一题要用entropy来做，但是我不明白，为什么“和比较，再平方和比较”这个方法不行？
UPDATE: 我搜索了下，这个网站上给的solution就是 “和比较，平方和比较“来解的。reference:http://www.ferozeh.com/Prep/Questions/Question45.aspx
哪位仁兄给一个反例出来，such that，两个同数量元素的set, 当sum和square sum也一样时，两组set中却有至少一个不同元素！

F*u2012-03-15 07:03

2 楼

第一题先排序O（NlogN）再扫一遍O(N)？

s*k2012-03-15 07:03

3 楼

hash费空间么？
第二题总要有些假设吧？这个数组里每个数的概率是1/10（如果不重复），
那么那个整数流里是否也必须满足这个条件呢？

【在 G**********s 的大作中提到】

: Q: Given two arrays of numbers, find if each of the two arrays have the same set of integers ? Suggest an algo which can run faster than nlogn without extra space?
: 我已经把这个题出现的老帖的所有回复查阅了一边，貌似第一题要用entropy来做，但是我不明白，为什么“和比较，再平方和比较”这个方法不行？
: UPDATE: 我搜索了下，这个网站上给的solution就是 “和比较，平方和比较“来解的。reference:http://www.ferozeh.com/Prep/Questions/Question45.aspx
: 哪位仁兄给一个反例出来，such that，两个同数量元素的set, 当sum和square sum也一样时，两组set中却有至少一个不同元素！

w*42012-03-15 07:03

4 楼

第一题同问和比较, 平方和比较为啥不行, 大不了三次方和再比较, 复杂度还是很低的

【在 G**********s 的大作中提到】

: Q: Given two arrays of numbers, find if each of the two arrays have the same set of integers ? Suggest an algo which can run faster than nlogn without extra space?
: 我已经把这个题出现的老帖的所有回复查阅了一边，貌似第一题要用entropy来做，但是我不明白，为什么“和比较，再平方和比较”这个方法不行？
: UPDATE: 我搜索了下，这个网站上给的solution就是 “和比较，平方和比较“来解的。reference:http://www.ferozeh.com/Prep/Questions/Question45.aspx
: 哪位仁兄给一个反例出来，such that，两个同数量元素的set, 当sum和square sum也一样时，两组set中却有至少一个不同元素！

i*e2012-03-15 07:03

5 楼

第一题我也想知道有没有 O(N) 解和 O（1） space 那么神奇的方法。
第二题是 reservoir sampling.

i*e2012-03-15 07:03

6 楼

你这不能确保百分百的一样，总是可以找到例外的。

低的

【在 w********4 的大作中提到】

: 第一题同问和比较, 平方和比较为啥不行, 大不了三次方和再比较, 复杂度还是很低的

g*e2012-03-15 07:03

7 楼

第一题他的意思应该是用一个256长的int array来记录，第二题没看懂

i*e2012-03-15 07:03

8 楼

啊？
难道是两个字符数组？

【在 g*********e 的大作中提到】

: 第一题他的意思应该是用一个256长的int array来记录，第二题没看懂

n*e2012-03-15 07:03

9 楼

XOR?

a*s2012-03-15 07:03

10 楼

Histogram

【在 G**********s 的大作中提到】

: Q: Given two arrays of numbers, find if each of the two arrays have the same set of integers ? Suggest an algo which can run faster than nlogn without extra space?
: 我已经把这个题出现的老帖的所有回复查阅了一边，貌似第一题要用entropy来做，但是我不明白，为什么“和比较，再平方和比较”这个方法不行？
: UPDATE: 我搜索了下，这个网站上给的solution就是 “和比较，平方和比较“来解的。reference:http://www.ferozeh.com/Prep/Questions/Question45.aspx
: 哪位仁兄给一个反例出来，such that，两个同数量元素的set, 当sum和square sum也一样时，两组set中却有至少一个不同元素！

i*e2012-03-15 07:03

11 楼

[3， 2] and [6，7]
both XOR equal to 1.

【在 n**e 的大作中提到】

: XOR?

n*e2012-03-15 07:03

12 楼

Let result = XOR all the integers in both arrays
return result == 0;

z*c2012-03-15 07:03

13 楼

和比较，加上平方和比较，实际上相当于比较两个分布的mean和variance。mean和
variance相同，两个分布不一定相同。问题是entropy相同，两个分布一定相同么？

n*e2012-03-15 07:03

14 楼

Let result = XOR all the integers in both arrays
return result == 0;
It does NOT work

g*y2012-03-15 07:03

15 楼

Hash 不行吧。
比如
a = [1,2,2,3,4]
b = [1,1,2,3,4]

i*e2012-03-15 07:03

16 楼

hash 记录加个出现的次数就行。

【在 g**********y 的大作中提到】

: Hash 不行吧。
: 比如
: a = [1,2,2,3,4]
: b = [1,1,2,3,4]

r*e2012-03-15 07:03

17 楼

可以尝试 count bloom filter的方法，牺牲精确度为代价，换内存利用率

【在 i**********e 的大作中提到】

: hash 记录加个出现的次数就行。

t*e2012-03-15 07:03

18 楼

Use XOR and sum to initial check, this will improve average case because the
common case are not eqaul. If XOR all element ==0 and sum are equal, start
sorting.

H*r2012-03-15 07:03

19 楼

1. 数组元素是啥类型？
2. 你说的偶真lost了

【在 G**********s 的大作中提到】

: Q: Given two arrays of numbers, find if each of the two arrays have the same set of integers ? Suggest an algo which can run faster than nlogn without extra space?
: 我已经把这个题出现的老帖的所有回复查阅了一边，貌似第一题要用entropy来做，但是我不明白，为什么“和比较，再平方和比较”这个方法不行？
: UPDATE: 我搜索了下，这个网站上给的solution就是 “和比较，平方和比较“来解的。reference:http://www.ferozeh.com/Prep/Questions/Question45.aspx
: 哪位仁兄给一个反例出来，such that，两个同数量元素的set, 当sum和square sum也一样时，两组set中却有至少一个不同元素！

s*o2012-03-15 07:03

20 楼

is XOR all == 0 enough already, if there are no duplicates?

the
start

【在 t********e 的大作中提到】

: Use XOR and sum to initial check, this will improve average case because the
: common case are not eqaul. If XOR all element ==0 and sum are equal, start
: sorting.

h*k2012-03-15 07:03

21 楼

第二题是老题，题目是从一个不知到总长度的int stream中采集k个样本，怎么做才能
使stream中的每个int被采的概率相同？

【在 G**********s 的大作中提到】

: Q: Given two arrays of numbers, find if each of the two arrays have the same set of integers ? Suggest an algo which can run faster than nlogn without extra space?
: 我已经把这个题出现的老帖的所有回复查阅了一边，貌似第一题要用entropy来做，但是我不明白，为什么“和比较，再平方和比较”这个方法不行？
: UPDATE: 我搜索了下，这个网站上给的solution就是 “和比较，平方和比较“来解的。reference:http://www.ferozeh.com/Prep/Questions/Question45.aspx
: 哪位仁兄给一个反例出来，such that，两个同数量元素的set, 当sum和square sum也一样时，两组set中却有至少一个不同元素！

H*12012-03-15 07:03

22 楼

怎么用XOR啊？
请详解，谢谢！

the
start

【在 t********e 的大作中提到】

: Use XOR and sum to initial check, this will improve average case because the
: common case are not eqaul. If XOR all element ==0 and sum are equal, start
: sorting.

f*r2012-03-15 07:03

23 楼

这个用quick sort based的方法，average case还是很好的。
1）先找一个数分两个数组。分的不等长，那么不一样。
2）等长，再quick sort的方法同时sort两个数组，每次都判断等不等长。
这个average case的复杂度应该是很不错的。

【在 G**********s 的大作中提到】

: Q: Given two arrays of numbers, find if each of the two arrays have the same set of integers ? Suggest an algo which can run faster than nlogn without extra space?
: 我已经把这个题出现的老帖的所有回复查阅了一边，貌似第一题要用entropy来做，但是我不明白，为什么“和比较，再平方和比较”这个方法不行？
: UPDATE: 我搜索了下，这个网站上给的solution就是 “和比较，平方和比较“来解的。reference:http://www.ferozeh.com/Prep/Questions/Question45.aspx
: 哪位仁兄给一个反例出来，such that，两个同数量元素的set, 当sum和square sum也一样时，两组set中却有至少一个不同元素！

a*m2012-03-15 07:03

24 楼

如果两个数组通常都相同的话这个期望复杂度是nlgn,只是比排序多了early out吧。

【在 f*****r 的大作中提到】

:
: 这个用quick sort based的方法，average case还是很好的。
: 1）先找一个数分两个数组。分的不等长，那么不一样。
: 2）等长，再quick sort的方法同时sort两个数组，每次都判断等不等长。
: 这个average case的复杂度应该是很不错的。

G*s2012-03-15 07:03

25 楼

leet大牛，谢谢指点第二题。学到了！

【在 i**********e 的大作中提到】

: 第一题我也想知道有没有 O(N) 解和 O（1） space 那么神奇的方法。
: 第二题是 reservoir sampling.

s*o2012-03-15 07:03

26 楼

how about this for 1:
bool
isSame(const vector& a1, const vector& a2) {
int result = 0;
if (a1.size() != a2.size()) {
result = 1;
} else {
for (int i=0; iresult ^= a1[i] ^ a2[i];
}
}
return (result == 0);
}

【在 G**********s 的大作中提到】

: leet大牛，谢谢指点第二题。学到了！

g*y2012-03-15 07:03

27 楼

XOR和sum的是错的：
0011
1100
vs
0101
1010
XOR为0，和也相等。

g*y2012-03-15 07:03

28 楼

Sum(a[i]) = Sum(b[i])
Sum(a[i]^2) = Sum(b[i]^2)
也推不出{a[i]} = {b[i]}
反例写个程序就可以算出来。

g*y2012-03-15 07:03

29 楼

这里有几篇paper讲test set equality的
http://www.sciencedirect.com/science/article/pii/S0020019004002
http://www.sciencedirect.com/science/article/pii/01966774929004
http://www.springerlink.com/content/7t26881372546666/
要付费才能读，不过这已经不象做题，这是做学问了。

i*e2012-03-15 07:03

30 楼

恩。这题是trick question，没注意到两个数组相同长度的条件。
可以逻辑证明是正确的，我就随便写写，证明不够严格请多多包涵。
我们这里尝试以逻辑推着找反例，如果逻辑证明有出入那就代表反例必定不存在的。
首先，我们只考虑两个数组和是相同的情况，因为如果不相同那肯定是不一样了。
假设数组 A 得和为 S.
a1 + a2 + ... + an = S
那么，我们考虑其中一个反例，就是把数组 A 的一对数 (ai, aj) 变成 (ai+k, aj-k)：
那么数组 B：
a1 + a2 + ... + (ai + k) + ... (aj - k) + ... + an = S，k 不等于 0.
那么，反例如果存在的话，也就意味着：
数组 B 的平方和等于数组 A 的平方和。
但是 (ai+k)^2 + (aj-k)^2
= ai^2 + aj^2 + 2k*(ai-aj) + 2k^2
> ai^2 + aj^2
因为 k 不可能等于 0，所以 2k^2 就 > 0 了。（如果 k 等于 0 的话就是数组相同的情况了，那就更之前我们的假设有出入）
那么，也就是当把数组 A 的一对数转换成 (ai+k, aj-k) 的时候，B 的平方和必定大于 A 的平方和，也就意味着这种情况是不可能找到反例的。
接着下来就是扩展到 m 对数，也一样类似的证明。

也一样时，两组set中却有至少一个不同元素！

【在 G**********s 的大作中提到】

: leet大牛，谢谢指点第二题。学到了！

g*y2012-03-15 07:03

31 楼

(1, 5, 6) vs (2, 3, 7)
1 + 5 + 6 = 12 = 2 + 3 + 7
1 + 25 + 36 = 62 = 4 + 9 + 49
在(1..100)的空间里，对k=3，可以算一堆这种解出来。

p*y2012-03-15 07:03

32 楼

这个证明不完全，因为还有这样的情况：
ai+k, aj-m, ak+m-k
需要不满足：
(ai+k)^2 + (aj-m)^2 + (ak+m-k) ^ 2 = ai ^ 2 + aj ^ 2 + ak ^ 2
given any integer k and m.
然后是4个数， 5个数...., n个数。
这道题其实就是n个变量，两个方程，再加上限制条件每个变量时整数，然后证明有
没有唯一解得问题。我觉得是没有的，但还没想出证明方法。

k)：

【在 i**********e 的大作中提到】

: 恩。这题是trick question，没注意到两个数组相同长度的条件。
: 可以逻辑证明是正确的，我就随便写写，证明不够严格请多多包涵。
: 我们这里尝试以逻辑推着找反例，如果逻辑证明有出入那就代表反例必定不存在的。
: 首先，我们只考虑两个数组和是相同的情况，因为如果不相同那肯定是不一样了。
: 假设数组 A 得和为 S.
: a1 + a2 + ... + an = S
: 那么，我们考虑其中一个反例，就是把数组 A 的一对数 (ai, aj) 变成 (ai+k, aj-k)：
: 那么数组 B：
: a1 + a2 + ... + (ai + k) + ... (aj - k) + ... + an = S，k 不等于 0.
: 那么，反例如果存在的话，也就意味着：

z*82012-03-15 07:03

33 楼

好吧，如果 XOR=0, 和相等，平方和相等，立方和相等，行不？

【在 p*****y 的大作中提到】

: 这个证明不完全，因为还有这样的情况：
: ai+k, aj-m, ak+m-k
: 需要不满足：
: (ai+k)^2 + (aj-m)^2 + (ak+m-k) ^ 2 = ai ^ 2 + aj ^ 2 + ak ^ 2
: given any integer k and m.
: 然后是4个数， 5个数...., n个数。
: 这道题其实就是n个变量，两个方程，再加上限制条件每个变量时整数，然后证明有
: 没有唯一解得问题。我觉得是没有的，但还没想出证明方法。
:
: k)：

g*y2012-03-15 07:03

34 楼

你还真不死心 :-)
不行！
这是个不定长的sequence, 随便你找多少种和出来，数学上都能构造出反例，只不过构
造起来困难点。
这个题正解应该是类似那几篇paper的思路，有O(N)甚至更低阶的解法，不过那些不是
面试范围内的。
等哪个大牛出来给个面试时间可用的O(N)解吧。

【在 z*********8 的大作中提到】

: 好吧，如果 XOR=0, 和相等，平方和相等，立方和相等，行不？

N*m2012-03-15 07:03

35 楼

for example,
(-3,4,12) and (13,0,0)

same set of integers ? Suggest an algo which can run faster than nlogn
without extra space?
但是我不明白，为什么“和比较，再平方和比较”这个方法不行？
的。reference:http://www.ferozeh.com/Prep/Questions/Question45.aspx
也一样时，两组set中却有至少一个不同元素！

【在 G**********s 的大作中提到】

: Q: Given two arrays of numbers, find if each of the two arrays have the same set of integers ? Suggest an algo which can run faster than nlogn without extra space?
: 我已经把这个题出现的老帖的所有回复查阅了一边，貌似第一题要用entropy来做，但是我不明白，为什么“和比较，再平方和比较”这个方法不行？
: UPDATE: 我搜索了下，这个网站上给的solution就是 “和比较，平方和比较“来解的。reference:http://www.ferozeh.com/Prep/Questions/Question45.aspx
: 哪位仁兄给一个反例出来，such that，两个同数量元素的set, 当sum和square sum也一样时，两组set中却有至少一个不同元素！

Q*T2012-03-15 07:03

36 楼

There are actually lots of possibilities.
Consider the case of three numbers, each within the range [-10,10],
one can find 257 pairs with the same sum and square sum.
For example
([-2, 7, 7], [1, 1, 10])
([-2, 7, 8], [-1, 4, 10])
([-1, 2, 2], [0, 0, 3])
([-1, 3, 4], [0, 1, 5])
([-1, 4, 6], [0, 2, 7])
([-1, 4, 7], [1, 1, 8])
([-1, 5, 5], [1, 1, 7])
([-1, 5, 8], [0, 3, 9])
([-1, 6, 6], [0, 3, 8])
([-1, 6, 7], [1, 2, 9])
([0, 3, 3], [1, 1, 4])
([0, 4, 5], [1, 2, 6])
([0, 5, 7], [1, 3, 8])
([0, 5, 8], [2, 2, 9])
([0, 6, 6], [2, 2, 8])
([0, 6, 9], [1, 4, 10])
([0, 7, 7], [1, 4, 9])
([0, 7, 8], [2, 3, 10])
([1, 4, 4], [2, 2, 5])
([1, 5, 6], [2, 3, 7])
([1, 6, 8], [2, 4, 9])
([1, 6, 9], [3, 3, 10])
([1, 7, 7], [3, 3, 9])
([1, 8, 8], [2, 5, 10])
([2, 5, 5], [3, 3, 6])
([2, 6, 7], [3, 4, 8])
([2, 7, 9], [3, 5, 10])
([2, 8, 8], [4, 4, 10])
([3, 6, 6], [4, 4, 7])
([3, 7, 8], [4, 5, 9])
([4, 7, 7], [5, 5, 8])
([4, 8, 9], [5, 6, 10])
([5, 8, 8], [6, 6, 9])
([6, 9, 9], [7, 7, 10])
......

【在 N***m 的大作中提到】

: for example,
: (-3,4,12) and (13,0,0)
:
: same set of integers ? Suggest an algo which can run faster than nlogn
: without extra space?
: 但是我不明白，为什么“和比较，再平方和比较”这个方法不行？
: 的。reference:http://www.ferozeh.com/Prep/Questions/Question45.aspx
: 也一样时，两组set中却有至少一个不同元素！

a*m2012-03-15 07:03

37 楼

恩。n个未知数，2个方称。

【在 p*****y 的大作中提到】

: 这个证明不完全，因为还有这样的情况：
: ai+k, aj-m, ak+m-k
: 需要不满足：
: (ai+k)^2 + (aj-m)^2 + (ak+m-k) ^ 2 = ai ^ 2 + aj ^ 2 + ak ^ 2
: given any integer k and m.
: 然后是4个数， 5个数...., n个数。
: 这道题其实就是n个变量，两个方程，再加上限制条件每个变量时整数，然后证明有
: 没有唯一解得问题。我觉得是没有的，但还没想出证明方法。
:
: k)：

a*m2012-03-15 07:03

38 楼

n个未知数至少需要n个方程。这么算复杂度必然是n^2。

【在 z*********8 的大作中提到】

: 好吧，如果 XOR=0, 和相等，平方和相等，立方和相等，行不？

H*r2012-03-15 07:03

39 楼

http://www.springerlink.com/content/7t26881372546666/
这篇说： “maintaining the constant time complexity of set equality-testing”
这太牛了吧？

【在 g**********y 的大作中提到】

: 这里有几篇paper讲test set equality的
: http://www.sciencedirect.com/science/article/pii/S0020019004002
: http://www.sciencedirect.com/science/article/pii/01966774929004
: http://www.springerlink.com/content/7t26881372546666/
: 要付费才能读，不过这已经不象做题，这是做学问了。

x*u2012-03-15 07:03

40 楼

same set of integers ? Suggest an algo which can run faster than nlogn
without extra space?
但是我不明白，为什么“和比较，再平方和比较”这个方法不行？
的。reference:http://www.ferozeh.com/Prep/Questions/Question45.aspx
也一样时，两组set中却有至少一个不同元素！
I don't think there's anything wrong with the existing solution.
assume out of the two arrays, in array 1, there is a number A, where in
array 2, there is number B and C, and B+C=A.
Now we sum the squares in two arrays.
in Array 1, A^2 = (B+C)^2 = B^2 + 2BC + C^2.
In array 2, B^2 + C^2
You can see they can't be equal.

【在 G**********s 的大作中提到】

: Q: Given two arrays of numbers, find if each of the two arrays have the same set of integers ? Suggest an algo which can run faster than nlogn without extra space?
: 我已经把这个题出现的老帖的所有回复查阅了一边，貌似第一题要用entropy来做，但是我不明白，为什么“和比较，再平方和比较”这个方法不行？
: UPDATE: 我搜索了下，这个网站上给的solution就是 “和比较，平方和比较“来解的。reference:http://www.ferozeh.com/Prep/Questions/Question45.aspx
: 哪位仁兄给一个反例出来，such that，两个同数量元素的set, 当sum和square sum也一样时，两组set中却有至少一个不同元素！

w*m2012-03-15 07:03

41 楼

entropy has lower prob of conflict than using sum+sum of square

same set of integers ? Suggest an algo which can run faster than nlogn
without extra space?
但是我不明白，为什么“和比较，再平方和比较”这个方法不行？
的。reference:http://www.ferozeh.com/Prep/Questions/Question45.aspx
也一样时，两组set中却有至少一个不同元素！

【在 G**********s 的大作中提到】

: Q: Given two arrays of numbers, find if each of the two arrays have the same set of integers ? Suggest an algo which can run faster than nlogn without extra space?
: 我已经把这个题出现的老帖的所有回复查阅了一边，貌似第一题要用entropy来做，但是我不明白，为什么“和比较，再平方和比较”这个方法不行？
: UPDATE: 我搜索了下，这个网站上给的solution就是 “和比较，平方和比较“来解的。reference:http://www.ferozeh.com/Prep/Questions/Question45.aspx
: 哪位仁兄给一个反例出来，such that，两个同数量元素的set, 当sum和square sum也一样时，两组set中却有至少一个不同元素！

t*02012-03-15 07:03

42 楼

这么大的数字做乘法要多大的空间，自己算算看，这还不算extra space?

same set of integers ? Suggest an algo which can run faster than nlogn
without extra space?
但是我不明白，为什么“和比较，再平方和比较”这个方法不行？
的。reference:http://www.ferozeh.com/Prep/Questions/Question45.aspx
也一样时，两组set中却有至少一个不同元素！

【在 G**********s 的大作中提到】

: Q: Given two arrays of numbers, find if each of the two arrays have the same set of integers ? Suggest an algo which can run faster than nlogn without extra space?
: 我已经把这个题出现的老帖的所有回复查阅了一边，貌似第一题要用entropy来做，但是我不明白，为什么“和比较，再平方和比较”这个方法不行？
: UPDATE: 我搜索了下，这个网站上给的solution就是 “和比较，平方和比较“来解的。reference:http://www.ferozeh.com/Prep/Questions/Question45.aspx
: 哪位仁兄给一个反例出来，such that，两个同数量元素的set, 当sum和square sum也一样时，两组set中却有至少一个不同元素！

w*m2012-03-15 07:03

43 楼

for Q1, an advanced version is:
how to check if two arrays of vectors are the same or not?
an more advanced version is:
given two graphs with different representations, how do u know if they share
the same structure or not?

same set of integers ? Suggest an algo which can run faster than nlogn
without extra space?
但是我不明白，为什么“和比较，再平方和比较”这个方法不行？
的。reference:http://www.ferozeh.com/Prep/Questions/Question45.aspx
也一样时，两组set中却有至少一个不同元素！

【在 G**********s 的大作中提到】

: Q: Given two arrays of numbers, find if each of the two arrays have the same set of integers ? Suggest an algo which can run faster than nlogn without extra space?
: 我已经把这个题出现的老帖的所有回复查阅了一边，貌似第一题要用entropy来做，但是我不明白，为什么“和比较，再平方和比较”这个方法不行？
: UPDATE: 我搜索了下，这个网站上给的solution就是 “和比较，平方和比较“来解的。reference:http://www.ferozeh.com/Prep/Questions/Question45.aspx
: 哪位仁兄给一个反例出来，such that，两个同数量元素的set, 当sum和square sum也一样时，两组set中却有至少一个不同元素！

w*m2012-03-15 07:03

44 楼

this is just a hash function to hash a distribution with infinite dimensions
to one or two numbers
always have conflicts.
if two arrays have the same entropy, they may still be different. need to
sort them and double check

same set of integers ? Suggest an algo which can run faster than nlogn
without extra space?
但是我不明白，为什么“和比较，再平方和比较”这个方法不行？
的。reference:http://www.ferozeh.com/Prep/Questions/Question45.aspx
也一样时，两组set中却有至少一个不同元素！

【在 G**********s 的大作中提到】

: Q: Given two arrays of numbers, find if each of the two arrays have the same set of integers ? Suggest an algo which can run faster than nlogn without extra space?
: 我已经把这个题出现的老帖的所有回复查阅了一边，貌似第一题要用entropy来做，但是我不明白，为什么“和比较，再平方和比较”这个方法不行？
: UPDATE: 我搜索了下，这个网站上给的solution就是 “和比较，平方和比较“来解的。reference:http://www.ferozeh.com/Prep/Questions/Question45.aspx
: 哪位仁兄给一个反例出来，such that，两个同数量元素的set, 当sum和square sum也一样时，两组set中却有至少一个不同元素！

f*w2012-03-15 07:03

45 楼

前文已经有人给出反例了

【在 x****u 的大作中提到】

:
: same set of integers ? Suggest an algo which can run faster than nlogn
: without extra space?
: 但是我不明白，为什么“和比较，再平方和比较”这个方法不行？
: 的。reference:http://www.ferozeh.com/Prep/Questions/Question45.aspx
: 也一样时，两组set中却有至少一个不同元素！
: I don't think there's anything wrong with the existing solution.
: assume out of the two arrays, in array 1, there is a number A, where in
: array 2, there is number B and C, and B+C=A.
: Now we sum the squares in two arrays.

S*e2012-03-15 07:03

46 楼

比如长度为三的数组，平方和相等说明他们在同一个球面上，和相等说明在一个平面上
，这个平面和球面相交的曲线上点的坐标都满足平方和相等并且和相等

same set of integers ? Suggest an algo which can run faster than nlogn
without extra space?
但是我不明白，为什么“和比较，再平方和比较”这个方法不行？
的。reference:http://www.ferozeh.com/Prep/Questions/Question45.aspx
也一样时，两组set中却有至少一个不同元素！

【在 G**********s 的大作中提到】

: Q: Given two arrays of numbers, find if each of the two arrays have the same set of integers ? Suggest an algo which can run faster than nlogn without extra space?
: 我已经把这个题出现的老帖的所有回复查阅了一边，貌似第一题要用entropy来做，但是我不明白，为什么“和比较，再平方和比较”这个方法不行？
: UPDATE: 我搜索了下，这个网站上给的solution就是 “和比较，平方和比较“来解的。reference:http://www.ferozeh.com/Prep/Questions/Question45.aspx
: 哪位仁兄给一个反例出来，such that，两个同数量元素的set, 当sum和square sum也一样时，两组set中却有至少一个不同元素！

i*e2012-03-15 07:03

47 楼

hehe, i am wrong.
My proof is flawed, didn't think that the counter examples would be so easy
to find.
So conclusion is there's no easy way to do this in O(N) time and O(1) space.
I guess the best is to look into how Java implement set.equals().

【在 g**********y 的大作中提到】

: (1, 5, 6) vs (2, 3, 7)
: 1 + 5 + 6 = 12 = 2 + 3 + 7
: 1 + 25 + 36 = 62 = 4 + 9 + 49
: 在(1..100)的空间里，对k=3，可以算一堆这种解出来。

h*e2012-03-15 07:03

48 楼

就random hash把。。。神码entropy，first moment, second moment都一样的不靠谱
。。都只是个statistic 而已。。

w*m2012-03-15 07:03

49 楼

random也有distribution
probability不是true和false的关系
但不同的概率算法，速度的order是不一样的

【在 h********e 的大作中提到】

: 就random hash把。。。神码entropy，first moment, second moment都一样的不靠谱
: 。。都只是个statistic 而已。。

E*T2012-03-15 07:03

50 楼

如果两列数a_i b_i都一致有界，那么比较sum of n^{a_i}和sum of n^{b_i}就行了，
复杂度好像O(n).

H*r2012-03-15 07:03

51 楼

这题如果只能用比较大小复杂度最小就是N*log(N).

easy
space.

【在 i**********e 的大作中提到】

: hehe, i am wrong.
: My proof is flawed, didn't think that the counter examples would be so easy
: to find.
: So conclusion is there's no easy way to do this in O(N) time and O(1) space.
: I guess the best is to look into how Java implement set.equals().

w*y2012-03-15 07:03

52 楼

reservoir sampling的算法看明白了, 可是不知道怎么证明, 咋办

【在 i**********e 的大作中提到】

: 第一题我也想知道有没有 O(N) 解和 O（1） space 那么神奇的方法。
: 第二题是 reservoir sampling.

H*r2012-03-15 07:03

53 楼

这要有个 a_i = INT_MAX 那算exp(a_i)可不容易

【在 E*****T 的大作中提到】

: 如果两列数a_i b_i都一致有界，那么比较sum of n^{a_i}和sum of n^{b_i}就行了，
: 复杂度好像O(n).

h*e2012-03-15 07:03

54 楼

别想了。。信息量不够，不可能有线性时间确定性算法的。。只有概率线性算法，work
with 1-1/poly(n) probability maybe.

l*m2012-03-15 07:03

55 楼

俺觉得和相等，乘积相等应该就是最优的吧。XOR有很多特殊情况是处理不了的。比如
22222，33333。

z*o2012-03-15 07:03

56 楼

3 4 3 4 10
5 5 6 8 0
这两组数就和一样平方和一样。

G*s2012-03-15 07:03

57 楼

火鸡，你太牛了吧！
敬仰敬仰！！

【在 g**********y 的大作中提到】

: 这里有几篇paper讲test set equality的
: http://www.sciencedirect.com/science/article/pii/S0020019004002
: http://www.sciencedirect.com/science/article/pii/01966774929004
: http://www.springerlink.com/content/7t26881372546666/
: 要付费才能读，不过这已经不象做题，这是做学问了。

v*t2012-03-15 07:03

58 楼

我想到一个方法，各位大牛帮忙看下啊
扫描一遍数组得到最小值min，令它的hashcode为 2，
再扫描一遍数组，令a[i]的hashcode就是第(a[i]-min)个prime number 求积得出数组
的hashcode，比较两个数组的hashcode即可
我现在采用的做法是用primearray存了10000以内的prime number，也可以用数学的方
法算（但这样的时间复杂度是n2？）。
public class ArrayEquality {

static boolean arrayequality(int a[], int b[])
{
int max=a[0];
int min=a[0];
long a_hashcode = 1;
long b_hashcode = 1;
int primearray[] ={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61
,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,
167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,
271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,
389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,
503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,
631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,
757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,
883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997,1009,1013,
1019,1021,1031,1033,1039,1049,1051,1061,1063,1069,1087,1091,1093,1097,1103,
1109,1117,1123,1129,1151,1153,1163,1171,1181,1187,1193,1201,1213,1217,1223,
1229,1231,1237,1249,1259,1277,1279,1283,1289,1291,1297,1301,1303,1307,1319,
1321,1327,1361,1367,1373,1381,1399,1409,1423,1427,1429,1433,1439,1447,1451,
1453,1459,1471,1481,1483,1487,1489,1493,1499,1511,1523,1531,1543,1549,1553,
1559,1567,1571,1579,1583,1597,1601,1607,1609,1613,1619,1621,1627,1637,1657,
1663,1667,1669,1693,1697,1699,1709,1721,1723,1733,1741,1747,1753,1759,1777,
1783,1787,1789,1801,1811,1823,1831,1847,1861,1867,1871,1873,1877,1879,1889,
1901,1907,1913,1931,1933,1949,1951,1973,1979,1987,1993,1997,1999,2003,2011,
2017,2027,2029,2039,2053,2063,2069,2081,2083,2087,2089,2099,2111,2113,2129,
2131,2137,2141,2143,2153,2161,2179,2203,2207,2213,2221,2237,2239,2243,2251,
2267,2269,2273,2281,2287,2293,2297,2309,2311,2333,2339,2341,2347,2351,2357,
2371,2377,2381,2383,2389,2393,2399,2411,2417,2423,2437,2441,2447,2459,2467,
2473,2477,2503,2521,2531,2539,2543,2549,2551,2557,2579,2591,2593,2609,2617,
2621,2633,2647,2657,2659,2663,2671,2677,2683,2687,2689,2693,2699,2707,2711,
2713,2719,2729,2731,2741,2749,2753,2767,2777,2789,2791,2797,2801,2803,2819,
2833,2837,2843,2851,2857,2861,2879,2887,2897,2903,2909,2917,2927,2939,2953,
2957,2963,2969,2971,2999,3001,3011,3019,3023,3037,3041,3049,3061,3067,3079,
3083,3089,3109,3119,3121,3137,3163,3167,3169,3181,3187,3191,3203,3209,3217,
3221,3229,3251,3253,3257,3259,3271,3299,3301,3307,3313,3319,3323,3329,3331,
3343,3347,3359,3361,3371,3373,3389,3391,3407,3413,3433,3449,3457,3461,3463,
3467,3469,3491,3499,3511,3517,3527,3529,3533,3539,3541,3547,3557,3559,3571,
3581,3583,3593,3607,3613,3617,3623,3631,3637,3643,3659,3671,3673,3677,3691,
3697,3701,3709,3719,3727,3733,3739,3761,3767,3769,3779,3793,3797,3803,3821,
3823,3833,3847,3851,3853,3863,3877,3881,3889,3907,3911,3917,3919,3923,3929,
3931,3943,3947,3967,3989,4001,4003,4007,4013,4019,4021,4027,4049,4051,4057,
4073,4079,4091,4093,4099,4111,4127,4129,4133,4139,4153,4157,4159,4177,4201,
4211,4217,4219,4229,4231,4241,4243,4253,4259,4261,4271,4273,4283,4289,4297,
4327,4337,4339,4349,4357,4363,4373,4391,4397,4409,4421,4423,4441,4447,4451,
4457,4463,4481,4483,4493,4507,4513,4517,4519,4523,4547,4549,4561,4567,4583,
4591,4597,4603,4621,4637,4639,4643,4649,4651,4657,4663,4673,4679,4691,4703,
4721,4723,4729,4733,4751,4759,4783,4787,4789,4793,4799,4801,4813,4817,4831,
4861,4871,4877,4889,4903,4909,4919,4931,4933,4937,4943,4951,4957,4967,4969,
4973,4987,4993,4999,5003,5009,5011,5021,5023,5039,5051,5059,5077,5081,5087,
5099,5101,5107,5113,5119,5147,5153,5167,5171,5179,5189,5197,5209,5227,5231,
5233,5237,5261,5273,5279,5281,5297,5303,5309,5323,5333,5347,5351,5381,5387,
5393,5399,5407,5413,5417,5419,5431,5437,5441,5443,5449,5471,5477,5479,5483,
5501,5503,5507,5519,5521,5527,5531,5557,5563,5569,5573,5581,5591,5623,5639,
5641,5647,5651,5653,5657,5659,5669,5683,5689,5693,5701,5711,5717,5737,5741,
5743,5749,5779,5783,5791,5801,5807,5813,5821,5827,5839,5843,5849,5851,5857,
5861,5867,5869,5879,5881,5897,5903,5923,5927,5939,5953,5981,5987,6007,6011,
6029,6037,6043,6047,6053,6067,6073,6079,6089,6091,6101,6113,6121,6131,6133,
6143,6151,6163,6173,6197,6199,6203,6211,6217,6221,6229,6247,6257,6263,6269,
6271,6277,6287,6299,6301,6311,6317,6323,6329,6337,6343,6353,6359,6361,6367,
6373,6379,6389,6397,6421,6427,6449,6451,6469,6473,6481,6491,6521,6529,6547,
6551,6553,6563,6569,6571,6577,6581,6599,6607,6619,6637,6653,6659,6661,6673,
6679,6689,6691,6701,6703,6709,6719,6733,6737,6761,6763,6779,6781,6791,6793,
6803,6823,6827,6829,6833,6841,6857,6863,6869,6871,6883,6899,6907,6911,6917,
6947,6949,6959,6961,6967,6971,6977,6983,6991,6997,7001,7013,7019,7027,7039,
7043,7057,7069,7079,7103,7109,7121,7127,7129,7151,7159,7177,7187,7193,7207,
7211,7213,7219,7229,7237,7243,7247,7253,7283,7297,7307,7309,7321,7331,7333,
7349,7351,7369,7393,7411,7417,7433,7451,7457,7459,7477,7481,7487,7489,7499,
7507,7517,7523,7529,7537,7541,7547,7549,7559,7561,7573,7577,7583,7589,7591,
7603,7607,7621,7639,7643,7649,7669,7673,7681,7687,7691,7699,7703,7717,7723,
7727,7741,7753,7757,7759,7789,7793,7817,7823,7829,7841,7853,7867,7873,7877,
7879,7883,7901,7907,7919,7927,7933,7937,7949,7951,7963,7993,8009,8011,8017,
8039,8053,8059,8069,8081,8087,8089,8093,8101,8111,8117,8123,8147,8161,8167,
8171,8179,8191,8209,8219,8221,8231,8233,8237,8243,8263,8269,8273,8287,8291,
8293,8297,8311,8317,8329,8353,8363,8369,8377,8387,8389,8419,8423,8429,8431,
8443,8447,8461,8467,8501,8513,8521,8527,8537,8539,8543,8563,8573,8581,8597,
8599,8609,8623,8627,8629,8641,8647,8663,8669,8677,8681,8689,8693,8699,8707,
8713,8719,8731,8737,8741,8747,8753,8761,8779,8783,8803,8807,8819,8821,8831,
8837,8839,8849,8861,8863,8867,8887,8893,8923,8929,8933,8941,8951,8963,8969,
8971,8999,9001,9007,9011,9013,9029,9041,9043,9049,9059,9067,9091,9103,9109,
9127,9133,9137,9151,9157,9161,9173,9181,9187,9199,9203,9209,9221,9227,9239,
9241,9257,9277,9281,9283,9293,9311,9319,9323,9337,9341,9343,9349,9371,9377,
9391,9397,9403,9413,9419,9421,9431,9433,9437,9439,9461,9463,9467,9473,9479,
9491,9497,9511,9521,9533,9539,9547,9551,9587,9601,9613,9619,9623,9629,9631,
9643,9649,9661,9677,9679,9689,9697,9719,9721,9733,9739,9743,9749,9767,9769,
9781,9787,9791,9803,9811,9817,9829,9833,9839,9851,9857,9859,9871,9883,9887,
9901,9907,9923,9929,9931,9941,9949,9967,9973};

if(a.length!=b.length)
return false;

for(int i=0;i{
if(a[i]>max)
max=a[i];
if(a[i]min=a[i];
}

for(int i=0;i{
if(b[i]>max||b[i]return false;
}

for(int i=0;i{
a_hashcode*=primearray[a[i]-min];
}

for(int i=0;i{
b_hashcode*=primearray[b[i]-min];
}

if(a_hashcode==b_hashcode)
return true;
else
return false;

}

public static void main(String args[])
{
int a[]={1,3,5,7,1000};
int b[]={1000,7,1,3,5};
if(arrayequality(a,b))
System.out.println("Two array have same elements");
else
System.out.println("Two array have different elements");

}
}

v*t2012-03-15 07:03

59 楼

能仔细讲下用entropy 怎么做啊
我的理解是entropy只和概率有关，和数组的值无关？

【在 w*********m 的大作中提到】

: entropy has lower prob of conflict than using sum+sum of square
:
: same set of integers ? Suggest an algo which can run faster than nlogn
: without extra space?
: 但是我不明白，为什么“和比较，再平方和比较”这个方法不行？
: 的。reference:http://www.ferozeh.com/Prep/Questions/Question45.aspx
: 也一样时，两组set中却有至少一个不同元素！

l*s2012-03-15 07:03

60 楼

For the first question, if the range is known, we can do the O(n) by the
following steps:
Step 1. build histograms for the two arrays on the given range;
Step 2. Normalize each histogram to one;
Step 3. compute their distance by the Bhattacharyya distance;
The smaller the distance, ther less similarity of the two arrays of numbers.
Each step is O(n), therefore, the final complexity for the whole algorithm
is O(n)

same set of integers ? Suggest an algo which can run faster than nlogn
without extra space?
但是我不明白，为什么“和比较，再平方和比较”这个方法不行？
的。reference:http://www.ferozeh.com/Prep/Questions/Question45.aspx
也一样时，两组set中却有至少一个不同元素！

【在 G**********s 的大作中提到】

: Q: Given two arrays of numbers, find if each of the two arrays have the same set of integers ? Suggest an algo which can run faster than nlogn without extra space?
: 我已经把这个题出现的老帖的所有回复查阅了一边，貌似第一题要用entropy来做，但是我不明白，为什么“和比较，再平方和比较”这个方法不行？
: UPDATE: 我搜索了下，这个网站上给的solution就是 “和比较，平方和比较“来解的。reference:http://www.ferozeh.com/Prep/Questions/Question45.aspx
: 哪位仁兄给一个反例出来，such that，两个同数量元素的set, 当sum和square sum也一样时，两组set中却有至少一个不同元素！

f*t2012-03-15 07:03

61 楼

记得数学老师说过方程组：
x1 + x2 + ... + x10 = Z
square(x1) + square(x2) + ... + square(x10) = Y
不是唯一解

k)：

【在 i**********e 的大作中提到】

: 恩。这题是trick question，没注意到两个数组相同长度的条件。
: 可以逻辑证明是正确的，我就随便写写，证明不够严格请多多包涵。
: 我们这里尝试以逻辑推着找反例，如果逻辑证明有出入那就代表反例必定不存在的。
: 首先，我们只考虑两个数组和是相同的情况，因为如果不相同那肯定是不一样了。
: 假设数组 A 得和为 S.
: a1 + a2 + ... + an = S
: 那么，我们考虑其中一个反例，就是把数组 A 的一对数 (ai, aj) 变成 (ai+k, aj-k)：
: 那么数组 B：
: a1 + a2 + ... + (ai + k) + ... (aj - k) + ... + an = S，k 不等于 0.
: 那么，反例如果存在的话，也就意味着：