10.28 Google面经回馈（附个人解法）

我面的是Google Singapore，所以题目对北美或者其他地区的朋友可能没什么帮助，但是大家满看一下吧。

首先最大的感觉是懵逼，很多平时觉得 哦很简单 的题目能给你问出花来。

第一面，三哥：第一问：如何存储一个电话簿。追问：如果要求输入一个子串，如何给出所有包含该子串的所有名字。第二问：标准LRU实现。

这题还算基础，没啥难点。第一问本问直接用trie就行，追问直接用suffix array＋二分查找。LRU实现没出什么其他问题。

第二面，俄罗斯大叔：第一问判断一个数是否中心对称，比如101，818这样的；第二问给定一个n，求n位数以内所有的中心对称数。

记得好像做过类似的题目，leetcode上可能有，但是忘了。第一问我的做法是生成中心对称然后比较是否相等，有个corner case是生成对称数的时候要用longlong存，因为可能会有166666666这样倒过来超界了的。第二问分奇偶讨论，奇数seed：0 1 2 5 8，偶数seed：11 22 55 69 88 96，然后放队列里，每次出队一个，然后两边加上0 1 2 5 6 8，其中6和9要注意一下。

第三面，国人大哥：如何只通过shuffle和remove构造最长的回文串，第一问能做出来就行，第二问要求除了新串之外只能用一个额外变量。

LC409 拓展，输出回文数版。本问不难，直接用hash统计每个char出现的个数，然后偶数全进去，奇数删一个再全进去就行，输出纯粹体力活，没啥说的。然后重点来了，这尼玛第二问是怎么回事（黑人问号？？）一个变量没有hash你特么逗我？后来在提示下想到一个非常妙的解法：

用一个int32（可以看成是一个32位bool数组）记录每一个char是否出现过，然后开始读input，如果当

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

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

000000">2. 和该节点相同颜色的儿子节点所在子树中至少有一棵包含直系空节点。（这点在面试的时候做错了，完全没想到，太慌了）

总结：
就我的面试而言，第五面直接错了加上是三哥面，基本稳跪了，不可能会给过的。


有一个面试技巧大家要记住，一定要和面试官交流，获得一些提示，这样能更清晰的design和优化算法。很多问题都不是面试官前一天准备然后第二天直接问的，很多问题的解答都是在经历了几十个面试者之后一步步的想出来的。像这次的第三面，我相信面试官最开始也只准备了hash做法，后来慢慢的发现，诶似乎可以简化掉hash，于是这个就成了一个followup了。然后要体会到这种解法，除非你真的很牛直接想到了，不然自己干想很难，甚至连方向都没有。

nevets 发表于 2016-12-13 00:24
是以输入串为子串的所有名字。可以利用后缀数组来找 :)

非常感谢lz的回复，请问你在题中提到的trie的作用是不是仅仅用作存储电话簿的数据结构呢？电话簿中的数据是什么样的形式的呢？怎么把姓名和号码结合在一起的呢？
这样的话，trie和后面的用后缀数组查找子串是不是没什么关系？

mr530 发表于 2016-11-3 02:04
感觉你前4轮都不错啊，就一轮不好。。google要求这么高？

根据最后recruiter给我的feedback，有两面的面试官给我的评价比较负面，尤其是第五面的面试官给我的评价很低，大概就是说基础知识不好之类，然后就跪了😂另外一个可能是第三面我要了hint吧。

chaosMonkey 发表于 2016-12-13 00:55
非常感谢lz的回复，请问你在题中提到的trie的作用是不是仅仅用作存储电话簿的数据结构呢？电话簿中的数据 ...

Trie和suffix array只是作为索引，能更好的执行 “查找包含某一子串” 这一任务而已。具体电话mapping可以非常直接的用hashmap做。

感觉你前4轮都不错啊，就一轮不好。。google要求这么高？

可以问下LZ人在哪里为啥要面google singapore么，感觉比北美难啊，和google  us 是分开招人么

elizabethxiazhi 发表于 2016-11-3 02:07
可以问下LZ人在哪里为啥要面google singapore么，感觉比北美难啊，和google  us 是分开招人么

因为我现在在新加坡工作，暂时也没有去美帝的打算 :p

nevets 发表于 2016-11-3 11:17
根据最后recruiter给我的feedback，有两面的面试官给我的评价比较负面，尤其是第五面的面试官给我的评价 ...

第三面的人略坑啊。。我觉得那个follow up现想出来已经很好了。。。

mr530 发表于 2016-11-3 12:26
第三面的人略坑啊。。我觉得那个follow up现想出来已经很好了。。。

这也无可奈何😂 可能他的bar比较高吧

谢谢楼主分享。感觉楼主应该是面了一天到最后有点晕，个人感觉第五面的题目比前四面都简单。。。

楼主运气不好， 碰到烙印。。

cezheng2 发表于 2016-11-3 18:22
谢谢楼主分享。感觉楼主应该是面了一天到最后有点晕，个人感觉第五面的题目比前四面都简单。。。

多谢安慰，当时感觉就是懵了 >< 平时一直觉得这种树遍历的题目难不到哪去，结果这次死在这上面也是捶胸顿足 :(