9月24日Google NYC Onsite 新鲜面经

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

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

楼主 " BFS遍历，存每个substree到list里，然后用双重循坏找" 的意思就是先把每个Node都加入list?如果这样的话，dfs的任何一种遍历都可以放进所有的node啊，时间复杂度是O(n^3)?

duplicate substree，不知道有没有更好的方法

1. public class DuplicateSubtree {
   
2. 
   
3.         static class Node {
   
4.                 Node left, right;
   
5.                 int val;
   
6. 
   
7.                 public Node(int val) {
   
8.                         this.val = val;
   
9.                 }
   
10.         }
    
11. 
    
12.         public List<Node> getDuplicateSubtree(Node root) {
    
13.                 List<Node> res = new ArrayList<Node>();
    
14.                 if (root == null) {
    
15.                         return res;
    
16.                 }
    
17.                 List<Node> nodes = new ArrayList<Node>();
    
18.                 addNodes(root, nodes);
    
19.                 HashSet<Node> set = new HashSet<Node>();
    
20.                 for (int i = 0; i < nodes.size() - 1; i++) {
    
21.                         for (int j = i + 1; j < nodes.size(); j++) {
    
22.                                 if (set.contains(nodes.get(i))) {
    
23.                                         break;
    
24.                                 }
    
25.                                 if (isSameTree(nodes.get(i), nodes.get(j))) {
    
26.                                         if (!set.contains(nodes.get(i))
    
27.                                                         && !set.contains(nodes.get(j))) {
    
28.                                                 res.add(nodes.get(i));
    
29.                                         }
    
30.                                         set.add(nodes.get(i));
    
31.                                         set.add(nodes.get(j));
    
32.                                 }
    
33.                         }
    
34.                 }
    
35. 
    
36.                 return res;
    
37.         }
    
38. 
    
39.         private boolean isSameTree(Node node1, Node node2) {
    
40.                 if (node1 == null && node2 == null) {
    
41.                         return true;
    
42.                 }
    
43.                 if (node1 == null || node2 == null) {
    
44.                         return false;
    
45.                 }
    
46.                 if (node1.val != node2.val) {
    
47.                         return false;
    
48.                 }
    
49. 
    
50.                 return isSameTree(node1.left, node2.left)
    
51.                                 && isSameTree(node1.right, node2.right);
    
52.         }
    
53. 
    
54.         private void addNodes(Node root, List<Node> nodes) {
    
55.                 if (root == null) {
    
56.                         return;
    
57.                 }
    
58.                 nodes.add(root);
    
59.                 addNodes(root.left, nodes);
    
60.                 addNodes(root.right, nodes);
    
61.         }
    
62.        
    
63.         public static void main(String[] args) {
    
64.                 Node root = new Node(1);
    
65.                 root.left = new Node(2);
    
66.                 root.right = new Node(3);
    
67.                 root.left.left = new Node(4);
    
68.                 root.right.left = new Node(2);
    
69.                 root.right.right = new Node(4);
    
70.                 root.right.left.left = new Node(4);
    
71.                 DuplicateSubtree d = new DuplicateSubtree();
    
72.                 List<Node> res = d.getDuplicateSubtree(root);
    
73.                 for (Node node : res) {
    
74.                         print(node);
    
75.                         System.out.println();
    
76.                 }
    
77.         }
    
78. 
    
79.         private static void print(Node node) {
    
80.                 if (node == null) {
    
81.                         return;
    
82.                 }
    
83.                 System.out.print(node.val + " ");
    
84.                 print(node.left);
    
85.                 print(node.right);
    
86.         }
    
87. }
    

复制代码

写了下第一题,

1. public class FibonacciNumberII {
   
2. 
   
3.        
   
4.         // can larger than Integer.MAX_VALUE;
   
5.         public static void main(String[] args) {
   
6.                 List<List<Integer>> res = getFibonacciNumberPair(100);
   
7.                 for (List<Integer> list : res) {
   
8.                         System.out.println(list.get(0) + " " + list.get(1));
   
9.                 }
   
10.                 System.out.println(res.size() + " * ");
    
11.         }
    
12.        
    
13.         public static List<List<Integer>> getFibonacciNumberPair(int n) {
    
14.                 List<List<Integer>> res = new ArrayList<List<Integer>>();
    
15.                 HashSet<String> set = new HashSet<String>();
    
16.                 long[] arr = new long[n];
    
17.                 arr[0] = 0;
    
18.                 arr[1] = 1;
    
19.                 for (int i = 2; i < n; i++) {
    
20.                         arr[i] = arr[i - 1] + arr[i - 2];
    
21.                 }
    
22.                 for (int i = 0; i < n - 1; i++) {
    
23.                         List<Integer> list = new ArrayList<Integer>();
    
24.                         list.add((int)(arr[i] % 10));
    
25.                         list.add((int)(arr[i + 1] % 10));
    
26.                         String key = list.get(0) + "#" + list.get(1);
    
27.                         if (set.contains(key)) {
    
28.                                 return res;
    
29.                         } else {
    
30.                                 set.add(key);
    
31.                         }
    
32.                         res.add(list);
    
33.                 }
    
34.                
    
35.                 return res;
    
36.         }
    
37. }

复制代码