roblox 第一轮三方面试

第一轮面试是Karak 第三方1小时面试前5分钟简单介绍自己tech背景
然后10分

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

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

hildPairs 和两个nod。

3. 找出最远距离的祖先

input是parentChildPairs和一个node

感觉和楼主面的同样一个人。。。。也是面试这些题目

1. # coding=utf-8
   
2. """
   
3. 找出有零或一个parent 的node
   
4. input是一个二维array represent the parentChildPairs,
   
5. 每个pair input[0] 是input[1] 的parent，比如 {{1,2}}
   
6. 表示1 是2 的parent.
   
7. """
   
8. 
   
9. from collections import defaultdict
   
10. 
    
11. def find_zero_one_parent_nodes(arr):
    
12.     ct = defaultdict(set)
    
13.     for p, c in arr:
    
14.         ct[c].add(p)
    
15.    
    
16.     res = set()
    
17.     for p, c in arr:
    
18.         if p not in ct:
    
19.             res.add(p)
    
20.         if len(ct[c]) == 1:
    
21.             res.add(c)
    
22.     return res
    
23. 
    
24. 
    
25. import unittest
    
26. class Test(unittest.TestCase):
    
27. 
    
28.     def test_1(self):
    
29.         arr = [(1, 2), (1, 2), (2, 3), (1, 3)]
    
30.         actual = find_zero_one_parent_nodes(arr)
    
31.         expect = set([1, 2])
    
32.         self.assertEqual(actual, expect)
    
33.         print(actual)
    
34. 
    
35. 
    
36. if __name__ == '__main__':
    
37.     unittest.main(verbosity=2)

复制代码

1. # coding=utf-8
   
2. """
   
3. 找出有零或一个parent 的node
   
4. input是一个二维array represent the parentChildPairs,
   
5. 每个pair input[0] 是input[1] 的parent，比如 {{1,2}}
   
6. 表示1 是2 的parent.
   
7. 找出两个node是否有共同的祖先
   
8. """
   
9. 
   
10. from collections import defaultdict
    
11. from collections import deque
    
12. 
    
13. def have_common_ancestor(arr, p1, p2):
    
14.     cp_graph = defaultdict(set)
    
15.     for p, c in arr:
    
16.         cp_graph[c].add(p)
    
17.     p1_ancestors = get_ancestors(cp_graph, p1)
    
18.     p2_ancestors = get_ancestors(cp_graph, p2)
    
19.     return bool(p1_ancestors & p2_ancestors)
    
20. 
    
21. def get_ancestors(cp_graph, p):
    
22.     visited = set()
    
23.     queue = deque([p])
    
24.     res = set()
    
25.     while queue:
    
26.         n = queue.popleft()
    
27.         res.add(n)
    
28.         for nxt in cp_graph.get(n) or []:
    
29.             if nxt not in visited:
    
30.                 visited.add(nxt)
    
31.                 queue.append(nxt)
    
32.     return res
    
33. 
    
34. 
    
35. import unittest
    
36. class Test(unittest.TestCase):
    
37. 
    
38.     def test_1(self):
    
39.         arr = [(1, 2), (1, 2), (2, 3), (1, 3)]
    
40.         actual = have_common_ancestor(arr, 1, 2)
    
41.         expect = True
    
42.         self.assertEqual(actual, expect)
    
43.         print(actual)
    
44. 
    
45.     def test_2(self):
    
46.         arr = [(1, 2), (1, 2), (2, 3), (1, 3)]
    
47.         actual = have_common_ancestor(arr, 1, 4)
    
48.         expect = False
    
49.         self.assertEqual(actual, expect)
    
50.         print(actual)
    
51. 
    
52.     def test_3(self):
    
53.         arr = [(1, 2), (1, 2), (2, 3), (1, 3), (4, 5), (5, 6)]
    
54.         actual = have_common_ancestor(arr, 2, 6)
    
55.         expect = False
    
56.         self.assertEqual(actual, expect)
    
57.         print(actual)
    
58. 
    
59. if __name__ == '__main__':
    
60.     unittest.main(verbosity=2)

复制代码

1. # coding=utf-8
   
2. """
   
3. 找出有零或一个parent 的node
   
4. input是一个二维array represent the parentChildPairs,
   
5. 每个pair input[0] 是input[1] 的parent，比如 {{1,2}}
   
6. 表示1 是2 的parent. no cycle
   
7. 找出最远距离的祖先
   
8. """
   
9. 
   
10. from collections import defaultdict
    
11. from collections import deque
    
12. 
    
13. def farest_ancestors(arr, n):
    
14.     cp_graph = defaultdict(set)
    
15.     for p, c in arr:
    
16.         cp_graph[c].add(p)
    
17.     print(cp_graph)
    
18.     p_ancestors = get_farest_ancestors(cp_graph, n)
    
19.     return p_ancestors
    
20. 
    
21. def get_farest_ancestors(cp_graph, node):
    
22.     queue = deque([node])
    
23.     res = set([node])
    
24.     while queue:
    
25.         len_queue = len(queue)
    
26.         res.clear()
    
27.         for _ in range(len_queue):
    
28.             n = queue.popleft()
    
29.             res.add(n)
    
30.             for nxt in cp_graph.get(n) or []:
    
31.                 queue.append(nxt)
    
32.     return res
    
33. 
    
34. 
    
35. import unittest
    
36. class Test(unittest.TestCase):
    
37. 
    
38.     def test_1(self):
    
39.         arr = [(1, 2), (1, 2), (2, 3), (1, 3)]
    
40.         actual = farest_ancestors(arr, 3)
    
41.         expect = set([1])
    
42.         print(actual)
    
43.         self.assertEqual(actual, expect)
    
44. 
    
45.     def test_2(self):
    
46.         arr = [(1, 2), (1, 2), (2, 3), (1, 3)]
    
47.         actual = farest_ancestors(arr, 4)
    
48.         expect = set([4])
    
49.         print(actual)
    
50.         self.assertEqual(actual, expect)
    
51. 
    
52.     def test_3(self):
    
53.         arr = [(1, 2), (1, 2), (2, 3), (1, 3), (4, 5), (5, 6)]
    
54.         actual = farest_ancestors(arr, 6)
    
55.         expect = set([4])
    
56.         print(actual)
    
57.         self.assertEqual(actual, expect)
    
58. 
    
59.     def test_4(self):
    
60.         arr = [(1, 2), (3, 2), (4, 1), (5, 3)]
    
61.         actual = farest_ancestors(arr, 2)
    
62.         expect = set([4, 5])
    
63.         print(actual)
    
64.         self.assertEqual(actual, expect)
    
65. 
    
66. if __name__ == '__main__':
    
67.     unittest.main(verbosity=2)

复制代码

和你面到了一样的题呢！

我也面到了一模一样的题目