[Google] Google兄弟公司Verily面经和包裹

Job Hunting Interview
, , , , ,
#1

面的是Alphabet下面的子公司Verily。性质和Waymo一样。名气稍微小一点。不过今年初拿到了1B的funding，现在在扩招。面试难度流程和Google基本一样。不过我碰到的题难度还是偏简单的。

电面：1. n ary tree. 用水从root往下倒。每条边有个value代表的是粘度即停留的时间。问wet 所有的leaf node需要多久。相当于求root到leaf的max sum，并且假设root.val = 0。 followup：按水到达每个点的顺序来输出所有的点。我是用hashmap来记录sum对应的所有点，即key是int代表sum，value是List代表从当前点。遍历tree，build map的同时记录一下sum的最大值和最小值。最后[min, max]遍历找map里的node。写完之后还提了一下可以用best first search以及时空复杂度

onsite: 5轮

  1. 下围棋的场景。m * n的grid。里面有白棋(0表示，自己定义的),黑棋(1)。implement一个api。input是m*n的2d int array和一个坐标点(两个int, 第几行和第几列)。return type是boolean。check一枚黑棋(可以保证给的坐标上一定是个黑棋)是不是被白棋包围了，被边界包围了也是true。只有当前点的connected graph连接到没有空(-1)的坐标(还没有被下棋)的情况下才return false。solution是一个dfs。碰到空格return false。碰到白棋或者边界return true。follow up，如果给的坐标不能确定是白棋黑棋或者空格。判断当前各自上的棋是不是被另一个颜色的棋包围了。空格的话直接return false。solution，传入一个initial node的颜色就可以了。code和之前的几乎一样。

  2. 设计一个贪吃蛇的游戏。给一个n*m的grid。初始状态，蛇的长度是1，坐标是最中间的位置，朝向是北。蛇的方向可以变，需要自己设计。游戏里面有苹果，蛇吃了苹果长度会+1. 当蛇头撞到边界或者撞到自己的身体游戏结束。需要自己定义苹果的出现，苹果如果被吃了必须要random的generate出来一个新的苹果，而且位置不能是蛇身体所在的位置。solution是，用一个int表示蛇头，一个int表示方向，一个queue来存蛇所有occupy的位置。三个method，move(), changeDirection(), generateApple(), 每次move()，先判断是不是terminate，再判断有没有吃到苹果，然后把蛇头下一个坐标offer进queue里。changeDirction(), 用0-3表示北西南东，对于当前dirction，每次+1 or -1，注意不要越界。苹果的话用一个random函数生成坐标，如果被蛇身体占据了就继续random生成。(这里面试官有问过优化，可以把空余的坐标存下来然后random pick一个，不过让我implement简单的那个方法了)。follow up，如果grid特别大，蛇身体特别大怎么办。solution，对于蛇身体occupy的坐标同一行，同一列的可以只记录起始和结束的点的坐标。例如，用两个hashmap，一个存row，一个存col。value的话用List<List>, (这里我回答错了，没有考虑到同一行/列可能会有不连续的几段出现，有点gg).

  3. 中午和manager聊天。一个微软过去的亚洲人，介绍组内情况和项目的时候特别自豪，给我的印象挺好的。不算是面试轮

  4. 给两个string。target = “boom”, lyrics = “everybody is looking for something”. 判断一下target能不能从lyrics的word中组成。每个单词最多只能用一个字母。solution: brute force的方法。每个check一下。当时觉得可以优化，当时没找到方法，提了一句用trie，但是和面试官讨论了一下发现更加worse。follow up，如果要求只能在连续的k个单词中找，fixed size sliding window。solution，preprocess一下所有的单词的unique的字母。用hashset，key是word的index，value是set，里面存该单词所有出现过的字母。最后问了几个问题，一个是hashmap能不能用array代替，答案是可以。还有个问题忘了。

  5. lc128。看了下discussion，发现自己想太多了/没想清楚，用了两个hashmap存数据，写的太复杂了。

  6. 给一个m*n的grid。每个坐标放一个server，有开启和关闭的状态。如果server在同一行或者同一列，server中的数据可以相互传输。要保留所有的server的数据，至少要开几个server。solution，需要存每个server col的信息。对于每个row判断一下需不需要放一个server。一开始想太多了，implement的有点复杂，答得比较一般。。。

XOOXO X代表运行的server

OXOOO O代表关闭的server。

OOOOO result = 2. 只需要保留两个server就可以存下所有的数据，右下的数据可以传到
OOOXO 同列第一行的server，这个server又可以把数据春到左上角的server，最后保留两个server。