谷歌滑铁卢面经

刚刚去完谷歌滑铁卢onsite，新鲜分享一些面试经验和题目，我来攒攒人品吧，希望得到大家的祝福。

----------------------
TL：

2月13日 ：HR找我问我有没有兴趣，回答当然，但是我要回国过年了，说先安排回加拿大电面
2月28号 ：很神奇的一件事发生了，HR突然给我了一个Good News，说可以跳过店面，直接onsite。。。emmmm，好厉害。之后我直接被推给加拿大的HR
3月7号   ：安排面试，先安排21号，当时我感觉两周复习时间不够，往后推了一下，到了27号
3月26号 ：前往水卢
3月27号 ：onsite 5 轮，上午3轮，中午一个小时休息，下午2轮

----------------------
第一轮：
Input: 1. 给一条路，路上的不同位置有不同的设施，有多个设施在不同位置的情况, List<Set<String>>
          2. 给一个需求设施的set
Output： 希望给出一个位置，距离所有设施的距离最近（注意，不是距离和！虽然我也不知道为什么）
面试者：白人小哥，硬件组
1. 先给了Naive来拖时间，每个位置把到其他点上所有距离找出来，然后通过比较给出答案，很明显是O（n^2）
2. 提到了可以预处理List<Set<String>> -> Map<String, List<Integer>> 把每个设施的位置变成一个List，然后放进Map里，可以节约时间
3. 想出来用一个int[][]的array map，每列对应不同的设施，每一排装road上装路上某一个点到该设施的最近距离， 然后同时go through 所有的不同设施，找到设施最小值所在的位置，其实如果是距离和，这个应该是最优解，面试小哥也说good enough，让我implement，O（n*k）,k是需求设施的个数
4. 最优解是O（n）,世界上是距离最远的两个需求设施的中点即可

因为其实我的方法代码量比较多，然后我通过先写interface完成思路，再具体implement小方法的解题思路应该逻辑很清晰，最后修复了一些bug，小哥给的反馈还比较满意，说了awesome

-----------------

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

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

5. 然后问除了Map,我能不能用别的更省空间，我就说可以array map啊，还提出了邪门歪道counting sort，妹子说可以set，好吧，实际上不还是Space：O（n）么

然后嗯，这个时间最优就是O（n），没有别的。。。这题真是吓我一身冷汗😓

----------------------

一些感想：

1. 住在Crown Plaza，水卢dt一家三星宾馆，体验极其糟糕，毛巾被套上都是氯水的味道，如果Google给你们订这个酒店，请务必拒绝，自己出钱换一家都好过这家
2. 中餐是真好吃，接待的小哥说有个叫Google 13的项目，还可以免费升级成Google 15或者Google 30， 就是加入谷歌第一年会长这么多肉，真羡慕，我也想参加这个项目！
3. 我之前看了很多人，说5个背靠背对体力要求很大，大概是我最近一直在健身的原因，觉得还OK，其实精神足够集中的话，真的不会感觉太累或者饿。另外就是之前几天和中午有意加大了碳水的摄入比例（也不要那么多，免得困），保证血糖供应。
4. 我准备了一个Saje的headache remedy，每个休息空间上个厕所，然后把这个往头上抹一点，保持清醒很重要！

希望对大家有所帮助，且希望获得大家的祝福！！！

第一题应该是伞一奇， 第二题应该是漆耳， 第三题follow up， 已知入口吗？应该就是BFS + 记忆化搜索吧，如果边的权重都一样，就直接BFS， 如果边的券种不同，需要加一个记忆化搜索。
第四题有点像斯要领，但是按照题主妹子叙述k是固定的，思路就不一样了吧？
第五题不知道怎么降低空间复杂度，求大神指点

第二轮可以用edit distance的思想，第三轮follow我觉得可以用拓扑排序？

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

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

第一题连着两天看到了，第四题是嗣腰龄原题，最近他的变形超高频

kaipeng21 发表于 2019-3-28 13:14
第一题连着两天看到了，第四题是嗣腰龄原题，最近他的变形超高频

哈哈哈 好像每个google面试都看到你啊，你是不是也在准备狗家啊

第三轮没见过，能不能更详细一点啊。或者举一些例子？

wow so intensive

yangyuzhiguang 发表于 2019-3-28 16:00
第二轮可以用edit distance的思想，第三轮follow我觉得可以用拓扑排序？

大佬太厉害了，我完全不记得Topological sorting了!
edit distance 实际上也是dp，应该也是很好的思路！

xiangwangtong6 发表于 2019-3-28 17:46
第三轮：
    int getTime(TNode root){
        if (root==null) return 0;

遍历，然后记录遇到的第一个设施位置，并实时更新最后一个设施的位置

第二轮KMP可用Robin-Karp替代 on average O(m + n) 还是可以写的