# Google 面經
https://docs.google.com/spreadsheets/d/1vlrDFAauI2crzWhldcP0eCXqPU-RE3l4d_AFjbFJOiU/edit?usp=sharing
https://jobs.1point3acres.com/companies/google/interview
## VO
- https://www.1point3acres.com/bbs/thread-883437-1-1.html
1. 东南西北以及四个斜的 八个方向 比如1N2,2N3, 3S1就是说1在2的北边，2在3的北边。3在1的南边（也就是1在3的北边），代表着1->2, 2->3, 1->3，此时返回true，
Answer: 找circle。如果有circlereturn false。没circle return true
2. 建一个MyIter class。假设已经建好了trie(ABC → “he”, DE → “llo”), 。trie的leaf是一个string。MyIter class的constructor input是一个javaioreader和一个已经建好的Node root
Answer:
弄一个buildStr method，给你一个ABCDE这种String，返回在tire里面的leaf的string的concandinate → “Hello”
Iter class还要写出hasNext和next method。这里可以把之前建好的string在class里面存下来，然后用一个index去做。
follow up：因为给的Node的children 是个node array，如果换成hashmap会怎么样
follow up：如果换成换hashMap的down side是什么
follow up：在memory层面还能如何优化？
3. 有个startRouter, 有个endRouter，有个RouterLocation Array，有每个Router可以connect的range。
看是否可以从start connect to end
union find。遍历每个pair，然后union在一起，然后find startRouter, find endRouter. 看他们的parent是否一样。一样就说明可以从start到end
4. 第四题 Wrap text 有点像利口留疤但其实不是。
Wrap text.
A function which takes text and a width (int) and returns the number of lines that the text would take on the page.
Example:
text = "asdf asdf asdf asdf asdf asdf"
width = 7
answer: 6
Example:
text = "asdf asdf asdf asdf asdf asdf"
width = 8
answer: 6
Example:
text = "abcdabcdaabcdabcda \n\t asdf asdf(1) asdf asdf(1) asdf(1)"
width = 9
answer: 5
text = "asdf asdf asdff asdf asdf asdf"
width = 14
asdf asdf
asd asdsadsd
asdf asdf
text = "a a a a a a a a a a a a"
width = 16
answer = 2
a a a a a a
a a a a a a
text = "a a a a"
width = 12
s = s.trim();
split("\\s+")
After split
for each single string, we need to use it and width to get how many lines it take
*/
我开始以为是利口留疤就按照那个思路去做了。这题corner case巨多，我现在也有点忘了具体要求，只记得一个特别长的String是可以跨越多行的，然后两个String中间如果有多个空格也不像留疤那样要缩减成1一个。当时很勉强做出来了。
Follow up: Assume Part 1 getLines works perfectly.
Write a new function:
int getColumnTextSplit(String s, int width, int col);
if width = 10, col = 5
then we have two columns of width 5
width = 10, col = 2
two columns, width 2 and 8
returns the split point in s
text = "asdf1 asdf2 asdf3 asdf4 asdf5 asdf6"
width = 12
col = 6
asdf1 | asdf4
asdf2 | asdf5
asdf3 | asdf6
asdf1 | asdf2
| asdf3
| asdf4
| asdf5
| asdf6
这里的col是指在哪一个col开始分。通过这个col可以得到两个width。然后根据这两个width，再从原String里面切一刀，然后左面String根据width1，右面String根据width2，得到两个lines number。目标是这两个lines number尽可能的靠近。
没做出来，面试官最后说了可以用Binary Search。估计就给我down level在这一轮了。
- https://www.1point3acres.com/bbs/thread-883204-1-1.html
1st round. 技术面
cord tree, 可以看蠡口的讨论区cord
（a）对leaf, internal 分别定义一个类，后续实现用isInstance() 区分
（b）对给定的index，返回对应的字母 树的遍历即可，注意corner case，这里有被面试官提醒，不知道会不会扣分
（c）在（b）的基础上，对给定的index，输出index~index+L的字符串，还是树的遍历+path 记录
（d）time/space complexity
2nd round. 技术面
secret & guess 有点像 蠡口的二舅舅
secret：CHALK
guess: AGBLC
output: YRRGY
就是 如果字符存在且位置正确，G；字符存在但是位置不对，Y；否则 R
（a）secret 每个字符是unique，guess 也没有重复字符
（b）secret 每个字符是unique，guess 有重复字符 ， 比如说 guess=“AGAIN”, output="RRGRR"
（c）secret 有重复，guess 有重复字符，我用了dictionary 记录count
（d）有一系列 guess 输入，让你比较每次的guess 是否有比上一次的guess 更好，没有implementation, 主要就在定义 何为“更好”。比如说 R->G 是一种improvement, 到这里我就有点云里雾里了 不知道在考察什么，然后就差不多到时间
3rd round. 技术面
snapshotarray....hhhhhhhh 正好周末刷到 蠡口瑶瑶撕溜
讨论区大佬用了binary search 和记录每个index 的 history record.
我自己用了个dictionary 记录每次的变化，但是空间复杂度有点高，最后follow up 我说了一下大佬的思路
4th round. BQ
一个笑眯眯的印度小姐姐。
就是一些 disagreement, conflicts, a happy experience, high goal
5th round. 技术面
filesystem, 也是个树结构，多叉树, 有dir, 有file, 然后file 有对应的filesize, 让你计算这个目录下的filesize 总和
（a）DFS 写了一个
（b）某些目录被多次访问，如何提高计算效率。用一个dict 记录
（c）BFS 又写了一个
（d）如果有cycle 怎么办，变成一个图的问题，用一个visited set 记录已经访问的节点
- https://www.1point3acres.com/bbs/thread-883080-1-1.html
楼主2/3年经验，面L4.
楼主大概运气不太好，先是Amazon店面一个corner case没考虑就被拒，再是Microsoft碰到两个Hard和一个黑人面试官（https://www.1point3acres.com/bbs/thread-880981-1-1.html），然后到🐶 onsite，四轮当中两轮hard，第二轮和第三轮的面试官还抽中同一题（我说了，第三轮换了一个题）。接下来只有meta了，其他的都没投进去，楼主现在是裸辞状态，真的有点郁闷。
=====
1. BQ。抢功劳的同事；紧急的deadline；unexpected problem。根据面试官的反馈，感觉还行。
2. 路由器题。输入是一堆路由器的(x, y, id)，每个路由器可以给radius范围内的其他路由器发消息，给一个初始id，和一个结束id，问消息能否从初始路由器发送到结束路由器。follow-up是，路由器只能给radius范围内最近的路由器发信息，选最近的路由器发消息；如果一个路由器有好几个最近的路由器，给所有的最近路由器发消息。
我用O(n^2)建图+BFS解决所有，一直写写写，没怎么优化。这一题不知道怎样。
3. 实现一个class，在xy平面上，一开始没有点，不断add和remove点，点用坐标(x,y)表示，每一步return一个最小box把所有的点框住，box平行于x/y轴，要求每一步优于O(n)解法。
我propose一个x2ydictionary，对每个x对应的y，double linked list O(1) delete, O(k) insertion，接着在面试官的引导下，用BST存x，但是python没现成的BST。凉凉。面完觉得面试官想要BST of BST？我觉得是个Hard。
4. 面试官一开始想考上一题，不想重演上一题的灾难，后来改成manager/employee题：一个class，一开始为空，有三个method，setManager(M, E), M是E的direct manager，setPeers(E1, E2), E1和E2是peers，E1的direct manager不是E2的，queryManager(MM, E)，问MM是否是E的manager，可以是很多层的manager。这三个method被call的顺序是随机的。
我的解法：dag表示manager-employee关系，udg表示peers关系，另外一个e2m字典，记录直接mgr，时间刚刚够写完，答了下时间复杂度。不知道怎样。
5. 霸一罢。一个车，初始速度为1，初始位置是0，两个指令，A速度加倍，R速度降为1位置不动。第一问，给一个instruction string，返回离初始位置的distance。第二问赛车本车，给最终距离，返回最短指令序列。
抽到这题心里就拔凉，知道第二问要dp，解法没太看明白。第一问写完问了时间复杂度，dry run with AARA。第二问尝试用那个dp解，没写完，事后后悔没用BFS写个brute-force。
四个题两个题考到盲点，上周四微软碰到两个hard一个黑人面试官，面完就有点自闭。今天面完更自闭了。亚麻和🐶家放大水为啥放不到我身上？
- https://www.1point3acres.com/bbs/thread-882935-1-1.html
第一轮：BFS, 问了time, space complexity 和几个follow up question，感觉不错。答完了时间多跟面试官还聊了聊
第二轮：问top n user的名字和wordCnt。楼主刚开始走了弯路用了sorting，后来面试官问有没有更快的方法，改成了Priority Queue。健谈白人大叔，还有一个shadow的人，聊的蛮开心的，就不知道这弯路会不会影响评分。
第三轮：滑轨的一轮。面试官是个韩国小哥。在地里看过类似的题但没当时没细看，现在追悔莫及。题目大概是告诉你一堆点之间的相对关系（八个方向）。问这是不是valid。比如1 N 2, 2 N 3, 3 N 1, 那output 就是invalid。我说detect cycle他说对这是正确思路。然后写了code，但没写完时间就到了。没有follow up question。这一轮应该是no hire了
第四轮：遇到国人里。问题是也在地里遇到的fun city question。楼主再一次没有细看（后悔ing）。后来用bfs找所有长为4的路径写了个complexity很高的code,楼主感觉要挂。面试结束楼主还不死心问了下optimal solution怎么解，就是下面链接楼主的解法。国人面试官很nice的表示我的solution work，他45分钟也写不出optimal的，马上写出optimal的他都默认以前做过原题。谢谢他的安慰了。
是这楼主里的第二题。https://www.1point3acres.com/bbs/thread-827588-1-1.html
第五轮：BQ 一些简单的问题，面试官感觉是俄罗斯大叔
- 处理people in different background
- 如果deadline但你的product不完美怎么办
- 你过去最满意的一个project
大叔人非常nice。听说这是最后一轮了就问我有什么问题都可以问他，时间很多。最后跟他聊google的team和cultural比预期多聊了二十多分钟。
感觉HC基本过不了了，也是一次难得的体验吧。LC总共做了不到10题所以也不知道有没有对应的。
https://www.1point3acres.com/bbs/thread-882904-1-1.html
补充内容 (2022-04-12 20:42 +8:00):
更正：manager/employee那题，setPeers（E1，E2），E1的direct manager是E2的，如果E1是C的manager，E2不是C的manager
## Phone
- https://www.1point3acres.com/bbs/thread-879616-1-1.html
## VO
- 150 x2 follow up是如何判断input valid，整体很不错
- 1293 (not shortest but yes or no)
- 212
- 843 + Worlde
- 986
- 给黄绿两种颜色的布，给定黄色布的位置，比如[1,3], [5,8], [9,15]，剩下所有位置都可以认为是绿色的布。input：黄色布的位置list，一块绿色布的长度。问：把绿色布放到任意位置，最多能剩多少黄色布。
- 匹配足球比赛，给定1.国家和足球队的dict（e.g. {'Italy': [c1, c2], 'Spain': [c3], 'France': [c4, c5, c6]) 2. 之前踢过比赛的队[c3, c6], [c4, c2], [c5, c1]，要求匹配下一轮的n场比赛（任意一种组合），要求同一个国家的不能一起比，之前踢过比赛的队也不能一起比。
- 366 follow up是，如果一个node没有任何leaf node，这个node就必须马上删除，no matter还有没有其他leaf node
- 给一个string，类似aaabbc的形式，就是相同的char都放在一起，不会有aba这种形式的，输出出现次数最多的那个char 用tow pointer follow up是怎么优化space和time complexity
- **写两个function，第一个function是插入一段interval和相应的一个operator name，判断能不能插入，可以的话分配一个不重复的id并且返回这个id，第二个function是用id找一个operator，如果存在这个id，就把相应interval删除，如果存在这个interval，删除成功，返回true，如果不存在，返回false 用的treemap，但是没能全写完，所以没follow up**
- 给一个integer array，找到一个subsequence，在这个subsequence里，后一个element总比前一个大1，输出它的长度 follow up是，如果要求的是在subsequence里，后一个element比前一个大的范围是1 ~ N，给出最长的subsequence
```cpp
#include "print.h"
#include <vector>
void getLongestSubsequence(const vector<int> &A, vector<int> &ans, int N = 1) {
const auto n = A.size();
// dp[i] := # of longest subseqs. that ends at A[i]
vector<int> dp(A.size(), 1);
// prev[i] := prev index of i
// A = [1 3 2 3]
// dp = [1 1 2 3]
// prev = [x x 0 1]
vector<int> prev(A.size(), -1);
for (auto i = 0; i < A.size(); ++i) {
for (auto j = i + 1; j < A.size(); ++j) {
// if (A[j] == A[i] + 1) {
if (A[j] > A[i] && A[j] <= A[i] + N) {
if (dp[i] + 1 > dp[j]) {
// find a better solution
dp[j] = dp[i] + 1;
prev[j] = i;
}
}
}
}
const auto it = std::max_element(begin(dp), end(dp));
const auto max_index = it - begin(dp);
const auto max_length = dp[max_index];
ans.reserve(max_length);
// start from max_index -> going backward
auto buildAns = [&prev, &ans, &A](int i) {
while (i != -1) {
ans.push_back(A[i]);
i = prev[i];
}
std::reverse(begin(ans), end(ans));
};
buildAns(max_index);
}
int main() {
vector<int> A{1, 3, 2, 3};
vector<int> B{1, 4, 2, 7, 8};
vector<int> ans;
// getLongestSubsequence(B, ans);
getLongestSubsequence(B, ans, 3);
print(ans);
}
```
- 给的题目是地里传纸条变体。原题是比较复杂的DP但感觉最近咕咕放水给改成一个纯math计算概率的题目了。计算概率公式搞清楚单纯遍历path就可以做出来，但因为抗抑郁药副作用比较大打字手抖还慢导致没写完...
- https://www.1point3acres.com/bbs/thread-878219-1-1.html
- Nary-tree的先序遍历变体并打印。一开始说回溯做但面试官表示用不着太麻烦了用递归遍历
- https://www.1point3acres.com/bbs/thread-877866-1-1.html
- 有一个店， T[N] , 表示N 个服务员和 他们服务一个人的时间（每个服务员只能同时服务一个顾客）。店刚开门，前面有M 个人在等着，这个时候来一个新顾客， 问他要等多长时间
- 一个pq就可以把，存的是服务员的开始服务时间和持续时间，每次弹出来最早且最快的，然后开始时间+=持续时间重新放回，重复m次，第m+1次取出来的开始时间就是需要他等待的时间
- 时间范围是 0 -minT[N] * M, 定义一个函数check 在时间t内能不能服务完 M个客人？
- 636 要格式化打印出每一步正在运行的函数。 当一个函数A start之后，如果没结束，再start另一个函数B，那么B就是A的子函数。如果再来个C，D，E类似的，这时候要打印：
- 给一堆坐标点，找里面面积最大的一条边平行于X轴的平行四边形。
- https://www.1point3acres.com/bbs/thread-877541-1-1.html
- 1167
- 1143
- 44
- 460
- https://www.1point3acres.com/bbs/thread-877053-1-1.html
- bike: 1057 1066
- https://www.1point3acres.com/bbs/thread-876745-1-1.html
- 输入一串两个点的名称和坐标位置关系，返回是否存在这样的位置关系（即是否有矛盾的）
例如[1 NE 2, 2 SE 3, 3 W 1]
返回true
解释：1在2的东北方，2在3的东南方，3在1的西方，空间上合理
- 给一个每个人的进出时间输出每段时间有哪些人
A，1，5
B，2，4
输出
1，2，A
2，4，AB
4，5，B
这个面试前正好在面经里看到了，是这个解法：把所有人的开始和结束全部作为事件，扔到一个list里面然后排序，然后拿个set一类的存一下当前有哪些人。类似飞机起落题目
- 是给一串String和dictionary，String是一句话，里面有错的词，正确的词在dictionary里，让你correct
input: Todxy is a god day.
dictionary: today, good
output: Today is a good day
先开始说dictionary是map有一一对应，之后问没有对应只有正确的单词的话怎么办，这里用edit distance
- 2096
- https://www.1point3acres.com/bbs/thread-875971-1-1.html
- 地里出现过的find all bad versions.
给定input数组，相邻的version只能一样bad，或者右侧的version比左侧的version更bad。同时给定一个helper function，input两个不同的version number ，假定为v1，v2，output是两个version时候一样bad，或者v2比v1更bad（假定v1 < v2）。
Lz先口头说了一下暴力解，然后用recursive binary search解出来了。需要注意的是recursive binary search最极端情况下时间复杂度也会达到O(n).
- 给一个二叉树，每个节点都有一个value值，求二叉树中相邻的K个节点所有value可以构成的maximum sum。
Lz的思路是dfs的同时，对于每个节点返回一个数组，数组的index对应 的值是该节点和其子树中任意节点（共index个节点）所能构成的maximum sum。这样只需要遍历所有节点一遍就可以得到最终结果。
- 1153
- https://www.1point3acres.com/bbs/thread-874886-1-1.html
- 已知有一个类， 有两个function可以调用， hasNext(), 和 getNext() 分别输出是否有下一个， 和得到下一个char.
假设已知这个类的两个实例， it1，和it2， 让我们来比较两个类的大小。
例子： it1 = 34.12345789
it2 = 34.12346
如果 it1 < it2: return 1
或者 it1 == it2: return 0
或者 it1 > it2: return -1
- There is a ball on the nth stairs, and it wants to get to the ground(level 0).
During odd time, you can jump down 1, 2 stairs. During even time, you can jump down 2, 3 stairs.
Return the number of ways you can get to ground.
第二题可以把一个stair拆成两个stair，一个odd time stair，一个even time stair，然后再DP。LC70的变种。
Sign in with Wallet
Connect another wallet