谷歌New Grad电面面经

11.27面的，烙印，上来就说今天做两道题

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

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

想问一下LZ第一题有什么具体思路么？个人感觉可以用个map存每一对childNode - parentNodeList，遍历完树再把map过一遍顺便输出结果，但感觉空间时间开销似乎都不是很好

不知道对不对。。。用Divided and Conquer做，然后4个判断，分别判断左孩子和右孩子的左右孩子是否相等。

1. def nodeWithTwoParents(root):
   
2.     if root is None:
   
3.         return None
   
4.     left = nodeWithTwoParents(root.left)
   
5.     right = nodeWithTwoParents(root.right)
   
6. 
   
7.     if left and right:
   
8.         if left.right and right.left and left.right == right.left:
   
9.             print("{} -> {}".format(right.val, right.left.val))
   
10.             return root
    
11.         if left.left and right.left and left.left == right.left:
    
12.             print("{} -> {}".format(right.val, right.left.val))
    
13.             return root
    
14.         if left.right and right.right and left.right == right.right:
    
15.             print("{} -> {}".format(right.val, right.right.val))
    
16.             return root
    
17.         if left.left and right.right and left.left == right.right:
    
18.             print("{} -> {}".format(right.val, right.right.val))
    
19.             return root
    
20.     return root
    
21. 
    
22. class Tree:
    
23.     def __init__(self, val):
    
24.         self.val = val
    
25.         self.left = None
    
26.         self.right = None
    
27. 
    
28. a = Tree('a')
    
29. b = Tree('b')
    
30. c = Tree('c')
    
31. d = Tree('d')
    
32. e = Tree('e')
    
33. f = Tree('f')
    
34. 
    
35. a.left = b
    
36. a.right = c
    
37. c.left = d
    
38. c.right = e
    
39. d.right = f
    
40. e.left = f
    
41. 
    
42. 
    
43. nodeWithTwoParents(a)

复制代码

easonlyx 发表于 2018-11-29 02:53
求米TOT 觉得例子能看懂的求加个米

第二题大概是这样？请楼主指点

1. class Time{
   
2.         long start;
   
3.         long end;
   
4.         String id;
   
5.         public Time(String id){
   
6.                 this.id = id;
   
7.         }
   
8. }
   
9. Queue<Time> q = new LinkedList<>();
   
10. public static void started(long timestamp, String requestId){
    
11.         Time a = new Time(requestId);
    
12.         a.start = timestamp;
    
13.         a.end = 0;
    
14.         q.offer(a);
    
15. }
    
16. public static List<Time> finished(long timestamp, String requestId){
    
17.         List<Time> res = new ArrayList<>();
    
18.         for(Time i : q){
    
19.                 if(a.id.equals(requestId)){
    
20.                         a.end = timestamp;
    
21.                 }
    
22.         }
    
23.         while(q.peek().timestamp!=0){
    
24.                 res.add(q.poll());
    
25.         }
    
26.         return res;
    
27. }

复制代码

请教一下楼主第二题怎么做的

请教第一题的dfs截止条件

dengzeyu147 发表于 2018-11-28 08:12
请教一下楼主第二题怎么做的

感觉可以用queue来做？不过得新创一个class

有两个父节点的话，请问应该如何表示d.parent 呢？ 求问第一题的dfs思路～ bfs的话是不是可以用level order + hashset做呢

就bfs queue+set 判断node的左右孩子是否set存在过？存在过就输出？

有人来个第二题的代码嘛？

junhezfm 发表于 2018-11-28 17:08
想问一下LZ第一题有什么具体思路么？个人感觉可以用个map存每一对childNode - parentNodeList，遍历完树再 ...

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

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