Google Onsite面经

分享一下1月底在kirkland 的onsite 挂经，整体感觉题难度属于medium以上。欢迎大家讨论！

1. LC 340; Follow up, what if the input is a stream? Can you make the space cost less?

2. Give a set of nodes in a hidden double linked list, return the number of connected components in the set.

        Follow up, what if we change the double linked list into single li

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

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

).


        Example:
                                                                current        high         low
                        update(1, 5)                5                           5                        5
                        update(2, 8)                8                           8                        5
                        update(1, 10)                8                           10                        8
                        delete(2)                        10                           10                        10

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

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. }

复制代码

组合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. }
    

复制代码

第四题代码 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. }
    

复制代码

感谢LZ分享，求问第五题设计的思路，要用到heap吗

第一题 follow up 因该药的是hashMap<Character, lastHappenIndex> 这样的space reduction 事吗?

第五题 感觉用hashHeap 因该可行? current 指的是timestamp 最新的price 这样吗?

第四题两两check if a 包含b 建立edge a-> b 形成一个DAG group 然后用BFS 从indeg = 0 的点 看几个connected component?

第2题，单链，只要有一个removed的set，就可以不用反转单链了吧？

nestwood 发表于 2017-2-20 05:39
第2题，单链，只要有一个removed的set，就可以不用反转单链了吧？

胡说了，比这要复杂

say543 发表于 2017-2-19 15:12
第四题两两check if a 包含b 建立edge a-> b 形成一个DAG group 然后用BFS 从indeg = 0 的点 看几个connec ...

不需要这么复杂吧，两两比较后把是子集的那个去掉不就结了？比如Bob 的邮件列表是Alice 的子集，那么把Bob 去掉就行了啊。

感谢楼主分享。请问楼主第4题有什么好方法么？我只能想到O(n^2)的暴力解法。

Zhenying 发表于 2017-2-20 10:02
感谢楼主分享。请问楼主第4题有什么好方法么？我只能想到O(n^2)的暴力解法。

O(n^2)的暴力解法？我觉得如果是纯暴力的话应该是O(kn^2), k 是每个mail list的平均长度。或者你有O(1)的方法来实现bool isSubset(list<int> a, list<int> b)这个功能？