Google MTV onsite面经

收到信说过HC了，发面经求RP求大米。。


某个周五去的

可能因为面试的楼里面都是做ads的，所以4轮+午饭，5个人里有4个做ads的。。。。。

除了最后一位，其他人都没什么表情。。。。

4轮的题目好像都没怎么见过啊，说好google喜欢考DP的，也没有。。。

#1 国人gg

一个系统不定期抛出错误，每次有错误时会调用一次alter(int timestamp)函数来检查在过去的period时间内出错数是否超过max_e，alert返回bool。可以认为当且仅当有一个新错误，alert才会被调用。

比如，出错时间为：1,3,3,8,10,13,13,13,20。给定max_e = 4, period = 5，那么每次出错后调用alert的结果依次为：F,F,F,F,F,F,T,T,F。第一个13返回F，因为8-13这段时间内一共3个报错，后面两个13返回T因为分别有4/5个报错。

可以用queue，每次alert就push，然后把过期的错误pop，然后检查size。

由于可能有duplicate，用hashmap存次数，遇到重复的就不push。

代码也是磕磕绊绊，两三个bug在提示下改对了。分析时间空间复杂度，然后分析平摊情况下的复杂度，这里也是给了提示才说出来。

fol

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

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

te，然后swap。每个byte，写个函数做flip。

复杂度是O(N)，不能更好了。

follow up： 怎么parallel优化，这里每个row可以独立处理，每个pair of byte可是独立，这两个比较naive。但是byte flip就不懂了，最后讨论了一下写了些公式，但我还是没看出怎么能比原来做的好。




是因为最近招聘季，大家比较累吗，面试官都没什么笑脸。。。。





之前电面的帖子：



补充内容 (2016-11-23 12:07):
发offer了，n^4那道题做成那样也能过我也很惊讶。。

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

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

oldwhite 发表于 2016-11-17 01:52
第二题能不能这么做：

第一遍 先找所有0，把0填进去

好像有道理，这样就是N^2了，因为每个位置只被更新一次。

我感觉楼主面的不好啊 第一轮很简单就leetcode变形 follow up就用counting sort 加circular array 应该bug free的 第二轮 明显也是原题变形啊 bfs o(n) 可解 第三轮类似第二轮还更简单 第四轮 没看明白
地里有些比较难的面经 基本都差不多答出来也挂了 感觉楼主题不难表现也没有特别出彩 反而过了 g家标准有点迷啊

Bless LZ. 感觉还不错啊， 希望拿下。
第一题 处理duplicate，哪些算dup？你的例子中13， 13， 13算吗？

houqingniao 发表于 2016-11-16 11:43
Bless LZ. 感觉还不错啊， 希望拿下。
第一题 处理duplicate，哪些算dup？你的例子中13， 13， 13算吗？

算啊，所以第一个13返回F，后面两个13就返回T。

恭喜LZ! 请问是onsite后多久知道消息的？

第二轮楼主的例子有误吧

1 0 1
1 1 0
0 1 0

返回：
1 0 1
2 1 0
0 1 0

不是应该返回：
1 0 1
1 1 0
0 1 0

而且这个为啥是用DFS O(n^4)做，不是先扫一遍矩阵找出所有的0，然后从这些0开始BFS，O(n^2)?是我理解错楼主说的题意了么

请问lz是哪个周五面的..

lz是在同时找实习和fulltime吗

fflute 发表于 2016-11-16 14:12
恭喜LZ! 请问是onsite后多久知道消息的？

一周以上，字数字数

cezheng2 发表于 2016-11-16 14:16
第二轮楼主的例子有误吧

1 0 1

你说得对，[1,0]那个位置应该是1

从某个0开始BFS是n^2，访问每个0要n^2，一共是n^4