狗家昂赛跪经

狗家onsite，一共五轮(3个coding，1个system design, 1个BQ)
两轮coding都是简单题，可

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

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

注意这类题。
system design是标准题，地里曾经有人报过，略去。

谷歌有点不地道了吧。ng考系统设计也就算了，计算几何虽然在考核范围内，但是考这个就明摆着，你别过。

找到leetcode上这条讨论：https://leetcode.com/discuss/int ... tained-in-a-polygon 以及感觉利口舞八期有点像
以及geeksforgeeks上这个 https://www.geeksforgeeks.org/how-to-check-if-a-given-point-lies-inside-a-polygon//

如有用也求点米（btw看到这个帖子居然是17年的，感觉最近gg经常往回问很多年前的高频题

先sort所有点从小到大 然后定下来最小的两个点找第三个点 如果第三个点是在第二个点顺时针 说明第二个点不对 所以pop 试一试下一个第二个点 再找第三个点是不是逆时针 直到找到x最大的点 这样做完就找到多边形的下半部分 然后再用同样方法找多边形上面部分

请问楼主计算几何学那题能给个题号吗？ 或者大概思路？ 多谢。

求楼主别略去了好嘛？狗家面经多容易翻漏掉。系统设计设计什么呢？谢谢！而且现在fresh PHD也要面系统设计了么？楼主面的5? 4应该是不需要的。

匿名用户 发表于 2021-03-20 19:55:30
请问楼主计算几何学那题能给个题号吗？ 或者大概思路？ 多谢。

估计是这个 https://en.m.wikipedia.org/wiki/Point_in_polygon

bbbooottt 发表于 2021-3-21 11:38
估计是这个 https://en.m.wikipedia.org/wiki/Point_in_polygon

对,是这个, 但是要考虑多边形的边有上千条和凹/凸情况

new grad 也来system design??????
不是5年以下不搞么

感谢LZ分享！

pud 发表于 2021-03-21 07:01:56
对,是这个, 但是要考虑多边形的边有上千条和凹/凸情况

naive循环所有边，优化一下对边做index比如R tree，复杂度logN，可以处理凹凸和大量的边。还可以做hash，理论上o1。wiki上应该有很多解法，但是这题有点难，只能说你运气不好