Google 店面2轮

之前发过google OA，后来一直推迟面试，1月9日早上面了2轮，三天之后HR发邮件说要加面，想问问地里筒子一般什么情况会加面？

可能因为LZ是妹子吧，感觉题目真的很简单。

第一轮：

给一个直角坐标系，系上给若干点，求任意两点，满足：这两点的连线将剩余点 on one side of this line, 就是说这条线可以把剩余点分到线的一边，而不存在这条线的两边都有点的情况。

一看题目很懵，但是面试官一直给hint. 先是问，给N个点可以画多少条直线？秒答 N*(N-1)/2;  

对了， struct P{double x;double y;};

然后给了一个API，说 int OnWhichSide(vector<Point> line, Point p); return -1表示在一遍，return 1 表示在另一边。

题目的function signature是( 这是我自己写的)　vector<Point> PointsOn

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

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

t;]["c","loop1"]["a","loop2"]["b","loop2"]["c","loop2"]}(最多2个a，2个b，2个c) 。

最后发点牢骚，从12月13号开始，收到google 和 facebook 的interview，觉得自己google无望，转头去准备fb的面经和tag题，刷了2遍吧at least，最后被fb当天就拒了，google完全抱着不可能，很放松去面的，结果给了加面（说明有戏？加面到底是什么情况。。。。），有点郁闷，等心情好一点再发fb跪经吧。

fishcrab 发表于 2018-1-15 09:30
感谢lz！！！恭喜lz有加面！
求问第一题有复杂度更低的方法吗？
我在想能不能只看min x 的点，min y 的点 ...

一开始取min x 的点作为起点，然后随便取一个点先弄一个直线。
之后跟其他点比较，如果有点在这个直线的右侧，就更新这个直线变成 起点-这个点，复杂度O(n)

lilydiaz 发表于 2018-1-15 09:35
我觉得你的想法是对的。。。
那个API是他看我想不出来以后给的，然后因为我一直想不出来。。就没要求我 ...

刚请教了下大佬，大佬的想法是直接找minx或miny或maxx或maxy与其他交点连线与垂直线或者水平线夹角最小的情况，这个应该可以用斜率算出，这样的话似乎就是o(n)

应该是说明两个评价差距比较大 需要再面一次才能决定是不是送hc

感谢lz！！！恭喜lz有加面！
求问第一题有复杂度更低的方法吗？
我在想能不能只看min x 的点，min y 的点，max x的点和max y的点与其他所有交点的连线，用给的api判断剩下的点是否有交点，这样是o(n^2)？不知道是否可行
然后OnWhichSide的api面试官要求你实现了吗？

fishcrab 发表于 2018-1-15 09:30
感谢lz！！！恭喜lz有加面！
求问第一题有复杂度更低的方法吗？
我在想能不能只看min x 的点，min y 的点 ...

我觉得你的想法是对的。。。
那个API是他看我想不出来以后给的，然后因为我一直想不出来。。就没要求我实现

第一题满足条件的点对必然是凸包上相邻的点，所以就是求凸包?

cp12321 发表于 2018-1-15 10:41
一开始取min x 的点作为起点，然后随便取一个点先弄一个直线。
之后跟其他点比较，如果有点在这个直线的 ...

似乎很有道理！

cp12321 发表于 2018-1-15 10:41
一开始取min x 的点作为起点，然后随便取一个点先弄一个直线。
之后跟其他点比较，如果有点在这个直线的 ...

似乎很有道理！

tinylic 发表于 2018-1-15 10:26
第一题满足条件的点对必然是凸包上相邻的点，所以就是求凸包?

第一反应也是用凸包，然后corner case可能需要处理一下。