google onsite

兄dei强推，免掉了无聊的oa和电面。现场5轮

第一轮 中国小哥不过貌似很早就来美国了姑且算abc吧。梨扣 期舞凌，没啥压力解决了，follow up是矩阵很大，怎么map reduce，随便扯了扯套路。

第二轮 白人nerdy小哥，几乎一句话也不说就木讷羞涩的看着我。。题是2d矩阵有一些球，如果这个球在这行或者这列有其他的球，那么这个球就可以take走，问最多能take多少球。一开始以为是个dp，后来发现好像不是，通过循序渐进的和小哥沟通，小哥终于开始不羞涩的说话了。。聊了聊我提出了我的猜想，看通过行和列能把多少个球连到一起，然后组成一个forest，这个forest最后可以take到只剩下一个球。所以有多少forest就有多少最后剩下的球，那么take走的球就是总球数减去forest树木。小哥表示同意问我想咋写。我就写了个BFS行和列找连接的森林. O(mn)(m+n)大概的时间复杂度。感觉这轮表现一般，虽然也写出来了。

第三轮 白人焦虑小哥，似乎他很忙，没

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

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

横着连着，另外一个在这个pattern 右下角的，然后这个pattern随机放一个地方，剩下地方继续random搞。小哥说不错，继续follow up说给一个没有move的board，你咋shuffle，楼主说这code量太大了，写不完，写伪代码吧，然后我的思路就是统计当前board里每个颜色有几个球，然后生成一个pattern放到一个地方，剩下的球想办法fit进去，如果造成了3个连续的话就swap解决。

整体感觉还好吧，脸欧没遇到烙印。虽然也不太想去g。

cwjade 发表于 2018-11-4 16:30
楼主第二题不是很明白forrest，可以再讲讲吗？O(∩_∩)O谢谢
如果就按题意贪心做，比如[j]位置有球，并且i ...

楼主的forest其实是指一个连通域，两个球如果在同行或者同列表示联通。贪心应该是不对的，和拿掉的顺序有关系，应该先拿掉degree最小的球。找出连通域的个数，答案就是总球数-连通域个数了

感觉最近他们招人很多，很缺人的感觉，bar低了不少，也许是脸欧，没遇到烙印和hard题。

lukuang 发表于 2018-11-4 23:19
感谢回复。。不过如果第二排是21122的话，把第三个1改成2了之后好像有三个2一起了不太对？

嗯，我和小哥聊的时候先说的swap，然后说如果只有2种颜色的话其实就可以1212这样间隔着放，然后他就让我假设说颜色很多了，这个swap思路我也是5秒钟内闪出来的想法，也算是后面最后写shuffle的伪代码的一部分吧，感觉他没指望我能秒想出可以完成这个swap的算法，重在沟通和假设。

楼主在哪里面的? 面的是google的哪个组?谢啦

第三轮，有两个parents 还是树吗？

请问汇率是什么题？

难道第四轮跟中国大哥聊了中美贸易战？

楼主能扯扯第一题怎么mapreduce咩

LZ在那个site面的 ？

usagi21 发表于 2018/11/04 00:57:41
楼主能扯扯第一题怎么mapreduce咩

同问 zszszs

统一回答一下。
在MTV总部面的。

好像是ads组吧，不过我觉得这不重要。

汇率是面经高频题啊兄dei们，也就是梨扣 伞伞酒啊。

第四题是倒着的树啊，因为从2个child变成2个parent了，并且可能有一个兔子的爹和娘是亲兄妹(爹和娘的爸爸妈妈是相同的)关系的情况。。。

第一题map reduce就纸上谈兵啊，这道题标准做法不是逐行扫描，然后每行是卡住left和right，如果两个都是1的话就看之前是否已经生成过这个patern了吗，然后通过一个patern比如left = 0 && right = 5生成一个string "0#5"然后去hash里面找之前存在的这个pattern的个数。
map的时候把矩阵分成多个部分，每个部分交给一台map机器去找pattern，然后reduce的机器按照string排序处理不同的pattern vote，这样多个map机器和多个reduce机器就可以把矩阵分开进行计算了。