一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

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

Uber学校一面

[复制链接] |试试Instant~ |关注本帖
yiranw 发表于 2016-10-25 08:45:52 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 本科 实习@Uber - 校园招聘会 - 校园招聘会 |Otherfresh grad应届毕业生

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

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

x
先问了hashtable的underlining data structur是什么,然后又问了collision该怎么办。我说了chaining和另外那个找下一个empty key的,比较了一下优缺点。
.鐣欏璁哄潧-涓浜-涓夊垎鍦
然后出了题是一个世界纪录保持者的system。给了(世界纪录的名字,保持到的年份,保持者名字)存到一个自己的设计的data structure里,然后在给(世界纪录的名字,年份)的时候,可以return保持者名字。值得注意的是这个年份是任意年份,所以要找到适合的interval。

我先说了用世界纪录的名字当key,把剩下的两个信息存在一个以年份排序的priority queue里。分析了一下发现lookup可以再optimize一下(priority queue的话只能linear search了)。于是我就说把priority queue换成min heap。我好久没碰min heap,有点不大熟悉,好像complexity分析的时候说的不大对。然后又让写了一下在min heap里找人名的code,感觉写的也蛮晕的....就结束了

一个小时前刚面完,心情很不好,感觉身体被掏空。以后打算只用Lyft了。大家好运。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

评分

2

查看全部评分

asdfg0042 发表于 2016-10-25 11:19:38 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
感觉就是把世界纪录跟年份放在一个tuple里作为key,然后找value
找到适合的interval是什么意思呢...不是只要return某一年的保持者吗
还是说是input是分开的,每段包含几个年份?

补充内容 (2016-10-25 11:24):
nvm 懂了。。。那就在遍历records的时候顺带把保持到的年份存到一个array里,然后binary search找到比input年大的最接近的年份,再从dictionary里取回对应的value
回复 支持 1 反对 0

使用道具 举报

huai10 发表于 2016-10-25 08:52:02 | 显示全部楼层
关注一亩三分地微博:
Warald
pq就是heap啊

补充内容 (2016-10-25 08:53):
你应该用balaced- BST
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-10-25 09:00:25 | 显示全部楼层
感觉应该是把 <世界纪录的名字,保持到的年份>包装成一个class obejct 作为key放进hashmap里,然后找离 query的保持到的年份 最接近的key其所对应的value就行了
回复 支持 反对

使用道具 举报

 楼主| yiranw 发表于 2016-10-25 09:10:33 | 显示全部楼层
huai10 发表于 2016-10-25 08:52
pq就是heap啊

补充内容 (2016-10-25 08:53):

那pq的lookup是多少啊?我是因为他说pq只能linear search才想到自己implement heap. Balanced BST和heap有什么区别呢?
回复 支持 反对

使用道具 举报

 楼主| yiranw 发表于 2016-10-25 09:11:51 | 显示全部楼层
wtcupup 发表于 2016-10-25 09:00
感觉应该是把 包装成一个class obejct 作为key放进hashmap里,然后找离 query的保持到的年份 最接近的key其 ...

最接近不行吧...比如1900前是A保持,2000前是B保持,那如果query是1901的话还是应该return B?
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-10-25 09:33:51 | 显示全部楼层
yiranw 发表于 2016-10-25 09:11
最接近不行吧...比如1900前是A保持,2000前是B保持,那如果query是1901的话还是应该return B?

这个<name, year> class是以year sorted的(需要定义comparator),如果是1901,就找next one, which is 2000
回复 支持 反对

使用道具 举报

 楼主| yiranw 发表于 2016-10-25 09:50:14 | 显示全部楼层
wtcupup 发表于 2016-10-25 09:33
这个 class是以year sorted的(需要定义comparator),如果是1901,就找next one, which is 2000

这样的话和我本来用的用category做key, <year, name>的priority queue做value有有什么区别呢...因为search的时候都会是linear的O(k), k是每个category下面record的数量吧?
回复 支持 反对

使用道具 举报

vincccho 发表于 2016-10-25 11:01:29 | 显示全部楼层
为什么不直接binary search?
回复 支持 反对

使用道具 举报

johnwen 发表于 2016-11-6 03:03:36 | 显示全部楼层
按理说现在不面这种system design的题了啊..
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2017-5-1 04:15

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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