Google Onsite面经

YY大帝 发表于 2017-2-19 11:28
感谢LZ分享，求问第五题设计的思路，要用到heap吗

该开始的思路是想用heap,但是因为有search操作，改成binary search tree(TreeMap).

say543 发表于 2017-2-19 14:54
第一题 follow up 因该药的是hashMap 这样的space reduction 事吗?

对对对。当时想了好久。。。

say543 发表于 2017-2-19 15:04
第五题 感觉用hashHeap 因该可行? current 指的是timestamp 最新的price 这样吗?

HashHeap 是啥数据结构？对，current是要latest price.

2ndpoet 发表于 2017-2-20 13:29
该开始的思路是想用heap,但是因为有search操作，改成binary search tree(TreeMap).

谢谢，那这样如果用treemap,是不是应该Price做Key了

xylxx92 发表于 2017-2-20 12:13
O(n^2)的暴力解法？我觉得如果是纯暴力的话应该是O(kn^2), k 是每个mail list的平均长度。或者你有O(1)的 ...

我也是用这种暴力方法，没有想到比O（k）更好的方法比较两个string lists的关系。

YY大帝 发表于 2017-2-20 13:41
谢谢，那这样如果用treemap,是不是应该Price做Key了

我是用price做key, 但是还用了一个hashmap 存了entry<timestamp, price>，因为要支持delete(timestamp)操作。

nestwood 发表于 2017-2-20 05:39
第2题，单链，只要有一个removed的set，就可以不用反转单链了吧？

removed的set怎么存？我当时是用了两个hashset, 一个存visited nodes, 一个存unvisited nodes; 每访问一个node的时候，check它的next是不是在这两个set里。

2ndpoet 发表于 2017-2-20 13:44
我也是用这种暴力方法，没有想到比O（k）更好的方法比较两个string lists的关系。

好吧，真想知道这道题怎么优化，想破头也没想出来。。。

2ndpoet 发表于 2017-2-20 13:44
我也是用这种暴力方法，没有想到比O（k）更好的方法比较两个string lists的关系。

对对对，忘了算这部分了。
我在想可不可以先按email的个数从大到小排个序，然后建一个email到user的mapping。这样当检查一个user的所有email时，如果发现这些email对应的user里面都有一个共同的user，那么这个user就是马甲。user可以用bitset来存，就可以做到O(k)的比较。
例子：
Alice: A, B, C
Bob: A, D
Cloud: B, C

对于所有map中没有的email都先初始化为0。

1. A: 000
   
2. B: 000
   
3. C: 000
   
4. D: 000

复制代码

先与操作所有Alice的email对应的bitset，发现为0，则给所有的bitset置Alice 对应的位

1. A: 001 (Alice)
   
2. B: 001 (Alice)
   
3. C: 001 (Alice)
   
4. D: 000

复制代码

检查Bob, 与操作所有email对应的bitset, 发现为0， 同样置位

1. A: 011 (Alice, Bob)
   
2. B: 001 (Alice)
   
3. C: 001 (Alice)
   
4. D: 010 (Bob)

复制代码

再检查Cloud，与操作结果大于0，所以Cloud是一个马甲。
最后或操作所有的bitset，得到011, 然后计算bitset中总共有几位得到用户数，是2。
这样的话时间复杂度好像是O(nlogn)排序 + O(nk)遍历每一个用户 + O(nk)计算unique的user数。

不知道这样做有没有问题。

2ndpoet 发表于 2017-2-20 14:30
removed的set怎么存？我当时是用了两个hashset, 一个存visited nodes, 一个存unvisited nodes; 每访问一 ...

多谢，说完就知道不对了，还没细想，反转单链肯定行不通。