Google onsite

简短描述一下最近google的onsiteround 1: 股票交易
round 2: 坐标上一堆点，求能

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

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

了，design的面试官非常不爽……
当然自己面的也很差，move on……

矩形那题基本是考数学了，如果矩形的边必须平行于坐标轴，任意取两点作为矩形对角线，算出另外两点，看是否在集合中，再比较面积；
如果不一定是平行于坐标轴，可以还是取两点为对角线，找到所有以这条线为直径的圆上的点，算出最后一个点是否在集合内，在的话比较面积。

"坐标上一堆点，求能组成的最小矩形 "怎么回答啊

edyyy 发表于 2017-6-13 21:44
"坐标上一堆点，求能组成的最小矩形 "怎么回答啊

感觉可以：先随机生成一个中心点，然后通过解一个最大值的最小化问题可以得到真正的矩形中心点，找到中心点之后，距离中心点最远的一个点（注意这里的距离使用block distance）作为矩形的一个顶点，这样就知道矩形的边界了。

_(:з」∠)_但是对于优化问题我只会用启发式算法来解，所以最后得到的只是一个近似值。

补充内容 (2017-6-13 22:55):
不是block distance，就是一般用的distance_(:з」∠)_

kennethinsnow 发表于 2017-6-27 00:23
矩形那题基本是考数学了，如果矩形的边必须平行于坐标轴，任意取两点作为矩形对角线，算出另外两点，看是否 ...

直觉是每对二维点可以形成矩形（包括面积为0的）让后横坐标排序，用two pointers, i = 0, j = n - 1 这样子，比较，移动那个和下形成面积较小的 i, j (你懂的)。用Container With Most Water的思路？？？

补充内容 (2017-6-29 10:20):
擦 我看错题了，是最小的矩形

Thank you for sharing!

楼主能不能说一下infrastructure那一轮考的是什么？我也有一轮这个

kennethinsnow 发表于 2017-6-27 00:23
矩形那题基本是考数学了，如果矩形的边必须平行于坐标轴，任意取两点作为矩形对角线，算出另外两点，看是否 ...

楼主牛叉啊，这个解答真漂亮！

JustAMF 发表于 2017-7-15 00:34
楼主能不能说一下infrastructure那一轮考的是什么？我也有一轮这个

什么infrastructure？可以share一下吗？谢谢

kennethinsnow 发表于 2017-6-27 00:23
矩形那题基本是考数学了，如果矩形的边必须平行于坐标轴，任意取两点作为矩形对角线，算出另外两点，看是否 ...

这个复杂度有点大吧。。
首先任意两点作为对角线 O(n(n-1)/2) = O(N^2)
然后剩余的点是否在对角线为直径的圆上，那么总共复杂度为 O(N^2)*O(N) = O(N^3).
或者是我没有理解你的意思了