Google 电面

您好！
本帖隐藏的内容需要积分高于 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

yangdaxian 发表于 2018-6-15 11:10
抱歉啊，本弱鸡还是没想出来怎么nlogn实现，求具体讲一下排序后怎么merge。。。

今天又想了一遍 merge的地方还是觉得是O(n^2) 楼主有什么进展吗？

merge的时候肯定不能只看X轴啊，因为如果和这个interval里面的方块没有重合，那X轴交叉也没意义啊，而且和任何一个interval比的时候，肯定要和里面所有的方块比，所以正常做应该是n方。30楼的思路我看了一下，理论上来讲可以，但是实在是太麻烦了，我觉得楼主被加面，可能和最优解没关系

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

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

yangdaxian 发表于 2018-6-16 12:19
根据现有的讨论来看，如果不用之前一个同学给出论文的复杂nlogn做法的话，我感觉应该是做不到nlogn的。。 ...

同意 我觉得3楼写的比较好理解 但是merge起来还是要O(n^2)

哈哈哈哈 看不了

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

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

nlogn:
1) sort rectangle :  via x, then y if x is same : nlogn
2) height[y1,y2] = sum if isConnected(prev, curr), otherwise height = curr's height. if height blocks road, break and return.  

请问：电面是直接写code，还是写 pseudo code ?