谷歌两次电面面经

这篇帖子分享我面试18年google暑期实习的经过，包括一点刷题经验和电面面经。

我17年9月-11月比较集中地刷了一些题。在此之前，我在16年也10-12月也刷过题，不过那个时候是随便做做，没有花很长时间。一直到面试前，在leetcode上做过的题大约有300道。其中，我按照知识点，把一些知识点（比如BFS，DFS，二分法，union and find等）的常考题刷了多次。但是还有很多题做完一遍就忘了，我也没有复习。leetcode的discuss中有很多优秀解法，可以参考。
临近面试之前，我买了会员，开始刷leetcode上tag为google的题目。但是这一部分题目增加非常快，有好几百道，而且没有什么定式，很多不能用之前的刷题常用套路来套。所以我只做了所有easy的和一小部分medium的，练了练做新题的手感。据说Facebook的题目很容易碰到原题，而Google有很大的题库，不容易碰到原体。所以面试的时候也有碰运气的成分，看当时能不能想出来了。

第一次电面在十一月份。面试时，面试官会给你题目，但是不像刷题时有定义好的函数让你填，函数要自己定义。我的第一场遇到了原题，是 m

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

录在一个log里。log只能写入，不能删除。
我不是很漂亮地写完了。第二问，是如何改进这两个API。我只好胡说一气。结束后，得知比较好的答案是，time可以用本地的time，而不依赖于传来的time 参数。因为可能有网络延迟。

第二次面试，第二天就告诉我通过了。但是也有很多人是面试完很久才通知的。这是因为面试官feedback有可能给的很慢，不代表每面好。

我觉得刷题的时候，因为不太好撞到原题，所以还是要注意基本功。另外，面试的时候，hangout面试真的比电话面试感觉好太多了。和面试官能互相看到的话，交流会非常顺畅。他们对面试的打分重要的一项就是否擅长交流，占权重的四分之一。

给定一个 tree 和一个 API，要求删除tree中的一部分节点，返回删除节点之后形成的forest。可以对每个节点调用这个API，API会告诉你此节点是否需要删除。比如
  1
/   \
2   3
/    / \
4   5  6
删除 2，5 节点的话， 就要返回 forest
［4，1］
         \
          3
           \.
           6.

1. import java.util.*;
   
2. public class RemoveTreeNode {
   
3.     public static void main(String[] args){
   
4.         RemoveTreeNode m = new RemoveTreeNode();
   
5. 
   
6.         TreeNode root = new TreeNode(1);
   
7.         TreeNode n2 = new TreeNode(2);
   
8.         TreeNode n3 = new TreeNode(3);
   
9.         TreeNode n4 = new TreeNode(4);
   
10.         TreeNode n5 = new TreeNode(5);
    
11.         TreeNode n6 = new TreeNode(6);
    
12.         TreeNode n7 = new TreeNode(7);
    
13.         TreeNode n8 = new TreeNode(8);
    
14. 
    
15.         root.left = n2;
    
16.         root.right = n3;
    
17.         n2.left = n4;
    
18.         n2.right = n5;
    
19.         n3.right = n6;
    
20.         n6.left = n7;
    
21.         n6.right = n8;
    
22. 
    
23.         //            1
    
24.         //         /     \
    
25.         //        2       3
    
26.         //       / \       \
    
27.         //      4   5       6
    
28.         //                 /  \
    
29.         //                7   8
    
30. 
    
31. 
    
32.         System.out.println("Preorder of original tree");
    
33.         m.preOrder(root);
    
34.         System.out.println();
    
35.         System.out.println("------------------------");
    
36. 
    
37. 
    
38.         System.out.println("After remove some nodes");
    
39.         List<TreeNode> ans = m.removeTreeNode(root);
    
40.         for(TreeNode node : ans){
    
41.             m.preOrder(node);
    
42.             System.out.println();
    
43.             System.out.println("------------------------");
    
44.         }
    
45.     }
    
46. 
    
47.     List<TreeNode> removeTreeNode(TreeNode root){
    
48.         ArrayList<TreeNode> ans = new ArrayList<TreeNode>();
    
49.         TreeNode pseudoNode = new TreeNode(-1);
    
50.         //Because pseudoNode is created by us,
    
51.         //it's impossible for removeAPI to remove this node
    
52.         //We create pseudoNode just in case of that removeAPI may remove the root of the tree
    
53.         pseudoNode.left = root;
    
54.         DFS(pseudoNode,ans);
    
55.         if(pseudoNode.left != null)
    
56.             ans.add(pseudoNode.left);
    
57.         return ans;
    
58.     }
    
59. 
    
60.     //the return value of DFS() means whether we want to remove the children or not
    
61.     boolean DFS(TreeNode node, ArrayList<TreeNode> ans){
    
62.         if(node == null)
    
63.             return false;   //don't have to remove this node
    
64.         boolean removeLeft = DFS(node.left,ans);
    
65.         boolean removeRight = DFS(node.right,ans);
    
66.         if(removeLeft)
    
67.             node.left = null;
    
68.         if(removeRight)
    
69.             node.right = null;
    
70.         if(removeAPI(node)){    //removeAPI says we have to remove this node
    
71.             if(node.left != null)
    
72.                 ans.add(node.left);
    
73.             if(node.right != null)
    
74.                 ans.add(node.right);
    
75.             return true;    //remove this node
    
76.         }
    
77.         return false;   //removeAPI doesn't say we have to remove this node
    
78.     }
    
79. 
    
80.     //I use this function to simulate removeAPI
    
81.     boolean removeAPI(TreeNode node){
    
82.         //remove nodes whose values are 1, 3, 6
    
83.         if( node.val == 1 || node.val == 3  || node.val == 6 )
    
84.             return true;
    
85.         return false;
    
86.     }
    
87. 
    
88.     void preOrder(TreeNode node){
    
89.         if(node == null)
    
90.             return;
    
91.         System.out.print(node.val + " ");
    
92.         preOrder(node.left);
    
93.         preOrder(node.right);
    
94.     }
    
95. }
    
96. 
    
97. class TreeNode{
    
98.     int val;
    
99.     TreeNode left;
    
100.     TreeNode right;
     
101.     TreeNode(int val){
     
102.         this.val = val;
     
103.     }
     
104. }
     

复制代码

lovedudu 发表于 2018-3-27 02:57
请问这道题目“你一个dictionary和一个word。让你找出这个word最长的substring，使得这个substring在dictio ...

可以参考蠡口妻舅儿

谢谢楼主分享，“不是CS专业”的能过狗家面试，还是很厉害的。！！

补充内容 (2018-3-27 01:52):
楼主match到哪个组了？

请问这道题目“你一个dictionary和一个word。让你找出这个word最长的substring，使得这个substring在dictionary中出现”楼主是什么思路呢？

edyyy 发表于 2018-3-27 01:40
谢谢楼主分享，“不是CS专业”的能过狗家面试，还是很厉害的。！！

补充内容 (2018-3-27 01:52):

我match到一个做信息提取和storage的组

lovedudu 发表于 2018-3-27 02:57
请问这道题目“你一个dictionary和一个word。让你找出这个word最长的substring，使得这个substring在dictio ...

我直接暴力recursion做了：如果word长度为n，那么先考虑长度为n-1的substring，再考虑n-2的，一直到1
复杂度O(2^n)， 不过没法再优化了

jing_222 发表于 2018-3-27 03:49
我直接暴力recursion做了：如果word长度为n，那么先考虑长度为n-1的substring，再考虑n-2的，一直到1
复 ...

谢谢楼主！

第二题是给你一个dictionary和一个word。让你找出这个word最长的substring，使得这个substring在dictionary中出现。substring的意思是删除原word中任意数量字母之后，剩余的string。比如
dictionary = {inter, te, as, ads, innal}, word = "international"， 那么这个substring就是 innal

請問是找 substring 還是 subsequence ? substring 應該是連續出現在 word 的 string，所以 innal 應該不是 substring，而是 subsequence
假如是找最長 subsequence 的話，為甚麼答案不能是 inter 呢? 它的長度和 innal 都一樣是5

lf963 发表于 2018-3-27 10:48
第二题是给你一个dictionary和一个word。让你找出这个word最长的substring，使得这个substring在dictionary ...

你说的对，是subsequence。inter也是对的~