面的是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轮
-
下围棋的场景。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和之前的几乎一样。
-
设计一个贪吃蛇的游戏。给一个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).
-
中午和manager聊天。一个微软过去的亚洲人,介绍组内情况和项目的时候特别自豪,给我的印象挺好的。不算是面试轮
-
给两个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代替,答案是可以。还有个问题忘了。
-
lc128。看了下discussion,发现自己想太多了/没想清楚,用了两个hashmap存数据,写的太复杂了。
-
给一个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。