Google 面经

请问lz merge interval 那个二分法能详细说说么
关于第三轮，数据太大，就是map reduce？

关于第一轮，可以参考这个应该 https://stackoverflow.com/questi ... s-intersect/565282#

我的最后一轮跟你的第一轮一模一样，真的是看到题整个是懵的，还让你自定义输入。我整个人就慌了，最后写的代码全是bug，面试官一直说你这个不work，改了之后你还是不work（蜜汁微笑），最后来了个Good luck。。。感觉也要挂在这一轮了，唉

第一题把每个点用坐标表示。用两两一组的点求线的斜率 y = kx + b 求k.  k一样的两条线必平行，所以没有交点。剩下的所有不平行的线，都有交点。 loop一下slope array 应该就是答案了。N条不平行的线，应该就有N!个交点。

看来面试完该向HR"抱怨"的还是要"抱怨一下"唉。。。

Tag: geometry
input lines: [(x,y),(x,y),(x,y),(x,y)] 很多个点的x，y
核心：如果p3p4 要和p1p2相交，
1. 当p2p3在p1p2 顺时针或逆时针方向， p2p4在p1p2 和前者相反的方向，
2. p1p3在p3p4 顺时针或逆时针方向，p2p3在p3p4 和前者相反的方向。
或者另一条边的一个点在线上

废话不多说 上代码

1. class Intersection:
   
2.     def find_intersections(self, lines):
   
3.         n = len(lines)
   
4.         res = 0
   
5.         for i in range(n):
   
6.             for j in range(i+1, n):
   
7.                 if self.intersect(lines[i][0], lines[i][1], lines[j][0], lines[j][1]):
   
8.                     res += 1
   
9.         return res
   
10.                
    
11.     # if p1p2 intersect with p3p4
    
12.     def intersect(self, p1, p2, p3, p4):
    
13.         o1,o2,o3,o4 = self.orientation(p1, p2, p3), self.orientation(p1, p2, p4), self.orientation(p3, p4, p1), self.orientation(p3, p4, p2)
    
14.         # p3 and p4 is different orientation to p1 and p3 and p4 is different orientation to p2
    
15.         # p1 and p2 is different orientation to p3 and p1 and p1 is different orientation to p4
    
16.         if o1 != o2 and o3!=o4:
    
17.             return True
    
18.         # if p3 is on p1p2 and p1p2 and p2p3 has same slope
    
19.         if o1 == 0 and self.on(p1,p2,p3):
    
20.             return True
    
21.         # if p4 is on p1p2 and p1p2 and p2p4 has same slope
    
22.         if o2 == 0 and self.on(p1,p2,p4):
    
23.             return True
    
24.         if o3 == 0 and self.on(p3,p4,p1):
    
25.             return True
    
26.         if o4 == 0 and self.on(p3,p4,p2):
    
27.             return True
    
28.         return False
    
29.     # p3p2 is counter clock wise or clock wise of p1p2
    
30.     def orientation(self, p1, p2, p3):
    
31.         #slope1 = p2[1]-p1[1] / p2[0] - p1[0]
    
32.         #sloep2 = p3[1]-p2[1] / p3[0] - p3[0]
    
33.         # slope1 - slope2 = (p2[1]-p1[1]) * (p3[0] - p3[0]) - (p3[1]-p2[1]) * (p2[0] - p1[0])
    
34.         diff = (p2[1]-p1[1]) * (p3[0] - p3[0]) - (p3[1]-p2[1]) * (p2[0] - p1[0])
    
35.         # 2 slope equal in the same line
    
36.         if diff == 0:
    
37.             return 0
    
38.         # slope1 > slope2 -> p2p3 is counter clock wise of p1p2
    
39.         if diff > 0:
    
40.             return 1 #
    
41.         # slope1 > slope2 -> p2p3 is clock wise of p1p2
    
42.         return 2
    
43.    
    
44.     # p3 is on p1p2
    
45.     def on(self, p1,p2,p3):
    
46.         maxx,maxy,minx,miny = max(p1[0],p2[0]), max(p1[1],p2[1]), min(p1[0],p2[0]), min(p1[1],p2[1])
    
47.         return minx <= p3[0] <= maxx and miny <= p3[1] <= maxy
    
48. 
    

复制代码

求个大米

感谢楼主分享！这种情况应该可以跟 recruiter 反馈将那一轮作废的，毕竟面试体验极差，面试官题目也没交代清楚。

这种计算几何问题确实很少见，普通求多个线段交点解法就是 O(n^2), bentley-ottmann 扫描线算法可以 O(nlogn)，不过 45 分钟最多写个 pseudo code 了，解释清楚都比较难，特别是 virtual interview. 遇到的类似题目的朋友算是运气比较差了。

匿名者 发表于 2021-5-5 02:06
第一题把每个点用坐标表示。用两两一组的点求线的斜率 y = kx + b 求k.  k一样的两条线必平行，所以没有交 ...

N条线不平行也可以只有一个交点啊，感觉还是只能暴力推

wtf is Q1?