https://docs.google.com/document/d/1qxA2wps0IhVRWULulQ55W4SGPMu2AE5MkBB37h8Dr58/edit#
删比这个数小的和比这个数大的我分成了两个function，一个其实就够了，但我和面试官说要increase readability，故意分成两个的，不是我不会，他说可以。最后面试完我问他您觉得我这个solution 可以吗？他说他觉得不错
LC 128 Longest Consecutive Sequence
题：
给一个array，全是int，求找出最长的sequence的长度，longest consecutive sequence。
例：[7，2，4，3，5]， return 4，因为最长的sequence是2345
分享一个小idea： 每次看到题目给一个list，然后答案不需要index的时候，想想能不能sort做。
我第一想法就是这道题sort之后就很简单了，先sort O(nlogn) + 走一遍找最大 O(n) + space O(1)， 然后和面试官说sort可以做但是肯定还有更优解，面试官打断我说你先把这个sort写出来，然后we go from there。
写出来花了15分钟，包括一开始的一些clearification花费的时间。
然后就觉得应该用hashmap，能比nlogn更快的我当时只想到hashmap，卡住了2-5分钟，面试官说你的方向是对的，但能不能用set呢，我说能，然后准备每找到一个数，就从那个数开始，把set里的比他大的数删掉，结果发现不行，面试官提示我你可以删大的和小的都删，然后花了10分钟写出来了，最后问我你有没有什么问题要问我的，我瞎扯了一通。然后时间就用完了。
例：[7，2，4，3，5]， return 4，因为最长的sequence是2345
分享一个小idea： 每次看到题目给一个list，然后答案不需要index的时候，想想能不能sort做。
我第一想法就是这道题sort之后就很简单了，先sort O(nlogn) + 走一遍找最大 O(n) + space O(1)， 然后和面试官说sort可以做但是肯定还有更优解，面试官打断我说你先把这个sort写出来，然后we go from there。
写出来花了15分钟，包括一开始的一些clearification花费的时间。
然后就觉得应该用hashmap，能比nlogn更快的我当时只想到hashmap，卡住了2-5分钟，面试官说你的方向是对的，但能不能用set呢，我说能，然后准备每找到一个数，就从那个数开始，把set里的比他大的数删掉，结果发现不行，面试官提示我你可以删大的和小的都删，然后花了10分钟写出来了，最后问我你有没有什么问题要问我的，我瞎扯了一通。然后时间就用完了。
删比这个数小的和比这个数大的我分成了两个function，一个其实就够了，但我和面试官说要increase readability，故意分成两个的，不是我不会，他说可以。最后面试完我问他您觉得我这个solution 可以吗？他说他觉得不错
翻转字符串到目标字符串(Isomorphic Strings变种)
题目很多人在面经里贴过：给定一个字符串s，问能不能转化成另一个字符串p，条件是每次转换要把所有相同的字母一起变动，例子如: abca(两个a一起变) -> dbcd(变c) -> dbed(变b) -> dced。所以abca能转化成dced，return true。
我目前只能想到：
首先必须原来s中字符相等的几个位置，在p中都要被转化成同一个字符，否则 return false
请大家指点一下思路，或者说下证明过程，谢谢啦！`
|
Idea:
如果有环，需要用中间tmp字符解开环后再变换
a->b->c->a需要变成a->b->c, c->k->a，这样解开字母之间的相互影响
如果tmp字符可以重复利用，一个tmp可以解开所有环，如果不能，一个环需要一个tmp字符
Code：tmp无法重复利用
Provider: null
private boolean isomorphic(String s, String p) {
if(s == null) return p == null;
if(p == null) return s == null;
if(s.length() != p.length()) return false;
int tmpNum = 26;
char[] str = s.toCharArray();
char[] pat = p.toCharArray();
Map<Character, Character> map = new HashMap<>();
for(int i = 0 ; i < str.length ; i++) {
if(map.containsKey(str[i])) {
if(map.get(str[i]) != pat[i]) return false;
} else {
map.put(str[i], pat[i]);
tmpNum--;
}
}
if(tmpNum > 0) return true;
boolean[] visited = new boolean[26]; // 找环
for(Character key: map.keySet()) {
if(!visited[key - 'a']) {
Character curr = key;
while (!visited[curr - 'a']) {
visited[curr - 'a'] = true;
curr = map.get(curr);
if(curr == null) break;
}
if(curr != null) return false;
}
}
return true;
}
还原黑白图片
给一个只有黑白pixel的图片，调用给定的两个method，把图片重新画出来。两个method分别是：int readSource(int x1, int y1, int x2, int y2)和void writeTarget(int x1, int y1, int x2, int y2);
补充
题目意思大概是要利用第一个method来判断坐标区域内是否为全黑全白或者都有，三种情况会分别返回1,-1,0。第二个method是在坐标区域内画图，但是画出来的图只有黑色。
|
·LC类似题目：427 construct quad tree
思路：
- dfs解法，先检查当前square是否全黑全白，如果全黑，涂黑当前区域，返回，如果全白，返回，如果有黑有白，按照construct quad tree的的思路分成4块递归
5-5
给候选人投票，票有时间点和候选人。问给定时间点选winner（不频繁调用）LC911 Online Election
Follow up：1. Top 1 2. Top k 3. 给top k求时间
思路：1. 前两个用hash table + 优先队列
2. 第三问（个人思路）用链表bucket存得票数，sort选票，遍历往链表上加。每次从后往前遍历k个查看是否符合要求（n*k）
7-25
LC60反向 给一个[2,1,3] 数字1-n，无重复，valid排序 返回他是排序中的第几个？
思路：第n位数字确定后的全排有(n-1)!个，所以题中百位2开头就说明1开头的都在前头，而1开头的数字有2个，以此类推到十位等等
7-25
1。LC20 valid parentheses
2。LC801 给两个等长array，assume互换位置后能全都递增，问最少换几次
思路：1. Stack 2. Dp记录当前节点换和不换的最少次数，注意条件别漏写
4-22
1。给double[]和target，用’+’ ’-’连接成target，输出可以得到target的所有方法
2。给string pairs [dogs, are], [cats, are], [are, cute], return “dogs cats are cute” 无环
思路：1. DFS + backtracking, 2^n 复杂度 每个空格可插加、减（memorization？怎么做）
3. LC210 拓扑排序 先构建dependency map，再DFS或BFS遍历 （DFS从头到尾各元素做DFS，途中碰到环false，BFS先扫一遍选出0dependency的种子点、每次减依赖、遍历后发现没全遍历则false）
中国/韩国小姐姐（全程期待中文脸，然而小姐姐全程英文，也许不是中国人？）
问我玩过candy crash没有，然后给我解释了一下游戏怎么玩（是消消乐吧？）
题目是candy crush游戏：一个board，每个格子里都要放随机的颜色。如果连续三个格子颜色相同，就可以消掉。可以swap相邻格子的颜色，使得出现能消掉的颜
input是int row, int col, int color，m和n是board的长宽，int color是颜色的种类。比如我假设是color = 5的时候，我们可以选0，1，2，3，4这样，小姐姐说可以哇
写一个method生成游戏的开局
要求：
随机生成，不能有地方直接消掉（不能有连续三个相同的颜色），比如:
1 2 3
1 3 4
1 3 4， 这样第一列就消掉了
follow up：能够走至少一步（必须存在至少一个地方，通过swap能消掉颜色）
这题还蛮好玩的，小姐姐也全程积极一起讨论，还会鼓励笑着跟你说that's prety cool!哈哈哈感谢小姐姐！
2.第二轮面试， 中国小哥， 字符串转换那道面经题，输入是String src, String target, 问你是否可以从src转换到target, 返回boolean. 比如abc -> def，转换方法就是建立映射map， a->d, b->e, c ->f转换具体过程就是abc -> dbc -> dec -> def.这是最简单的情况。如果字符串map是有环的，例如, ab -> ba, 其中的环就是a->b->a,这会造成转换失败。ab -> bb ->aa ->bb .......， 但是呢你可以借助第三个变量来完成转换，还是ab -> ba, 你可以建立map a->c b->a, c->b, 转换过程就是， ab ->cb -> ca ->ba。所以其实ab -> ba是可以成功转换的，返回true。 所以失败的case就是，如果你没有这样额外的变量c可以借用来解决换的问题了。假设字符集只有a-z， 你abcdef....z -> bcdef...za就不能转换，因为在26个字母中没有额外字母可以用来解环。
第一轮的小姐姐说这题她第一次出
有一个binary tree（不是平衡的） 两个人A和B轮流占领node
规定每一次占领node的时候只能占领自己已经拥有的node相连的node 如果对方无node可占领，则获胜
现在已经知道了A的第一步占领的node A，求B的第一步应该落在哪
follow up是 如果你是A 第一步应该落在哪 讲了思路写了一部分postorder的代码
思路：count subtree of all neighbors, where the max is the start point of player 2
public List<Integer> kthUser(int[][] log, int K){ }
----------------
input: int[][] log=new int[n][3], log代表user可能在这个interval里任意时间点访问过这个网站:
@log[0]: user id;
@log[1]: start time;
@log[2]: end time;
问第k个访问网站的用户可能有哪些，返回他们的user id，顺序随意；
eg. log=[[1,20,30],[2,0,50],[3,45,70],[4,35,55]],
if(K==1)---->return res=[1,2];
if(K==2)---->return res=[1,2,3,4];
if(K==4)---->return res=[2,3,4];
思路：用enddatesort，取第K个寻找与这个interval有intersection的就是
这里的思路我个人认为是很容易举出反例的，比如有特别长跨度的interval存在的情况下，举例，k = 2, [1, 5, 10], [2, 11, 16], [3, 5, 20] 这种情况下每个人都有可能是第二个访问的，而不是只有2和3
valid(intv[x]) -> # of (intv[i].end < intv[x].start) < K && #(intv[i].start < intv[x].end) >= K
public int NumberOfDistinctIsland(int[][] matrix){ }
--------------
LC 711 Number of Distinct Island II
给一个只包含0、1的matrix，0为水，1为岛，岛屿为四联通区域。返回distinct的岛屿的数目。
如果一个岛屿通过上移、下移、左移、右移可以和另一个岛屿完全重合，它们被认定为一个岛屿；Eg.
if matrix=={
[1, 1, 1, 0, 0, 0],
[1, 1, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 0],
[1, 1, 1, 0, 0, 0],
[1, 1, 0, 0, 1, 1]}
return 3;
左上角左下角岛屿相同，被判定为一个岛屿，matrix[2][3]为一个岛屿，右下角还有一个岛屿，共三个
思路：将岛屿用dfs遍历方式编码去重
在一个平面上有很多的矩形，有的有overlap，有的没有，现在已知有个算法可以随机产生一个在矩形覆盖范围内的点，然后让你设计算法来验证这个算法产生的点在矩形覆盖范围中确实是随机分布的，而不会集中在某个矩形中，或者只分布在矩形的一个角上。
__L_R__ 题目是一个一维的棋盘，上面有l和r两种棋子，l只能往左走，r只能往右走，不能跨过其他棋子，下划线代表空格。给初始和最终的两个state作为input，输出一个boolean，判断第二个state是否可以由第一个state通过若干操作达成
b. Follow up，棋子走到边界会消失
思路：LC777 双指针两边一起过LR，忽略空格。判断位置是否合理。follow up用subarray方法判断。
挂的是这轮，要找长度为50的bar code, bar code是由黑白两色构成，第一个和最后一个只能是白色，且最多连续三白和连续三黑，问有多少种符合条件的 bar code.
维护一个50×6的dp。50是barcode的长度，6只一共只有六种结尾的状态，即：1白， 2连白， 3连白， 1黑， 2连黑， 3连黑。. 1point3acres
int Solution::google(void) {
vector<vector<int>> dp (6, vector<int> (50, 0));
dp[0][0] = 1;
int mod = 1e9 + 7;
for (size_t i = 1; i < dp[0].size(); ++i) {
// end with 1 white
dp[0][i] = (dp[3][i - 1] + dp[4][i - 1] + dp[5][i - 1]) % mod;
// end with 2 white
dp[1][i] = (dp[0][i - 1]) % mod;
// end with 3 white
dp[2][i] = (dp[1][i - 1]) % mod;
// end with 1 black
dp[3][i] = (dp[0][i - 1] + dp[1][i - 1] + dp[2][i - 1]) % mod;
// end with 2 black
dp[4][i] = (dp[3][i - 1]) % mod;
// end with 3 black
dp[5][i] = (dp[4][i - 1]) % mod;
}
return dp[0].back() + dp[1].back() + dp[2].back();
}
给一个场景，比如Gmail的每个用户（如果没有自己设置头像）就会自动分配一个头像，有着名字首字母和一个特定的背景颜色。问题是给定一个List<Color> colors，给一个List<String> names，给每个名字分配一个颜色。分配规则是：相同的人必须有相同的颜色；相邻的名字要有不同的颜色。Followup：再设计一个函数，使得输入一个名字，就能输出一个Color，但除了List<Color> colors之外，不能有其他的global variables （就是说不能有个global 的map来存映射关系了）。比较两种方法的pros and cons。
思路：相邻name建无相连接图，暴力bfs着色
给一个List<int[]> 存放一大堆坐标。坐标用来描述一副画好的map。坐标依次为 最左下方的顶点，沿边顺时针各顶点。比如：
B________C
| |
| E__|D
|______|
A F
再给一个坐标（X,Y）判断坐标是不是在闭合的图内。（坐标假设valid 即永远可以构成一个闭合图形， 且边要么竖直要么水平 没有斜边）
思路：可以选择一个方向 水平or 竖直 然后向一个方向做射线，如果交过两条边，那么这个点就在图外（偶数都是图外，可以自己画图试试）
给你一个array，每个数字代表工作量。再给一个K，表示最多几天做完。要minimize 每天工作量的max。比如说给你[1,2,3],要一天内做完，那么答案就是6，要两天内做完的话，可以第一天做1，第二天做5，也可以第一天做3，第二天做3。这种情况下output是min{max{1, 5}, max{3, 3}} = 3
思路：1. Binary search找res，然后遍历validate 2. 二维dp[i][j] i：用前i个工作j天内做完要多少工作量 recursion rule左大段右小段 整一个helper prefix sum
0 0 0
0 1 1
0 3 2
0 6 3
先自我介绍问了几分钟简历。面筋题。判断target字符串是否可以由给定字符串转换得到。转换的规则是：每次转换要变所有的相同字母
比如：abca -> cdec 可以 abca -> abea -> cbec -> cdec
这道题当时看面经的时候就觉得很怪，也没仔细想，加上和第一轮又很像，当时有点慌，讨论了蛮久，还好面试官super nice
最后讨论的结果是很简单，只要check对应的映射规则都满足就行了，当然长度一定要相同。
然后问什么时候需要中间变量？比如ab -> ba，必须先ab -> cb -> ca -> ac，不能直接a到b，b到a。讨论了一下lz说check有没有环，面试官满意。然后写了个dfs检查有没有环，这一轮就结束了。
01矩阵走路问题(高频2次)
0和1的grid，1是墙，0是路，从左上角走到右下角，最少多少步。BFS
Follow-up: 现在说能把grid中的一个1变成0，问新的最小步数是多少步
思路：Bi-BFS算左上，右下到每个1的点距离和的最小值
思路2: BFS的时候，用1来标记是否已经走过。现在拆掉了墙，可以用新的状态，如-1来标记拆了墙走过。其实本质还是记录不同的状态。
一个白人小哥哥，给你一个source string, 要求找长度为K的字母排序最前面的subsequence，一开始思路不明确，先随便讨论了一下brute force的解法，时间复杂度2^n * K，问能不能提高，想出了N*K的解法，写了代码。继续问对于最差的Corner case怎么提高，用上了heap，继续改了代码。follow-up问如果要top 10 subsequence
思路：1. 初始化char array，greedy每次选最靠左最小的char，同时保证后面的subsequence够长 2. 感觉只能brutal force了 recursion + backtracking + memo
LC611给一堆三角形的边长，问能构成多少个三角形
思路：确定最长边然后two sum(确定最短的两边然后binary search找最长边？)
5. 股票，貌似是面经题，对一支股票实现价格的添加，删除，修改，查询最高价格，查询当前价格
LC679 follow up: construct result list
第四轮: 无限大的棋盘里马找从起点到底终点的路径(BFS) Follow Up: 如果有有限个Obstacles，如何判断是否可以从起点到达终点（Bi-BFS）
Follow up: 由于有可能block所有从起点到终点的路径，所以两遍一起同时搜索，若有一个queue没了则停止
Follow up: 无限棋盘 没有block 用A star heuristic.
2. 使用 dfs + memo 的概率题
给一个 input num，随机抽1~10的数字加到 num 去得到新的 sum，如果 sum < 20 继续抽数字加和，20 <= sum <= 25 算 win，25 < sum 算 lose，求 lose probability
dfs permutation 的思路加上 memo，每一层尝试用 num += 1~10，然后 recursion。应该需要算 probability 的平均值，所以 dfs 需要返回 avg prob 和一个 count 用来重新计算 avg prob
Provider: Lei Li
写了一个python版本，如果有错误请指出。
2
3
4
5
6
7
8
9
10
11
12
|
def win_rate(num):
rates = {}
def dfs(num):
if num > 25: return 1
if 20 <= num <= 25: return 0
if num in rates:
return rates[num]
return sum(dfs(num + i) for i in range(1, 11)) / 10.0
return dfs(num)
|
建水井
第一轮建水井，一个村庄里有很多房子，有的房子旁边能建水井，有的房子只能通过与其他房子建立管道获得供水。给出了在不同房子旁边建水井的花费，已及两个房子间建管道的花费，要求结果给出一份竞价，使得总花费尽可能少 第一题就卡住了，给出了个不算特别好的算法，我又试了别的想法，但是没想出来，面试官问是要个提示还是就之前我给出的完整的算法写，我选择要了提示，面试官根据我第二个思路引导我构成联通图 最后怕时间不够写代码，提醒说用最小生成树-.
