谷歌onsite

Augustus 发表于 2018-2-22 13:47
这面经难爆了。。。  放弃治疗了，今年都什么bar。。。

一半在lc上能找到 剩下的几道题如果仔细看地里这几个月的面经 都可以找到类似的 所以我觉得认真地准备下 还是有机会的

请问lz 3面第一题怎么做呢？把所有node都push进heap？

tm1234 发表于 2018-2-23 01:29
请问lz 3面第一题怎么做呢？把所有node都push进heap？

差不多吧 保持一个大小为k的priority_queue 然后从上往下用bfs扫 当node的值小于pq的top时 就不往下继续展开这个node了

楼主，求问第一题follow up内存小，数据大怎么回答的？谢谢

yexiaojiaycc 发表于 2018-2-23 17:42
楼主，求问第一题follow up内存小，数据大怎么回答的？谢谢

在disk上preprocess 把interval的起点和终点分离开 然后用on disk sort 最后在memory里用线扫描

感谢LZ分享，果然Google爱考hard题。

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

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

楼主， 第二轮 第二题 followup什么思路？ 谢谢

Augustus 发表于 2018-2-26 07:47
楼主， 第二轮 第二题 followup什么思路？ 谢谢

用一个 map来存 interval, 再用两个hash table 存interval在 map里的iterator（key 分别是 起点和终点） 这样 删除也只需要logN的复杂度

anywho 发表于 2018-2-26 09:04
用一个 map来存 interval, 再用两个hash table 存interval在 map里的iterator（key 分别是 起点和终点）  ...

但是这样你一旦删除一个iterator，其他的iterator都失效了