谷歌中国（Google）面试经验

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

（美国的面经不能选，只好选北京了）3轮代码面试，不能透露具体的题目，考察的知识点是：生成所有子集树的Recursive Traversal并查集Tree结构和Hash结构的比较，什么时候用啥，为啥，实现一个常见数据结构（最快速度下只耗费必要空间）。 面试经验是： ＊好像面试官在面纯code时候根本不问简历的东西，连问一两句都不问。我觉得一个是不影响结果，另一个是面试官不想浪费你时间，所以更要加油看45分钟的时间可以做完多少了。 ＊沟通挺重要的，我每要实现一个啥的时候，如果先和面试官说我要怎么写，如果比较机械或重复，往往他都说ok我明白了你可以跳过。这样可以省很多时间和不必要的detail tuning。 ＊G家好像面经没啥用，因为面试官太多了，没有统一口径。但我遇到的面试官都挺nice的，整体体验挺好。

一面 先是通过腾讯会议与直接领导一对一面试，要求做PPT自我介绍。自我介绍后提了两个简单问题，很满意。和直接领导及部门主任现场面试。仍然是自我介绍，这回将得更具体。之后提了几个比较深入的问题，回答得很满意。谈工资。

今天Google家结束了，两轮背靠背+加面，真的也是准备了很久，说过面完写一下心得分享一下自己总结的资料，所以前来兑现。也不知道结果如何，感觉心理已经很坦然了，挂就挂了，能过自然高兴，看天意了，毕竟已经尽力了。首先说一下狗家的简历。以前是只要有内推，就至少给一个面试的机会，但现在不是了，还是要看简历的。关于简历的事情，额，我算是有些心得吧，在Facebook那个总结贴写了一些，但很多人问过我udemy的问题，具体的我也没有时间一个个回答，前几天地里的坛主找过我说想要我写一下分享一下，等我找到实习后就给大家写一下，看地里真的好多同学都因为简历的事情苦恼，希望到时候帮助到一些同学。然后就是面试了。狗家的面试我认为，是所有大公司中，最难的，没有之一。题库大，没有规律可循，碰见题的难易程度完全是靠人品决定。人品好的遇见国人哥哥姐姐就放水，这里说一下狗家的国人真的是非常友好，大多数帖子国人出的题真的比平均水平简单。人品不好的连题都看不懂，或者一个题能把A4纸都写满，理解完题的意思就20分钟过去了。所以面狗家的同学们，做好心理准备，可能你面的题感觉就是全程高能，因为你面的是Google。

Garena 儲備幹部共有四關，履歷、筆試、人資面試、總經理面試履歷關基本上有過不錯的比賽或實習經歷就可以過關，筆試的部分網上很多模考題可以刷，最難的應該是人資面試人資面試主要看中的是人格特質跟公司的向性合不合，建議可以多做準備

1，一颗n叉树，从树的root(顶上)倒水下来，水从每个node到下面的node都有特定时间，求把整个树都浸润的时间Follow up，如果是个undirected graph，每个node到node的关系想象成一个pipe，从一个node放水，求把所pipe填满的时间。 2，给你一个rectangle，随机返回这个长方形里的一个点。给你一个list of rectangles，每个rectangle有两个顶点，求随机生成一个point within the area of those rectangles。 3，inorder traverse两棵树，看两棵树inorder traverse的结果是不是一样。 4，引入一个概念，random binary search。就是说mid不取中点了，随意取当前search range里的一个点。给你一个input array，unsorted，求这个array里面，用random binary seaech一定可以求得的targets。 5，sqrt。传统九宫格键盘打字，给你一个字典，里面有很多单词(String)，通过输入九宫格里的数字，返回所有的字典里面的candidates。merge sort，quick sort，bucket sort时间空间复杂度，优胜劣汰，什么情况用哪个，还给你几个情况让你选择用哪个sort。