Snapchat 电面面经 求讨论！

waye_tt 发表于 2016-5-2 15:42
followup部分 如果这个数出现的比较分散就不行诶 譬如 [1, 3, 6, 1, 2, 10, 9, 1] 这样找1 投票是投不出 ...

楼主第二题我还是没看明白，找题目描述扫两遍数组不就知道出现的概率了吗？

看到一个帖子 和这个很像http://www.geeksforgeeks.org/find-the-maximum-repeating-number-in-ok-time/
但面试时候想到这个 太困难了。。。。

wwtwxlwjh 发表于 2016-11-1 09:21
看到一个帖子 和这个很像http://www.geeksforgeeks.org/find-the-maximum-repeating-number-in-ok-time/
...

这个对原数组有要求？ k必须小于n ?

geeks里的是对原数组有要求 必须是1-n-1

如果没有这个要求，很多方法都做不了

所以我不会

所以求解答。。。

范围没有限制用GEEKS FOR GEEKS那个变负数的方法也不行了，你确定是要constant space吗?

忆梦前尘 发表于 2016-5-2 11:43
感觉思路可能是bucket sorting，先扫一遍数组拿到最大值和最小值，比如{1,2,3,1,4}，最大值是4，最小值是1. ...

人家要CONSTANT SPACE。。。。

liurudahai 发表于 2016-11-13 16:20
人家要CONSTANT SPACE。。。。

是啊。。这个要求太苛刻了。。如果说数字是1，n之间，还是有可能的。。

忆梦前尘 发表于 2016-11-14 09:29
是啊。。这个要求太苛刻了。。如果说数字是1，n之间，还是有可能的。。

没准就是前面那个人说的那个方法，还是bucket sort，不过是开2^32个bucket, constant space

liurudahai 发表于 2016-11-13 17:38
没准就是前面那个人说的那个方法，还是bucket sort，不过是开2^32个bucket, constant space

这个"constant"角度新奇啊，我之前一直以为有限个指针这种才是constant。。。

ericlee27 发表于 2016-10-3 10:48
楼主第二题我还是没看明白，找题目描述扫两遍数组不就知道出现的概率了吗？

因为有O(1)空间的限制，每次扫数组的时候不允许记住以前的数值，所以扫两边怎么判断出最frequent的数值呢？（求概率等价于求frequency）