google/youtube onsite面经 3/14/2018

刚面完YouTube，在san bruno，没有phone interview直接去的onsite， 所以面了五轮，累死第一轮，中国人，题目是0-1矩阵，find component number in array， leetcode上的那个isolate island那题，变了个说法，我说可以dfs可以union find，然后他让我用union find写，秒了，然后follow up加一个方法可以把其中的0变成1，然后实时计算componet数量，很简单。之后用中文聊天他告诉我不要一开始就说union find，要慢慢来，要么都没法问follow up了 ＝。＝ 这个中国大哥超级nice。

第二轮， 烙印，第一题 find minimal submetrix in a metirx. 我记得刷过不过不记得n3的解法了，就硬着头皮写了个n4的presum解法，烙印也没刁难算法复杂度，不过问了我溢出怎么办，我说换成long，又问用long会不会溢出，我说如果矩阵数量太大还会溢出，问我怎么办，我没想出来就说用string来算加法？问了一下算法复杂度又下一题。给你一个矩形，用最少的square填充满，我当时想用dp，后来讨论了一下发现不太行，然后他给了

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

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

是上来就做题，完全不问你做过什么项目什么的，而且很喜欢考你unit test，基本每一轮都问你test cases。
面完了感觉发挥不是很好，尤其第二轮，应该是跪了，不过还是求人品求大米求offer

神特么是哈密尔顿，烙印也是厉害，哈密尔顿一个NPC的问题。。。这个题其实是二分图的最小加权完美匹配，有N^3的做法（N是自行车数=人数），不过我不相信面试会写这个。

补充内容 (2018-4-4 03:23):
第三题

估计楼主把匈牙利算法听成汉密尔顿算法了吧

LZ放宽心！他家绝壁不看一轮结果，更何况你这轮是给出解的了。我大年初一面的youtube（同5轮coding），答的一塌糊涂最后还能有几个positive feedback的。  youtube发展真的非常好！听朋友说内部都认为youtube特有前景。记得中午被陪同小哥去他家街对面新楼溜达了一圈，挺赞的。可惜自己技不如人甘拜下风面完正好3周后被HR通知拒了。。。

第四轮有点萌比，感觉既不用2 pointer也不用dfs...还是说dict里面也会有extension? 比如word="hellooooo",dict=["hellooo"]，这时候返回还是true?

第二轮是这题吗？ https://www.geeksforgeeks.org/dynamic-programming-set-27-max-sum-rectangle-in-a-2d-matrix/

谁能帮忙解释下”然后follow up加一个方法可以把其中的0变成1，然后实时计算componet数量“ 是怎么做的吗？谢谢！

谁能帮忙解释下 ， union find 怎么做“然后follow up加一个方法可以把其中的0变成1，然后实时计算componet数量” ，谢谢！

ivyjwyu 发表于 2018-3-16 06:33
谁能帮忙解释下 ， union find 怎么做“然后follow up加一个方法可以把其中的0变成1，然后实时计算componet ...

就是你每加一个1进去，就和四周的union一下

ivyjwyu 发表于 2018-3-16 06:33
谁能帮忙解释下 ， union find 怎么做“然后follow up加一个方法可以把其中的0变成1，然后实时计算componet ...

就是你每加一个1进去，就和四周的union一下，只用union一次就可以

wtcupup 发表于 2018-3-16 02:59
第二轮是这题吗？ https://www.geeksforgeeks.org/dynamic-programming-set-27-max-sum-rectangle-in-a-2d- ...

对的，字数字数

tinylic 发表于 2018-3-16 02:45
第四轮有点萌比，感觉既不用2 pointer也不用dfs...还是说dict里面也会有extension? 比如word="hellooooo",d ...

dict里面不会有extension的
求教有什么解法？