Google电面 08/25/2015

wenqiang88 发表于 2015-9-17 09:17
onsite加油啦

谢谢~~~^_^

宝贝忆彼岸 发表于 2015-9-17 09:09
嗯嗯，没错，我有个疑问，就是如果不一样，就是要把hashmap所有key的value值都减1，这个一边遍历一边修改 ...

可以新建一个map，只把当前value大于1的那些减1加到新的map里面，然后再赋给原来的map，这样原来本身里面是1的那些就自动没有了。

flyaway25 发表于 2015-9-17 09:23
可以新建一个map，只把当前value大于1的那些减1加到新的map里面，然后再赋给原来的map，这样原来本身里面 ...

谢谢回复，这样可能会每次加一个数都开一个temp，空间不是就特别大？不过好像也没有什么别的方法了。。。

补充内容 (2015-9-17 09:35):
新的map，说错了

Yunying 发表于 2015-9-17 09:04
呃面试小哥给的答案是每次查1/4size的头和尾。比如一共有30个element你就查array[0]和array[7]。如果它们一 ...

直接遍历一遍，全部扔进hashmap里，然后遍历hashmap一遍，出答案。时间复杂度O（N）

jiebour 发表于 2015-9-17 08:52
对！比如 1 2 3 4 1 2 3 4 1 2 3 4 4 5 5

对对。。。

顺带一说，这个是O(N)时间O(1)空间的做法。。。

不限空间的话，还是直接hash统计一下找最大。。

mint0715 发表于 2015-9-17 07:30
每次扔掉四个不同的element，直到最后剩下的就是popular.
因为popular的数量超过1/4，所以无论怎么扔，pop ...

I believe your algorithm fails at this input case: [1, 2, 3, 1, 5, 6]
You would've kicked off 1 by the end, but it IS a popular element.
I think adding 3 when the element occurs can fix it.

snklee 发表于 2015-9-18 07:37
I believe your algorithm fails at this input case: [1, 2, 3, 1, 5, 6]
You would've kicked off 1 b ...

srry，细节有误。
当遇到新的元素x时：
1.如果x在列表里，对应frequence+1
2.如果x不在列表里，检查列表里当前是否有frequence == 0的元素y，用x->0取代y->0。

最后检查列表里剩下的三个元素，是否满足总count>1/4。

补充内容 (2015-9-18 13:27):
3.如果x不在列表里，且列表里所有元素的frequence都不为0，那么列表里所有元素的frequence-1。

遍历一次，保存一个长度为3的数组：
1. 如果数组中包括这个数，则概数count + 1
2. 如果数组中有空位，则放入概数，count置为1
3. 如果数组中有数字count为0，则替换概数，count置为1
4. 所有数字count减1

最后数组中剩下的数，就是candidate，每个统计一下就可以了

这个方法可以解决任意1/n的majority number

坐看云起 发表于 2015-9-22 07:13
遍历一次，保存一个长度为3的数组：
1. 如果数组中包括这个数，则概数count + 1
2. 如果数组中有空位，则 ...

弱弱的问一下再检查一次是要再花o(n) ?

5 3 5 3 1 2

這個example 最後會有5(count =1) 3(count=1) 1(count=0)  要怎麼做呢？

say543 发表于 2015-9-22 09:50
弱弱的问一下再检查一次是要再花o(n) ?

5 3 5 3 1 2

这个过程是O(k)的，此处k==3，因为数组长度取决于要找的目标所占比例，所以这道题可以当作是常量时间