一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 749|回复: 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的,比较了一下优缺点。
. visit 1point3acres.com for more.
然后出了题是一个世界纪录保持者的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

查看全部评分

huai10 发表于 2016-10-25 08:52:02 | 显示全部楼层
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其 ...
. Waral 鍗氬鏈夋洿澶氭枃绔,
最接近不行吧...比如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?
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

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

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

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

custom counter

GMT+8, 2016-12-7 21:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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