https://docs.google.com/document/d/1qxA2wps0IhVRWULulQ55W4SGPMu2AE5MkBB37h8Dr58/
第三轮比较简单，给一个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]。
Follow-up是在原List<Integer>插入n+1，然后返回所有的车队车数可能性。最后问了算法复杂度
1. 输入一些subiterators, 合成一个superiterator, 都是升序的. 类似LC 23 Merge k Sorted Lists. heap搞定.
2. LC 253 Meeting Rooms II
2.第二题是个东南亚老大哥 亚裔，贼严肃，也不说话，上来就说题目， 然后题目是 给你两个string s1 s2, s2会比s1多一个char，
要你找出来那个char的index 比如 today, todxay, return 3
O(1) space better than O(N) time,我想了半天，巧妙一点的二分，follow up是如果两个string 乱序怎么办，就先sort
3.中午一个白人小姐姐带我吃了饭，下午第一轮是个中国大哥，贼亲切，一上来就用中文跟我打招呼，说接下来我们说题目用英文吧
我说好， 题目是 col order tree traversal，就是 一个tree 1 - 2 -3 root 的col是0 left leaf是-1， right leaf 是1
没有follow up跟我中文闲聊了十分钟，真的很感谢，说是自愿来当面试官，希望为华人也多分担一些，给华人学生多一些机会
4. 最后一轮来了两个大哥， 有一个是面试官trainee？??, 第一题是 设计一个tree ？？？ 一天三道tree。。。 然后写个function level order traversal
第二题是 给你个rand（） return 0，1之间的随机值，要你随机从一个dataset中取数据， 就是假如说数据里面有300个美国，100个中国，100个韩国，那么
这个function output 美国的概率就是3/5 etc
http://massivealgorithms.blogspot.com/2015/06/leetcodecount-complete-tree-nodes.html
频率 3次。
1。LC676 magic dictionary 各种变种 所求word再dict单词差一个字母
思路：两种解决思路。可以把words按length存起来然后每有词想search时候遍历查找相符。第二种是存的时候就开始删，记得要记录删的地方的index，最后和所求删的index是否相等
2。LC849 选座位 跟exam room
思路：注意边界条件和怎么判断距离
http://massivealgorithms.blogspot.com/2018/11/leetcode-849-maximize-distance-to.html
3。LC418 sentence screen fitting
思路：见lc
http://massivealgorithms.blogspot.com/2016/10/leetcode-418-sentence-screen-fitting.html
5。LC844 Backspace string compare
思路：简单stack秒杀 注意follow up是O(1) space → two pointers
6。 LC394 s = "3[a]2[bc]", return "aaabcbc".
思路：recursion call括号中间的项
7。LC334 给一个array，arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.
思路：从左到右过array，用两个变量存第一小和第二小的数（初始最大值），更新尽量小的数，若同时遇到第三小的数，则为true
8。LC774 加油站最短距离
思路：用binary search寻找最短的距离，边search边找当前mid是否符合mid条件，注意判断边界条件和mid==target怎么走
这个帖子里要求必须用dp，这里贴一个dp解法。
Dp[i][j]表示前i个加油站增加j个站点最小的最大距离.
9。LC337 二叉树House Robber
思路：dfs+dp存抢当前node和不抢当前node的最大值
10。LC340 longest substring with at most K distinct characters
思路：基本滑动窗口问题，遇到就是赚到
12。LC426 BST撸直变成双向链表 首尾相接
思路：简单DFS。想清楚思路！！！开始dummy当prev留住head，最后prev是tail。其中prev可当做class变量
13。LC215 Kth largest element in an array
思路：可以先用优先队列装个怂，再用quick select
思路：二维dp问题。dp[left][right]代表能在当前段内能扎出来的最高分。memorize是当dp非零则是没计算过。
15。LC769 LC768 问一个array在怎样trunk sorted之后只经过拼接就能得到升序array
思路：[0~n]的array做法为maintain一个max变量存当前max，当max==当前index则count++
无限制array时候做法为构造两个新的array存maxOfLeft和minOfRight。当一个数左看都比自己小，右看都比自己大的时候，则可以trunk。（这个更加generalize
http://massivealgorithms.blogspot.com/2019/02/leetcode-769-max-chunks-to-make-sorted.html
http://massivealgorithms.blogspot.com/2019/02/leetcode-768-max-chunks-to-make-sorted.html
http://massivealgorithms.blogspot.com/2019/02/leetcode-769-max-chunks-to-make-sorted.html
http://massivealgorithms.blogspot.com/2019/02/leetcode-768-max-chunks-to-make-sorted.html
16。LC505 the maze II 求total steps
思路：用BestFS+PQ+memorization做，注意撞墙别忘了往回退一步
17。LC96 Unique Binary Search Trees
思路：递归+memorization
18。LC834 Sum Of distances in tree
思路：两次遍历，更新count和res。第一次post order 第二次pre order
http://massivealgorithms.blogspot.com/2019/03/leetcode-834-sum-of-distances-in-tree.html
***
LC939 && LC963 给一堆坐标点，求坐标点形成的横平竖直矩形最小面积
思路：任取两点当对角线做矩形，存在set里。若已有set存在则因为另外一个对角线存在，更新面积
http://massivealgorithms.blogspot.com/2018/11/leetcode-939-minimum-area-rectangle.html
http://massivealgorithms.blogspot.com/2019/01/leetcode-963-minimum-area-rectangle-ii.html
http://massivealgorithms.blogspot.com/2019/01/leetcode-963-minimum-area-rectangle-ii.html
LC230: Kth smallest in BST，followup 若要改树怎么整 [改树是什么意思？有很多树call这个函数多次？]如果中间有人要insert node to BST的话，如何实现同样功能
思路：建一个TreeNodeWithCount，这样以后改的时候也是log n复杂度。改树的同时改TreeNodeWithCount
http://massivealgorithms.blogspot.com/2016/11/leetcode-230-find-k-th-smallest-element.html
4. 面试官迟到 15 分钟。面试时间实际为 30 分钟。给定一个 picture (二维)。里面有一些有色的像素，保证所有像素是相连的（上下左右相连），且只有一个联通块。返回一个最小矩阵，这个矩阵能包含所有的有色 pixel。
这题是找上下左右的极大和极小值吗
是的 LC302原题，用二分查找做的，上下左右分别二分找边界
http://massivealgorithms.blogspot.com/2015/11/leetcode-302-smallest-rectangle.html
5. 给定一个棋盘，里面有一些棋子。你能移走这个棋子，当且仅当这个棋子的同行同列有其它棋子。要求最多能移走多少棋子。类似LC 947
思路：可以把所有棋子放到list里，每row，col存在的棋子再分别放到set of set of nodes里。用dfs思路第一轮删除任意一点，然后往后推第二次在上一次基础上清除任意满足要求的那个点，直到最后无点可清除时回溯看总共清除了多少。可mem
更新思路：用union find看能有多少组划分出来（如果同行或同列分成一组），然后最多能移走的棋子数=总棋子-组数（number of islands）
follow up ：是应该用什么顺序拿，才能保证能拿最多 (这个follow up应该怎么解呢)尽量先把一个component里的都去掉？
优先拿掉不导致component数量增加的棋子。
| |
| http://massivealgorithms.blogspot.com/2016/10/leetcode-410-split-array-largest-sum.html |
国人。 一个只有正整数的list， 其中插入+， * 或者（），求得到式子最大的值。 e.g. [1，2，1，2 ]-> (1+2)*(1+2)=9. dp解， follow up， 如果有负数该怎么办， 如果想要拿到最大的式子该怎么办。
思路：类似burst balloon dp[i][j] = max of for (k : i ~ j max(dp[i][k - 1] * dp[k][j], dp[i][k - 1] + dp[k][j]))
LC739 array of temperatures, tell me how many days have to wait till next warmer weather
思路：用stack从后往前存，每次看天气时候pop出比栈顶温度低的日子，再peek出比当前暖和的一天index
LC731 持续加intervals，问会不会出现triple booked
思路：按start end加到treemap里，start+1， end - 1，每次从小到大遍历treemap看是否存在count>2
https://massivealgorithms.blogspot.com/2018/04/leetcode-731-my-calendar-ii.html
LC736 非常难 parse lisp expression 注意边界条件和判断条件
思路：分情况 let mult add讨论，用一个parse function处理运算符以后的事宜
https://massivealgorithms.blogspot.com/2019/03/leetcode-736-parse-lisp-expression.html
LC768 乱序数组 chunk出最多组使得每组sort后整个sort好
思路：从右往左扫一遍最小值，从左到右扫一遍最大值。在第二遍途中若看到左最大<=右最小时++
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
- There are two colors in the matrix, find the shortest manhattan distance of two colors
- There are an array of lights. I have a list of intervals, eg [0,2) which means switch the light #0, and light #1. I want to know the final state of these lights
朋友的面经，请问这两道有什么好的方法？
第一题用BFS，第二题区间开头加一结尾减一遍历一遍判断奇偶数？
感觉第一题就是人车匹配，可以bfs也可以heap
第一题面试官说bfs太慢了。。第二题面试官问有没有比O(N) 快的方法
第一题给个例子吧，第二题如果是要确认所有的灯Output 不就O(n)了?如果是像my calendar系列那样一个function change state一个function check，用segment tree或binary index tree把change state和check state都做到log(n)
领我进门的中国小哥。面经上看到过，应该好好写一遍。 {a, b}c{d,e}f 需要return 所有可能的组合，acdf，acef，bcdf，bcef。followup 怎么处理 nested case: a{b{c, d}e{f}}
这个题哪位同学有例题链接求贴
移除石头 + string deduplication + bingo game + skip iterator
SETI Onsite，MTV, Fail
Provider: null
第一轮：白女，LC 947 remove marble，不过输入可以自己定义，我定义的输入是个二维矩阵，好写一点。
http://massivealgorithms.blogspot.com/2018/11/leetcode-947-most-stones-removed-with.html
思路：没什么好说的，直接dfs，本来想用union find，但是面试官明确想让我用dfs去找connected components。写完面试官表示code写得很不错，然后没有follow up
当时写的白板代码：
int count;
int totalCount;
int rows;
int cols;
int[][] graph;
// 0是空格，1是marble
int removeMarble(int[][] graph) {
// sanity check, 这里只是说了下corner case，面试官说不用写
rows = graph.length;
cols = graph[0].length;
this.graph = graph;
for(int i = 0 ; i < rows; i++) {
for(int j = 0 ; j < cols ; j++) {
if(graph[i][j] == 1) {
dfs(i, j);
count++;
}
}
}
return totalCount - count;
}
void dfs(int row, int col) {
totalCount++;
graph[row][col] = 0;
for(int i = 0 ; i < rows ; i++) {
if(graph[i][col] == 1) {
dfs(i, col);
}
}
for(int j = 0 ; j < cols ; j++) {
if(graph[row][j] == 1) {
dfs(row, j);
}
}
}
1. 给一堆职员及其老板的关系，要求实现两个query： A. 输入职员姓名按顺序返回其老板chain B. 输入老板姓名，按顺序返回职员chain
思路：
看起来像常规的建图和搜索
2. 给一个长长的String，String里面有一些char是separator，给一个isSeparator函数可以调用判断是不是separator。separator将该String分成若干部分，判断每部分是不是一个valid password。定义一个valid的password就是长度在6-10的string，包含两个以上的数字和字母。求所有valid password的数目。
思路：Two Pointers
3. google doc 有个comment 功能，每个comment是个tuple（int A，int B）。A表示是指向正文中哪一行的comment, B表示当前comment实际显示在正文对应的哪一行。要求实现用户在前一行插入一个comment后如果space不够了，后面的comment自动下移。
4. 国王住在King's Landing, 他手下有很多的信使，他要发布一项消息给所有的kingdoms，派信使去送信。问通知完所有的kingdoms所需要花费的最长时间。
5. 给两个文件，一个文件A很长，另一个文件B记录的是bad words。要求把文件A里面所有match的文件B里面的bad words替换成掉。
(Provider: anonymous， 匹兹堡office)
第二题：
给一个路径列表，找出每个路径在列表里的parent路径。例子：exports = [“/a/b/c”, “/abc/foo”, “/a”, “/abc”, “/a/b”, “/foo/abc”]，return [[“/a/b”, “/a”], [“/abc”], [], [], [“/a”], []]
思路：建立trie，在node里有map of children和boolean isValid。然后遍历exports，到最后一个node把isValid设为true。再遍历exports，如果碰到isValid为true的parent node就把当前string加入结果。时间复杂度O(m*n)，m为路径个数，n为每个路径里“/”的个数。
第三题：
删除二叉树中多余的一个edge。假设input是root node，而且删完edge后还是root。
例子： 1
/ \
2 3
/ \ /
4 5
删除2-5或3-5都可以
follow up: 如何测试？
思路：从root开始遍历，建立set保存visited node，如果碰到有node的儿子已经在set里就删除这个edge。（lc 685的超级简化版）
第四题：
面经题，给定宽为w高为h的screen，和一句话string，还有字体的上限和下限，问能使这句话fit进screen的最大字体。有两个写好的api分别是getWidth(Character c, int font), getHeight(int font)。
思路：二分法找median font，然后parse string看能不能fit进screen。
刚刚面完的Onsite
new grad SETI Sunnyvale
lc 484 find permutation
第一轮：
印度小哥
第一题：给一个pattern “IIDDI”, D代表decrease, I代表increase，找出能满足这个pattern的由数字1到n组成的值最小的Permutation，n=pattern.length+1，比如上面这个例子结果就是125436
思路：
先将原数组升序排列，满足了所有的I, 然后对于连续的D，全部reverse
code:
class Solution {
public int[] findPermutation(String s) {
int len = s.length();
int[] res = new int[len + 1];
for(int i = 0 ; i < res.length ; i++) {
res[i] = i + 1;
}
for(int i = 0 ; i < len ; i++) {
if(s.charAt(i) == 'D') {
int j = i;
while(j < len && s.charAt(j) == 'D') j++;
reverse(res, i, j);
i = j - 1;
}
}
return res;
}
private void reverse(int[] arr, int left, int right) {
int l = left, r = right;
while(l < r) {
swap(arr, l++, r--);
}
}
private void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
二叉树找最多siblings的层
第二题：给一个二叉树，找maximum size of level which has the largest number of siblings。这里sibling的定义就是从这一层的左端点到右端点的所有存在或者不存在的node，也就是假设这中间的Parent都有左右孩子的情况下，从左端点到右端点总共有多少个。
思路：
利用完全二叉树的index性质，按层遍历，记录每层起始node的index和末尾的index，相减后得到的距离，然后更新最大值
code：
Provider: null
private class MyNode {
int idx;
TreeNode node;
public MyNode(TreeNode node, int idx) {
this.node = node;
this.idx = idx;
}
}
public int maxSiblings(TreeNode root) {
if(root == null) return 0;
int res = 0;
Queue<MyNode> queue = new LinkedList<>();r
queue.offer(new MyNode(root, 1));
while(!queue.isEmpty()) {
int size = queue.size();
int first = queue.peek().idx;
while(size-- > 0) {
MyNode curr = queue.poll();
if(curr.node.left != null) {
queue.offer(new MyNode(curr.node.left, curr.idx * 2)); //如果树比较高，会很快溢出的
}
if(curr.node.right != null) {
queue.offer(new MyNode(curr.node.right, curr.idx * 2 + 1));
}
res = Math.max(res, curr.idx - first + 1);
}
}
return res;
}
棋盘上铺多米洛骨牌
lc 790 follow up poj 2446
第二轮：
中国大哥
给一个2*n的board，每个格子有两种情况，为空或者被block了。现在有大小为1*2的多米诺骨牌，问这个board最多能放多少个骨牌
思路：
动态规划
dp[i] 表示[0, i] 的最多骨牌
case 1: i列上没有block
dp[i] = dp[i - 1] + 1;
case 1.1: 如果dp[i-1]也没有block
dp[i] = max(dp[i], dp[i-2] + 2)
case 2: i列上有一个block
dp[i] = dp[i-1]
case 2.1: 如果i-1列上没有block or i-1上有一个block在同侧
dp[i] = max(dp[i], dp[i-2] + 1)
case 3: i列上有两个block
dp[i] = dp[i - 1]
- 这道题面经是我贡献的，为了不让大家觉得这道题难得过分以及花太多时间在这道题上，我想具体说明一下。根据面试时面试官给我的信息，这道题能够用greedy或者dp做出2*n的情况就已经非常不错了，如果你能答出m*n的思路当然非常加分，但是即使不知道也完全没关系，更不用要求能写出代码了。我自己在面的时候也只是在面试官的帮助下写出了dp，followup完全是面试官自问自答lol，最后还是过了HC。所以希望大家不用太panic，时间有限的情况下可以不用太在意followup
followup: board的size为m * n
思路：
二分图的最大匹配,匈牙利算法
对于一张二维矩阵，我们可以将所有cell分为两个点集，(x, y), x+y为奇数，x+y为偶数。
其中x+y为奇数被4个x+y为偶数包围，x+y为偶数被4个x+y为奇数包围，所以一条多米诺骨牌其实就是链接两个点集中的一条匹配边，这个题目就可以转化为删除两个点集中的一些点，求剩下点集的最大匹配，用匈牙利算法。
code
provider: null
// board[i][j] = 1 -> blocked, 0 -> unblocked
List<List<Integer>>point;
int rows;
int cols;
int[][] board;
int[] link;
boolean[] used;
public int chessBoard(int[][] board) {
// init parameters
this.board = board;
rows = board.length;
cols = board[0].length;
point = new ArrayList<>();
link = new int[rows * cols];
used = new boolean[rows * cols];
for(int i = 0 ; i < rows * cols ; i++) {
point.add(new ArrayList<>());
}
for(int i = 0 ; i < rows ; i++) {
for(int j = 0 ; j < cols ; j++) {
if(i - 1 >= 0 && board[i-1][j] == 0) {
point.get(i * cols + j).add((i - 1) * cols + j);
}
if(i + 1 < rows && board[i + 1][j] == 0) {
point.get(i * cols + j).add((i + 1) * cols + j);
}
if(j + 1 < cols && board[i][j + 1] == 0) {
point.get(i * cols + j).add(i * cols + (j + 1));
}
if(j - 1 >= 0 && board[i][j - 1] == 0) {
point.get(i * cols + j).add(i * cols + (j - 1));
}
}
}
Arrays.fill(link, -1);
// hangary algorithm
return hangary();
}
boolean find(int x) {
for(int i = 0 ; i < point.get(x).size() ; i++) {
int vertex = point.get(x).get(i);
if(used[vertex]) continue;
else {
used[vertex] = true;
if(link[vertex] == -1 || find(link[vertex])) {
link[vertex] = x;
return true;
}
}
}
return false;
}
int hangary() {
int ans = 0;
for(int i = 0 ; i < rows ; i++) {
for(int j = 0 ; j < cols ; j++) {
if(board[i][j] == 0) {
Arrays.fill(used, false);
if(find(i * cols + j)) {
ans++;
}
}
}
}
return ans;
}
判断表达式是否合法
第三轮：
中国小哥
第一题：给一个表达式算术1+2*(3-4)，判断它是否合法，可能出现的字符就是数字、运算符、括号和其他非法字符。先要求提出一些比较模糊的case比如(0)、+5然后自己定义它们是否合法，然后问如果有人写好这么一个程序，你会用哪些test case来测试它，最后implement。
思路：
感觉就是考想出来所有corner cases
第二题：有一个填满了的数独board，已知有且只有一个数字填错了，且这个数字还是在1-9之间，找出这个填错的数字的坐标。
第四轮 直接扔给我一张纸，一开始看到题目是懵逼的 ，输入是一堆线段，找所有可以形成的正方形的数量，自己设计数据结构和算法。clarify之后如下，平面无限大，线段都是水平或者竖直，不会cross，但端点可能在另一个线段上。解法大概是枚举对角线，然后check四条边，但是不能直接check每一条边是不是在input 的线段当中，因为可能正方形的一条边是由多个input线段组成的，或者完全被包含在某一个线段当中，所以需要对所有x和y值建segment tree，然后每一个查四条边是不是完全被当前坐标的segment tree cover
有没有同学可以分享一下思路,如何用线段树判断一段距离都被cover了
思路：不用线段树的操作，建立两个并查集来merge水平和垂直方向上坐标相同的点。 初始状态是一堆输入的线段就可以认为是并查集的初始状态。
LC Car Fleet (频率 8)
第三轮比较简单，给一个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]。
Follow-up是在原List<Integer>插入n+1，然后返回所有的车队车数可能性。最后问了算法复杂度
思路：
感觉比原题 car fleet还要简单一些，直接从前往后扫一下，如果cars[i-1] < cars[i], cars[i] = cars[i-1]，然后分别统计连续的数字个数
最大化连续子串最小sum (LC 410)
有一个数组，分成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。
思路：
如题主描述
这个题应该可以用binary search 解，思路与 lc410 相似
矩阵填字符
一个矩阵，里面有空字符和abc等character，用最近的字符填满矩阵。
A ‘’ ‘’ ‘’ ‘’
‘’ ‘’ ‘’ ‘’ ‘’
‘’ ‘’ ‘’ B ‘’
空字符填上最近字符，有tie的话随便选一个
follow up：char比空字符多
思路：
先扫一遍得到有哪些字符，然后对每个字符best-first search, 用min heap当queue，heap里面装
Node{
int i; int j;
char c; int distance;
}
根据distance来决定优先级，距离小的在前面，每次poll出来一个新node看那个位置上有字符没有，没有的话填上，有的话忽略
code
Provider: null
public void fillMatrix(char[][] matrix) {
int rows = matrix.length;
int cols = matrix[0].length;
Queue<Node> pq = new PriorityQueue<>((a, b) -> a.dis - b.dis);
for(int i = 0 ; i < rows ; i++) {
for(int j = 0 ; j < cols ; j++) {
if(matrix[i][j] != ' ') {
pq.offer(new Node(i, j, matrix[i][j], 0));
}
}
}
int[][] dirs = new int[][] {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
while(!pq.isEmpty()) {
Node curr = pq.poll();
if(matrix[curr.i][curr.j] == ' ') {
matrix[curr.i][curr.j] = curr.c;
}
// generate
for(int[] dir : dirs) {
int x = curr.i + dir[0];
int y = curr.j + dir[1];
if(isValid(matrix, x, y) && matrix[x][y] == ' ') {
pq.offer(new Node(x, y, curr.c, curr.dis + 1));
}
}
}
}
private boolean isValid(char[][] m , int i, int j) {
return i >= 0 && i < m.length && j >= 0 && j < m[0].length;
}
private static class Node{
int i; int j; char c; int dis;
public Node(int i, int j, char c, int dis) {
this.i = i;
this.j = j;
this.c = c;
this.dis = dis;
}
}
int rows = matrix.length;
int cols = matrix[0].length;
Queue<Node> pq = new PriorityQueue<>((a, b) -> a.dis - b.dis);
for(int i = 0 ; i < rows ; i++) {
for(int j = 0 ; j < cols ; j++) {
if(matrix[i][j] != ' ') {
pq.offer(new Node(i, j, matrix[i][j], 0));
}
}
}
int[][] dirs = new int[][] {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
while(!pq.isEmpty()) {
Node curr = pq.poll();
if(matrix[curr.i][curr.j] == ' ') {
matrix[curr.i][curr.j] = curr.c;
}
// generate
for(int[] dir : dirs) {
int x = curr.i + dir[0];
int y = curr.j + dir[1];
if(isValid(matrix, x, y) && matrix[x][y] == ' ') {
pq.offer(new Node(x, y, curr.c, curr.dis + 1));
}
}
}
}
private boolean isValid(char[][] m , int i, int j) {
return i >= 0 && i < m.length && j >= 0 && j < m[0].length;
}
private static class Node{
int i; int j; char c; int dis;
public Node(int i, int j, char c, int dis) {
this.i = i;
this.j = j;
this.c = c;
this.dis = dis;
}
}
不需要用priority queue吧，简单的queue就可以了
Merge K Sorted Lists + Meeting Room II
第一轮：1. 输入一些subiterators, 合成一个superiterator, 都是升序的. 类似LC 23 Merge k Sorted Lists. heap搞定.
2. LC 253 Meeting Rooms II
第四轮：
中国小哥哥。
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). 谢谢小哥哥了.
中国小哥哥。
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). 谢谢小哥哥了.
这题是不是LC417, BFS可以达到O(kmn)
类似，另外能不能用一个int[][] matrix来记录（i,j）能到达target的数量，就是从target bfs时候每到一个点matrix(i,j)+1，最后看matrix哪几个点的数字是target的个数？感觉可以不用每一个bfs一个存一个set
第五轮：
模拟抓娃娃机。
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里. 面试官就是看看我怎么想的, 说是知道不太好写.
模拟抓娃娃机。
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里. 面试官就是看看我怎么想的, 说是知道不太好写.
Tree Isomorphism Problem LC951(频率7)
1.一开始是个白人老大哥，跟我闲聊了差不多10分钟，介绍了他们组的项目，问我对于google什么项目感兴趣，然后看时间差不多了，出题
题目是check which two tree are similar, 就是一个function， 就是 1 - 3 - 2 和 1 -2 -3 就是similar， 然后follow up问我recursion的runtime，
我太紧张了硬是没有答出来 具体题目看连接 https://www.geeksforgeeks.org/tree-isomorphism-problem/ 估计我就是挂在这里
题目是check which two tree are similar, 就是一个function， 就是 1 - 3 - 2 和 1 -2 -3 就是similar， 然后follow up问我recursion的runtime，
我太紧张了硬是没有答出来 具体题目看连接 https://www.geeksforgeeks.org/tree-isomorphism-problem/ 估计我就是挂在这里
思路：
dfs，经典题目
两个string找多出来的char
2.第二题是个东南亚老大哥 亚裔，贼严肃，也不说话，上来就说题目， 然后题目是 给你两个string s1 s2, s2会比s1多一个char，
要你找出来那个char的index 比如 today, todxay, return 3
O(1) space better than O(N) time,我想了半天，巧妙一点的二分，follow up是如果两个string 乱序怎么办，就先sort
思路：
如果没有duplicate的话，根据时间空间复杂度要求自然联想到二分查找：
在长的string上二分
mid = l + (r - l) / 2
每次比较长的mid位置上的char和短的mid位置上的char是否一样，因为最多只会被插入一个字符，一样的话，说明左边部分没被插入东西，target一定右边，否则target在左边
注意：空串需要特殊处理，不然charAt会抛异常
如果有duplicate，感觉无法better than O(N)，一个极端例子dddddddddd, dddddddddde,如果不check每个位置的话，无法找到多余的那个字符
code
Provider: null
public int findExtra(String s1, String s2) {
if(s1.length() == 0) return 0;
if(s2.length() == 0) return 0;
String longer = s1.length() > s2.length() ? s1 : s2;
String shorter = s1.length() > s2.length() ? s2 : s1;
int l = 0, r = longer.length() - 1;
while(l + 1 < r) {
int mid = l + (r - l) / 2;
if(longer.charAt(mid) == shorter.charAt(mid)) {
l = mid;
} else {
r = mid;
}
}
if(longer.charAt(l) != shorter.charAt(l)) return l;
else return r;
}
def find_extra(str1, str2):
if len(str1) > len(str2):
str1, str2 = str2, str1
lo, hi = 0, len(str1)
while lo < hi:
mid = (lo + hi) >> 1
if str1[mid] != str2[mid]:
hi = mid
else:
lo = mid + 1
return loBinary Tree Vertical Order Traversal #LC 314 and LC 987
3.中午一个白人小姐姐带我吃了饭，下午第一轮是个中国大哥，贼亲切，一上来就用中文跟我打招呼，说接下来我们说题目用英文吧
我说好， 题目是 col order tree traversal，就是 一个tree 1 - 2 -3 root 的col是0 left leaf是-1， right leaf 是1
没有follow up跟我中文闲聊了十分钟，真的很感谢，说是自愿来当面试官，希望为华人也多分担一些，给华人学生多一些机会
思路：
- preorder标记每个node的vertical和level坐标，用map存，或者自定义类
- 如果同一个position上的node也有顺序的话还得排序
代码：主要思想是map + BFS，map可以对key进行排序
provider: (please fill your name)
class Solution {
public:
vector<vector<int>> verticalOrder(TreeNode* root) {
vector<vector<int>> res;
if (!root) return res;
queue<pair<TreeNode*, int>> q;
q.emplace(root, 0);
map<int, vector<TreeNode*>> m;
while(!q.empty()) {
int len = q.size();
for (int i = 0; i < len; i++) {
auto tmp = q.front();
q.pop();
m[tmp.second].push_back(tmp.first);
if (tmp.first->left) q.emplace(tmp.first->left, tmp.second - 1);
if (tmp.first->right) q.emplace(tmp.first->right, tmp.second + 1);
}
}
for (auto ele : m) {
res.push_back(vector<int>());
for (auto node : ele.second) {
res.back().push_back(node->val);
}
}
return res;
}
};
public:
vector<vector<int>> verticalOrder(TreeNode* root) {
vector<vector<int>> res;
if (!root) return res;
queue<pair<TreeNode*, int>> q;
q.emplace(root, 0);
map<int, vector<TreeNode*>> m;
while(!q.empty()) {
int len = q.size();
for (int i = 0; i < len; i++) {
auto tmp = q.front();
q.pop();
m[tmp.second].push_back(tmp.first);
if (tmp.first->left) q.emplace(tmp.first->left, tmp.second - 1);
if (tmp.first->right) q.emplace(tmp.first->right, tmp.second + 1);
}
}
for (auto ele : m) {
res.push_back(vector<int>());
for (auto node : ele.second) {
res.back().push_back(node->val);
}
}
return res;
}
};
Random Pick With Weight #LC 528
4. 最后一轮来了两个大哥， 有一个是面试官trainee？??, 第一题是 设计一个tree ？？？ 一天三道tree。。。 然后写个function level order traversal
第二题是 给你个rand（） return 0，1之间的随机值，要你随机从一个dataset中取数据， 就是假如说数据里面有300个美国，100个中国，100个韩国，那么
这个function output 美国的概率就是3/5 etc
思路：
见lc
王位继承（10+频率）+歌词找单词+sign tree+找重复元素
第一轮 王位继承 美国小姐姐 这轮感觉还可以
第二轮 给两个 string 分别是lyric 和 word，问能不能用lyric 构成 word
比如 lyric "HIT ME BABY ONE MORE TIME" word = "BOOM" 那么是可以的
follow up 是优化时间
第三轮 给两个 tree， root1 root2, 问计算结果等不等
tree 里面只有 加号 和 字母， 并且 input 保证valid.
加号就是hashmap统计词频
减号是dfs的时候把sign传进去？
这题加了减号，不是一般的麻烦，类似basic计算器的那题，而且还不好合并，那道题是数字，这题是字母
传sign可以，然后如果是负数，可以存小写字母的对应大写（如果全是小写的话，如果不是，就自定义个映射），最后还是比较hashmap
第四轮 LC 287 find duplicate number
给一个数组长度为n+1，包含从1到n到数字，有重复元素，找出重复元素
开始没反应过来 后来才反应过来的。
follow up 就是优化空间，牺牲时间。
最后 他直接说告诉你这个 想看看我写binary search 看我的code implement ability
思路：
- 初始解法：用set（可以先装一波没见过）
- 如果数组可以改变，用heap sort可以做到o(1)空间 o(nlogn)时间
- 如果数组不可以改变，可以提出最优解 - 快慢指针找环和找环的入口，不过这里可能会被问到证明找环的入口的算法正确性，略麻烦
- 面试官期待的binary search 做法，o(1)空间，O(nlogn)时间,不改变数组
对值域进行二分[1, n]，如果count出来小于等于mid数字个数比mid多，说明dupliate在mid左边，反之小于等于mid的数字个数等于mid或者比mid少，duplicate在mid右边
Code
Provider: 九章算法
public int findDuplicate(int[] nums) {
int l = 1;
int r = nums.length - 1; // n
while (l + 1 < r) {
int mid = l + (r - l) / 2;
if (count(nums, mid) <= mid) {
l = mid;
} else {
r = mid;
}
}
if (count(nums, l) <= l) {
return r;
}
return l;
}
private int count(int[] nums, int mid) {
int cnt = 0;
for (int item : nums) {
if (item <= mid) {
cnt++;
}
}
return cnt;
}
二叉树删除多余边 （频率 13）
第一轮是一个比较严肃的美国小哥，题目不难但我太紧张导致脑子短路: 一个binary tree里有1个extra edge，找到并且fix。我用dfs做的，然后写完小哥让我自己找我的code能不能cover所有的情况, 然后发现并不能，改了几下之后code终于能work。反正这轮磕磕绊绊，要挂就挂在这了。
完全树数node（频率 5）
第二轮是个超酷的打耳钉的美国小姐姐。高频题LC222，先给你一个数，找这个数在不在tree里面，followup找到树的大小。这轮真是 使尽各种演技。。。
http://massivealgorithms.blogspot.com/2015/06/leetcodecount-complete-tree-nodes.html
用路径string找word
第三轮美国小哥，题目很长很绕但交流之后其实很简单，简洁地表述下大概就是：用户在手机屏幕上滑动打字， 给你一串string记录了你手指滑动经过的char，举个例子比如， “hrwcewelwlcfo”, 这个手指滑动可以打出一个”hello”。用户从h开始，手指划过“rwc”, 打出一个“e”, 划过”we“, 打出”l“, 划过w, 打出”l“, 再划过”cf“, 打出“o”. 这样就打出“hello”，很神奇有没有？？
然后给你一个路径的string和一个dictionary of words, 问你有多少个word可以被用这个路径打出来。路径的第一个字符和最后一个字符一定是会被打出来的。这题本质很简单基本靠交流。 我说了两种方法，一种从路径入手，排列组合，一个一个放到dictionary里面查；另一种一个一个word拿出来，two pointer比较。比较了两种方法的复杂度，还算了一些数学公式，写了第二种的code。followup是如果在同一个位置可以停留多次怎么做，就是在同一个char上可以重复打好多次。比如“hwelpto”也可以打出“hello”，这里“l”重复打了两次，也不难，秒了。
lc853原题car fleet
第四轮印度哥, 是sweti，题也很简单，一列车队n辆车，速度分别是1到n，随机排列成一条，然后开始开，不能超车，问你无限时间之后return一个车队cluster array，每个数代表cluster里车的个数，要按顺序。比如input【2， 3， 1， 4】返回的是【2，2】。一开始我以为他要问cars fleet那题，没想到问了个更简单的。。。follow up是现在有一辆车speed是n+1，我们把它加入到这个n车车队的空隙中，总共n+1个空隙，然后问你每种加入，最后导致的车队cluster array，就是return一个array of array。写完followup之后讨论怎么test。
House Robber III (频率 5)
思路：见LC337，返回两个结果的recursion函数
抽搐词(lintcode twitch words)
返回重复超过三次的letter的起点和终点
Example
Given str = "whaaaaatttsup", return [[2,6],[7,9]].
Explanation:
"aaaa" and "ttt" are twitching letters, and output their starting and ending points.
follow up：给一个dic，通过删除生成合法的词语
思路：backtracking
