谷歌中国（Google）

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

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

从下沙做了一个多小时地铁赶到了萧山，办公环境不错，跟前台打了招呼说是面试的后，在沙发等待了五分钟左右，就去面试了。 第一个问题是你知道synchronized关键字吧，那你知道在方法中加了static和没加有什么区别吗？答：synchronized是对当前实例进行加锁，如果加了static则是对该类的所有的对象加锁 。        第二个问题是你知道mysql的隔离级别吗？答：读未提交、不可重复读、可重复读、串行化、         还有第三个问题忘记了，感觉回答的还可以。 重点来了，接下来的就是你有什么想问我的吗？这么快就结束了？估计才五分钟吧，我问了问题后感觉面试官也是很水的回答了下，大致就是我在这面了三天了，很无聊。面试过十几家公司，这算是最不尊敬面试者的，一般的面试持续半小时不过分吧，结果这次就持续了五分钟。

过去面试的时候，看到他们公司的很多东西都是没装上去的，以为是公司刚搬过来，而他们告诉我说是公司正在装修，可没看到装修师傅，先是个人介绍，面试的是两个人一起来的，可没有人事来，问了几个问题（时间有点长，题目忘了，不过是一些跟基础差不多的题目）有些没回答上来。

笔试,笔试题不是特别难,不过面试的时候会问到笔试题的,介绍下自己的项目,问点基础,对你项目中出现的问题是怎么解决的,然后就是数据库的SQL语句,笔试题的最后一题是SQL题,比较坑,当时没做出来,给面试官讲了讲思想也行。

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

实现一个带加权的随机生成器。面试官很好，题目不难，有一些附加问题，总体感觉不错。比如，给出一系列字符串，red，red，red，green，green，yellow那么，每运行一次随机生成器，就会返回其中一个字符串，概率为3/6， 2/6， 1/6。