Google VO

第一次发帖所以设置了100分的权限，不能看的朋友可以看截图。最近relocate比较忙，所以如果想要phone interview的面经，我也可以之后更新下。

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式

cathy.0517 发表于 2022-5-27 13:17
请问能不能具体说下怎么寻找合适的bucket？bucket里面是num-d和num+d吗？这样的话这个bucket里最大的num+d ...

我只能想到一个笨一点的方法
因为我们建造bucket就是要保证bucket里面的差值不能超过d
BST只是用来搜索放到哪个bucket
我们可以用一个int array来表示bucket 它的size为2 里面存的当前bucket最大值和最小值
当新进来一个值的时候，我们check一下是不是属于这个bucket
判断属于不属于就等于我把当前值加进去会不会使整个bucket的差值大于d
如果不属于，看它比当前bucket的最大值大，还是比最小值小，从而决定了走哪个方向
bucket之间会有overlap 但是不会完全重叠 因为我们新建一个bucket的时候一定是不在范围内才建的
我们会在所有符合的bucket当中都加入当前值
可能需要自己写BST java的Treemap我用的不是很多 不知道可不可以实现



补充内容 (2022-05-28 07:23 +8:00):
需要证明 possible solution

Question3:
一点思路.... but not sure
根据题意 我们需要maintain 一系列的buckets 对于每一个buckets来说差值要小于d
问题的关键在于我们如何去traverse这些bucket
如果linear scan的话 会达到O(n)
可以尝试用binary search去寻找合适的bucket --> TreeMap(self-balancing BST)
如果当前值可以落入当前bucket的范围 我们就加入到当前的bucket
如果不可以 添加新的node到BST
这样下来每个bucket一定是没有overlap的
如果只是单纯返回一个random list with size 3, maintain a global list
如果需要范围差值最小的list, traverse each bucket
(这个时候每个bucket里面的数值差值一定小于d 就移除了d对于题目的影响)

第三题相当于要实现一个API，里面有一个method，每次从数据流中接受一个值，然后看  加上当前值之后，以往的数据流里有没有满足条件的三个数。
我最一开始想的是heap，但似乎不对。
我最后的解是，call一次这个method的时间是O(n)。但因为数据流每来一个数据都要call一次这个method，所以整个API的复杂度是O(n^2)
最后没有时间了，然后就口头说了下优化方案。但面试官没说对还是不对

求问最后一题有什么advanced思路吗 我能想到的只是 用TreeMap统计 每个数字出现的频率
之后 每进来一个新的数字 对 [max(TreeMap.first(),num-d), min(TreeMap.last(),num+d)] 之内的数字更新result
但是如果d很大的话可能会有点问题？求问有什么follow up吗～

最后一题如果能sort，就能用heap来解，类似meeting room II，但是数据流应该不能sort把

楼主电话面试后多久约VO啊？

请问第一题的符号总是大于号吗？

还是没弄明白第三题怎么解。求指点

匿名者 发表于 2022-5-26 12:32
请问第一题的符号总是大于号吗？

是的zszszszs

匿名者 发表于 2022-5-26 09:53
楼主电话面试后多久约VO啊？

店面之后，第二天吧，就收到onsite