G-o-o-g-l-e 电面

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

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

leixiang5 发表于 2016-9-23 10:05
这样速度太慢了~...给2个1 million长的..1milllion宽的rectangles..这是要million * million的节奏啊~

求好一点的解。。。这不是允许overlap嘛。。。

跟wtcupup说的一样，具体方法看perfect ralectangle o(nlogn)的解法，改下条件变量

楼主，我有个不成熟的想法，就是把上下左右的点找出来，然后就知道应有的面积，把所有矩形面积和减去重叠面积后的结果跟应有面积对比

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

WhatsFLAG 发表于 2016-9-23 22:21
我的理解就是sweep line从左往右，遇到右上角就出队列，新进队列的跟老元素取交集，所有交集难道不能直接 ...

也许可以~...这太需要visual了...

我感觉40分钟写出来好困难啊，存不存在三哥给三哥留位置的潜规则这种说法啊

WhatsFLAG 发表于 2016-9-23 23:09
我感觉40分钟写出来好困难啊，存不存在三哥给三哥留位置的潜规则这种说法啊

谁知道呢......过几天有没有onsite就知道了~

模糊的感觉是先找到上下左右四条边，然后从左向右扫，同时保证从上到下的线上是全部被覆盖的。。。

题外话，有个思路：以后跟小伙伴合作，万一面试面不好了，就赶紧把火警叫起来。。。。