谷歌中国（Google）

首先过去面试，会先让你做一份笔试题，笔试题难度一般，最后一题是写表关联的sql语句，没有编程题。有几道逻辑选择题，其他都是java基础题。做完笔试题，会过来给你面试，会根据你笔试的情况以及简历内容问你一些java基础问题，难度并不大。

一面需要切分 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，一个子如何走下一步。