近期论坛无法登录的解决方案


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 7353|回复: 23
收起左侧

Uber 面经 (2015年8月)

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
有同学在Uber实习,请其Mentor帮忙内推,拿到面试。两轮电面之后被拒。发个面经攒攒人品。安排时间非常效率,确实是正在快速扩张的团队。周一联络然后第一轮安排在同一周的周四,然后周五联系第二轮,安排在下一周的周一,然后第二轮后两天发拒信。
面试在codepad上进行,所以可以现场执行,要自己写一些测例,面试官还会补充一些觉得可能有问题的测例。不像Google在google doc上写代码,没有语法高亮也不能运行。. Waral 鍗氬鏈夋洿澶氭枃绔,

第一轮
给定一段英文消息,以及一个固定的长度,要求将消息分割成若干条,每条的最后加上页码如 (2/3),然后每条总长度不超过给定的固定长度。典型的应用场景就是短信发送长消息。
经过询问之后得到更多详细要求及假设:(1)消息数量尽可能少,不必凑整句,可以在任意空格处分页;(2)这个固定长度可能非法,比如某个词很长导致一条消息放不下,要判断并抛出异常;(3)假设空格分割,不会出现连着两个空格的情况。.鏈枃鍘熷垱鑷1point3acres璁哄潧

这题比较tricky,没想到什么1 pass的方法,用了2 pass,第一遍判断总页数,第二遍生成预期的结果。写得一塌糊涂。. 1point3acres.com/bbs

. 鍥磋鎴戜滑@1point 3 acres第二轮.鏈枃鍘熷垱鑷1point3acres璁哄潧
形式化来说,给N个未排序的数组,找出全局中位数。
应用场景是,有N个hosts,每隔一段时间就会报告一些参数,比如qps和平均延迟等,现有某个用于monitor的机器收集信息,并且返回特定时间段内同一参数所有数据的的中位数。
先给brute force,对所有数据排序然后找中位数。
之后改进版YY了一个基于bucket的方法,算是在精确度和时空复杂度之间的trade off,不过面试官不是很满意……

. 1point 3acres 璁哄潧


评分

1

查看全部评分

flyaway25 发表于 2015-8-20 22:16:11 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
求问lz你面的是哪个team?
回复 支持 反对

使用道具 举报

 楼主| clockwise9 发表于 2015-8-20 22:18:11 | 显示全部楼层
关注一亩三分地微博:
Warald
flyaway25 发表于 2015-8-20 22:16
求问lz你面的是哪个team?

听说new grad是先general地面试然后再match team。
回复 支持 反对

使用道具 举报

flyaway25 发表于 2015-8-20 22:19:33 | 显示全部楼层
clockwise9 发表于 2015-8-20 22:18. 鍥磋鎴戜滑@1point 3 acres
听说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来安排你面试的人

哦想起来了,我填的应该是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. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  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.";. more info on 1point3acres.com
  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. class Answer {
  16.     List<String> lists;
  17.     int limit;
  18.     int remaining;
  19.     StringBuilder builder;
  20. .1point3acres缃
  21.     public void print() {
  22.         int size = lists.size();. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  23.         int cnt = 1;
  24.         for (String line : lists) {
  25.             System.out.println(line + " (" + cnt + "/" + size + ")");
  26.             cnt++;
  27.         }
  28.     }

  29.     public int process(String words, int limit) {
  30.         this.lists = new ArrayList<String>();-google 1point3acres
  31.         this.limit = limit;
  32.         this.remaining = limit;. From 1point 3acres bbs
  33.         this.builder = new StringBuilder();

  34.         int fast = 0;
  35.         int slow = 0;. 1point 3acres 璁哄潧
  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;
  46.             slow = fast;
  47.         }. 鍥磋鎴戜滑@1point 3 acres

  48.         if (builder.length() > 0) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  49.             lists.add(builder.toString());
  50.         }. 1point3acres.com/bbs

  51.         return 0;
  52.     }

  53.     public int insert(String word) {
  54.         if (builder.length() == 0) {
  55.             if (word.length() > limit) {
  56.                 return -1;
  57.             } else {
  58.                 builder.append(word);
  59.                 remaining -= word.length();
  60.             }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  61.         } else if (1 + word.length() <= remaining) {
  62.             builder.append(" ").append(word);
  63.             remaining -= 1+ word.length();
  64.         } else {
  65.             lists.add(builder.toString());. 1point3acres.com/bbs
  66.             builder = new StringBuilder();
  67.             remaining = limit;
  68.             return insert(word);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  69.         }
  70.         return 0;
  71.     }
  72. -google 1point3acres

  73. }
复制代码
回复 支持 反对

使用道具 举报

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

  2. class Solution {
  3.     public static void main(String[] args) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  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));
  7.         lists.add(Arrays.asList(7, 4, 1));
  8. . 1point 3acres 璁哄潧
  9.         Answer ans = new Answer();
  10.         int ret = ans.process(lists);
  11.         System.out.println(ret);
  12.     }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  13. }. more info on 1point3acres.com

  14. class Answer {
  15.     List<List<Integer>> lists;
  16.     int count;. more info on 1point3acres.com
  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) {
  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();. From 1point 3acres bbs
  30.             Collections.sort(list);. 鍥磋鎴戜滑@1point 3 acres
  31.             if (!list.isEmpty()) {
  32.                 heap.add(new Item(list.get(0), i, 0));
  33.             }
  34.         }

  35.         int idx = 0;
  36.         while (!heap.isEmpty()) {. 1point3acres.com/bbs
  37.             Item item = heap.poll();
  38.             if (idx == count / 2) {
  39.                 return item.val;
  40.             } else {
  41.                 idx++;.1point3acres缃
  42.             }
  43.             if (item.col < lists.get(item.row).size() - 1) {
  44.                 heap.add(new Item(lists.get(item.row).get(item.col + 1), item.row, item.col + 1));
  45.             }
  46.         }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

  47.         return 0;
  48.     }

  49. }

  50. class Item {
  51.     int val;
  52.     int row;. 1point 3acres 璁哄潧
  53.     int col;

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

使用道具 举报

一日一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 | 显示全部楼层

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

虽然个人感觉一般不会用到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 ...
. from: 1point3acres.com/bbs
我没有考虑 (2/3)页码 的位置。
如果真的需要动态考虑页码所占空间,那这道题复杂度一下就高了许多,可能就变成了动态规划题。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
如果可以近似估计的话,预留一个固定的大小给页码,就简单了很多。
我觉得面试的45分钟时间内更有可能是后面的这种情况。
你觉得呢?
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

 楼主| clockwise9 发表于 2015-8-22 00:02:29 | 显示全部楼层
tonyjiang 发表于 2015-8-21 09:49
coderpad 没有highlight?

当然是有的,都可以编译运行的,当然也会有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增加一位,从个位涨到十位,十位涨到百位,然后重复第二部。.1point3acres缃

因为每涨一位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
. more info on 1point3acres.com
貌似写的时候没有,运行后有
回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-6-26 10:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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