谷歌中国（Google）面试经验

HR透過Linkedin聯繫我, 電話面試約莫30分鐘, 主要是Background Check, 都是中文對話, 最後才切換成英文確認英文能力是否ok接著約一周後與Hiring Manager視訊面試. Google會發正式邀請函, 且還會留時間給你做視訊測試, 以確保interview不會有技術上的干擾.第二關約莫45分鐘, 全英文進行Hiring Manger很注重你的邏輯能力, 每回答一個問題就要繼續深究你的答案, 為何如此作答? 你的邏輯是?此職位雖然是Procurement, 但我認為比較偏向Program Manager, 因為會考驗你要如何讓一個產品順利推出, 從Procurement的角度你可以做甚麼?有些問題當初沒準備到, 回答當下也有點緊張, 甚至不是很有自信. 面試完精疲力盡, 同時也知道自己搞砸了! 隔天下午就接到HR的通知不會再Move on(這點真要讚揚Google, Hiring process很有制度且有效率). 雖然挺沮喪的, 不過知道自己哪裡不足, 希望未來有機會再戰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的，整体体验挺好。

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。

最近接到了梦想公司谷歌的面试邀请，先是和HR沟通一些基本信息，投递的岗位和我的经验背景比较吻合，现在已经收到了下一轮时间安排表，正在积极准备接下来和美国那边工程师的视频面试，希望努力付出会有回报加油

分享面经第一道很简单，思路清晰，但是当时太紧张，导致前15s脑子和手下的纸一样。还慌神了一次,好在还是写完了，然后分析复杂性，脑子还没恢复，居然没听懂他让我分析最差情况，现在想起来太丢脸了。。。不过面试官很nice，重复了几遍。然后他提出了对我参数和返回值的疑问，我马上改了下程序。最后, 他变换了条件让我给出解决方案，讨论了一会儿这道题就算结束了。第二道比第一道难些,但是是某经典算法的变种，考虑了一会儿,说了自己的算法,应该没问题，然后要求我编程实现。大脑充血，短路了几次。有些边界情况考虑的不周全，感觉写的过程中飘飘的。