谷歌新鲜电面，求米

wsq922

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

本帖最后由 wsq922 于 2022-7-19 17:27 编辑

Given a data stream and a distance d, output three values that withi

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

范围 idx-3, idx+3进行搜索。后来聊天才发现面试官想让我用binary search tree 的方法，不过anyway 都是log N 的解法

来自APP · 2022-7-21 19:31:25

你好想问一下为什么4是None 而不是[1,2,4] 呀，谢谢！

joepass

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

orlandowzb

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

neverlate

已米，
但是bs插入如果不用tree的话，复杂度是n，不是lgn

wsq922

neverlate 发表于 2022-7-19 17:40
已米，
但是bs插入如果不用tree的话，复杂度是n，不是lgn

学习了，看来还是得用bst

orlandowzb

如果是 125678，用 moving window，会不会错过 126 这种，除非要求只要有就行，或者说必须要连续的

wsq922

orlandowzb 发表于 2022-7-19 18:04
如果是 125678，用 moving window，会不会错过 126 这种，除非要求只要有就行，或者说必须要连续的

有的话需要从整个array中pop出去

匿名用户-WWNHS *2022-7-21 12:38:36* · 2022-7-21 12:38:36

直接用TreeMap找floorKey然后数3个是不是更简单？

say543

所以用binary search tree maintain input , 然后每次input = val, binary search tree ? 一次 bst tree 好像没办法直接找到前后+3 or -3 要用另外的储存空间? 另外input 有 duplicate 吗?

wsq922

匿名用户发表于 2022-7-21 04:31
你好想问一下为什么4是None 而不是[1,2,4] 呀，谢谢！

因为一旦有三个就pop出去，所以1，2， 5 就没了

谷歌新鲜电面， 求米