Uber 面经 (2015年8月）

有同学在Uber实习，请其Mentor帮忙内推，拿到面试。两轮电面之后被拒。发个面经攒攒人品。安排时间非常效率，确实是正在快速扩张的团队。周一联络然后第一轮安排在同一周的周四，然后周五联系第二轮，安排在下一周的周一，然后第二轮后两天发拒信。
面试在codepad上进行，所以可以现场执行，要

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

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

的中位数。
先给brute force，对所有数据排序然后找中位数。
之后改进版YY了一个基于bucket的方法，算是在精确度和时空复杂度之间的trade off，不过面试官不是很满意……

First One.

1. import java.util.ArrayList;
   
2. import java.util.List;
   
3. 
   
4. class Solution {
   
5.     public static void main(String[] args) {
   
6.         String words = "This is good meal. I love it. I want to have it everyday.";
   
7.         Answer ans = new Answer();
   
8.         if (ans.process(words, 10) == -1) {
   
9.             System.out.println("Error");
   
10.         } else {
    
11.             ans.print();
    
12.         }
    
13.     }
    
14. }
    
15. 
    
16. class Answer {
    
17.     List<String> lists;
    
18.     int limit;
    
19.     int remaining;
    
20.     StringBuilder builder;
    
21. 
    
22.     public void print() {
    
23.         int size = lists.size();
    
24.         int cnt = 1;
    
25.         for (String line : lists) {
    
26.             System.out.println(line + " (" + cnt + "/" + size + ")");
    
27.             cnt++;
    
28.         }
    
29.     }
    
30. 
    
31.     public int process(String words, int limit) {
    
32.         this.lists = new ArrayList<String>();
    
33.         this.limit = limit;
    
34.         this.remaining = limit;
    
35.         this.builder = new StringBuilder();
    
36. 
    
37.         int fast = 0;
    
38.         int slow = 0;
    
39.         // or words.split(" +");
    
40.         while (fast < words.length()) {
    
41.             while (fast < words.length() && Character.isSpaceChar(words.charAt(fast))) {
    
42.                 fast++;
    
43.                 slow++;
    
44.             }
    
45.             while (fast < words.length() && !Character.isSpaceChar(words.charAt(fast))) {
    
46.                 fast++;
    
47.             }
    
48.             if (insert(words.substring(slow, fast)) == -1) return -1;
    
49.             slow = fast;
    
50.         }
    
51. 
    
52.         if (builder.length() > 0) {
    
53.             lists.add(builder.toString());
    
54.         }
    
55. 
    
56.         return 0;
    
57.     }
    
58. 
    
59.     public int insert(String word) {
    
60.         if (builder.length() == 0) {
    
61.             if (word.length() > limit) {
    
62.                 return -1;
    
63.             } else {
    
64.                 builder.append(word);
    
65.                 remaining -= word.length();
    
66.             }
    
67.         } else if (1 + word.length() <= remaining) {
    
68.             builder.append(" ").append(word);
    
69.             remaining -= 1+ word.length();
    
70.         } else {
    
71.             lists.add(builder.toString());
    
72.             builder = new StringBuilder();
    
73.             remaining = limit;
    
74.             return insert(word);
    
75.         }
    
76.         return 0;
    
77.     }
    
78. 
    
79. 
    
80. }
    

复制代码

第二题，感觉就是把每个list都sort一下，然后就是merge N sorted list问题，用一个counter记录找到median就可以了。
那个Log(N)的median of two sorted array太复杂了，而且你这个又是N个list，有限时间内，应该很难Log(N)写出来。

1. import java.util.*;
   
2. 
   
3. class Solution {
   
4.     public static void main(String[] args) {
   
5.         List<List<Integer>> lists = new ArrayList<List<Integer>>();
   
6.         lists.add(Arrays.asList(9, 6, 3));
   
7.         lists.add(Arrays.asList(8, 5, 2));
   
8.         lists.add(Arrays.asList(7, 4, 1));
   
9. 
   
10.         Answer ans = new Answer();
    
11.         int ret = ans.process(lists);
    
12.         System.out.println(ret);
    
13.     }
    
14. }
    
15. 
    
16. class Answer {
    
17.     List<List<Integer>> lists;
    
18.     int count;
    
19.     PriorityQueue<Item> heap;
    
20. 
    
21.     public int process(List<List<Integer>> lists) {
    
22.         this.lists = lists;
    
23.         this.count = 0;
    
24.         heap = new PriorityQueue<Item>(100, new Comparator<Item>() {
    
25.             @Override
    
26.             public int compare(Item o1, Item o2) {
    
27.                 return ((Integer) o1.val).compareTo(o2.val);
    
28.             }
    
29.         });
    
30. 
    
31.         for (int i = 0; i < lists.size(); i++) {
    
32.             List<Integer> list = lists.get(i);
    
33.             count += list.size();
    
34.             Collections.sort(list);
    
35.             if (!list.isEmpty()) {
    
36.                 heap.add(new Item(list.get(0), i, 0));
    
37.             }
    
38.         }
    
39. 
    
40.         int idx = 0;
    
41.         while (!heap.isEmpty()) {
    
42.             Item item = heap.poll();
    
43.             if (idx == count / 2) {
    
44.                 return item.val;
    
45.             } else {
    
46.                 idx++;
    
47.             }
    
48.             if (item.col < lists.get(item.row).size() - 1) {
    
49.                 heap.add(new Item(lists.get(item.row).get(item.col + 1), item.row, item.col + 1));
    
50.             }
    
51.         }
    
52. 
    
53.         return 0;
    
54.     }
    
55. 
    
56. }
    
57. 
    
58. class Item {
    
59.     int val;
    
60.     int row;
    
61.     int col;
    
62. 
    
63.     public Item(int val, int row, int col) {
    
64.         this.val = val;
    
65.         this.row = row;
    
66.         this.col = col;
    
67.     }
    
68. }
    

复制代码

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

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

求问lz你面的是哪个team？

flyaway25 发表于 2015-8-20 22:16
求问lz你面的是哪个team？

听说new grad是先general地面试然后再match team。

clockwise9 发表于 2015-8-20 22:18
听说new grad是先general地面试然后再match team。

当时填那个link里面不是有几个team么，我问hr，hr说尽量根据那个interest来安排你面试的人

flyaway25 发表于 2015-8-20 22:19
当时填那个link里面不是有几个team么，我问hr，hr说尽量根据那个interest来安排你面试的人

哦想起来了，我填的应该是Backend和RealTimeSystem

楼主，2/3这三个字符算吗？

补充内容 (2015-8-21 07:36):
还有，楼主求个靠谱内推。。。。谢谢！

请问lz已经毕业了嘛？

jiebour 发表于 2015-8-20 23:42
楼主，2/3这三个字符算吗？

补充内容 (2015-8-21 07:36):

当然是算在里面的，所以才tricky