wish电面

Job Hunting Interview
, , , ,
1

美国大哥
1.给你一个list，找出最短的sublist的sum大于指定的threshold。比如[1,2,3,4,5], threshold = 5, return -> [3,4] or [4,5]

2.find median of data stream
follow up:
假设有个百万级request的api 百分之90的数据在100-200之间怎么找出median？楼主只做出来百分之100的数据在100-200之间，我用bucket来做的。
至于90%我和面试官讲了思路，用四个heap 一个max heap 一个min heap 类似于find median of data stream一样 分别存小于100和大于200的数据

2

秒掉两道以及followup还是很牛的

3

过奖了过奖了。。不知道能不能onsite

4

应该会有

5

用四个heap 一个max heap 一个min heap

分别存小于100和大于200的数据

这两个heap只是用来计数对吧？用来决定100-200之间的两个heap的size？
另外想问下90%这一点，为什么不能同样用bucket做？

6

也可以 但是不能用array 存bucket 要用linkedlist来存bucket