谷歌中国（Google）

之前在谷歌官网注册后按照要求填写了一份个人简历，本以为简历会筛选不通过，没想到第二周HR打电话过来，先简单告诉了下招人的是谷翔，但是所有福利待遇和谷歌一样，然后说如果有意向的话，会将简历发给面试官审核下，如果审核通过才能笔试。 第二周说审核通过，然后约下周笔试，笔试题目不是很难，都是Web 开发基础。第三周面试，一共两轮，都是问算法，没有偏重具体语言。

4月份参加的广工宣讲会，当时现场会有笔试安排，题目不会很难，都是选择题，而且相当基础。 笔试完三天后，hr打电话通知我去公司面试，公司还挺大的，里面设施设备很好。当天面试有三轮，前两轮都是技术面，最后一面是hr面。 第一轮技术面问的都是很基础的问题，考察java基本功吧，例如Java 的集合还有io这些，当然也问了很多计算机知识，考察整个计算机体系结构知识吧。 第二轮也是技术面，当时问了几个相对难一点的问题吧，但是也不会很难，有准备的话都能答对，其实也是数据结构的知识。 第三面就是hr面了，问了下三观之类的问题，还有问对加班怎么看待，然后就叫我回去等通知了，一个星期之后给答复。 最终结果就是一周后也没任何音讯，邮件问了hr也没回我，知道应该是凉了。

问了一个LintCode原题 add and search word，设计算法支持两个操作，一个是add一个字符串，一个是search某个字符串是否在目前的字典中。查找的串可能包含通配符‘."，匹配任意一个字符。用Trie Tree即可。 然后小哥问了一下如何在space和time之间trade off，这个问题我做题的时候就想过，因为这题有两种做法，一是建树时不把"."作为一个字符，而在搜索时碰到"."时搜索所有儿子节点。另外一种是建树时把"."加入到每个节点的儿子节点中，把所有包含"."的字符串也存在Trie Tree中。两种做法的区别在于，前者空间复杂度低，每次add时间复杂度是字符串长度，每次search时间复杂度是O(26^"."的个数)；后者空间复杂度高，每次add时间复杂度是2的字符串长度次方，每次search时间复杂度是字符串长度。印度小哥表示挺满意的～

主要分为两个步骤，一个是项目经理面谈，和你聊聊技术层面，和逻辑方面，一个是公司会组织技术和hr和你聊聊，虽然自己有意向，但是因为上一家公司就是加班加的太厉害，自己适应不了现在公司的加班才选择不去的，祝你好运~

百度面试需要先到前台签到，领取自己的编号，这个编号最好记住，毕竟会有重名的。然后排队等待面试，百度会有专人引领去面试场地（由于人很多，百度的面试场地设在了自己公司的中餐厅）。 一面是一个挺和善的帅哥，年龄差不多三十来岁，人家也很客气，主要问了以下问题（与序号无关）： 1.自我介绍; 2.实习项目的介绍以及你在项目中做的内容; 3.Java有几种基本数据类型？分别占几个字节？ 当时一紧张忘记char占几个字节了，他很客气告诉我是2两个字节。百度员工还是不错的，没让我感到太多拘束。  4.有两个有序数组a[10, 20, 30]，b[5, 15, 25]，设计算法如何取出两个数组中第3小的数（也就是取出15）； 设计时一定要考虑效率和内存问题。  5.HashMap底层的原理，put(key, value)、get(key)原理 ; 6.接口与抽象类的区别; 7.什么是继承与多态; 8.常用的设计模式并分别讲解一下; 9.Linux常用命令; 10.数据库的联合索引; 11.数据库事务，ACID的介绍; 12.从坐标原点（0， 0）到坐标（m， n）有多少条路径; 13.Java虚拟机的堆与栈以及回收算法有哪些？新生代用什么算法，老生代用什么算法？  14.你有什么想问我的吗？可以随便问。  15.平时关注谁的博客？有GitHub项目吗？ 还有几个问题记不得了……一面下来差不多一个多小时，大部分都能答上来，不会的就说不会，面试官有时候还会告诉你该怎么做，叮嘱我一定要刷题。 面完之后差不多11：40，百度提供零食可以自助；如果需要吃正餐需要自己出去。 二面是下午1点开始，等到快3点多才轮到我，百度的负责人把我安排到一个C/C++面试官那里，我问不影响我面Java吗，她说都可以面，现在没有Java面试官了，都排满了。我就信以为真了，呜呜……  面试内容如下（与序号无关） 1.自我介绍; 2.实习项目介绍，以及项目中用到的算法（问的很细); 3.文件有N行数据，随机读取M行不能重复；设计算法，如何优化 还是要注意效率和内存问题; 4.给你10G内存，500G数据，请问如何排序？说说思路即可; 5.ping是在哪一层？流程是什么？  6.有哪几种常见排序？复杂度分别是多少？哪个排序算法最快？  7.你自己用过的设计模式，介绍一下; 8.自己的开发环境是什么？介绍下Linux命令 还有几个问题，不记得了……面试官最后和我说：很遗憾，你的算法能力还不够，百度不适合你。你还年轻，慢慢来。相遇即缘份，人生第一次互联网公司面试就交给了百度，虽然失败了，但是挺感谢百度给的这次机会。 我自己总结了一下（仅仅是个人想法，姑且言之）： 百度有一轮笔试，三轮面试，我的理解是这样的 笔试刷去20%申请者 一面刷去20%面试者 二面再刷20%面试者 三面再刷20%面试者 最后留下的这20%中肯定有很多获取其他公司offer，不一定会留在百度，所以最终百度只会留下10%左右的人。 这样来看我仅仅是打败了40%-50%的申请者，距离成功还很遥远。 给自己简单定位，总结教训，向着前方奔跑！我还有三点感悟:  1.当运气来了，没有实力一切免谈；基础不牢，地动山摇。 2.看看前辈们的总结，多吸取教训；即使那是一碗毒鸡汤，你也要有中毒的征兆才行，不然跟喝白开水有什么区别。  3.多反思，多走走，看看外面的世界；想清楚自己要什么，不要在奋斗的年龄选择安逸。 结篇：不要让今天辜负了昨天的努力！

没有面试题，先填写一份个人基本情况表，开始面试时面试官先介绍公司的状况，然后交流会儿就开始面试。都是基本知识，刚出学校出来的毕业生都能简单答出，当然也有一些需要两三年开发经验的问题，不好答。 建议就是诚实作答，不要东拉西扯。

一面需要切分 query string，每个切分如果都在 weight 内，sum 所有的 weight 值，求一个 query string 的最大的 weight 值，如果某个切分其中一个子串不在 weight 内则返回 -1。例如：query: abcdefg, weights: {“a”: 1, “abc”: 10, “bcd”: 11, “cde”: 30, “e”: 3, “fg”: 5} 应该返回 20。切分是 a、bce、e、fg。回答：用 DP 求解，一个 array 存储从 query[:i + 1] 的子串的最大 weight，两个指针 i, j 用于遍历 query string，根据 dp[i - 1] 是否为 -1 判断是否应该继续，如果不为 -1 且 query[i:j] 在 weights 内则 dp[:j] 的值应该是 dp[i - 1] + weight[query[i:j]]。遍历完后结果在 dp[-1] 内。优化：weight 是 hash 的，最坏情况下复杂度是多少？能不能优化。提示说可以用 Trie 树。.1point3acres实现了个 Trie 树。 二面经理面，问了 behavior question：过去的项目经验最自豪的项目是否遇到过和其他团队成员沟通过程中的意见分歧，如何解决。 三面给定一个 words of dictionary， 看一个 word 是不是能通过在任意位置增加一个 char 也能是在 dictionary 内，这样递归下去能组成一个 chain，返回最长的 chain 的长度。 四面英语面试：设计个 tcp reciever 端的逻辑，包括来了一个包应该怎么处理，怎么处理上层的 read 调用。包是无序的，但是不会丢失，而且 size 不固定。五面设计一个跳棋，包括棋盘的布局设计，bondary check，一个子如何走下一步。