Google Onsite面经

nestwood 发表于 2017-2-21 15:36
晕晕乎乎写了一个复杂的，希望能看到更简洁的

应该是union find的思路，看了楼上Zhenying的实现，自己想转成java，搞得更晕乎，写了个set的版本，感觉比自己前一个简洁了, O(n) runtime, O(n) space。

1. public int linkedComponent(List<ListNode> nodes) {
   
2.     if (nodes == null || nodes.isEmpty()) {
   
3.         return 0;
   
4.     }
   
5. 
   
6.     int total = nodes.size();
   
7.     Set<ListNode> set = new HashSet<>();
   
8.     set.addAll(nodes);
   
9. 
   
10.     Set<ListNode> visited = new HashSet<>();
    
11.     for (ListNode root : nodes) {
    
12.         if (visited.contains(root)) {
    
13.             continue;
    
14.         }
    
15.         ListNode next = root.next;
    
16.         while (next != null && set.contains(next) && !visited.contains(next)) {
    
17.             visited.add(next);
    
18.             next = next.next;
    
19.         }
    
20.     }
    
21. 
    
22.     return total - visited.size();
    
23. }

复制代码

补充内容 (2017-2-23 03:00):
回头发现， return set.size() 就可以了。

补充内容 (2017-2-23 03:01):
又胡说，仍然是 return total - visited.size();

第五题参考各位的意见写了代码，求指正

1. public static class Stock{
   
2. 
   
3.   public TreeMap<Integer, Integer> priceMap;
   
4.   public TreeMap<Integer, Integer> countMap;
   
5. 
   
6.   public Stock(){
   
7.     priceMap = new TreeMap<Integer, Integer>();  //key is the timestamp and value is the price
   
8.     countMap = new TreeMap<Integer, Integer>();  // key is the price and value is the number of the price
   
9.   }
   
10. 
    
11.   // update(timestamp t2, price): timestamp can be an old one or a new one.
    
12.   public void update(int timestamp, int price){
    
13.     if(priceMap.containsKey(timestamp)){
    
14.       int origin = priceMap.get(timestamp);
    
15.       if(countMap.get(origin) == 1) countMap.remove(origin);
    
16.       else countMap.put(origin, countMap.get(origin) - 1);
    
17.     }
    
18.     priceMap.put(timestamp, price);
    
19.     countMap.put(price, countMap.getOrDefault(price, 0) + 1);
    
20.   }
    
21. 
    
22.   //delete(timestamp t1): delete the data at timestamp t1
    
23.   public void delete(int timestamp){
    
24.     if(! priceMap.containsKey(timestamp)) return ;
    
25.     int price = priceMap.get(timestamp);
    
26.     if(countMap.get(price) == 1) countMap.remove(price);
    
27.     else countMap.put(price, countMap.get(price) - 1);
    
28.     priceMap.remove(timestamp);
    
29.   }
    
30. 
    
31.   public int getCurrentPrice(){
    
32.     if(priceMap.size() == 0) return -1;
    
33.     else return priceMap.lastEntry().getValue();
    
34.   }
    
35. 
    
36.   public int getHighPrice(){
    
37.     if(countMap.size() == 0) return -1;
    
38.     else return countMap.lastKey();
    
39.   }
    
40. 
    
41.   public int getLowPrice(){
    
42.     if(countMap.size() == 0) return -1;
    
43.     else return countMap.firstKey();
    
44.   }
    
45. }

复制代码

csehao 发表于 2017-2-22 15:20
问下第二题什么是hidden linked list, 是不是就是说有一堆double linked list, 然后给出其中一些node, 然后 ...

hidden linked list 是指这个linked list的head node不知道是哪个，input只给出一些nodes，它们是属于这个linked list里面的。

Zhenying 发表于 2017-2-20 16:56
对对对，忘了算这部分了。
我在想可不可以先按email的个数从大到小排个序，然后建一个email到user的mapp ...

第四题应该是union find， 和第二island II是一样的思路

Zhenying 发表于 2017-2-20 16:56
对对对，忘了算这部分了。
我在想可不可以先按email的个数从大到小排个序，然后建一个email到user的mapp ...

第四题应该是union find， 和第二island II是一样的思路

erty 发表于 2017-2-23 06:16
第五题参考各位的意见写了代码，求指正

写的非常好啊

楼主你好 想问下第五题可不可以用两个TreeMap  TreeMap<Time,Price> time,TreeMap<Price,TreeSet<Time>> price来解答？这样update的时间复杂度是logN*logN

单链表

1.    public int numComponents(List<Node> nodes) {
   
2.         HashSet<Node> exist = new HashSet<>();
   
3.         HashSet<Node> preExist = new HashSet<>();
   
4.         int count = 0;
   
5.         for (Node node : nodes) {
   
6.             if (!exist.contains(node)) {
   
7.                 count++;
   
8.                 if (node.next != null && exist.contains(node.next)) {
   
9.                     count--;
   
10.                 }
    
11.                 if (preExist.contains(node)) {
    
12.                     count--;
    
13.                 }
    
14.                 exist.add(node);
    
15.                 if (node.next != null) {
    
16.                     preExist.add(node.next);
    
17.                 }
    
18.             }
    
19.         }
    
20. 
    
21.         return count;
    
22.     }
    
23. }

复制代码

第四题代码 union find ,另一种方法是建一个图，然后dfs

1. public class UserFindByEmail {
   
2. 
   
3.     static class Contact {
   
4.         String name;
   
5.         List<String> emails;
   
6. 
   
7.         public Contact(String n, List<String> es) {
   
8.             name = n;
   
9.             emails = es;
   
10.         }
    
11.     }
    
12.     public int unionUsername(List<Contact> input) {
    
13.         if (input == null || input.size() == 0) {
    
14.             return 0;
    
15.         }
    
16. 
    
17.         int[] roots = new int[input.size()];
    
18.         HashMap<String, List<Integer>> map = new HashMap<>();
    
19.         int n = input.size();
    
20.         for (int i = 0; i < n; i++) {
    
21.             roots[i] = i;
    
22.         }
    
23. 
    
24.         for (int i = 0; i < input.size(); i++) {
    
25.             Contact user = input.get(i);
    
26.             for (String email : user.emails) {
    
27.                 if (!map.containsKey(email)) {
    
28.                     map.put(email, new ArrayList<>());
    
29.                 }
    
30.                 map.get(email).add(i);
    
31.             }
    
32.         }
    
33. 
    
34.         for (List<Integer> list : map.values()) {
    
35.             for (int i = 0; i < list.size() - 1; i++) {
    
36.                 union(roots, list.get(0), list.get(1));
    
37.             }
    
38.         }
    
39. 
    
40.         int res = 0;
    
41.         for (int i = 0; i < roots.length; i++) {
    
42.             if (roots[i] == i) {
    
43.                 res++;
    
44.             }
    
45.         }
    
46. 
    
47.         return res;
    
48.     }
    
49. 
    
50.     public void union(int[] roots, int i, int j) {
    
51.         int x = find(roots, i);
    
52.         int y = find(roots, j);
    
53.         roots[x] = y;
    
54.     }
    
55. 
    
56.     public int find(int[] roots, int x) {
    
57.         while (roots[x] != x) {
    
58.             roots[x] = roots[roots[x]];
    
59.             x = roots[x];
    
60.         }
    
61. 
    
62.         return x;
    
63.     }
    
64. 
    
65.     public static void main(String[] args) {
    
66.         UserFindByEmail u = new UserFindByEmail();
    
67.         List<Contact> input = new ArrayList<>();
    
68.         input.add(new Contact("Jack1", Arrays.asList("123@gmail.com", "ggg@gmail.com")));
    
69.         input.add(new Contact("Jack2", Arrays.asList("hh@gmail.com", "fff@gmail.com")));
    
70.         input.add(new Contact("Bob", Arrays.asList("123@gmail.com", "eeegg@gmail.com")));
    
71.         input.add(new Contact("Jack4", Arrays.asList("ccc@gmail.com", "aaa@gmail.com")));
    
72.         input.add(new Contact("Jack5", Arrays.asList("efg@gmail.com", "ccc@gmail.com")));
    
73.         System.out.println(u.unionUsername(input));
    
74.     }
    
75. }
    

复制代码

组合contacts，建图的方法

1. public class GroupContactsII {
   
2.     static class Contact {
   
3.         String name;
   
4.         List<String> emails;
   
5. 
   
6.         public Contact(String n, List<String> es) {
   
7.             name = n;
   
8.             emails = es;
   
9.         }
   
10.     }
    
11.     public int unionUsername(List<Contact> input) {
    
12.         if (input == null || input.size() == 0) {
    
13.             return 0;
    
14.         }
    
15. 
    
16.         int[][] graph = buildGraph(input);
    
17.         boolean[] visited = new boolean[input.size()];
    
18.         int res = 0;
    
19.         for (int i = 0; i < input.size(); i++) {
    
20.             if (!visited[i]) {
    
21.                 dfs(graph, i, visited);
    
22.                 res++;
    
23.             }
    
24.         }
    
25. 
    
26.         return res;
    
27.     }
    
28. 
    
29.     private void dfs(int[][] graph, int k, boolean[] visited) {
    
30.         if (visited[k]) {
    
31.             return;
    
32.         }
    
33. 
    
34.         visited[k] = true;
    
35.         for (int i = 0; i < graph.length; i++) {
    
36.             if (graph[k][i] == 1) {
    
37.                 dfs(graph, i, visited);
    
38.             }
    
39.         }
    
40.     }
    
41. 
    
42.     public int[][] buildGraph(List<Contact> input) {
    
43.         int n = input.size();
    
44.         int[][] graph = new int[n][n];
    
45. 
    
46.         HashMap<String, List<Integer>> map = new HashMap();
    
47.         for (int i = 0; i < input.size(); i++) {
    
48.             for (String s : input.get(i).emails) {
    
49.                 if (!map.containsKey(s)) {
    
50.                     map.put(s, new ArrayList<>());
    
51.                 }
    
52.                 map.get(s).add(i);
    
53.             }
    
54.         }
    
55. 
    
56.         for (List<Integer> list : map.values()) {
    
57.             for (int i = 0; i < list.size(); i++) {
    
58.                 for (int j = i + 1; j < list.size(); j++) {
    
59.                     graph[list.get(i)][list.get(j)] = 1;
    
60.                     graph[list.get(j)][list.get(i)] = 1;
    
61.                 }
    
62.             }
    
63.         }
    
64. 
    
65.         return graph;
    
66.     }
    
67. 
    
68.     public static void main(String[] args) {
    
69.         GroupContactsII u = new GroupContactsII();
    
70.         List<Contact> input = new ArrayList<>();
    
71.         input.add(new Contact("Jack1", Arrays.asList("123@gmail.com", "ggg@gmail.com")));
    
72.         input.add(new Contact("Jack2", Arrays.asList("hh@gmail.com", "fff@gmail.com")));
    
73.         input.add(new Contact("Bob", Arrays.asList("123@gmail.com", "eeegg@gmail.com")));
    
74.         input.add(new Contact("Jack4", Arrays.asList("ccc@gmail.com", "aaa@gmail.com")));
    
75.         input.add(new Contact("Jack5", Arrays.asList("efg@gmail.com", "ccc@gmail.com")));
    
76.         System.out.println(u.unionUsername(input));
    
77.     }
    
78. }
    

复制代码