Uber学校一面

先问了hashtable的underlining data structur是什么，然后又问了collision该怎么办。我说了chaining和另外那个找下一个empty key的，比较了一下优缺点。

然后出了题是一个世界纪录保持者的system。给了（世界纪录的名字，保持到的年份，保持者名字）存到一个自己

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

in heap里找人名的code，感觉写的也蛮晕的....就结束了

一个小时前刚面完，心情很不好，感觉身体被掏空。以后打算只用Lyft了。大家好运。

感觉就是把世界纪录跟年份放在一个tuple里作为key，然后找value
找到适合的interval是什么意思呢...不是只要return某一年的保持者吗
还是说是input是分开的，每段包含几个年份？

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

pq就是heap啊

补充内容 (2016-10-25 08:53):
你应该用balaced- BST

感觉应该是把 <世界纪录的名字，保持到的年份>包装成一个class obejct 作为key放进hashmap里，然后找离 query的保持到的年份 最接近的key其所对应的value就行了

huai10 发表于 2016-10-25 08:52
pq就是heap啊

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

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

wtcupup 发表于 2016-10-25 09:00
感觉应该是把 包装成一个class obejct 作为key放进hashmap里，然后找离 query的保持到的年份 最接近的key其 ...

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

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

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的数量吧？

为什么不直接binary search？

按理说现在不面这种system design的题了啊..