當了一年的 Facebook Rotational Software Engineer 心得分享

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 8058|回复: 23
收起左侧

Uber 面经 (2015年8月)

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

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

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

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

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

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

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

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



.本文原创自1point3acres论坛

评分

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?

听说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来安排你面试的人
. Waral 博客有更多文章,
哦想起来了,我填的应该是Backend和RealTimeSystem
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-8-20 23:42:22 | 显示全部楼层
楼主,2/3这三个字符算吗?
. Waral 博客有更多文章,
补充内容 (2015-8-21 07:36):. more info on 1point3acres
还有,楼主求个靠谱内推。。。。谢谢!
回复 支持 反对

使用道具 举报

dobestdobest 发表于 2015-8-21 03:04:26 | 显示全部楼层
First One.
  1. import java.util.ArrayList;
  2. import java.util.List;.1point3acres网
  3. -google 1point3acres
  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.";. 1point 3acres 论坛
  7.         Answer ans = new Answer();
  8.         if (ans.process(words, 10) == -1) {
  9.             System.out.println("Error");
  10.         } else {
  11.             ans.print();
  12.         }
  13.     }. Waral 博客有更多文章,
  14. }

  15. class Answer {
  16.     List<String> lists;
  17.     int limit;
  18.     int remaining;
  19.     StringBuilder builder;.1point3acres网

  20.     public void print() {
  21.         int size = lists.size();
  22.         int cnt = 1;
  23.         for (String line : lists) {
  24.             System.out.println(line + " (" + cnt + "/" + size + ")");
  25.             cnt++;
  26.         }
  27.     }
  28. . 一亩-三分-地,独家发布
  29.     public int process(String words, int limit) {
  30.         this.lists = new ArrayList<String>();
  31.         this.limit = limit;
  32.         this.remaining = limit;
  33.         this.builder = new StringBuilder();
  34. . Waral 博客有更多文章,
  35.         int fast = 0;
  36.         int slow = 0;-google 1point3acres
  37.         // or words.split(" +");
  38.         while (fast < words.length()) {. 留学申请论坛-一亩三分地
  39.             while (fast < words.length() && Character.isSpaceChar(words.charAt(fast))) {
  40.                 fast++;
  41.                 slow++;
  42.             }
  43.             while (fast < words.length() && !Character.isSpaceChar(words.charAt(fast))) {
  44.                 fast++;
  45.             }
  46.             if (insert(words.substring(slow, fast)) == -1) return -1;
  47.             slow = fast;
  48.         }
  49. . from: 1point3acres
  50.         if (builder.length() > 0) {
  51.             lists.add(builder.toString());
  52.         }

  53.         return 0;
  54.     }
  55. . 1point3acres
  56.     public int insert(String word) {
  57.         if (builder.length() == 0) {
  58.             if (word.length() > limit) {
  59.                 return -1;. 一亩-三分-地,独家发布
  60.             } else {
  61.                 builder.append(word);
  62.                 remaining -= word.length();
  63.             }
    . visit 1point3acres for more.
  64.         } else if (1 + word.length() <= remaining) {
  65.             builder.append(" ").append(word);
  66.             remaining -= 1+ word.length();. 留学申请论坛-一亩三分地
  67.         } else {
  68.             lists.add(builder.toString());. From 1point 3acres bbs
  69.             builder = new StringBuilder();
  70.             remaining = limit;
  71.             return insert(word);
  72.         }
  73.         return 0;.1point3acres网
  74.     }


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

使用道具 举报

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>>();. 1point 3acres 论坛
  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. . 牛人云集,一亩三分地
  9.         Answer ans = new Answer();
  10.         int ret = ans.process(lists);
  11.         System.out.println(ret);.本文原创自1point3acres论坛
  12.     }
  13. }

  14. class Answer {. more info on 1point3acres
  15.     List<List<Integer>> lists;
  16.     int count;
  17.     PriorityQueue<Item> heap;. Waral 博客有更多文章,

  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);.1point3acres网
  29.             count += list.size();. 1point3acres
  30.             Collections.sort(list);
  31.             if (!list.isEmpty()) {. Waral 博客有更多文章,
  32.                 heap.add(new Item(list.get(0), i, 0));.本文原创自1point3acres论坛
  33.             }
  34.         }

  35.         int idx = 0;
  36.         while (!heap.isEmpty()) {
  37.             Item item = heap.poll();. visit 1point3acres for more.
  38.             if (idx == count / 2) {
  39.                 return item.val;
  40.             } else {. 围观我们@1point 3 acres
  41.                 idx++;
  42.             }
  43.             if (item.col < lists.get(item.row).size() - 1) {. From 1point 3acres bbs
  44.                 heap.add(new Item(lists.get(item.row).get(item.col + 1), item.row, item.col + 1));
  45.             }. 留学申请论坛-一亩三分地
  46.         }

  47.         return 0;.留学论坛-一亩-三分地
  48.     }.1point3acres网

  49. }. 1point3acres

  50. class Item {
  51.     int val;
  52.     int row;
  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. }
复制代码
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

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

使用道具 举报

 楼主| clockwise9 发表于 2015-8-21 09:26:45 | 显示全部楼层
jiebour 发表于 2015-8-20 23:42 来源一亩.三分地论坛.
楼主,2/3这三个字符算吗?.本文原创自1point3acres论坛

补充内容 (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
. more info on 1point3acres第二题,感觉就是把每个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 ...

我没有考虑 (2/3)页码 的位置。
如果真的需要动态考虑页码所占空间,那这道题复杂度一下就高了许多,可能就变成了动态规划题。
如果可以近似估计的话,预留一个固定的大小给页码,就简单了很多。.留学论坛-一亩-三分地
我觉得面试的45分钟时间内更有可能是后面的这种情况。. 1point3acres
你觉得呢?
回复 支持 反对

使用道具 举报

 楼主| clockwise9 发表于 2015-8-21 23:59:56 | 显示全部楼层
dobestdobest 发表于 2015-8-21 09:55
我没有考虑 (2/3)页码 的位置。
如果真的需要动态考虑页码所占空间,那这道题复杂度一下就高了许多,可 ...
. 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 | 显示全部楼层
谢谢分享。对于楼主第一道题,如果页码是变长度的,可不可以这样处理:. 1point3acres
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
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-5-20 20:38

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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