传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 1994|回复: 4
收起左侧

Uber full-time 电面

[复制链接] |试试Instant~ |关注本帖
andr_ 发表于 2015-7-23 13:18:15 | 显示全部楼层 |阅读模式

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

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

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

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

评分

1

查看全部评分

hulahu 发表于 2015-7-23 14:09:40 | 显示全部楼层
那个 median of two sorted arrays 不好写啊。
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-7-23 14:10:12 | 显示全部楼层
blessed and Good luck
回复 支持 反对

使用道具 举报

xiaotdl 发表于 2015-7-23 16:09:54 | 显示全部楼层
这种问题要是直接写了logn的二分、分治解法,是不是就没有follow up的问题了。log array也都是排好序的。
回复 支持 反对

使用道具 举报

Atomic123 发表于 2015-8-1 12:22:18 | 显示全部楼层
nlogn?两个array都已经sort好了的只用O(n)吧。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-25 16:16

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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