onsite4轮
1.Number of islands变种，如果多一个陆地，找到最大的岛屿（BFS）
2.矩阵走路问题，从左下角出发，只能向上或者向右，问有多少种方法走到某行某列， follow-up：有多少种方法走到某一列， 有多少种方法走到某一列，并一定过其中的某些点/不过某些点
类似面经题， DP
3.生成随机迷宫，要求从起点到终点只有一条path（DFS）
面经题
4.高频smashable string
可能是471，得做
加面题：
1.给一个很大的文件，以及一个query list，query要求把某个string替换成别的string，输出转化后的文件
2.tweak identical， follow up如何剪枝优化
得找
----------------------------------------
https://www.1point3acres.com/bbs/thread-477628-1-1.html
前几天去G家onsite，其他题都还好，就这个题不是特别会，只想出了DFS的解法，想问问大家有什么更好的。
已知有一消息在一群人中间传播。消息从A发出。比如 A->B A-> C A->D B->E B->F C->E，请自行设计数据结构并回答下列问题
1）如果每个人至多从一个人那里得到消息，那么A如果不把此消息传给谁会使最少的人得到此消息。
是个Tree，找A的子结点的最大的树
2）如果取消这一限制至多一人的限制，又该肿么办呢？
是个graph，找所有只能连接到A的点。从A的neighbour出发，每遇到一个点要degree - 1，(额外用一个set来记录被A走过edge), 最后找degree为0的个数
网上另一个方法，更简单:
两个数组value(I)，表示节点I是从A的那个儿子访问到的，初始-1
visited(I)表示I节点是否访问过，初始false
for loop节点A的儿子们：
reset visited数组全为false
出发做DFS，经过的每个节点都：
标记visited true
如果value为-1，更新为A的当前儿子的值
否则，更新为-2
最后找出谁最多就是答案，这里面也可以另外弄个数组记录每个儿子节点的染色个数，最后就不用再统计一遍了。
时间复杂度O(n^2)
这个解法关键在于找出有两条及以上信息来源的子节点
private static String findId(Node node) {
Map<String, String> values = new HashMap<>();
for (Node n : node.neighbor) {
Set<String> visited = new HashSet<>();
dfs(n, n, values, visited);
}
Map<String, Integer> rt = new HashMap<>();
String max = "";
for (String id : values.values()) {
rt.put(id, rt.getOrDefault(id, 0) + 1);
if (max == "" || rt.get(max) < rt.get(id)) {
max = id;
}
}
return max;
}
private static void dfs(Node root, Node node, Map<String, String> values, Set<String> visited) {
for (Node n : node.neighbor) {
if (!visited.contains(n)) {
visited.add(n.id);
if (values.containsKey(n.id)) {
if (!values.get(n.id).equals(node.id)) {
values.put(n.id, "");
}
}else {
values.put(n.id, root.id);
}
}
}
}
----------------------------------------https://www.1point3acres.com/bbs/thread-477625-1-1.html
2019 Google 国内 summer intern 面试中……
前面两轮一面表现不好，第一次面试说话语无伦次，而且最后也没有给出一个面试官想要的答案，但是我也不知道为啥给我发了二面邀请。听说可能因为（划重点） [/hide=200]和面试官交流很多！！！[/hide]
二面是MTV的小哥给我做的面试，还挺顺利，先问了[/hide=200]一个用stack来删除重复连续字母的题，时间来得及就让我讲了一下一题binary tree思路，大概意思是n个节点有多少种排法。。。因为讲思路嘛……就好过一点。而且一样，全程基本没有冷场的尴尬，就算说不出来，你也可以慢慢和面试官剖析一下题目[/hide]
送了HC以后反馈是加面。。。fine 而且因为我寒假结束回美国上课，时间问题，可能安排英文面试。看了论坛面经感觉被提到的题目跟我的就不是一个难度=。=求英文的面经？？
以及，新人多赏我点米
不懂
----------------------------------------
https://www.1point3acres.com/bbs/thread-477619-1-1.html
就是让我做各种关于tree的operation ex. in order traversal, post traversal之类的
后面给你一个tree root, 一个bst变成的array 把他从上到下变回原来的array, tree的结构不变
第二个面的是印度小姐姐 问了好几遍才听懂她讲的
也是很简单 把一个单词里有可能打出重复的letter删掉看dictionary里有没有match的 ex. whaaaaat -> what
dfs + combination
----------------------------------------
https://www.1point3acres.com/bbs/thread-477503-1-1.html
狗家昂赛 题好难 感觉已挂
有一个大小为n的数组，一个大小为k的窗口，1<k<=n, 窗口在数组上slide，每到一个位置去掉数值大小前x% 和后x%的数，
然后求剩下的数的均值。对每一个窗口算一次，最后output出一个数组。求一个 nlogn的解法。。。
2个priority queue
类似480
----------------------------------------
https://www.1point3acres.com/bbs/thread-477414-1-1.html
昨天收到狗家过HC的消息，今天来地里发个面经造福一下大众。是1月18号去狗家面试的，因为1月14号面了EA然后HR当时已经给了口头offer，所以心态特别好地去了（顺便吐槽一下狗家的效率，EA当天面完第三天就给了口头offer，正式offer1月22号就出来了，狗家面试完后两个星期才刚过HC，然而EA这边的ddl快过了，蛋疼）
以下内容需要积分高于 160 您已经可以浏览
一共四轮
第一轮是给一个二叉树，然后再给一个list的TreeNode，这个list里的TreeNode是肯定在二叉树里的，然后要把这些TreeNode删除，最后返回一个原二叉树删除这些TreeNode后得到的Forest
举个例子，如果二叉树如下：
A
/ \
[B] C
/ \ \
D E [F]
方括号内的TreeNode是要删除的，最后返回的Forest是[A, D, E]。
这道题我用recursion做的，输入参数一个是TreeNode，一个是它的parent是不是被删除的boolean。然后要我给出不同的test case
Solution, 打印出所有不跟原root连接的root node（包括原来的root），
2种方法,dfs,bfs
public static void main(String[] ss) {
Node a = new Node("A");
Node b = new Node("B");
Node c = new Node("C");
Node d = new Node("D");
Node e = new Node("E");
Node f = new Node("F");
a.left = b;
a.right = c;
b.left = d;
b.right = e;
c.left = f;
Set<Node> deleted = new HashSet<>();
deleted.add(b);
deleted.add(a);
deleted.add(d);
List<Node> rt = getForest(a, deleted);
for (Node n : rt) {
System.out.print(n.id + " ");
}
}
private static List<Node> getForest(Node root, Set<Node> deleted) {
List<Node> rt = new ArrayList<>();
dfs(root, null, rt, deleted);
// bfs(root, rt, deleted);
return rt;
}
private static void dfs(Node root, Node parent, List<Node> rt, Set<Node> deleted) {
if (root == null) return;
if (!deleted.contains(root) && (parent == null || deleted.contains(parent))) {
rt.add(root);
}
dfs(root.left, root, rt, deleted);
dfs(root.right, root, rt, deleted);
}
private static void bfs(Node root, List<Node> rt, Set<Node> deleted) {
Queue<Node> que = new LinkedList<>();
que.add(root);
if (!deleted.contains(root)) rt.add(root);
while (!que.isEmpty()) {
Node n = que.poll();
if (n.left != null) {
que.add(n.left);
if (deleted.contains(n) && !deleted.contains(n.left)) rt.add(n.left);
}
if (n.right != null) {
que.add(n.right);
if (deleted.contains(n) && !deleted.contains(n.right)) rt.add(n.right);
}
}
}
第二轮是面经高频题，Google Snapshot，这里就不赘述了
实现三个functions， get, set, take snapshots。其实就是一个长度为N的Array。Set可以设置Index i的值，每次take snapshot， version + 1，并且记录下当前version下 Array里面的值。然后get方法可以得到某一个Version下，每一个Index的Array的值。就是非常Naive的方法，在Chromebook上写完了。写完之后有一个变量名Typo被指出。口头跑了Test case。Follow up 时空复杂度，并且要节省空间。
举例
初始 100001
take a snapshot 返回sid 1
改变成 100201.
take a snapshot 返回sid 2
这时lookup get（3，1）（ get(index, snapshotID)）应该返回0而不是2，这是version control的原理可是关键在怎么存最省空间
可以参考视频压缩，每隔若干帧保存一份完整的图像，期间只保存delta。重建图像的时候，从最近的full snapshot开始，然后apply 每个version的delta
第三轮比较简单，给一个Integer，n，形成一个List<Integer>，包含1-n的所有元素，每个元素代表一辆车的车速，最后会形成车队，要返回的是每个车队的车数。举个例子，[2,4,1,3]，最后返回的是[2,2]，因为前两辆车会被第一辆车的车速2所限制，而后两辆车则会被第三辆车的车速1限制。再举个例子，[1,2,3,4,5]，最后返回[5]。[2,4,5,3,1]，返回[4,1]。
类似853，但更简单
Follow-up是在原List<Integer>插入n+1，然后返回所有的车队车数可能性。最后问了算法复杂度
第四轮比较难，出了我不大擅长的dp，说给一个m x n的矩阵，可以横着切或者竖着切，每横着切一刀的cost为被切矩阵的列数的平方，每竖着切一刀的cost是被切矩阵的行数的平方。然后给一个desired area，问切到这个area大小最少的cost是多少。好像切好以后两个矩阵都能继续切，差点没做出来，还是弱鸡啊
是求全局最小值，换句话假设这次我选择横着劈，将原本m x n的矩阵劈成了k x n和(m-k) x n，如果desired area是A，那么我需要做的就是cost = Math.min(cost, n^2 + func(k, n, a) + func(m-k, n, A-a))，a是从0遍历到A，k是从1遍历到m/2。然后再切换成竖着劈，再求cost。其中func就是要implement的函数
----------------------------------------
https://www.1point3acres.com/bbs/thread-477333-1-1.html
第一轮白人 easy, 两个list a b，输入两个list，第一个list a中有，b中没有的元素，第二个b中有a中没有的元素。map做。。。没了。。。聊天
一个map应该可以做
第二轮白人 easy，一个int[] 表示电影院一排，坐满情侣，00 11 22。。数字相同表示一对，现在坐乱了，怎么然他们坐在一起，最少swap，直接两个两个扫，发现不对就去后面找，然后swap，没了。。。聊天。。
第三轮白人not easy for me，因为我笨。。设计限流器，好像利口有，我用map存处理的过的key和时间。后来问怎么清除内存。反正没答上来。。。后来直接告诉我用bucket存，过了时间就直接清除。。。我真的笨，又没咋写代码。。。写了几行
359
第四轮白人 easy判断矩阵是否toplitz。。。你没看错。。拓展矩阵太大，每次处理10行，实现代码，没啥变化，不过我写的code全是bug，再也不能用他给的chrome windows。。
766
第五轮白人 easy？ 实现auto complete，其实就是说出trie。。。that's it。。。利口好像也有。聊了40min，写了几分钟代码，都没写完，面试官说没时间了不写了，我就不写了。。。
642
总体基本都是easy，都是聊天，代码不多，还被我写出了很多bug。谷歌面试就是随缘，心态放轻松，白人就跟他聊就对了，亚裔中国人就跟他飙利口bug free就够了，印度人就猜他心里想的啥，，按照他心里的想法，千万别反驳他就对了。
----------------------------------------
https://www.1point3acres.com/bbs/thread-477290-1-1.html
今天下午面的Google 全职电面 面试官感觉像个国人大哥 挺nice的 题也不难 但是一开始想复杂了
给两个长度一样的string A，B 把他们对齐切一刀 这样就得到了A1 A2 B1 B2 四个substring
写一个func check 能不能找到这一刀 A1和B2 拼起来 或者A2和B1拼起来能组成parlindrome
e.g. A = "abcbbbb" B = "xxxbcba" 那么在第三个char之后切一刀 A1 = "abc" B2 = "bcba" 拼起来 "abcbcba" 那就返回true
如果找不到这一刀返回false
. 1point3acres
followup 是如果两个string不对齐 切的话 比如 A可以在第一个char之后切 B可以在最后一个char之前切 这样他们能组成 "aa" 也是parlindrome
问题是怎么切这俩string 能让组成的parlindrome最长
感觉用正常的two pointers就能做了 一开始没申清题花了点时间 然后有个case没考虑 面试官也提醒了下 之后打code的时候把速度放慢了点 顺带着解释 虽然也没啥好解释的 就尽量interact 所以后面没啥时间 followup时候就讲了idea怎么实现 没具体写code了 希望能给个旅游的机会吧
----------------------------------------
https://www.1point3acres.com/bbs/thread-477289-1-1.html
recruiter去年十一月就找我了，结果一直拖到现在。由于面过一次onsite，这次就没有电面，直接onsite了。去年给我的onsite安排是"3 will focus on Python coding, data structures & algorithms. 2 will focus on general computer science fundamentals and problem solving". 以为还有系统设计，毕竟也工作了将近4年。结果昨天面试发现5轮全是算法，早知道就不急着准备系统设计了，还能多花点时间刷刷题。
anyway...
第一轮：
1. 输入一些subiterators, 合成一个superiterator, 都是升序的. 类似LC 23 Merge k Sorted Lists. heap搞定.
2. LC 253 Meeting Rooms II
第二轮：
输入一些 parent-child pairs, 然后给一个pair, 判断他们是否genetically related. 比如(p1, c1)表示p1生了c1, c1有p1的gene. 输入(p1, c1), (p2, c1), (p1, c2), (p2, c2). 画图可知(c1, c2)是related, (p1, p2)不是related. 面试官给了一个无向图, 结点就是p1, p2, c1, c2, 根据输入把边加上, 然后我就一直按无向图来做了, 觉得从一点dfs遍历能看到另一个点就行了. 其实这应该是有向图. 如果是无向图, p1通过c1可以到达p2, 但其实不应该. 有向图就不会有问题. 后来发现这其实很像树, 这题就是要找common ancestor, 如果有就是related. 把一个点的所有ancestor放到一个set里, 另一个点的放到另一个set里, 有交集就代表related. 这题最大的失误就是想复杂了, 想成general graph了, 其实根据遗传的知识来想要简单一些, 更像是树. 代码写出来了, 面试官说有bug, 但我觉得不是. 由于下一个面试官已经在外面等着了, 就没继续解释了. 事后想想应该说明白, 也就一两分钟的事儿, 面过试的应该都能理解. 最好还是不要有bug吧?
第三轮：
value: 9, 8, 6, 8, 7
label: A, A, B, A,B
输入一些node, node里有value和label, 找出K个value最大的, 但每个label不能超过M个. 比如K=3, M=2, 答案是 9, 8, 7. 8 > 7, 但是A的数量不能超过2.
A, A, B A B
先sort by value再从大到小scan，复杂度O(nlogn).
面试官又写了另外三个其它可行的复杂度, A:O(n), B: O(nlogk), C: 不记得了. 问我想再试试哪个, 我选了O(nlogk), 感觉像是heap. 一开始想错了, 面试官直接说这样不行, 很多人都这样想过但就是不对. 然后就是全程带着我做, 还让我把算法的步骤写在白板上, 说是思路更清楚. 我当时都有点儿懵,没见过这样的... 再加上还在想着上一轮bug的事儿, 精力有点不太集中. 后来想出来了, 也不难. 对每个label用heap选出M个最大的, 然后再从这些用heap选出K个最大的, 最后就是O(nlogk). 中午带着吃饭的大哥说这人好像是欧洲那边的, style确实不太一样, 有点儿严厉, 但还有点儿可爱, 挺有意思. 讨论完时间不多了, 就让写了O(nlogn)的解法, 简单问了问如何测试.
午饭：
中国大哥带着吃的, 吃完饭我还把第二轮面试的情况跟大哥说了说. 大哥安慰我说不用太担心, 评价面试者是从整体看的, 有很多方面会考虑. 在这谢谢大哥了.
第四轮：
中国小哥哥。
4, 5, 6, 8
5, 5, 6, 9
6, 7, 9, 10
红色表示目的地. 问题是要找出能到所有目的地的点. 可以从其它任何点出发, 上下左右四个方向,, 只能往小于等于当前值的点挪(8可以去6, 但6不可以去8, 5可以去5). 图中绿色点就是答案. 刚开始对题目有一些问题, 后来小哥哥给了提示, 说是目的地不多. 后来就决定反着来了, 看从目的地开始能反着到哪些点, 存成set. 再用每一个点试, 如果在所有的set里就表示从这个点出发能到所有的目的地. 假设k个目的地, m行n列, 复杂度是O(kmn). 然后问如何并行. 对每个目的地都可以单独做, 我以为是O(mn), 但其实复杂度最高的地方是最后的test部分. 把所有的set放到一台机器上复杂度还是O(kmn). 类似merge sort, set也应该两两merge. 最后能优化到O(logkmn). 谢谢小哥哥了.
. 1point3acres
第五轮：-baidu 1point3acres
模拟抓娃娃机。
color count
Green: 3 3个绿娃娃
Blue: 5
Red: 2
随机抓, 哪个颜色的数量多, 那个颜色被抓的概率也相应的高. 抓完要把相应颜色的数量减去1.
类似LC 528 Random Pick with Weight, 但不同点在于每次要减去1. 开始用数组, 二分查找O(logn), 更新O(n). 面试官没让写O(logn)的, 写个O(n)的就行. 写完了说想想能不能把更新的部分也优化一下. 我知道要用segment tree, 但想不起来了, 还是不太熟练. 主要是一直在想用用数组实现的方式, 卡在坐标变换上了. 面试官提示说还是用tree node吧, 好想一些. 请参考: https://leetcode.com/problems/ra ... n-with-segment-tree . 我觉得应该也把左右子树的sum放在node里. 面试官就是看看我怎么想的, 说是知道不太好写.
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=467093&extra=page%3D3%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3086%5D%5Bvalue%5D%3D8%26searchoption%5B3086%5D%5Btype%5D%3Dradio%26searchoption%5B3087%5D%5Bvalue%5D%3D4%26searchoption%5B3087%5D%5Btype%5D%3Dradio%26searchoption%5B3046%5D%5Bvalue%5D%3D1%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311%26orderby%3Ddateline
跟着这个帖子准备的, 但感觉面试题没有没有里面的题难, 有些面经题比我面的要难很多, 看答案都得看几个小时. 感谢LC里的大神们给分享答案啊.
. From 1point 3acres bbs
回馈地里, 从地里学到了很多. 祝大家早日拿到offer. 也祝大家"猪"事顺利啊.
----------------------------------------
https://www.1point3acres.com/bbs/thread-477287-1-1.html
OA, 提供一个数据点 02/01收到的OA, 还是email和coupon两道题
----------------------------------------
https://www.1point3acres.com/bbs/thread-477073-1-1.html
没有店面，只有OS
1. 有一个数组，分成K部分，要求， min of subarray sum is maximized, [1,2,4,3,3] 分成3部分， 你可以分成 1| 2,4|3,3 最小数组 是1, 但是你分成 1,2 |4|3,3 最小的数组sum就变成了3. 3是想要的答案。 这个我提出了DP和recursive, 面试官都不满意, 最后用的是二分查找. 比如说你给 一个数 N , 看这个数组能不能被分成K部分, 每个部分都大于N， 如果不能，就试试N/2。
2. 面经删除棋子题，follow是如何记录移除顺序 -> 图
3. 设计一个api, start(), end(). 有事件发生[START,END ]比如有 [1,5], [2,7], [3,4]， 时间开始始的时候你要call start, 结束的时候你要call finish. 然后你需要按start的顺序emit log. emit是已经给出的API.
所以这个例子需要:
1. start(1) -> start(2) -> start(3) -> end(4) [这个时候不能emit log, 因为3不是start time 最小的事件] -> end(5) -> emit (1) -> end(7) -> emit(2) -> emit(3)
用queue或者 treeMap都可以
follow 如果开始时间一样,按结束时间sort
4. O(1) random() 数据结构 刷题网上有
5. 设计骨骼量级的 type ahead 和suggestion.
----------------------------------------
https://www.1point3acres.com/bbs/thread-477063-1-1.html
新鲜的骨骼跪经
第一个应该是个国人，结果他说他会议室预定错了不适合打电话，电流声超级大，于是给我reschedule了。但是我的recruiter今天其实oof了。。不知道啥时候给我答复
第二个是个美国小哥，人其实挺好的解释也很清楚，题目也不难。但是我比较蠢没有写出来
并且电话依然听不太清。。我怀疑是外放的原因了。我在绞尽脑汁的时候电话对面传来了欢声笑语让人更加紧张了。给一个数字n，输出有几种字母组合的方法
比如n=3，AAA,AAB,ABA,ABB,ABC 有5种
明显是DP但是我没推出数字的关系。。。其实可以直接输出所有的可能性然后输出list的size但是当时头脑一片空白根本没想到。。
哎，还是要多刷题啊。球一点米。
我觉得这个稳跪了，估计recruiter直接不给我reschedule了吧，哎
----------------------------------------
https://www.1point3acres.com/bbs/thread-477055-1-1.html
1/30 的电面， 今天收到回复 move on next step。
我一定要先感谢一下， 这次通过，跟我的能力一毛钱关系都没有。完全得益与地里的资源， 和面试小姐姐的super super super 给力。 小姐姐如果你看到这个帖子而且没男票的话，请联系我！！. 1point3acres
题目就是 https://www.1point3acres.com/bbs ... p;extra=&page=1 差不多。
给两个字符串 A， B。实现 IsTransformAble。 条件是每次转换必须保证转换所有相同字符。 给的例子是 abca -》 fchf。 注意转换的顺序需要 a -》 f， c -》h， b-》 c。其实另外一种转换方式是不需要考虑执行顺序， 先转换成临时字符。 比如 b -》 c这一步， 先做b-》# 然后 c-》h，最后再做#-》c这样。 上边那个帖子再回复里楼主有提到。 不过这道题只要求做判断， 所以哪种方式无所谓。
我给的做法是维护一个 key -》value pair， java里用的map。key是A的char，value是B的char， 只要保证 一个key 对应一个value 就是true（这里不需要一个value 对应一个key）。利口有类似的题，具体哪个忘了。 关于这个解法， 再上边的帖子里和原帖楼主讨论了好多（有兴趣的可以去看上贴回复），一个limitation是像那个楼主说的那样， 如果转换的临时字符是有限制的，这个解法就GG了。
不过好在这题开始没说这些限制， 所以是ok的。 最主要是小姐姐给力啊！她说ok， 那现在有一个follow up， 我知道你想到了用临时字符转换的方法（其实我压根就没想到， 因为距离看到上个帖子已经很久了，我早就忘了这题怎么解了），那现在你在实现一个
isNeedTemp ， 判断如果不用临时字符可不可以转换。 然后我卡了一会， 问她提示， 她就是在原来的方法基础上， 判断一下map里有没有circle，然后我就按照这个思路写了一下，就到时间了。然后have a good day。
----------------------------------------
https://www.1point3acres.com/bbs/thread-477048-1-1.html
一年半工作经验。
白人小哥 1.1 转换字符 判断环 1.2 航空路线 dfs
国人大哥 2.1 扩展bracket字符串 2.2 有nest bracket怎么办，还剩十分钟，没写代码，说了下思路
白人大哥 3 树中删除node，返回森林，一开始用bfs，面试官说可以做但是代码太复杂，让我再想想，于是最后用preorder遍历做对了。
白人小哥 4.1 circle linkedlist 隔一个删除node 4.2 按顺序输出item from list of streams pq
国人姐姐 5.1 围棋盘判断子是否alive bfs 5.2 自行车匹配问题 pq，还剩十分钟，写了pseudo code
面完后其实感觉很棒，每个题都做出来了，而且做了很多题，由于在原公司也是做的cloud，所以跟面试官都相谈甚欢。
但是昨天HR打电话过来说先提交了team match然后再送HC，我问feedback如何，HR说mixed feedback，说负面的评价有：没法一开始做出最优解，代码里有小bug，代码没写完。
估计第三轮一开始思路错了，跟面试官聊了bfs思路聊了十多分钟，面试官给了不少hints，虽然最后给出最优解，面试官看起来很满意。
代码有bug我估计应该是写代码中途面试官指出一些小问题，很快都改正了。
代码没写完可能是第二轮时间不够了，但是那是因为跟国人大哥聊得久了一点，而且写代码让我先写简单版，写完就剩十分钟了。
总体来说我觉得自己尽力了，可是还是有地方做得不够好，feedback好不好还是看人品。
要多注意代码变量名和不要出小错，最好是一开始就能思路清晰的给出最优解，因为现在大家基本都能写完代码，但是拿offer的比例总是比较低的。
感觉内心挺难受的，最后想问一下mixed feedback有人拿过offer的嘛？
----------------------------------------
https://www.1point3acres.com/bbs/thread-477006-1-1.html
第一题，是一个台湾小姐姐，给了一颗树状图，每一个节点代表一个水塔，每一条边代表一根水管，每根水管上有一个数字，代表水流过这个水管需要多久。问题是从root开始灌水，需要多久可以灌满整个图。follow up是如果图里有环该怎么做。
第二题，是一个北欧小哥，题目是给一颗complete tree，每课树节点只有left，right这两个变量，求特定标号的节点在不在树上。follow up是给定一颗complete tree，求这棵树有多少节点。
第三题，一个中东小哥，比较简单，竟然是LRU和LFU……，都是老题了，比较幸运。
第四题，一个印度小哥，给定一个没有排序的随机数组，使用二分法找数组里的各个元素，返回有多少元素是用二分法永远找不到的。要求算法复杂度为O(n), 楼主不会。印度小哥让楼主用例子试一试，看看能不能找到什么规律。楼主试了试，没找到规律…………最后给出了nlog（n）的解法，估计最后挂在这了。
----------------------------------------
https://www.1point3acres.com/bbs/thread-476895-1-1.html
第一轮： 扫地机器人。给了3个扫地机器人的方法，可以直接调用，1. isObstacle(Direction d) return true if the next grid in direction d is an obstacle. 2. move(Direction d) move one grid towards direction d. 3. clean(). 然后给了一个enum类， enum Direction { UP; RIGHT; DOWN; LEFT} 大概类似这样。问题是： 实现一个方法，cleanRoom()， 调用这个方法一次就可以让扫地机器人扫完整个房间。房间有多大是不知道的。面经高频，DFS就完事儿了。
第二轮： 给一个二维矩阵grid，每一个格子是0或1中的一个。如果是1就当成陆地，0就当成水。上下左右相连在一起的1可以组成一片岛屿。要求输出所有岛屿的border的坐标，属于一片岛屿的border要放在一起。输出一个List<List<int[]>> 类似这种。题目不难，DFS就可以解决。但是面试我的大哥不太满意简单的DFS，让我优化。想了半天怎么再优化memorized DFS，然后给了他一个解法，（我并不觉得那个方法会快，而且实现起来比DFS麻烦，大家可以自己想想如何优化DFS），他说可以了。但是讨论解法的时间太长了，我前前后后一个给他说了3种方法。最后代码没写完。感觉可能要跪在这里。
第三轮： 人自行车匹配问题，面经高频。给一个二维数组，车用1表示，人用2表示，什么都没有的格子用0表示（这个是我自己规定的）。要求输出一种可行的人和自行车匹配的方案。输入保证没有自行车到两个人的距离相等的这种情况，每个人都是同时行动去找距离自己最近的自行车的，并且人很机智，如果发现有别人比自己更快到达某一辆自行车，他就不会去找那一辆了。我用的PriorityQueue + Set做的。 最后问了时间复杂度和空间复杂度，以及还能不能再稍微优化一点。
第四轮： 可能是个神仙题。题目是说，A想组织一场生日聚会，他要邀请他的朋友们。但是他的朋友们比较傲娇，表示“如果我的朋友被邀请的少于三个，就不要邀请我了”。 A知道他朋友的朋友关系，即A知道他的朋友们都有哪些朋友。这个是本题的输入。即一个HashMap<Integer, Set<Integer>>. 例如A有朋友BCDEF，我们表示为A:BCDEF, 那么输入将会是A的朋友BCDEF的朋友关系。那么什么样的人会被A邀请呢，举个例子。若输入为： B: CDEFG, C: BFPMN, D: BEFK, E: BDF, F: BCDEZXV 那么，因为只有BCDEF是A的朋友，所以除了BCDEF以外的其他人都一定不会被A邀请。又因为C的朋友里，只有B和F会被邀请，C少于三个朋友被邀请，于是A不会邀请C。而BDEF，四个人因为都有三个朋友被邀请，于是他们4个都会被邀请。这道题，总之我是用DFS做的，但是面完之后想了想感觉好像有bug。因为在以上的例子中，要判断C是否会被邀请，需要判断B和F是否需要被邀请，而判断B和F是否被邀请的时候，又要判断C会不会被邀请。所以是一个循环。希望大佬教教我。。。
----------------------------------------
https://www.1point3acres.com/bbs/thread-476883-1-1.html
楼主去年可谓霉运上身，连挂g和f。发出来回馈地里，同时跪求大米，约了另外两家，米不够看不了面经，希望大家帮忙给大米！
2轮coding:
1. 一堆的形如 <a,b>, <a, c>的pair，意思是前一个task依赖后一个task。 问能否完成所有的task。典型的图的问题。 build graph, 迭代把InDegree为0的去掉。最后如果剩不下就可以。
2. BST求 succeesor, 利口原题。 followup是说求第 n个successor，问如何改数据结构。其实只要在每个node加一个子节点总数即可。
design:
1. 设计一个throttle系统，只允许处理不超过1000 qps的请求。 2个线程，一个enqueue, 另外一个判断qps，不超过threshold就执行
2. 一个大文件，问如何random sort。
楼主挂在了design 第二题， 这个问题有点像random shuffle，但是文件很大，不能全部放在内存，所以需要额外处理。
----------------------------------------
https://www.1point3acres.com/bbs/thread-476860-1-1.html
两道算法题 这段时间的google好像大部分人都是unique email address和coupons的题目
但是我遇到的unique email好像和别人的不太一样（其实是和LC的不太一样）
LC上的unique email address （久而久） 问的是 “[color=rgba(0, 0, 0, 0.65)]How many different addresses actually receive mails? ” 也就是不同的address有几种. 1point3acres
[color=rgba(0, 0, 0, 0.65)]我在OA遇到的题，需要返回的是重复数最大的那个address的个数
[color=rgba(0, 0, 0, 0.65)]比如["test.email+alex@leetcode.com","test.e.mail+bob.cathy@leetcode.com","t.e.s.temail@leetcode.com","testemail+david@lee.tcode.com"]
返回的是 3 ，因为一共两个unique address ，testemail@leetcode.com 和 testemail@lee.tcode.com，但是第一种一共有三个，所以返回3.
----------------------------------------
https://www.1point3acres.com/bbs/thread-476794-1-1.html
第一轮，判断两个矩形是否overlap,如果overlap则输出两者合并后enclosed的最大矩形；LC有类似easy题
第二轮，扫地机器人，高频面经，卒，follow up 怎么判断room是否clean??? ( 请问各位看官，没有room信息怎么判断clean all cell??)
----------------------------------------
https://www.1point3acres.com/bbs/thread-476784-1-1.html
第一轮：
上来warm up：两个interval 求并。
一个2xN的房间铺地板，一共有两种不同地板砖，一种 1x2, 一种2x1,问一共有多少种铺地板砖的方法。DP就可以了。
Follow up：增加两种不同方向的L形状地板砖，同样DP即可。
第二轮：
里扣 五刘二
没做过这道题，一开始想复杂了，后来提示了一下想出来了n方的解法，但是实现过程中面试官对我的写法有异议，后来又按照他的指示改了，没时间follow up了。
第三轮：
里扣 八死散
这题刷过，做的比较顺利。
----------------------------------------
https://www.1point3acres.com/bbs/thread-476709-1-1.html
一个是给一个 list: [a, b, c, ab, abd, abcd, abc], 找出list里面最长的串的长度，串的要求是每一次只能增加一个字符，比如：a-ab-abc-abcd ，这样的话长度就是4。 用的dfs加memo做的
一个是写一个function 判断是否是triangle sorted array，给了triangle sorted array的定义： 两边是最小的中间比两边大，只能有一个peak，element不能重复 e.g.: [1,2,5,4,3]。然后问怎么把一个triangle sorted arr 变成 一个sorted arr，我写了个quicksort，问了选择quicksort不用mergesort （不知道为啥。。。
），然后问怎么在一个triangle sorted arr里找出一个val，logn，先binary search找出peak来然后两边各binary search。
----------------------------------------
https://www.1point3acres.com/bbs/thread-476707-1-1.html
四轮 三中中三
1.n-nary sum……嗯我也不敢相信它会出这个 但是是的……一个TreeNode有两个List, 一个list表示children nodes 一个list表示父node到其中一个子node的cost.问遍历整个tree的cost. 秒
答完这个还剩了10来分钟 又给我出了个完全不相干的题……没写完就到时间了……那个题不太好描述，我觉得我可能到最后还没理解对题意……写得不好
2.一个地图 每个城市是一个字符串表示。 有个已经定好的路线A。 问地图中所有可能的路线里哪个路线这个路线A最相似。秒
3.二叉树 1）问某个节点是否存在 2） 问总共有多少个节点 节点的值表示节点在树中的位置。秒
4.一堆人出去旅游，有人花钱多 有人花钱少，问旅游回来后，怎样互相找钱 最后能让大家花的一样多。秒
PS：面试官们非常友好，都聊得挺高兴的。尤其是和二三轮的两位。HR说明天要给我打电话，不知道是什么结果……希望有好人品，找工作真的找得好累
补充内容 (2019-2-2 01:07):
hr打电话来说 湾区没有sde的位置了 一定要当sde的话就德州或者加拿大 在湾区的话sre或seti,seti要加面一轮，选sre了。然后一会儿就收到邮件说已经按sre送到hc了……求接下来好运……
----------------------------------------
https://www.1point3acres.com/bbs/thread-476661-1-1.html
两轮电面各45分钟
1. 给A,B两组坐标系上的点, 找到跨组距离最近的两个点
2. 给有向图, 找出最短的环路经 (环包含起点)
----------------------------------------
https://www.1point3acres.com/bbs/thread-476659-1-1.html
补一个最近面的狗家面经
硬度大叔
就一题 力扣138 用的普通hashmap解 然后133 要求写了BFS和DFS
然后尬聊了一下提前结束了
----------------------------------------
https://www.1point3acres.com/bbs/thread-476553-1-1.html
1 是 给两个strings, 可以在其中一个string上增删改，请问是否更删改一次是否可以把一个string变成另一个string
比如说 google 和 goagle 可以把a改成 o 就变成google， 返回true
第二个部分是 寻找最优增删改次数，这就是DP啦。
大概答案就是max(len(str1), (len(str2)) - longest_common_subsequence(str1, str2)
----------------------------------------
https://www.1point3acres.com/bbs/thread-476483-1-1.html
给一个array，所有的element都是相邻且pair up的除了一其中一个，要求找出这一个single element
比如221199522，返回5
先给了一个linear scan的解法，要求提高时间复杂度，于是给了binary search的做法，大概就是每次看右边（包含中间的element）然后就知道这个single element在左边还是右边，比如上面这个例子，右边是99522，右边的长度是奇数又是99这个pair开头，那single element肯定就在右边
写出来有点bug，改了改。search到最后几个element的case还蛮多的，我也是没想的太清楚，不过还是给过了。
求大米啊，我的号借给朋友看面经，给我把大米全用完了，哭死，现在啥也看不了。
补充内容 (2019-2-1 02:59):
补充一下，linear scan 也有一些corner case 需要注意，比如一个element的情况， 112的情况。最后还问了如何测试和code coverage。大米大米老铁们
----------------------------------------
https://www.1point3acres.com/bbs/thread-476395-1-1.html
第一个电话
[1,2,3,4,4,5]
判断一个list能不能分成groups，一个group必须含有两个或两个以上的元素是重复的
follow up：
判断能不能分成groups，每个group必须是五个连续的元素
第二个电话：
A,B,C,D,E
F,G,H,I,J
K,L,M,N,O
P,Q,R,S,T
U,V,W,X,Y
Z
输入一个string：WEST 输出 RRDDDD*UUUURR*DDDL*R*
去那个list里面找这个string的字母，连续输出方向。 第一个字母W，从A开始向右两次，向下四次。
第二个字母E从W出发，向上四次，向右两次
补充内容 (2019-1-31 11:23):
第一个问题[1,1,3,3,5,5,4,4] 可以分成[1,1,3,3][5,5,4,4],这个就是合法的返回true，所有的元素都要在groups里，每个group 必须要有两个或两个以上重复元素。主要是检测原list有没有足够的重复元素的
----------------------------------------
https://www.1point3acres.com/bbs/thread-476317-1-1.html
第一小问concat iterator：给两个iterator，分别有next和hasnext两个method，concat的要output两个iterator里面所有的element。比如两个input的iterator分别output出来1，5，9和2，5，6，然后concat那个就需要output出来1，5，9，2，5，6。
第二小问：在这基础上写一个skip的method，比如当前iterator位置在1，call skip(5)以后在call concat的next的时候就会跳过第一个5，call两次skip(5)的话后面那个5也会跳过。
这一轮第一小问当时太谨慎了觉得有点太简单沟通了半天确认，导致很晚才开始第二小问，然后第二小问没完全写完（小哥说还有些edge cases但是没时间了）
给一个整数数组，求整数数组里面的数乘起来以后的product结尾有几个0（不是结尾的0不算）。比如10100 output出来的结果就是2而不是3。面试完了以后搜了一下，应该是叫做trailing zeros of product。关键点就是找到2和5倍数的数量。
这题做完已经三十多分钟了，小哥也没说还有没有第二。最后还问了一些我有没有写过test，我表示我就写过一点unit test，小哥看起来挺满意说你现在会写一点test就挺好了
给一个directed graph，有一个node是success，问从任何一个node里面出发能不能【保证】最后来到success node。需要注意的是有可能会陷入一个loop里面，然后这样就不能保证必定去到success node了；另一方面，如果可能去到一个没有out edge的node，就也属于不能保证去到success node。总而言之就是从一个node开始有没有可能保证不会进入loop也不会去到dead end node同时能reach到success node。
我用的dfs写的，检测dead end node很简单就是看看还有没有neighbors，但是loop那里到了最后都没有完全figure out。我提出来一种暴力解法就是从每个node再dfs/bfs一次看看能不能reach到前面经过的node，可以的话就有loop，小哥沉思良久表示I can buy it。但是很显然这个办法非常不实际，他就提示有没有可能cache一下能否reach到success，不过那时候已经没有时间了
----------------------------------------
https://www.1point3acres.com/bbs/thread-476276-1-1.html
第一题是给几个括号，看是不是balance，我是用stack解的。
第二题是给一个single linked list, 然后把它分成k段，比如说[1,2,3,4] k=2 就是[[1,2],[3,4]]
----------------------------------------
https://www.1point3acres.com/bbs/thread-476270-1-1.html
用iterator 实现一个特制的iterator class，
需要实现方法 next(), hasNext(), skip(element),
skip(element)会跳过iterator中第一个出现的此element
example: [1,2]
skip(2);
next(); =>1
hasNext(); => false
----------------------------------------
https://www.1point3acres.com/bbs/thread-476268-1-1.html
找一个dom元素里前k个字儿；实现一个同一时刻只有一个请求在进行的fetcher；地里前段面经太少了，希望大家多分享下呀；攒人品；攒人品；攒人品。
----------------------------------------
https://www.1point3acres.com/bbs/thread-476263-1-1.html
第一轮：好像是印度小哥？给一个str，让你判断所有的permutations中能不能形成palidrome. 然后就是讨论如何优化。完了小哥说You are doing a great job.. check 1point3acres for more.
第二轮：白人小哥：先是一道palidrome的题目，但是我忘了具体是啥，反正不难……
然后第二题好像是说一个game，两个players，有一个worddict（类似英汉词典），然后两个players轮流往后面填字儿，规则是到你的时候不能是worddict里的word，也不能无词儿可填。然后要implement这个往下填字儿的function。我说用Trie做预处理，然后就选不是词儿的那些options. 没有特别的followup，但就是讨论了很多如何赢这个game、think how many steps forward之类的。feedback也挺好的
第三轮：印度小哥：又是一个游戏，给定一个word，然后几个筛子，筛子每一面都会随机有几个字母，筛子不能重复利用，然后问能否用这些筛子来组成这个给定的word。典型的dfs吧，feedback也挺好。
lunch：白人小哥，纽约过去的，聊得还挺开心。
第四轮：做android的韩国人。说了个hello上来就做题。这轮真的是好崩溃，他一开口，我就觉得要跪了，能听懂30%？？两个印度小哥我都觉得还ok，但是纯正的韩国口音我真的是好无语。。。/(ㄒoㄒ)/~~ 问了机器人左上走到右上那题，幸好题目我见过，所以虽然没太听懂他说啥，但还是做出来了。folloup1是必须走某一行怎么办，followup2是必须按照某个sequence来走某些列该怎么走。2我当时忘记具体怎么做的了，卡了一下，然后他给提示我又真的是听不懂啊，画来画去都没搞明白。总之最后给了一个思路，但是没做完。。。
第五轮：白人：好像是LC原题吧，给一个list，偶数位是重复次数，奇数位是数字，一个iterator，然后一直iterate。这个是我写白板写最认真的一轮，讨论了很多edge cases，思路也很清晰。大叔一直在做笔记，很认真的样子。聊的也挺好，最后他送我出来了。
还是挺sad的，题目都是面经题，其他几轮都还挺enjoy和面试官边交流边写code，遇到烙印也没有传说中可怕的口音，只有第四轮。。。第四轮那个followup后来我想起来怎么做了，但是当时被他的口音搞得好郁闷，根本没法交流，一紧张就卡了……sigh，准备了那么久，最后因为这样被拒。。。我可以去申诉么。。。
补充内容 (2019-2-1 01:52):
第二题：赢的规则是对方猜中了词库中的词或者到他的时候无词可猜；第三题，骰（tou）子，就是六面体哇，没面上有随机的字母（可重复）；第四题，按sequence就是比如行是【3，1，3】就必须先走3，再走1再走3
----------------------------------------
https://www.1point3acres.com/bbs/thread-476261-1-1.html
分享一个去年年底的店面，为onsite求人品
蠡口三五八. Fro
----------------------------------------
https://www.1point3acres.com/bbs/thread-476246-1-1.html
给一个2D Array 里面的element是0~9的数，对于每个元素，可以沿着对角线或者左右上下traverse。
1，2，3
4，5，6
7，8，9
一个例子：如果选择左上角元素1，沿着右方向traverse一步，可以得到12，在traverse一步得到 123
同时给了一个helper function可以check一个数是不是prime
要求return出现次数最多的prime number
----------------------------------------
https://www.1point3acres.com/bbs/thread-476161-1-1.html
刚刚面试了狗家的onsite，其实这是人生中第一次onsite，因为还是工作准备的也不是很充分，就当是练手了。来地里发一下面经回馈一下大家。
1. 第一轮，interviewer来晚了十分钟，之后又问了简历内容大概说了快20分钟，所以开始做题的时候已经只剩半个小时左右了。。题是一道实现题。interviewer一开始说的很不清晰，说一个city里面有一条街，这条街里面有很多个blocks，每个block里有多个retail store(library, spa, bar, grocery...自己定义)，你刚刚搬到这条街上，你有一个list of interest stores是你经常去的店，需要求的是the minimum distance of the maximum distance shop in the interested list. 因为题目出的很不清晰，楼主花了很长时间和interviewer讨论一些details去确定input/output data structure 和题目的意思(一开始真的是蒙的。。)，最后确定了input是List<List<String>> blocks(String里面自己定义不同的shops)， List<String> interested, return index of block 需要满足的条件是从这个block到最远的在interested list里面的shop最近的distance。因为当时大概只剩十几分钟了，楼主只想到了暴力解法，开始coding，大概coding了一半就到时间了，后面的写的suedo code，感觉不是很好。。
2. 第二轮，interviewer上来就开始做题了，时间充裕。第一道题很简单，就是longest consecutive substring, 给一个array，让你找到最长的连续＋1的数的长度。leetcode应该有原题。楼主写完之后，第二问是如果我们把array换成tree，怎么做，基本上跟leetcode 298(Binary Tree Longest Consecutive Sequence), 但是interviewer说这个tree并不是binary tree，小变形，只要把left child和right child换成list of children就可以了。这两个问题之后都有follow up question，问的都是如果数据量过大怎么办。第一问楼主回答的是1.bitset 2. partition。第二问楼主回答的是因为treenode是一个structure, 可以在每个node里面存一个变量去存到当前点有多少consecutive node。这一轮就结束了，因为是做过的题所以多少有一些印象，基本没有问题。
3. 第三轮。第一问是一个简单的string题。recruiter说，有一个game, 你有一个secret word和一个guess word，我们可以assume secret word和guess word都是长度为5的upper case letter，写一个function duplicateLetters(String secret, String guess)，return 这两个string里面有多少个相同的字母。记得leetcode里面好像有差不多的题，这道题不管用couting sort还是hashmap都可以做出来。之后interviewer说如果我们不能保证两个input string 是valid的怎么办，楼主说可以做一个text justification first然后写了一下具体怎么做就过了，第三问，如果我们现在有一个SecretKeeper class, 这个class里面有一个guessWord(String guess), inside this function，1.有一个global counter++，2. call deplicateLetters()(第一问的function)，同时我们有另一个class，里面有个List<String> dictionary，在这个dictionary里面有很多words，也包含一个secret word（但是我们不知道是哪个）要求的是像一个algorithm，去让我们用最少的call to guessWord() 去找到secret word，楼主这一问想了有一阵子，最后想了一个solution，techniqly 是可以reduce call times，不过很尴尬的是举例子的时候不是很顺利，不过interviewer貌似比较认可这个solution，可能还需要加另一个checker去把这个算法完善。这一轮就结束了。
. From 1point 3acres bbs
4.第四轮。一个中国小哥哥，挺和蔼可亲的(嘻嘻)。第一问，string题，给两个string(e.g: abca and bcdb)，写一个function去判断这两个string是不是可以transform to each other，leetcode里面有差不多的题，楼主就用hashmap很简单的做了。第二问比较难想，是说还是有两个已经确定可以transform的string，写一个function去判断这两个string是不是indirectTranformString(eg: xy and yx, 如果我们想tranform这两个, 先把x replace成y，这时第一个string就变成了yy，所以我们需要一个indirect letter k，让x replace 成 k first，然后y replace 成 x，最后把k replace成y)。楼主想了很久但是不是很能确定规律，interview给举了几个例子去提示楼主，最后终于看出了规律（跟环有关系）写了代码。这一轮就过了。
5. 第五轮。实现题。input是List<String>, 每个string里面是两种currency的名字缩写，和rate，input 2 是另一个list of tuple，里面是两种不同的currency。写一个function去return list of string, 每一个string是input2里面的tuple和这个tuple的rate，楼主和interviewer沟通确定details之后决定用hash map和一些实现的code去做，最后写了很多之后发现其实应该用recursive的function去写。
----------------------------------------
https://www.1point3acres.com/bbs/thread-476058-1-1.html
一月29号sunnyval onsite new grad 面经
第一轮电面：记不清了，反正是一道easy难度的题，不用想直接写的那种。不过面试官是写js的（我之前问卷好像填的prefered language是js），我上来直接写java,面试官表示能不能写js，当时好久没用js了，语法不是很熟，可能写了一些bug，就加面了。
第二轮电面：写一个贪吃蛇游戏的class lc原题
onsite：
第一轮，印度小哥，移石子高频面经，看到题后心中窃喜，演了会开始说union-find方法，可能自己讲的不是很清楚，小哥表示听不懂。。。一下就慌了。。又试着讲了讲还是没讲懂。。然后小哥问还有什么方法吗？我知道还有dfs，但之前没看过，就直接说了dfs。然后小哥就说你先构个图吧，我当时想的是o(n方)两个for loop的解法，不知道他让我构图干啥，然后就随便说了说，时间也不多了，就写了n方的dfs代码，然后小哥说他还想知道移石子的顺序，不知道这个算不算是follow up。写完后时间超了一些，也没时间看有没有bug。。。感觉这轮经典面经答得很不好很可惜。
第二轮，国人小哥，course schedule I II，很给力，面完说他这轮没什么问题
lunch被一个美国大的带到了楼里的"secret room"..还打了会狂扁小朋友的游戏机。。很有趣。。
第三轮，印度小哥，输入一个array里都是人，给一个isFriend()的fun可以判断是否两个人是直接的friend. 判断输入的list里是否所有人可以形成一个friend group。我用bfs写的，把所有是friend的加到一个set里最后比较set和input的length，时间复杂度o(n方）。写完还有时间小哥也没问follow-up,就让我给一些testcase，我说了input里可能有重复的，然后就改了改代码。 然后小哥让问问题，我对我的n方复杂度的代码很没信心，作死问小哥代码是否可以优化，他说可以考虑多个机器，并问我有什么想法。。。我想了会说不知道。。他说没事并给我大概讲了一下（没有听懂。。）
第四轮，国人校友小哥，一个瓶子里有整粒的药和半粒的药，并都知道个数，先写了个pick() function，要求选到两种药的概率一样， 并且pick整药的话半粒的药个数加一。 写完后，又给了瓶子里期望的剩下的整粒药和半粒药的个数，可以多次pick，要起返回pick到跟期望一样的概率。我用bfs写的，写的时候有bug小哥提醒了一下。写完后问复杂度脑子一抽直接说错了，小哥提示后改正。时间也超了一点，结束后建议我以后注意提高面试过程中的交流问题。
面试还有个问题，因为我第一次电面完后就决定用js刷题，onsite选的语言也是js，但hr好像搞错了，onsite 4个面试官都以为我是用java的，不知道有没有关系。。。
总的感觉碰到的题都很简单，三个bfs都差不太多。。。但总体来说答得并不是很好。。楼主转专业菜鸡本来对google就是抱着来免费旅游一趟的想法来面试的，感觉可能浪费了这么简单的题和这么nice的面试官。。。
----------------------------------------
https://www.1point3acres.com/bbs/thread-475991-1-1.html
第一轮是个白人小哥哥很友好，跟我聊了会天缓解了紧张情绪之后开始出题，题目和之前面经里见过的grid水管题很像（也许就是一道？）。具体说来就是给定一个M*N的grid图和每个方格里的水管连接，水从(0,0)进入，从(M-1, N-1)流出，水管连接方向可以是各种比如 "L" 比如 "_|" 比如 "十"，然后有leakage，这个需要自己讨论什么是leakage，比如某个流经的格子是空格（什么管道都没有），或者管道连接不对，比如从(0, 0)流入(0, 1)但是(0,1)锁在grid对应的管道并没有接入(0,0)的，那么也算leakage，或者流出grid的也算leakage。要求return一个boolean，如果能从起始点到终结点最后成功流出就算是True，如果有leakage或者无法流到算false。用了个单向BFS因为面试官明确说了不担心space and time complexity，但是要注意讨论各种leakage的corner cases。
第二轮居然是hangout interview，然后我这边还没预定chrome，所以只能通过摄像头看白墙勉强答题。对方又是一个白人小哥哥，头发长长的好飘逸（不像我一尝试留长发过两个月一模全是油赶紧剃短）。题目是quad tree（并不知道什么意思，最后那张记录题目的小纸条上偷偷瞄到的），具体来说就是像分形(fractal)一样画H：给定一个长度x，那么画出来的H的两条竖直边和一条横边的长度都应该是x，然后如果有两层，那么要以第一层的H的四个竖直边顶点为中心继续画H，新的H的边长变为sqrt(x)，以此类推。具体画多少层没给，有啥API也没给，就是要通过和面试官沟通然后询问有没有某个我需要的API。我的做法是写了个draw_H(x, y, l, n)的函数，x,y是H中心点坐标，l是边长，n是剩余需要画的H的层数，然后做了个递归，每次递归层数n减一。然后问了有哪些需要的test cases，以及time complexity （O(4^n)?）以及space complexity （O(n)?）。
第三轮忘了。。。是个国人小哥哥。万一想起来了再补充。
然后是午饭，是个做compiler的阿姨带我穿过各个食堂找吃的。不得不说google食堂貌似并没我想的好。。。
下午“最后”一轮tecn interview的白人小哥哥迟到了快10分钟。看起来比较年轻可能刚毕业不久的样子？不过我一向看人年龄不准，没准人家才18岁呢。题目很简单，先让我写了个binary tree node，然后给一个should_delete(node) 的function，要写一个erase(root)的function，对从root开始的树的每个node进行检测看需不需要被移除，如果需要则remove corresponding node，然后return一个所有新产生的roots，比如
1
/ \
2 3
/ \
4 5
如果要移除2，那么return的nodes对应的values分别是[1, 4, 5]。水过，不过写好了之后在小哥的提醒下发现只return了没真正delete，所以改了下。最后小哥都不知道问啥了，就尬聊了一小会。
高潮来了。最后一轮说好的thesis discussion and behavioral round，一个中国小哥哥进来之后就说"I'm not a physics major so I can't talk to you about your thesis, hence I'll just do another tech interview"。然后就开始在白板上写起了C++（我要求的是Python）。题目如下：给定一些meetings的start and duration，比如P1(15, 5), P2(22, 10)，design一个data structure来实现一个叫check 的function，用来查询对于一个新的P(start, duration)，能不能添加进已有的schedule里。在那个点脑子已经不转了然后就准备用最蠢的list水过，然后被面试官阻止了，说的是I can tell you the follow up question:比如我给你一些schedule了，然后有4个room，问能不能实现（也就是并行）。在脑子完全不转的情况下做了对每个时间段的切割（想写成segment tree但是并不会）时间超了也并没做完，而且很多corner cases没handle。目测这轮挂的厉害。更要命的是面试官不会Python，所以在写的过程中经常被打断问这行代码在干嘛，思维过程也是断断续续的。
本来面完前四轮感觉应该面得不算太差结果被最后一轮弄得心情极差。面完马上给recruiter发了邮件描述了最后一轮发生的事情，recruiter也只是说这个面试结果统计的过程是看trend不会只看单个的一场面试。不知道地里的各位有没有类似经历的可以分享？如果真的是被最后一轮额外的tech interview灭了那真是欲哭无泪了。
No comments:
Post a Comment