Uber电面面经

周一面的，面完15分钟HR就说有update。Uber真的是move so fast...
一共两题，都不难：
1、

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

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

词能不能被元素周期表拼出来，提供元素名字的hashset

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

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

iwknow 发表于 2016-9-14 14:23
我怎么感觉第一题可以这样做：
假设 现在stream走到第n个数，avg是（n-1）个数的mean
那么第n个数（假设 ...

第n个的 median 怎么类似。。。

第一题求follow up2 用tree map代替 优先队列 然后用一个额外数组记录按插入顺序 记录在map的地址 用来删除维护 最近k个的map吗

我的做法是直接存vector<ListNode*>，链表顺序=插入顺序，vector保持sorted

UpDownDOTA 发表于 2016-9-14 13:30
我的做法是直接存vector，链表顺序=插入顺序，vector保持sorted

你这是o(n)吧

UpDownDOTA 发表于 2016-9-14 13:30
我的做法是直接存vector，链表顺序=插入顺序，vector保持sorted

哦哦 不是o(n) 是log(n) 和 o(1)

zyoppy008 发表于 2016-9-14 13:48
哦哦 不是o(n) 是log(n) 和 o(1)

是的，我不是很熟Java，不过我记得Java的话应该有个结合了hashmap和queue的type可以直接拿来用

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

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

我怎么感觉第一题可以这样做：
假设 现在stream走到第n个数，avg是（n-1）个数的mean
那么第n个数（假设数值是x）的mean = (avg*(n-1) + x)/(n) = avg - avg/n + x/n
这样维护一个计数变量n 和一个平均值 avg 就好了。
meadian可以用类似的方法

find median from data stream and window size K median 应该都是用两个heap做， 每当node超过window size时，pop heap中第一个插入的