一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 3761|回复: 23
收起左侧

Uber 面经 (2015年8月)

[复制链接] |试试Instant~ |关注本帖
clockwise9 发表于 2015-8-20 22:11:19 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@Uber - 内推 - 技术电面 |Failfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
有同学在Uber实习,请其Mentor帮忙内推,拿到面试。两轮电面之后被拒。发个面经攒攒人品。安排时间非常效率,确实是正在快速扩张的团队。周一联络然后第一轮安排在同一周的周四,然后周五联系第二轮,安排在下一周的周一,然后第二轮后两天发拒信。
面试在codepad上进行,所以可以现场执行,要自己写一些测例,面试官还会补充一些觉得可能有问题的测例。不像Google在google doc上写代码,没有语法高亮也不能运行。
. 1point 3acres 璁哄潧
第一轮
给定一段英文消息,以及一个固定的长度,要求将消息分割成若干条,每条的最后加上页码如 (2/3),然后每条总长度不超过给定的固定长度。典型的应用场景就是短信发送长消息。
经过询问之后得到更多详细要求及假设:(1)消息数量尽可能少,不必凑整句,可以在任意空格处分页;(2)这个固定长度可能非法,比如某个词很长导致一条消息放不下,要判断并抛出异常;(3)假设空格分割,不会出现连着两个空格的情况。

这题比较tricky,没想到什么1 pass的方法,用了2 pass,第一遍判断总页数,第二遍生成预期的结果。写得一塌糊涂。
. visit 1point3acres.com for more.
第二轮
. visit 1point3acres.com for more.形式化来说,给N个未排序的数组,找出全局中位数。
应用场景是,有N个hosts,每隔一段时间就会报告一些参数,比如qps和平均延迟等,现有某个用于monitor的机器收集信息,并且返回特定时间段内同一参数所有数据的的中位数。
先给brute force,对所有数据排序然后找中位数。
之后改进版YY了一个基于bucket的方法,算是在精确度和时空复杂度之间的trade off,不过面试官不是很满意……




评分

1

查看全部评分

flyaway25 发表于 2015-8-20 22:16:11 | 显示全部楼层
求问lz你面的是哪个team?
回复 支持 反对

使用道具 举报

 楼主| clockwise9 发表于 2015-8-20 22:18:11 | 显示全部楼层
flyaway25 发表于 2015-8-20 22:16
求问lz你面的是哪个team?
. 鍥磋鎴戜滑@1point 3 acres
听说new grad是先general地面试然后再match team。
回复 支持 反对

使用道具 举报

flyaway25 发表于 2015-8-20 22:19:33 | 显示全部楼层
clockwise9 发表于 2015-8-20 22:18
听说new grad是先general地面试然后再match team。

当时填那个link里面不是有几个team么,我问hr,hr说尽量根据那个interest来安排你面试的人
回复 支持 反对

使用道具 举报

 楼主| clockwise9 发表于 2015-8-20 22:57:43 | 显示全部楼层
flyaway25 发表于 2015-8-20 22:19
当时填那个link里面不是有几个team么,我问hr,hr说尽量根据那个interest来安排你面试的人
. 1point 3acres 璁哄潧
哦想起来了,我填的应该是Backend和RealTimeSystem
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-8-20 23:42:22 | 显示全部楼层
楼主,2/3这三个字符算吗?

补充内容 (2015-8-21 07:36):
还有,楼主求个靠谱内推。。。。谢谢!
回复 支持 反对

使用道具 举报

dobestdobest 发表于 2015-8-21 03:04:26 | 显示全部楼层
First One.
  1. import java.util.ArrayList;
  2. import java.util.List;

  3. class Solution {
  4.     public static void main(String[] args) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  5.         String words = "This is good meal. I love it. I want to have it everyday.";
  6.         Answer ans = new Answer();
  7.         if (ans.process(words, 10) == -1) {
  8.             System.out.println("Error");
  9.         } else {
  10.             ans.print();
  11.         }
  12.     }
  13. }

  14. class Answer {
  15.     List<String> lists;
  16.     int limit;
  17.     int remaining;
  18.     StringBuilder builder;

  19.     public void print() { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  20.         int size = lists.size(); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  21.         int cnt = 1;
  22.         for (String line : lists) {
  23.             System.out.println(line + " (" + cnt + "/" + size + ")");. 1point 3acres 璁哄潧
  24.             cnt++;
  25.         }.1point3acres缃
  26.     }
  27. -google 1point3acres
  28.     public int process(String words, int limit) {. visit 1point3acres.com for more.
  29.         this.lists = new ArrayList<String>();
  30.         this.limit = limit;
  31.         this.remaining = limit;
  32.         this.builder = new StringBuilder();
  33. . 鍥磋鎴戜滑@1point 3 acres
  34.         int fast = 0;
  35.         int slow = 0;
  36.         // or words.split(" +");
  37.         while (fast < words.length()) {
  38.             while (fast < words.length() && Character.isSpaceChar(words.charAt(fast))) {
  39.                 fast++;
  40.                 slow++;
  41.             }
  42.             while (fast < words.length() && !Character.isSpaceChar(words.charAt(fast))) {
  43.                 fast++;
  44.             }
  45.             if (insert(words.substring(slow, fast)) == -1) return -1;. more info on 1point3acres.com
  46.             slow = fast;
  47.         }

  48.         if (builder.length() > 0) {
  49.             lists.add(builder.toString());
  50.         }

  51.         return 0;
  52.     }. 1point 3acres 璁哄潧

  53.     public int insert(String word) {
  54.         if (builder.length() == 0) {.1point3acres缃
  55.             if (word.length() > limit) {
  56.                 return -1;
  57.             } else {
  58.                 builder.append(word);. Waral 鍗氬鏈夋洿澶氭枃绔,
  59.                 remaining -= word.length();
  60.             }
  61.         } else if (1 + word.length() <= remaining) {
  62.             builder.append(" ").append(word);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  63.             remaining -= 1+ word.length();. visit 1point3acres.com for more.
  64.         } else {
  65.             lists.add(builder.toString());
  66.             builder = new StringBuilder();. Waral 鍗氬鏈夋洿澶氭枃绔,
  67.             remaining = limit;
  68.             return insert(word);. 1point 3acres 璁哄潧
  69.         }
  70.         return 0;
  71.     }. From 1point 3acres bbs

  72. . 1point3acres.com/bbs
  73. }
复制代码
回复 支持 反对

使用道具 举报

dobestdobest 发表于 2015-8-21 03:57:48 | 显示全部楼层
第二题,感觉就是把每个list都sort一下,然后就是merge N sorted list问题,用一个counter记录找到median就可以了。. 1point3acres.com/bbs
那个Log(N)的median of two sorted array太复杂了,而且你这个又是N个list,有限时间内,应该很难Log(N)写出来。
  1. import java.util.*;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

  2. class Solution {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  3.     public static void main(String[] args) {. more info on 1point3acres.com
  4.         List<List<Integer>> lists = new ArrayList<List<Integer>>();
  5.         lists.add(Arrays.asList(9, 6, 3));
  6.         lists.add(Arrays.asList(8, 5, 2));. more info on 1point3acres.com
  7.         lists.add(Arrays.asList(7, 4, 1));. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

  8.         Answer ans = new Answer();
  9.         int ret = ans.process(lists);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  10.         System.out.println(ret);
  11.     }
  12. }
  13. . From 1point 3acres bbs
  14. class Answer {
  15.     List<List<Integer>> lists;
  16.     int count;
  17.     PriorityQueue<Item> heap;

  18.     public int process(List<List<Integer>> lists) {
  19.         this.lists = lists;
  20.         this.count = 0;
  21.         heap = new PriorityQueue<Item>(100, new Comparator<Item>() {
  22.             @Override
  23.             public int compare(Item o1, Item o2) {. visit 1point3acres.com for more.
  24.                 return ((Integer) o1.val).compareTo(o2.val);
  25.             }
  26.         });

  27.         for (int i = 0; i < lists.size(); i++) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  28.             List<Integer> list = lists.get(i);
  29.             count += list.size();
  30.             Collections.sort(list);
  31.             if (!list.isEmpty()) {. more info on 1point3acres.com
  32.                 heap.add(new Item(list.get(0), i, 0));
  33.             }
  34.         }

  35. . more info on 1point3acres.com
  36.         int idx = 0;
  37.         while (!heap.isEmpty()) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  38.             Item item = heap.poll();
  39.             if (idx == count / 2) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  40.                 return item.val;. visit 1point3acres.com for more.
  41.             } else {
  42.                 idx++;
  43.             }.1point3acres缃
  44.             if (item.col < lists.get(item.row).size() - 1) {
  45.                 heap.add(new Item(lists.get(item.row).get(item.col + 1), item.row, item.col + 1));
  46.             }. 1point 3acres 璁哄潧
  47.         }

  48.         return 0;
  49.     }

  50. }
  51. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  52. class Item {
  53.     int val;
  54.     int row;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  55.     int col;

  56.     public Item(int val, int row, int col) {
  57.         this.val = val;
  58.         this.row = row;
  59.         this.col = col;
  60.     }
  61. }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
复制代码
回复 支持 反对

使用道具 举报

一日一ad 发表于 2015-8-21 05:34:46 | 显示全部楼层
请问lz已经毕业了嘛?
回复 支持 反对

使用道具 举报

 楼主| clockwise9 发表于 2015-8-21 09:26:45 | 显示全部楼层
jiebour 发表于 2015-8-20 23:42
楼主,2/3这三个字符算吗?

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

当然是算在里面的,所以才tricky
回复 支持 反对

使用道具 举报

 楼主| clockwise9 发表于 2015-8-21 09:37:54 | 显示全部楼层
dobestdobest 发表于 2015-8-21 03:04. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
First One.

这位大侠好认真……不过在你给出的解法里,好像是没有把(2/3)页码算到总长度里的,比如第61行判断word.length() > limit,这个是不够的,当页数小于10页的时候,要考虑(2/3)的长度为5,如果达到10页或者更多,就要考虑是第几页了,比如(2/10)长度6,(10/10)长度7。以及第67行判断1 + word.length() <= remaining也是类似。
. more info on 1point3acres.com
虽然个人感觉一般不会用到10页这么多。
回复 支持 反对

使用道具 举报

 楼主| clockwise9 发表于 2015-8-21 09:49:37 | 显示全部楼层
dobestdobest 发表于 2015-8-21 03:57
第二题,感觉就是把每个list都sort一下,然后就是merge N sorted list问题,用一个counter记录找到median就 ...

嗯用堆这个方法靠谱!我其实会那个logN找两个有序数组的中位数,但是死活没想出来如何扩展到N个数组……
回复 支持 反对

使用道具 举报

tonyjiang 发表于 2015-8-21 09:49:46 | 显示全部楼层
coderpad 没有highlight?
回复 支持 反对

使用道具 举报

 楼主| clockwise9 发表于 2015-8-21 09:50:10 | 显示全部楼层
一日一ad 发表于 2015-8-21 05:34
请问lz已经毕业了嘛?

还没,年底毕业,所以在找full time嘛
回复 支持 反对

使用道具 举报

dobestdobest 发表于 2015-8-21 09:55:48 | 显示全部楼层
clockwise9 发表于 2015-8-21 09:37
这位大侠好认真……不过在你给出的解法里,好像是没有把(2/3)页码算到总长度里的,比如第61行判断word.le ...
. visit 1point3acres.com for more.
我没有考虑 (2/3)页码 的位置。
如果真的需要动态考虑页码所占空间,那这道题复杂度一下就高了许多,可能就变成了动态规划题。
如果可以近似估计的话,预留一个固定的大小给页码,就简单了很多。
我觉得面试的45分钟时间内更有可能是后面的这种情况。
你觉得呢?
回复 支持 反对

使用道具 举报

 楼主| clockwise9 发表于 2015-8-21 23:59:56 | 显示全部楼层
dobestdobest 发表于 2015-8-21 09:55
我没有考虑 (2/3)页码 的位置。.鐣欏璁哄潧-涓浜-涓夊垎鍦
如果真的需要动态考虑页码所占空间,那这道题复杂度一下就高了许多,可 ...

首先肯定要考虑页码所占据的长度,不然就太简单了而且不符合实际情况。我当时就是给出的近似解,只对10页以下的有效,因为页码引起的附加长度是固定的,然而面试官还是不太满意……也可能是我表达有问题吧。
回复 支持 反对

使用道具 举报

 楼主| clockwise9 发表于 2015-8-22 00:02:29 | 显示全部楼层
tonyjiang 发表于 2015-8-21 09:49.鐣欏璁哄潧-涓浜-涓夊垎鍦
coderpad 没有highlight?
. From 1point 3acres bbs
当然是有的,都可以编译运行的,当然也会有syntax highlight
回复 支持 反对

使用道具 举报

nvidia_shen 发表于 2015-8-22 03:00:31 | 显示全部楼层
谢谢分享。对于楼主第一道题,如果页码是变长度的,可不可以这样处理:
1. “粗略”判断大概需要多少页(<10, <100, <1000?设为estimated_num_pages),这样首先固定<curr_page>/<total_pages>中的<total_pages>的字符串为estimated_num_pages,也就临时固定了这个total_pages的字符串长度。
2.把输入字符串tokenize,然后进行遍历同时生成短消息(在生成页面n时,此时该页的page_num部分字符串的长度是已知的,即len(n/<total_page>) ,用size_msg-len(n/<total_pages>即为token的可用msg_size)。
3.如果第二步中生成的短消息数量超过estimated_num_pages,则我们把estimated_num_pages增加一位,从个位涨到十位,十位涨到百位,然后重复第二部。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
因为每涨一位estimated_num_pages所增加的页码空间非常大(*10),我们可以期待第二次遍历成功的概率非常高。

第二道题,其实和find median in unsorted list是一样的(或者更普遍的,find kth largest element),用quickselect算法解决。O(logn)的算法应该是不存在的,因为是unsorted,光读取所有的n数据就要O(n)。

补充内容 (2015-8-22 03:03):
补充一下第一道题的思路,在预留len(<total_pages>)固定长度的空字符串之后,需要在第二部成功结束后返回来填入实际的总页数。
回复 支持 反对

使用道具 举报

ChrisGates23 发表于 2015-8-22 04:00:05 | 显示全部楼层
clockwise9 发表于 2015-8-22 00:02
当然是有的,都可以编译运行的,当然也会有syntax highlight

貌似写的时候没有,运行后有
回复 支持 反对

使用道具 举报

iorisli 发表于 2015-8-22 04:46:29 | 显示全部楼层
第一题感觉就是考bugfree的... 文本第一遍分页完了,要再遍历几遍, 看看有没有因为页数太多, 导致前面需要更新的. 一直遍历检查是否要更新, 直到不需要更新为止. 感觉电面不太可能bugfree... 自己写了一下: https://gist.github.com/si-yao/95bdffec986a65da4aa7
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 10:33

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表