Uber full-time 电面

原帖地址:一亩三分地

Uber HR最近貌似特别忙,面试都说不能reschedule…
面试官是个烙印,在Uber一年多一点,也算资格比较老的了。
一开始先聊了聊我的项目,有服务器通讯的问题。然后他出题目说现在有两个服务器,每个服务器都输出一个按时间排好序的log list,然后要按时间取中位数。
其实就是median of two sorted array,要在codepad现场写现场跑现场测试。
我一开始就说merge了然后直接取,又说我觉得存在更优解但是暂时没想出来,打算先写code吧。
实际上我写的code是直接l1 + l2然后sort,也是用这个测试的,特别快,才花了五分钟。
测试完之后想起来好像可以用两个堆的方法,其实这个方法是用来解median of stream的,但是一时也晕晕的没想起来那个二分查找的方法,本来那题在leetcode刷过的…
就开始写伪代码,一个大顶堆一个小顶堆,然后怎么维持两个堆的大小,怎么随时输出这个median
最后时间来不及了代码写到一半,面试官就问你这个复杂度和你之前写好的那个复杂度分别是多少,我说实际都是nlogn,
然后他又问那第二个有什么好处,我就往他给我的服务器的背景上扯说这样比较scalable因为每一次增加一条记录取得median的复杂度都是logn,而第一种每次都要重新排序要nlogn
面完之后一个小时就收到cong,大概下周去onsite