请教Uber onsite follow up interview

温家小猫 发表于 2015-11-25 09:41
楼主加油啊，我周一面的，目前还没有消息。。。

祝你好运呀！可能这周有holiday会通知的慢一些？

follow up interview: tech interview, design rate limiter,C++ chrono库里的函数用的不熟，边查边写的，不知道面试官会不会介意T.T 求RP...

rebe90 发表于 2015-11-26 01:42
祝你好运呀！可能这周有holiday会通知的慢一些？

谢谢楼主，已收到offer,也祝楼主顺利拿到！

写了下第三题java版，感觉它们加系统设计真多啊

1. public class GroupContacts {
   
2. 
   
3.         static class Contact {
   
4.                 String name;
   
5.                 List<String> emails;
   
6.                 public Contact(String name, List<String> emails) {
   
7.                         this.name = name;
   
8.                         this.emails = emails;
   
9.                 }
   
10.         }
    
11. 
    
12.         static class UnionFind {
    
13.                 HashMap<Integer, Integer> father = new HashMap<Integer, Integer>();
    
14. 
    
15.                 UnionFind(int n) {
    
16.                         for (int i = 0; i < n; i++) {
    
17.                                 father.put(i, i);
    
18.                         }
    
19.                 }
    
20. 
    
21.                 int compressed_find(int x) {
    
22.                         int parent = father.get(x);
    
23.                         while (parent != father.get(parent)) {
    
24.                                 parent = father.get(parent);
    
25.                         }
    
26.                         int tmp = -1;
    
27.                         int fa = father.get(x);
    
28.                         while (fa != father.get(fa)) {
    
29.                                 tmp = father.get(fa);
    
30.                                 father.put(fa, parent);
    
31.                                 fa = tmp;
    
32.                         }
    
33. 
    
34.                         return parent;
    
35.                 }
    
36. 
    
37.                 int find(int id) {
    
38.                         while (id != father.get(id)) {
    
39.                                 id = father.get(id);
    
40.                         }
    
41. 
    
42.                         return id;
    
43.                 }
    
44. 
    
45.                 void union(int x, int y) {
    
46.                         int fa_x = compressed_find(x);
    
47.                         int fa_y = compressed_find(y);
    
48.                         father.put(fa_x, fa_y);
    
49.                 }
    
50.         }
    
51. 
    
52.         public static List<List<Contact>> groupContacts(Contact[] input) {
    
53.                 Map<String, List<Integer>> emailRecord = new HashMap<String, List<Integer>>();
    
54. 
    
55.                 int n = input.length;
    
56.                 for (int k = 0; k < input.length; k++) {
    
57.                         for (String email : input[k].emails) {
    
58.                                 if (emailRecord.containsKey(email)) {
    
59.                                         emailRecord.get(email).add(k);
    
60.                                 } else {
    
61.                                         List<Integer> list = new ArrayList<Integer>();
    
62.                                         list.add(k);
    
63.                                         emailRecord.put(email, list);
    
64.                                 }
    
65.                         }
    
66.                 }
    
67.                 UnionFind uf = new UnionFind(n);
    
68.                 for (List<Integer> p : emailRecord.values()) {
    
69.                         for (int i = 0; i < p.size() - 1; i++) {
    
70.                                 uf.union(p.get(i), p.get(i + 1));
    
71.                         }
    
72.                 }
    
73.                 Map<Integer, List<Integer>> groups = new HashMap<Integer, List<Integer>>();
    
74.                 for (int i = 0; i < n; i++) {
    
75.                         int parent = uf.find(i);
    
76.                         if (groups.containsKey(parent)) {
    
77.                                 groups.get(parent).add(i);
    
78.                         } else {
    
79.                                 List<Integer> list = new ArrayList<Integer>();
    
80.                                 list.add(i);
    
81.                                 groups.put(parent, list);
    
82.                         }
    
83.                 }
    
84. 
    
85.                 List<List<Contact>> ret = new ArrayList<List<Contact>>();
    
86.                 for (List<Integer> p : groups.values()) {
    
87.                         List<Contact> vs = new ArrayList<Contact>();
    
88.                         for (int c : p) {
    
89.                                 vs.add(input[c]);
    
90.                         }
    
91.                         ret.add(vs);
    
92.                 }
    
93.                 return ret;
    
94.         }
    
95.        
    
96.         public static void main(String[] args) {
    
97.                 Contact c1 = new Contact("John", Arrays.asList("john@gmail.com"));
    
98.                 Contact c2 = new Contact("Mary", Arrays.asList("mary@gmail.com"));
    
99.                 Contact c3 = new Contact("John", Arrays.asList("john@yahoo.com"));
    
100.                 Contact c4 = new Contact("John", Arrays.asList("john@gmail.com", "john@yahoo.com", "john@hotmail.com"));
     
101.                 Contact c5 = new Contact("Bob", Arrays.asList("bob@gmail.com"));
     
102.                 Contact[] input = {c1, c2, c3, c4, c5};
     
103.                 List<List<Contact>> res = groupContacts(input);
     
104.                 for (List<Contact> list : res) {
     
105.                         for (Contact i : list) {
     
106.                                 System.out.print(i.name + ":  ");
     
107.                                 for (String email : i.emails) {
     
108.                                         System.out.print(email + " ");
     
109.                                 }
     
110.                         }
     
111.                         System.out.println();
     
112.                 }
     
113.         }
     
114. }
     

复制代码

楼主可以具体说说subscription 和tilt maze是什么，楼主怎么做的吗？

并查集写的很牛！这是一个视频，分享给大家，讲得也很好。
https://www.youtube.com/watch?v=hqvV2ui29fQ

Tilt maze你怎么想的？用什么数据结构来表示maze? 应该还是DFS
https://www.mathsisfun.com/games/tilt-maze.html

第一题ｅｘｃｅｌ是设计题还是ｌｅｅｔｃｏｄｅ上的那两道之一？