刚结束的狗家西雅图上门面试

homlyee 发表于 2019-5-28 12:08
我是存ABE,BEB,EBG. 最后一个node里加上count。所以trie只有三层。可能不一定是最优解，还是浪费了一些空 ...

啊 有道理 查询长度只有2 不用继续往下存

这第一轮，1000个数的数据流follow up有歧义。这个数据流是指总共1000个数，但不是一下子给你，而是一个个给？还是指有无穷个数，要你返回1000个数的滚动窗口之中掐头去尾后的平均值？若是后者的话，segment tree应该做不了，因为segment tree是静态的。

好奇如果用python 面试能不能直接用bisect_left bisect_right找数字的边界来计算次数。。。有点作弊的感觉，不过确实很方便，肯定能写完。。。

补充内容 (2019-5-28 20:12):
第5题

楼主可以说一下二分法思路吗

请问一下第二题怎么讨论hashmap 和 trie的优劣呢？
space 都是 On， time也都是 construct On  查询O1

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

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

yangyuzhiguang 发表于 2019-5-29 00:00
楼主可以说一下二分法思路吗

就是把数组分为三部分然后找左右边界算数量呀。一共6次logn就够了

Wyf2222 发表于 2019-5-29 05:21
请问一下第二题怎么讨论hashmap 和 trie的优劣呢？
space 都是 On， time也都是 construct On  查询O1

google一下2种数据结构对比的pros和cons就有很多。trie主要就是省空间

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

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

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

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies