一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 1590|回复: 28
收起左侧

Uber电面面经

[复制链接] |试试Instant~ |关注本帖
UpDownDOTA 发表于 2016-9-14 12:29:16 | 显示全部楼层 |阅读模式

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

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

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

x
周一面的,面完15分钟HR就说有update。Uber真的是move so fast...
一共两题,都不难:
1、有一个数据流的int要处理,要实现求当前mean和median的功能。
follow up1: 有没有别的实现方法
follow up2: 只需要求最近k个int的mean和median(k是常数)
2、简单DP:求一个单词能不能被元素周期表拼出来,提供元素名字的hashset

评分

1

查看全部评分

zyoppy008 发表于 2016-9-14 14:30:37 | 显示全部楼层
iwknow 发表于 2016-9-14 14:23
我怎么感觉第一题可以这样做:. from: 1point3acres.com/bbs
假设 现在stream走到第n个数,avg是(n-1)个数的mean
那么第n个数(假设 ...

第n个的 median 怎么类似。。。
回复 支持 1 反对 0

使用道具 举报

zyoppy008 发表于 2016-9-14 13:25:15 | 显示全部楼层
第一题求follow up2 用tree map代替 优先队列 然后用一个额外数组记录按插入顺序 记录在map的地址 用来删除维护 最近k个的map吗
回复 支持 反对

使用道具 举报

 楼主| UpDownDOTA 发表于 2016-9-14 13:30:29 | 显示全部楼层
我的做法是直接存vector<ListNode*>,链表顺序=插入顺序,vector保持sorted
回复 支持 反对

使用道具 举报

zyoppy008 发表于 2016-9-14 13:47:12 | 显示全部楼层
UpDownDOTA 发表于 2016-9-14 13:30
我的做法是直接存vector,链表顺序=插入顺序,vector保持sorted

你这是o(n)吧
回复 支持 反对

使用道具 举报

zyoppy008 发表于 2016-9-14 13:48:41 | 显示全部楼层
UpDownDOTA 发表于 2016-9-14 13:30
我的做法是直接存vector,链表顺序=插入顺序,vector保持sorted

哦哦 不是o(n) 是log(n) 和 o(1)
回复 支持 反对

使用道具 举报

 楼主| UpDownDOTA 发表于 2016-9-14 13:57:00 | 显示全部楼层
zyoppy008 发表于 2016-9-14 13:48
哦哦 不是o(n) 是log(n) 和 o(1)

是的,我不是很熟Java,不过我记得Java的话应该有个结合了hashmap和queue的type可以直接拿来用
回复 支持 反对

使用道具 举报

zyoppy008 发表于 2016-9-14 14:10:10 | 显示全部楼层
UpDownDOTA 发表于 2016-9-14 13:57
是的,我不是很熟Java,不过我记得Java的话应该有个结合了hashmap和queue的type可以直接拿来用

我也用的是c++
c++ 应该有四种方法吧
第一种 你这种 但是因为 vector插入不太效率。。。用list的话 又没法用lower_bound做binary search
第二种 priority queue 这个比较好. From 1point 3acres bbs
第三种 binary tree 这个比较麻烦。。要写蛮多 但是可以直接用map(tree map) 跟第二种差不多
第四种 就是用c++ nth_element 但是一个0(1), 一个o(n) 好处是简单好写 而且插入顺序不变。。。

对于第二个follow up的话 vector配合list比较好写,但是还是vector插入删除不效率, priority_queue 因为不好删,所以maybe改成map就好一点,稍微写起来麻烦一点。 第四个会不会比较不错?直接屁股后面插就行,前面都可以不用删,该范围就行,写起来简单就是时间复杂度高一点0(n),但是我想其他的操作其实并不效率,coefficient也很大呀。
回复 支持 反对

使用道具 举报

iwknow 发表于 2016-9-14 14:23:45 | 显示全部楼层
我怎么感觉第一题可以这样做:
假设 现在stream走到第n个数,avg是(n-1)个数的mean
那么第n个数(假设数值是x)的mean = (avg*(n-1) + x)/(n) = avg - avg/n + x/n. 鍥磋鎴戜滑@1point 3 acres
这样维护一个计数变量n 和一个平均值 avg 就好了。
meadian可以用类似的方法
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-9-14 15:20:05 | 显示全部楼层
find median from data stream and window size K median 应该都是用两个heap做, 每当node超过window size时,pop heap中第一个插入的
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-9-14 22:10:51 | 显示全部楼层
median是用两个堆实现的嘛。。? 以及 还有啥别的实现方法呀? 排序?
回复 支持 反对

使用道具 举报

 楼主| UpDownDOTA 发表于 2016-9-14 23:23:18 | 显示全部楼层
小A要当码农 发表于 2016-9-14 22:10
. From 1point 3acres bbsmedian是用两个堆实现的嘛。。? 以及 还有啥别的实现方法呀? 排序?
. 1point3acres.com/bbs
还有就是保持插入的数sorted,具体可以用vector或者优先队列(binary search插入位置)
然后follow up1我回答的是用两个堆的做法,还可以用balanced binary search tree不过实现就都比较复杂了
回复 支持 反对

使用道具 举报

 楼主| UpDownDOTA 发表于 2016-9-14 23:24:44 | 显示全部楼层

宵夜你这是把论坛从头到尾水了一遍么= =这都能被发现!
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-9-14 23:31:26 | 显示全部楼层
UpDownDOTA 发表于 2016-9-14 23:23
还有就是保持插入的数sorted,具体可以用vector或者优先队列(binary search插入位置). 1point 3acres 璁哄潧
然后follow up1 ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
用vector的话, 每进来一个新数,都要插入到指定位置?
回复 支持 反对

使用道具 举报

 楼主| UpDownDOTA 发表于 2016-9-14 23:37:44 | 显示全部楼层
小A要当码农 发表于 2016-9-14 23:31. From 1point 3acres bbs
用vector的话, 每进来一个新数,都要插入到指定位置?
. 1point 3acres 璁哄潧
是的。。虽说不太效率不过面的时候第一想法是这个,也好写,所以就回答的这个哈哈= =
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-9-14 23:39:09 | 显示全部楼层
UpDownDOTA 发表于 2016-9-14 23:37
是的。。虽说不太效率不过面的时候第一想法是这个,也好写,所以就回答的这个哈哈= =

&#128077; 祝楼主 昂赛好运呀
回复 支持 反对

使用道具 举报

 楼主| UpDownDOTA 发表于 2016-9-14 23:49:31 | 显示全部楼层
小A要当码农 发表于 2016-9-14 23:39
&#128077; 祝楼主 昂赛好运呀

多谢!借你吉言~
回复 支持 反对

使用道具 举报

readman 发表于 2016-9-14 23:55:46 | 显示全部楼层
UpDownDOTA 发表于 2016-9-14 13:57
是的,我不是很熟Java,不过我记得Java的话应该有个结合了hashmap和queue的type可以直接拿来用

没有, Java的hashheap需要自己实现
回复 支持 反对

使用道具 举报

 楼主| UpDownDOTA 发表于 2016-9-15 00:36:05 | 显示全部楼层
readman 发表于 2016-9-14 23:55. From 1point 3acres bbs
没有, Java的hashheap需要自己实现

不是有个叫LinkedHashMap的东西嘛= =我也是道听途说自己没用过
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 20:26

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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