Google Sunnyvale Onsite 1/8 New Grad

去年10月投的简历，找了两个学长，还有室友实习时候认识的朋友内推。12月因为期末和假期所以推迟到1月onsite，等了很久4月15终于收到了Offer。过去了很久题目可能有些记不清了，可能题目本身不relevant了但是还是分享一下经历。也祝福还在准备面试的朋友们。
[hide=1701. 第一轮面试官是个印度大哥，在Google工作五年以上了。题目是这样的，有n个城市，每个城市都有平均m班次飞机，飞机有各自的起飞时间和降落时间。问一个人从A城市出发，到B城市结束一个multistop flight，寻找最快的到达时间。

我的思路是先考虑两个城市之间的最快到达时间。然后每个城市的所有飞机通过对起飞/降落时间排序来寻找可用航班。
这一轮代码没有写很多，绝大部分时间都在和面试官讨论一些细节，聊该用什么数据结构。我一直觉得每一

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

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

一起搞不清然后一起写代码跑case。。。
然后manager又无法在同一张图里表示需要另一个Tree。最后的follow up是怎么判断这个tree是valid的。我然后又开始胡说了。
[/hide]

题目如果没有解释清楚欢迎讨论，但是细节可能我也记得不完美了。重点还是和面试官沟通。祝大家找工作顺利，不要放弃啊，你看我第一个OA帖子已经5个月过去了啊。也感谢地理分享经验的朋友们，内推我的学长们，帮我mock的朋友们。Fight On。

evissoup 发表于 2019/04/19 00:36:01
楼主没hide成功????

是的但是我没法编辑了:(
假装hide成功好了

恭喜楼主！加油加油！紫薯紫薯

楼主没hide成功😂

赞不hide！

现在hide成功了

请问一下第二轮第二题 怎么算能形成三角形

这种两种怎么算？
1  -- 2
|      |
3 — 4

1  — 2  — 4
\            /
   \       /
      3

Wyf2222 发表于 2019/05/30 11:57:50
请问一下第二轮第二题 怎么算能形成三角形

这种两种怎么算？
1  -- 2
|      |
3 — 4

1  — 2  — 4
\            /
   \    ...

三个点两两之间有一条边这种

写了个O(E*(V+E))解法  

1. """
   
2. 
   
3. given a graph with V vertex, E edges
   
4. how many triangles are there in this graph
   
5. 
   
6. """
   
7. import collections
   
8. 
   
9. def build_graph(edges):
   
10.         graph = collections.defaultdict(set)
    
11.         for u,v in edges:
    
12.                 graph[u].add(v)
    
13.                 graph[v].add(u)
    
14. 
    
15.         return graph
    
16. 
    
17. 
    
18. def find_cycle(graph,src,dst):
    
19.         queue  = collections.deque()
    
20.         queue.append((src,[src]))
    
21.         result = []
    
22.         while queue:
    
23.                 size = len(queue)
    
24.                 for _ in range(size):
    
25.                         cur,path = queue.popleft()
    
26. 
    
27.                         if len(path)==3:
    
28.                                 if cur==dst:
    
29.                                         result.append(path)
    
30.                                 else:
    
31.                                         continue
    
32.                         for nxt in graph[cur]:
    
33.                                 if nxt not in path:
    
34.                                         queue.append((nxt,path+[nxt]))
    
35. 
    
36.         return result
    
37. 
    
38. def remove_edge(u,v,graph):
    
39.         graph[u].remove(v)
    
40.         graph[v].remove(u)
    
41. 
    
42. def add_edge(u,v,graph):
    
43.         graph[u].add(v)
    
44.         graph[v].add(u)
    
45. 
    
46. def graph_triangle(V, edges):
    
47. 
    
48.         graph = build_graph(edges)
    
49. 
    
50.         visited = [[False]*V for _ in range(V)]
    
51.         ans = 0
    
52.         for u,v in edges:
    
53.                 if visited[u][v] or visited[v][u]:
    
54.                         continue
    
55.                 remove_edge(u,v,graph)
    
56.                 result = find_cycle(graph,u,v)
    
57.                 ans += len(result)
    
58.                 for i in range(len(result)):
    
59.                         for j in range(len(result[i])):
    
60.                                 for k in range(j+1,len(result[i])):
    
61.                                         visited[result[i][j]][result[i][k]] = True
    
62.                                         visited[result[i][k]][result[i][j]] = True
    
63. 
    
64.                 add_edge(u,v,graph)
    
65. 
    
66.         return ans
    
67. 
    
68. V = 17
    
69. edges = [
    
70.         [0,1],
    
71.         [3,0],
    
72.         [0,2],
    
73.         [3,2],
    
74.         [1,2],
    
75.         [4,0],
    
76.         [3,4],
    
77.         [3,5],
    
78.         [4,5],
    
79.         [2,5],
    
80.         [1,5],
    
81.         [1,3]
    
82. ]
    
83. 
    
84. print(graph_triangle(V,edges))

复制代码

Guoyi 发表于 2019-5-30 12:25
三个点两两之间有一条边这种

thanks
这样的话，我觉得应该可以找长度为3的cycle， bfs based。
能否请教你说的两种解法的思路呢？