一亩三分地论坛

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

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

Google phone interview 面经

[复制链接] |试试Instant~ |关注本帖
tianlu1 发表于 2016-3-8 09:43:30 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 博士 全职@Google - 内推 - 技术电面 |Passfresh grad应届毕业生

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

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

x
上周一(2/29/2016)的google电面,今天刚刚收到通过的通知电面通过,赶快过来发面经。

面我的是个白人小哥,人非常nice,只问了一个问题:moving window average for double value。楼主用了类似LRU的double linkedlist 和 sum 解的, 但是感觉这个应该不是最好的办法。

follow up 1) 如果input data stream非常大的话会不会有error
              2) linkedlist会有会有经常delete/create node,有没有什么改进。

楼主从电面到收到通知之间用了一个星期,不知道是不是答得一般,committee意见有分歧。onsite求bless!

评分

1

查看全部评分

darktemple9 发表于 2016-3-8 13:03:35 | 显示全部楼层
lz 能稍微详细说下题目嘛,有点没看明白
回复 支持 反对

使用道具 举报

xiaojiujie 发表于 2016-3-8 20:29:40 | 显示全部楼层
同没明白,能稍微解释一下这几个词组成的意思么?
回复 支持 反对

使用道具 举报

googlerr 发表于 2016-3-9 05:53:28 | 显示全部楼层
麻烦楼主解释一下题目吧,谢谢!
回复 支持 反对

使用道具 举报

 楼主| tianlu1 发表于 2016-3-9 12:28:48 | 显示全部楼层
不好意思,这个题没有说明白。
题目是有一个data stream, find the average of latest k numbers。 data 是 double parameter。这就类似于array 的moving window average
回复 支持 反对

使用道具 举报

jemi 发表于 2016-3-9 12:32:04 | 显示全部楼层
楼主你这两个follow up 是怎么答的啊
回复 支持 反对

使用道具 举报

 楼主| tianlu1 发表于 2016-3-9 12:45:39 | 显示全部楼层
jemi 发表于 2016-3-9 12:32
楼主你这两个follow up 是怎么答的啊

这两个follow up是根据我的回答问的。
1) 我用了一个sum 来记录window值的总和, window 里每次加入/剔除一个树时就update一下sum,这样求average是O(1)的时间。但是如果data stream太大,每次求sum的error会累积,最后就不准确了。.1point3acres缃
我当时回答如果data stream太大就不用sum记录了,但是这样求average 就是O(k)。

现在想,其实可以每一定量数(e.g 1000)后refresh一下sum,这样还是可以keep O(1)in time。

2) 这个面试小哥是想说每次create list node 和delete list node不太好,可以保持list node 不变,每次改node value 就可以了。
回复 支持 反对

使用道具 举报

GUIXIANG 发表于 2016-3-21 06:58:04 | 显示全部楼层
tianlu1 发表于 2016-3-9 12:28
不好意思,这个题没有说明白。
题目是有一个data stream, find the average of latest k numbers。 data  ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
这个问题听着像是simple moving average
https://rosettacode.org/wiki/Averages/Simple_moving_average#Java-google 1point3acres

请问follow up第一问到底什么意思,为什么会有error呢?
回复 支持 反对

使用道具 举报

hyj143 发表于 2016-4-15 10:27:26 | 显示全部楼层
用array应该更好吧
回复 支持 反对

使用道具 举报

cwjade 发表于 2016-5-12 05:53:53 | 显示全部楼层
想问楼主是用什么语言刷题的呀?
回复 支持 反对

使用道具 举报

 楼主| tianlu1 发表于 2016-5-12 07:53:58 | 显示全部楼层
cwjade 发表于 2016-5-12 05:53. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
想问楼主是用什么语言刷题的呀?
. 1point3acres.com/bbs
用java刷题的

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

adiggo 发表于 2016-5-12 10:28:33 | 显示全部楼层
tianlu1 发表于 2016-3-9 12:28
不好意思,这个题没有说明白。
题目是有一个data stream, find the average of latest k numbers。 data  ...

楼主 这个题 有size 的限制 是么。 是k 肯定不会大于那个window size么。。
回复 支持 反对

使用道具 举报

 楼主| tianlu1 发表于 2016-5-12 10:29:46 | 显示全部楼层
adiggo 发表于 2016-5-12 10:28
楼主 这个题 有size 的限制 是么。 是k 肯定不会大于那个window size么。。

k 是valid的
回复 支持 反对

使用道具 举报

Christy2013 发表于 2016-5-12 10:30:16 | 显示全部楼层
bless bless bless
回复 支持 反对

使用道具 举报

qinqinhao 发表于 2016-5-12 13:14:13 | 显示全部楼层
tianlu1 发表于 2016-3-9 12:45
这两个follow up是根据我的回答问的。
1) 我用了一个sum 来记录window值的总和, window 里每次加入/ ...
. From 1point 3acres bbs
楼主为什么要用ddl,不用数组。
还是refresh是什么意思呀。
回复 支持 反对

使用道具 举报

jjustc 发表于 2016-6-13 10:02:37 | 显示全部楼层
tianlu1 发表于 2016-3-9 12:45
这两个follow up是根据我的回答问的。
1) 我用了一个sum 来记录window值的总和, window 里每次加入/ ...

delete/create list node 都是O(1) 的为啥不太好 面试官是咋想的?
回复 支持 反对

使用道具 举报

hkc593 发表于 2016-6-13 10:53:48 | 显示全部楼层
jjustc 发表于 2016-6-13 10:02-google 1point3acres
delete/create list node 都是O(1) 的为啥不太好 面试官是咋想的?

new/delete是有额外开销的。
回复 支持 反对

使用道具 举报

jjustc 发表于 2016-6-13 11:00:25 | 显示全部楼层
hkc593 发表于 2016-6-13 10:53
new/delete是有额外开销的。

哦。。。。。。那如果 要改list node值的话 得从头到尾扫一遍 往前挪吧……不是更慢……
如果 我用C++的deque还会存在这个问题吗? 谢谢!
回复 支持 反对

使用道具 举报

jjustc 发表于 2016-6-13 11:01:14 | 显示全部楼层
qinqinhao 发表于 2016-5-12 13:14
楼主为什么要用ddl,不用数组。. visit 1point3acres.com for more.
还是refresh是什么意思呀。

refresh就是重新把list扫一遍算一次sum吧 这样保证sum从现在开始就是准确的 不会继续 累积误差
回复 支持 反对

使用道具 举报

hkc593 发表于 2016-6-13 11:50:06 | 显示全部楼层
jjustc 发表于 2016-6-13 11:00
哦。。。。。。那如果 要改list node值的话 得从头到尾扫一遍 往前挪吧……不是更慢……
如果 我用C++ ...

不需要update list的每一个node的 。我想是把head pop出来,update value,然后再append到list的尾部。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 19:53

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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