谷歌new grad电面+onsite，求米

Zcy_929 发表于 2020-1-7 05:52
类似建堆这个是我表述不准确了。我用的方法是跟为空字符串，从前往后遍历，对每个字符串查看当前节点是否 ...

这个树中每个节点应该是保存一个指向父节点的指针吧？这样对新进来的字符串只要从最后一个节点顺着父节点往上找它的最长prefix。这样感觉很优化。

spirit_room 发表于 2020/01/07 11:25:22
这个树中每个节点应该是保存一个指向父节点的指针吧？这样对新进来的字符串只要从最后一个节点顺着父节点往上找它的最长pref...

对，这样就是O(n+s)了

请问楼主第一题的思路是什么？ 用什么数据结构较合理？ input 是 streaming data 吗？ add() 和 kmax()  两个方法是混合着出现的吗？

举个例子： add(3), kmax(), add(4), kmax(), add(5), kmax()
这个例子中 所有 kmax() 的结果都是 3？

谢谢楼主的分享

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

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

iceburg2005 发表于 2020-3-13 07:26
我觉得这题思路应该和stream data 中求median类似，唯一区别是保持左边的heap的size始终为kmax()调用次数 ...

按照你的思路，相当于每次调用 kmax() 都返回当前最大值？

iceburg2005 发表于 2020-3-13 07:26
我觉得这题思路应该和stream data 中求median类似，唯一区别是保持左边的heap的size始终为kmax()调用次数 ...

你的方法看起来很可行， 谢谢

eraser 发表于 2020-3-13 14:54
按照你的思路，相当于每次调用 kmax() 都返回当前最大值？

对，返回左边maxheap的最大值，前提是maintain他的size始终为当前kmax()调用次数加1