谷歌中国（Google）

上来简历寒暄5min。剩下40min 做两题。 1. use one loop to print out the content of 2D array/list - 难点在于 list 的每一行size 可能不一样 2. A-B 朋友，B-C 朋友 => isFriend(A, B) == T, isFriend(A, C) == false, isAcquisition(A, C) == true。用 unionFind

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

本来要面四轮，结果面了五轮，两轮design，三轮算法。 一个烙印，看上去是manager，面的算法，不太好。 一个白人，面的design，也不太行 三个中国人，面的都还不错