兴趣钉热乎新oa

兴趣定oa换题啦 地里似乎还没有面筋所以来发一下 一道题四个小时 题目还是挺简单的

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

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

接下来是要面karat了 球rp球大米看面筋

求一下timeline

请问一下是directed graph还是undirected graph?

AiLiner 发表于 2018-10-21 07:16
求一下timeline

十月初内推的 之前太忙了oa一直拖到十月中的时候做 做完两天就出回复了

xyzppp 发表于 2018-10-23 05:47
请问一下是directed graph还是undirected graph?

directed

谢谢楼主面经，一样的题

谢谢楼主的面经~请问这个是直接用dfs做吗？有没有什么比较tricky的case呢？明天要做了好紧张

写了一下：

1. from typing import List
   
2. from collections import defaultdict
   
3. 
   
4. 
   
5. def longest_cycle_in_graph(edges: List[List[str]]) -> List[str]:
   
6.     graph = defaultdict(list)
   
7.     visited = defaultdict(lambda: False)
   
8.     visiting = defaultdict(int)
   
9.     ids = set()
   
10.     for item in edges:
    
11.         graph[item[0]].append(item[1])
    
12.         ids.add(item[1])
    
13.         ids.add(item[0])
    
14. 
    
15.     longest_cycle = []
    
16.     path = []
    
17. 
    
18.     def traverse(id, index):
    
19.         nonlocal graph, path, visited, visiting, longest_cycle
    
20.         if visited[id]:
    
21.             return
    
22. 
    
23.         path.append(id)
    
24.         if id in visiting:
    
25.             if index - visiting[id] + 1 > len(longest_cycle):
    
26.                 longest_cycle = path[visiting[id]:(index + 1)]
    
27.             path.pop()
    
28.             return
    
29. 
    
30.         visiting[id] = index
    
31.         for next_id in graph[id]:
    
32.             traverse(next_id, index + 1)
    
33. 
    
34.         del visiting[id]
    
35.         visited[id] = True
    
36.         path.pop()
    
37.         return
    
38. 
    
39.     for id in ids:
    
40.         traverse(id, 0)
    
41. 
    
42.     return longest_cycle
    
43. 
    
44. 
    
45. edges = [list(pair)
    
46.          for pair in ['ab', 'bd', 'dc', 'ca', 'de', 'ef', 'fg', 'gh', 'hd']]
    
47. print(longest_cycle_in_graph(edges))
    
48. 
    
49. edges = [list(pair)
    
50.          for pair in ['ab', 'bd', 'dc', 'ca', 'de', 'ef', 'fh', 'he']]
    
51. print(longest_cycle_in_graph(edges))
    

复制代码