Uber 面经 (2015年8月)

原帖地址:一亩三分地

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

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

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

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