Google 12/01 onsite面经

土木硕士转专业，Google是第一家给onsite的。面试在kirkland，整体过程不算非常困难，总感觉google的面试（甚至所有IT公司的面试）都有从题目易懂但算法难想向题目综合，问题复杂但算法知识要求降低的变化趋势。传说中Google最爱的DP完全没有遇到，倒是图，树，DFS，BFS这些比较容易结合具体问题的知识点考了很多。发面经求好运。

时间线

•          15th Oct – 内推

•          17th Oct – 收到OA

•          23rd Oct – 完成OA

•          31st Oct – 收到HR邮件OA通过，没有电面直接onsite。和HR通电话准备下一轮

•          20th Nov – 和工程师Coaching Call。介绍onsite内容，考核点，注意点

•          2nd Dec - Onsite

•          19th Dec – HR通知HC过

面试题

OA

10月的OA依然是那两道经典题。

1. Given a number(of type string, decimal) greater than or equal to 10, for each two adjacentdigits, take them out, calculate the average ((floor(a + b) /2 ) of them andput the digit back. Output the maximum possible value (of type string).

题目说明不需要考虑效率问题只需要考虑正确性，因此brute force，直接字符串操作就可以，不需要考虑字符串split和combine的效率问题。题目规定了数字大于等于10，因此边界条件也不太需要考虑。

2. LC 388 变种。题目要求可能不同（诸如输出包括文件名最长的路径，不包括文件名最长的路径，包括图片文件最长的路径等）。

具体方法是stack和dfs。扫描输入并对于每一个文件夹或文件计算出当前路径的长度，同时用另一个变量记录所有满足条件的最长的路径的长度。需要注意的是根目录的边界情况，因为题目要求根目录是”:\”，根目录下某一子目录的路径是”:\subdirectory”，所以实际上根目录比其他目录长度多1.

Onsite

1. 白人大叔。聊了聊专业，上过的课，介绍了一个project。开始做题。

Museum map: Given a map (oftype char[][]) of a museum where ‘.’ stands for an empty room, ‘G’ stands for aguardian and ‘L’ stands for a locked room. A guardian is able to reach neighboring(up, down, left, right) empty rooms in 1 move, but can not enter a locked room.Return how many moves the nearest guardian has to take to reach each emptyroom. The return value should be an int[][] whose size is the same as the inputmap. For an empty room mark the corresponding cell with -1 and for a guardianmark with -2.

讨论：地图是不是永远valid，是不是静态的，是不是可以放到内存里；guardian的数量相对于整个地图room的数量是不是trivial的。

回答：地图永远valid，静态的，可以放倒内存，guardian数量远远小于room的数量。

我的做法：一开始想法是对于每一个guardian做一次bfs，得到他到每一个room的距离，然后把所有guardian的bfs结果汇总，对于每一个room取最小值作为结果输出。面试官说可以让写code。

写完发现bfs中有一个变量有bug，经提示改正。面试官说code应该是对的，但是不够efficient。我说似乎可以在一开始把所有的guardian加到bfs的queue中，然后一次dfs就可以完成。面试官说可以。没有要写code。让我问了些问题，第一轮结束。

2. 白人大叔和白人小哥一起。

题目：Given the root directory of a file system (represented by an-ary tree), return all the directories and files (return as List<Node>).

讨论：具体的Node的表示方法，输入不合法需不需要handle等。

回答：可以用类似Leetcode那种方法表示，需要handle不合法输入（该情况下其实只是根节点是null）。

我的做法：用Queue implement一个BFS完成。

跟进 1: what if the file system has symbolic links? (i.e. the tree isnow a graph). 要求在原来的代码上进行修改。

我的做法：保存一个hashset表示已经访问过的节点避免重复。

跟进2: reconstructthe file system in another drive w/o the symbolic links (i.e. deep copy thetree)

我的做法：将上述hashset改为hashmap，key是原来的树里需要copy的节点，value是复制后的节点。依然用BFS进行deepcopy。

跟进3: What isthere are symbolic links? (i.e. deep copy the graph)?

讨论了一下做法，依然保留上述hashmap，如果hashmap中有的key-value-pair就不需要复制。没有需要写code。

3. 午饭。Google kirkland的食堂叫Hashtable，如果来面试的话里面的pad thai值得一试。

4. 国人大姐。聊了一下做过的project当中的难点，以及如何解决的。

题目：Given a sidewalk with length 100.0, and a stream of rain drops,assuming the length of a rain drop is 1.00 and the rain drop could fall randomly anywhere w/in the sidewalk, return the number of raindrops untilthe sidewalk is all wet.

讨论：raindrop stream是不是无限的，raindrop stream api的形式，raindrop会不会滴到sidewalk以外，区间开闭等。

回答：是无限，类似Iterator，不会滴到sidewalk以外，区间为闭区间。

我的做法：一开始不太有想法，想到是区间问题可能是用树比较合适，跟面试官讨论面试官说可以你先写写看（这里吐槽一下google的面试官，大多情况下只要我有想法都会说你开始写吧，而不会先讨论清楚具体怎么写）。写着写着发现用treemap确实可以写的通，用treemap存sidewalk上已经湿了的区间，其中key是区间左端点，value是区间右端点。对于新的raindrop调用treemap的api ceiling和floor找到左右区间，分类讨论看能不能和左右合并并分别处理。写完跟面试官交流，被面试官质疑分类有不完整的地方，检查了一下做了修改，和面试官讨论通过。

跟进1: 如何测试。

我的做法：新雨点不和旧区间overlap：raindrop左端点的位置依次是0.00, 1.00, 2.00…，返回值应该是100. 测试新雨点与左边区间overlap: raindrop左端点依次是0.00，0.10，0.20，…，返回值应该是1000. 测试新雨点与右边区间overlap:99.0, 98.5, 98.0 …；新雨点与旧雨点完全重合：0.00，0.00，1.00，1.00……等

跟进2: 时间空间复杂度

一开始我说时间是O(lgn), n是树里面的区间的个数，空间是O(n)。面试官说再看一看条件，发现树里面的区间不可能超过100个，因此时间空间复杂度都是O(1).

5. 国人大哥。聊了聊过去project中自己觉得最有意思的地方。

问题1: Giventhe root of a tree and a list of nodes that are about to be erased, return theforest (represented by a list of root nodes) after the erase.

我静静思考了几秒钟面试官立刻说你需要 think out loud. 于是开始胡言乱语说BFS，用Queue，又说erase好像不是很好操作，因为erase的节点的孩子还是要继续访问的，但是孩子又有可能是被erase的……可以在bfs出队的时候对孩子进行判断，但是又好像不太对……面试官看不下去了说你的想法应该可行，开始写code吧。写完拿了一个例子walk through可行。

跟进1: 如何测试。

我的回答：空树，[1,2,3]完全树根节点被erase，左子树根节点被erase，右子树根节点被erase，只有左子树左子树被erase等等。面试官说还需要测根和左子树都被erase。我说您说得对啊。

问题2: Given alist of Iterators, Design a class which implements the interface Iterator (i.e. include hasNext() and next()), which woulditerate through the iterators in a round-robin way. E.g., [[1, 2, 3], [4, 5, 6], [7, 8,9]], next() 依次输出1, 4, 7, 2, 5, 8, 3, 6, 9.

我的做法：存一个deque，每次next()从队首deque一个iterator，call这个iterator的next(), 如果空了就扔掉，还有下一个就再加到队尾。

跟进2: 如果还需要hasPrev()和 prev() 怎么办。

我说，那就反过来好了从后面deque从前面enqueue.面试官说不行，因为你有些iterator到头了就扔掉了。我说那不扔，他说还是不行，比如[[1, 2, 3], [4], [5, 6, 7]]就会有问题。我想了半天没听明白为啥接着问，他又解释了一遍我好像明白了，我说那再加一个variable表示iterator到了level，他说可以，没有写code。

总结：Google Kirkland的环境确实好，国人和白人很多，人也都很nice，做的project偏cloud和一些内部的technical support。整个组比较精干，work life balance 很好。但是headcount很少。HR已经通知我说今年没有hc所有office都只有MTV在招人了。作为本地人LZ还是想留在本地所以最近还在接着面本地其他厂。求好运o(≧v≦)o。

Onsite 1, 一遍BFS

1. struct point {
   
2.     int x, y;
   
3. 
   
4.     point(int a, int b): x(a), y(b) {}
   
5. };
   
6. 
   
7. vector<vector<int>> bfs(vector<vector<char>> &map)
   
8. {
   
9.     size_t row = map.size();
   
10.     size_t col = map[0].size();
    
11. 
    
12.     vector<vector<int>> result;
    
13.     for (size_t i = 0; i < row; i++)
    
14.         result.push_back(vector<int>(col));
    
15. 
    
16.     queue<point> q;
    
17. 
    
18.     for (size_t i = 0; i < row; i++) {
    
19.         for (size_t j = 0; j < col; j++) {
    
20.             if (map[i][j] == 'G') {
    
21.                 point p(i, j);
    
22.                 q.push(p);
    
23.                 result[i][j] = -2;
    
24.             }
    
25.         }
    
26.     }
    
27. 
    
28.     //up, down, left, right
    
29.     vector<vector<int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
30. 
    
31.     int d = 1;
    
32.     while (!q.empty()) {
    
33.         size_t size = q.size();
    
34.         for (size_t i = 0; i < size; i++) {
    
35.             point p = q.front(); q.pop();
    
36. 
    
37.             for (auto dir : directions) {
    
38.                 int x = p.x + dir[0];
    
39.                 int y = p.y + dir[1];
    
40. 
    
41.                 if (x >= 0 && x < row && y >= 0 && y < col) {
    
42.                     if (map[x][y] == '.') {
    
43.                         if (result[x][y] == 0) {
    
44.                             result[x][y] = d;
    
45.                             q.push(point(x, y));
    
46.                         }
    
47.                     } else if (map[x][y] == 'L')
    
48.                         result[x][y] = -1;
    
49.                 }
    
50. 
    
51.             }
    
52.         }
    
53. 
    
54.         d++;
    
55.     }
    
56. 
    
57.     return result;
    
58. }
    
59. 
    
60. int main()
    
61. {
    
62.     vector<vector<char>> map = {
    
63.         {'G', 'L', 'L', '.'},
    
64.         {'.', '.', 'G', '.'},
    
65.         {'L', '.', 'L', '.'},
    
66.         {'.', 'G', 'L', 'G'},
    
67.         {'.', '.', '.', '.'},
    
68.     };
    
69. 
    
70.     vector<vector<int>> result = bfs(map);
    
71.     for (size_t i = 0; i < result.size(); i++) {
    
72.         for (size_t j = 0; j < result[0].size(); j++) {
    
73.             cout << result[i][j] << " ";
    
74.         }
    
75.         cout << endl;
    
76.     }
    
77. 
    
78.     return 0;
    
79. }

复制代码

写一个LC388的,　这现场真是很难写对

1. class Solution {
   
2. public:
   
3.     int lengthLongestPath(string input) {
   
4.         size_t i = 0;
   
5.         int max_len = 0;
   
6.         int cur_len = 0;
   
7.         vector<int> levels;
   
8.         bool is_file = false;
   
9.         size_t indent = 0;
   
10. 
    
11.         while (i < input.size()) {
    
12.             if (input[i] == '\n') {
    
13.                 i++; //skip '\n'
    
14. 
    
15.                 int len = cur_len + 1;
    
16.                 if (indent > 0)
    
17.                     len += levels[indent-1];
    
18. 
    
19.                 if (indent == levels.size())
    
20.                     levels.push_back(len);
    
21.                 else
    
22.                     levels[indent] = len;
    
23. 
    
24.                 if (is_file && len > max_len)
    
25.                     max_len = len;
    
26. 
    
27.                 cur_len = 0;
    
28.                 is_file = false;
    
29.                 indent = 0;
    
30. 
    
31.                 while (i < input.size() && input[i] == '\t') {
    
32.                     indent++;
    
33.                     i++; //skip '\t'
    
34.                 }
    
35.             } else {
    
36.                cur_len++;
    
37.                if (input[i] == '.')
    
38.                     is_file = true;
    
39.                i++;
    
40.             }
    
41.         }
    
42. 
    
43.         if (is_file) {
    
44.             int len = levels[indent - 1] + cur_len;
    
45. 
    
46.             max_len = max(len, max_len);
    
47.         }
    
48. 
    
49.         return max_len;
    
50.     }
    
51. };
    
52. 
    
53. int main()
    
54. {
    
55.     Solution s;
    
56. 
    
57.     string input = "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext";
    
58. 
    
59.     cout << s.lengthLongestPath(input) << endl;
    
60. 
    
61.     return 0;
    
62. }

复制代码

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

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

第二轮 “可以用类似Leetcode那种方法表示” 具体是leetcode哪一题啊？

wtcupup 发表于 2017-1-4 13:52
第二轮 “可以用类似Leetcode那种方法表示” 具体是leetcode哪一题啊？

说的是Leetcode对树的节点的表示方法哈，
class Node {
    String name;
    Node[] next;
}
这样。

这我学弟，特意来支持一下

独魔圣剑 发表于 2017-1-4 13:58
这我学弟，特意来支持一下

学～～～～长～～～～

大师我来支持你啦！！！！

OA第1题是如下这么个意思吗?

比如: 3208,有３种可能
1. floor((3+2)/2) = 2, 得208
2. floor((2+0)/2) = 1, 得318
3. floor((0+8)/2) = 4, 得324

所以最大可能值是324

minggr 发表于 2017-1-4 14:23
OA第1题是如下这么个意思吗?

比如: 3208,有３种可能

恩对的哈

momoly27 发表于 2017-1-4 14:19
大师我来支持你啦！！！！

刷题小分队加油！