https://docs.google.com/document/d/1qxA2wps0IhVRWULulQ55W4SGPMu2AE5MkBB37h8Dr58/edit#
4. Guess Word 高频 12次
LC 题目：LC843 猜词，一个未知target，猜一个词会返回正确猜对的字母数
第一轮 白人小哥。猜词游戏，写一下如何判断player猜词的score（guess word 和 secret word中相同char的个数），然后如何根据history判断guess word是不是good guess。
思路: 见leetcode discussion
当一个单词和其他单词match number为0的次数越多，那么这个单词越不好，因为match number为0时我们减少搜索空间的速度最慢。
假如现在有无限多长度为6的单词，对于word X，和他match number为0的单词有25^6这么多个，然而和X match number为1的单词则减少到了25^5 * 6这么多个，为2时为 C(6, 2) * 25^4，以此类推，match number越大我们下一轮的搜索空间会越小，所以这里我们每一轮都挑选出当前搜索空间中和其他单词match number为0的次数最少的单词作为guess word来猜，这样minimize了每次猜词的worse case。
参考代码：
(Provider: leetcode: lee215)
Time Complexity: O(n ^ 2)
Space Complexity: O(n ^ 2);
class Solution {
public void findSecretWord(String[] wordlist, Master master) {
List<String> list = new ArrayList<>();
for(String str: wordlist) list.add(str);
for(int i = 0 ; i < 10 ; i++) {
Map<String, Integer> zeroMatch = new HashMap<>();
for(String s1: list) {
zeroMatch.putIfAbsent(s1, 0);
for(String s2: list) {
if(match(s1, s2) == 0) {
zeroMatch.put(s1, zeroMatch.get(s1) + 1);
}
}
}
Pair pair = new Pair("", 101); // list size is 100
for(String key : zeroMatch.keySet()) {
if(zeroMatch.get(key) < pair.freq) {
pair = new Pair(key, zeroMatch.get(key));
}
}
int matchNum = master.guess(pair.key);
if(matchNum == 6) return;
List<String> tmp = new ArrayList<>();
for(String s: list) {
if(match(s, pair.key) == matchNum) {
tmp.add(s);
}
}
list = tmp;
}
}
private static class Pair {
String key;
int freq;
public Pair(String key, int freq) {
this.key = key;
this.freq = freq;
}
}
private int match(String s1, String s2) {
int res = 0;
for(int i = 0 ; i < s1.length() ; i++) {
if(s1.charAt(i) == s2.charAt(i)) res++;
}
return res;
}
}
5. LC890 word pattern match 高频8次
题目描述：
给一个word list和一个pattern，返回list中所有和pattern相match的单词
此处的match为能在pattern和word之间找到一个双射函数，和LC Isomorphic String中的双射函数一样
思路：
1. 用两个map，用putIfAbsent存互相的对应关系，然后再查一遍对应
2. 单map把string转换成pattern array，用map.put(char, map.size())存不存在的char
这道题目本质是LC205
6. LC489 位置地形扫地机器人 高频 7次
思路：常规DFS
- 需要用参数追踪当前机器人朝向
- 每次backtracking时候别忘了掉头回正
- 用string记录visit过的位置
参考代码：（disscussion 里面看到的代码量少，比较好写的代码）
class Solution {
// 0: up, 1: right, 2: down , 3: left
public void cleanRoom(Robot robot) {
dfs(new HashSet<>(), 0, 0, 0, robot);
}
private void dfs(Set<String> visited, int i, int j, int currDir, Robot r) {
if(visited.contains(i + "," + j)) return;
visited.add(i + "," + j);
r.clean();
for(int k = 0 ; k < 4; k++) {
if(r.move()) {
int x = i, y = j;
switch(currDir) {
case 0: x -= 1; // up
break;
case 1: y += 1; // right
break;
case 2: x += 1; // down
break;
case 3: y -= 1; // left
break;
}
dfs(visited, x, y, currDir, r);
r.turnRight();
r.turnRight();
r.move();
r.turnRight();
r.turnRight();
}
r.turnRight();
currDir += 1;
currDir %= 4;
}
}
}
7. LC855 考试找位子，尽量分散坐，人会离开 高频 6次
思路：见leetcode
1.用优先队列：
用优先队列存slot，slot包含左右端点和长度。exclusive好算。注意如果是最左或最右时长度为right - left，若非则为(right - left) / 2，因为如果选择坐边上可以不管端点。seat时候去pq最大slot，中间切开offer两段。leave时候遍历找到左右两段整合
离开时间复杂度 O(n)
坐下时间复杂度 O(logn)
`
1.2 在优先队列外再建一个BST可以把离开的时间优化到logn。离开的时间主要来自于一个线性的遍历，在BST里可以logn找到左右邻居，并且BST有logn时间的query/insert，不会影响坐下的时间复杂度。
2. 用TreeSet
每次坐下时，遍历set找到最大的距离，并且记录位置，离开则直接删除目标数字
离开时间复杂度O(logn)
坐下时间复杂度O(n)
3. C++用Set(BST)和HashMap(Unordered_Map) 可以做到离开和坐下都是O(logn)
8. Key有过期时间的hashmap 高频 6次
题目：
面试官是个安卓组的小姐姐，45分钟，感觉答得一般，求过o 0
Create a map with expiring entries:
Example
12:00:00 - put(10, 25, 5000)
12:00:04 - get(10) -> 25
12:00:06 - get(10) -> null
Create a map with expiring entries:
Example
12:00:00 - put(10, 25, 5000)
12:00:04 - get(10) -> 25
12:00:06 - get(10) -> null
思路：两个hash map，一个记录key，value pair，一个记录key的过期时间，get的时候检查key是否过期，如果过期了，删除key返回null
Put方法有三个参数，除了key，value还有个duration
Follow up: 采用更主动的策略删除过期的Key
思路；创建后台线程定期清理过期的Key。
用两个map，一个装<key, value>一个装<key, expiredTime>
在get中采用lazy deletion，get的时候检查key是否过期，如果过期的话两个map中都删除key，返回null。put的时候每次都更新key的expiredTime。
后台线程每过一段时间遍历所有key，调用get方法删除过期key。此处为了避免多线程冲突，Map用ConcurrentHashMap实现。
参考代码 （用后台线程主动删除）
Provider: null
class MyMap<K, V> {
Map<K, V> map;
Map<K, Long> time;
private static final int DEFAULT_CAPACITY = 16;
private static final float DEFAULT_LOAD_FACTOR = 0.75f;
private Thread clearThread = new Thread(new Runnable() {
@Override
public void run() {
while(true) {
try {
Thread.sleep(5000);
}catch(Exception e) {
e.printStackTrace();
}
for(K key : map.keySet()) get(key);
}
}
});
public MyMap() {
this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
}
public MyMap(int capacity) {
this(capacity, DEFAULT_LOAD_FACTOR);
}
public MyMap(int capacity, float loadFactor) {
map = new ConcurrentHashMap<>(capacity, loadFactor);
time = new ConcurrentHashMap<>(capacity, loadFactor);
clearThread.start();
}
public synchronized V get(K key) {
long now = System.currentTimeMillis();
Long expired = time.get(key);
if(expired == null) return null;
if(Double.compare(now, expired) > 0) {
map.remove(key);
time.remove(key);
return null;
} else {
return map.get(key);
}
}
public V put(K key, V value, long duration) {
long now = System.currentTimeMillis();
long expired = now + duration;
time.put(key, expired);
return map.put(key, value);
}
}
9. 多个不重复的长方形内随机取点【类似LC497?】 高频 6次
onsite最后一轮的面试题。其他轮都没啥发的必要就不发了。题目是这样的 给你一个list的长方形。。每个长方形面积不一样，但是你要取个点，这个点可以是任何长方形里的。但是要你每次取点的概率都是一样的。不会因为长方形大小而不同。
长方形的输入形式：左下坐标和长宽
- （主要考察加权抽样和merge squares）
思路：把重复的长方形分成不重复的LC 类似题目：小块，然后用prefix sum进行二分查找
请问follow up是啥思路？用什么思路处理重叠的矩阵？以及是否需要考虑三重或者更多重的重叠区域
LC850 Rectangle Area II （如果有重复部分，思路和此题打碎矩形去掉重复部分的思路一样）
LC497 Random Point in Non-overlapping Rectangles （没有重复部分的原题）
LC528 Random Pick with Weight （类似题目）
对于有多个矩形的情况，我们可以考虑先选出一个矩形，再在该矩形内选点
di要求每个点选取的概率相同，那么选取一个矩形的概率就和该矩形的面积成正比
所以我们可以把所有矩形的面积的和sum算出来，然后在rand一个数%sum，再判断落在哪个矩形里
比如说有面积为3, 2, 1, 4的矩形，总和是10，randM = rand() % 10 ，如果randM==0,1,2就选面积为3的矩形，randM == 3,4就选面积为2的矩形，其他的同理
选出了矩形，然后在该矩形内选点即可
10. LC853 car fleet问题 高频 6次
多辆车再单行路上开，给起始地点和车速，不能超车只能位置重合跟着。问最后有几次的重合车次撞线。
思路：
TreeMap
用treeMap<position, time>去存，从接近target的地方往后遍历，local variable存最大撞线时间。若currTime > maxTime，则车次++
Sort
计算每个位置的车到destination的时间，然后根据位置把车排序，从后往前scan排序后的car数组，如果cars[i]的到达时间比cars[i-1]要晚，说明可以合并cars[i-1]和cars[i]，同时更新car[i-1]的到达时间
code
class Solution {
public int carFleet(int target, int[] position, int[] speed) {
int len = position.length;
Car[] cars = new Car[len];
for(int i = 0 ; i < len ; i++) {
cars[i] = new Car(position[i], speed[i], target);
}
Arrays.sort(cars, (a, b) -> a.pos - b.pos);
int carFleet = len;
for(int i = len - 1 ; i > 0 ; i--) {
if(Double.compare(cars[i].time, cars[i - 1].time) >= 0) {
cars[i - 1].time = cars[i].time;
carFleet--;
}
}
return carFleet;
}
private static class Car {
int pos;
int speed;
double time;
public Car(int pos, int speed, int target) {
this.pos = pos;
this.speed = speed;
time = (target - pos + 0.0) / speed;
}
}
}
11. LC857 雇工人 高频 6次
思路:
根据描述任何一个合法的pay group里面任意两个worker之间 quality1/quality2 = wage1/wage2，转化一下 wage1/quality1 = wage2 / quality2，即所有的工人他们的paid wage和他们的quality的比值都应该是一样的，根据这个性质，我们每一个合法的pay group只能取最大的wage/quality当作所有工人的pay ratio。
假如我们不取最大的，选择的ratio为w1/q1，而且存在一个工人的wagei/qualityi > w1/q1，转换一下很容易得到 wagei > quaility * w1/q1，即表示该工人的最低工资大于了他实际得到的工资，和题意不符合。
所以有了以上性质后，直接根据ratio排序，然后又需要每个group的pay最小，每个group的总工资计算方法（q1+q2+q3+...+qk）* ratio，所以就是需要quality的sum最小，那每次我们加入了一个新的ratio就把quality最大worker踢出group，这样每次group的pay可以保证是新ratio下的最小pay。遍历数组，记录所有ratio中出现的pay最小值即可。
Code
Provider: leetcode solution
class Solution {
public double mincostToHireWorkers(int[] quality, int[] wage, int K) {
int len = quality.length;
Worker[] worker = new Worker[len];
for(int i = 0 ; i < len ; i++) {
worker[i] = new Worker(quality[i], wage[i]);
}
Arrays.sort(worker, (a, b) -> Double.compare(a.ratio, b.ratio));
Queue<Worker> pq = new PriorityQueue<>((a, b) -> b.quality - a.quality);
int sum = 0;
double min = Double.MAX_VALUE;
for(int i = 0 ; i < len; i++) {
if(pq.size() >= K) {
Worker tmp = pq.poll();
sum -= tmp.quality;
}
pq.offer(worker[i]);
sum += worker[i].quality;
if(pq.size() == K) {
min = Math.min(min, sum * worker[i].ratio);
}
}
return min;
}
private static class Worker {
int quality;
int wage;
double ratio;
public Worker(int quality, int wage) {
this.quality = quality;
this.wage = wage;
ratio = (wage + 0.0) / quality;
}
}
}
12. LC750 Corner Rectangle个数 高频 5次
思路：任选两行for for loop，若相对应列（第三个for）都有点，就count++，然后对这两行的count任取两个组合，加到result上
13. LC815 Bus Route 高频 5次
每个公交车有多个站，给一堆公交车，问A到B点最少换乘次数
思路：BFS + mem。map<stop, List<bus>>，然后用Set<bus>存visited bus（不能用stop查重，会很慢）。每次层序遍历poll出的站都是在这个step中所有能走到的站
14. LC659 Split Array into Consecutive Subsequences 高频 6次
判断一个升序含重复元素的array是否能分成多个三个数字以上构成的顺子
思路：
用freq map先过一遍存频率，再建一个map存我们能用到的tail number。再过第二遍的时候，若freq==0 continue；若能接上前面的顺子，就接；不能则新开一个顺子（记住新开时候直接要把连着的两个数字剔除，因为要保证长度为三）；都不行则为false。记住最后别忘了更新当前频率
对于每一个element，我们有两种选择
- 把它加入之前构造好的顺子中
- 用它新开一个顺子
此处用贪心策略，如果1能满足总是先满足1，因为新开顺子可能失败，即使新开顺子成功，当1能满足的时候，将新开顺子加入之前的顺子也能成功，所以能够选择策略1的时候没必要冒风险选择策略2
目标是用策略1或者2消耗掉所有的元素
如果两个策略都无法选择，直接返回false
用另一个map记录已经构造好的顺子中现在需要哪些尾巴，来实现将当前元素加入构造好的顺子中
15. 王位继承 高频 10+次
【update time：10/22/2018】
void birth(String parent, String name) 父亲名字和孩子名字，生个娃
void death(String name) 此人要死
List<String> getOrder() 返回当前的继承顺序，string array/list
讨论得知，每个人的名字是唯一的，继承顺序符合如下规律:
假设王有大皇子二皇子三皇子，大皇子有长子次子三子，那么继承顺序是王->大皇子->大皇子长子->大皇子次子->大皇子三子->二皇子->三皇子
死掉的人不能出现在继承顺序里，但是如果上面例子中大皇子死了，只需把大皇子移除，原始继承顺序保持不变：王->大皇子长子->大皇子次子->大皇子三子->二皇子->三皇子
三个function会被反复调用，实现function细节。
思路：看起来不难的设计题，DFS只查最左枝v
参考代码11
Provider: null
// key: parent, value: children
Map<String, List<String>> tree = new HashMap<>();
Set<String> dead = new HashSet<>();
String root = "king";
{
tree.put("king", new ArrayList<>());
}
public void birth(String parent, String name) {
if(!tree.containsKey(parent)) {
// throw exception
} else {
tree.get(parent).add(name);
tree.put(name, new ArrayList<>());
}
}
public void death(String name) {
dead.add(name);
}
Zelong Qiu: 这个方程只是lazy delete会不会导致dead越存越大？面试官会不会问如果需要实际删除发方法
根据看到的面经，还没有人被遇到过这个问题，如果有人遇到需要实际删除的问题，欢迎提供思路和代码
Provider: Yang Qi
对于动态删，提供一个思路，用一个map记录子节点到父节点的映射，如果当前节点挂掉，把自己的子节点插入的父节点自身对应的位置之后
public List<String> getOrder(){
List<String> res = new ArrayList<>();
dfs(root, res);
return res;
}
private void dfs(String curr, List<String> res) {
if(!dead.contains(curr)) {
res.add(curr);
}
for(String child : tree.get(curr)) {
dfs(child, res);
}
}
16. LC951 Tree Isomorphism Problem 树的同构问题 高频 5次
https://www.geeksforgeeks.org/tree-isomorphism-problem/
951. Flip Equivalent Binary Trees
思路：简单的DFS
参考代码：
public boolean flipEquiv(TreeNode root1, TreeNode root2) {
if(root1 == null) return root2 == null;
if(root2 == null) return root1 == null;
if(root1.val != root2.val) return false;
return (flipEquiv(root1.left, root2.left)&&flipEquiv(root1.right, root2.right)) || (flipEquiv(root1.left,root2. The right) && flipEquiv(root1.right, root2.left));
}
17. N叉树，要求删一些node，返回list of roots 高频 8次
More Detail : 给一个tree有红的node有蓝的node，把红的去掉后剩下一堆零零散散的tree， 返回这些tree的node，只要node，不要children，也就是说把这个node的children设置成null然后加到list里。
参数是这个树的root。找到所有的红点然后delete掉，去掉这些红点之后就会把一个tree变成散落的几个tree，然后返回这几个tree的root。直接一个recursive判断一下，如果这个node是红点的话就ignore 掉再去判断这个node的children，如果这个node是蓝点的话，要看这个蓝点的parent是不是个红点，是的话，这个蓝点就是散落的tree中其中一个tree的root。
思路：简单BFS。。不应是dfs?
想问一下这题返回的顺序重要吗？
没想到怎么做，有没有大佬写了code能发一下的?感激不尽
(Provider: fill your name)
private void dfs(Node root, Node parent, List<Node> res) {
if (root == null) {
return;
}
if ((parent == null || parent.color == red) && root.color != red) {
res.add(root);
}
for (Node children : root.children) {
dfs(child, root, res);
}
}
public void dfsHelp (Node root, List<Node> res) {
if (root == null) {
return;
}
if (root.isRed) {
for (Node child:root.childrens) {
if (!child.isRed) {
res.add(child);
}
dfsHelp(child, res);
}
} else {
res.add(root);
Iterator<Node> it = root.childrens.iterator();
while (it.hasNext()) {
Node child = it.next();
if (child.isRed) {
root.childrens.remove(child);
}
dfsHelp(child, res);
}
}
}
class TreeNode(object):
def __init__(self, val, color):
self.val = val
self.color = color
self.children = []
class Solution(object):
def listOfRoots(self, root):
if not root: return []
ans = []
def dfs(node, parent):
if not node: return
if node.color == 'b':
if parent.color == 'r': ans.append(node.val)
// should check if parent is None
else: ans.append(-1)//这里加上负一是为什么？
for child in node.children:
dfs(child, node)
dfs(root, None)
return ans
18. 可乐饮料机 高频 5次
有一系列按钮，每个按钮按下去会得到一定体积范围的可乐。先给定一个目标体积范围，问不限制按按钮次数，能否确定一定能得到目标范围内的可乐？
举例：有三个按钮，按下去得到的范围是[100, 120], [200, 240], [400, 410],
假设目标是[100, 110], 那答案是不能。因为按下一，可能得到120体积的可乐，不在目标范围里。
假设目标是[90, 120]，那答案是可以。因为按下一，一定可以得到此范围内的可乐。
假设目标是[300, 360], 那答案是可以，因为按下一再按二，一定可以得到此范围内
假设目标是[310, 360], 那答案是不能，因为按下一再按二，有可能得到300，永远没可能确定得到这个范围内的可乐。
假设目标是[1, 9999999999]，那答案是可以。随便按一个都确定满足此范围。
思路：dfs+memorization从0开始暴力解 一开始[0, 0] 通过bfs、dfs往上加直到出界
public static boolean dfs(List<Soda> sodas, int volumeLower, int volumeUpper,
int targetLower, int targetUpper, Map<String, Boolean> memo) {
Boolean val = memo.get(volumeLower + "-" + volumeUpper);
if (val != null) {
return val;
}
if (volumeLower >= targetLower && volumeUpper <= targetUpper) {
return true;
}
if (volumeUpper > targetUpper) {
return false;
}
// if (volumeUpper - volumeLower > targetUpper - targetLower) retuurn false;
for (Soda soda : sodas) {
if (dfs(sodas, volumeLower + soda.lower, volumeUpper + soda.upper, targetLower, targetUpper, memo)) {//false的子问题会重复计算
memo.put(volumeLower + "-" + volumeUpper, true);
return true;
}
}
memo.put(volumeLower + "-" + volumeUpper, false);
return false;
}
据说这题是binary search？ 这个应该bfs，dfs都能做。但是据说还可以用dp，dp怎么做啊。谁能po个解法？
区间DP的做法：(Provider: anonym)
public static boolean coke(List<List<Integer>> buttons, List<Integer> target) {
public static boolean coke(List<List<Integer>> buttons, List<Integer> target) {
int m = target.get(0);
int n = target.get(1);
boolean[][] dp = new boolean[m + 1][n + 1];
//Init
for (int i = 0; i <= m; ++i) {
for (int j = 0; j <= n; ++j) {
for (List<Integer> button: buttons) {
if (i <= button.get(0) && j >= button.get(1)) {
dp[i][j] = true;
break;
}
}
}
}
for (int i = 0; i <= m; ++i) {
for (int j = 0; j <= n; ++j) {
for (List<Integer> button: buttons) {
int preL = i - button.get(0);
int preR = j - button.get(1);
if (preL >= 0 && preR >= 0 && dp[preL][preR]) {
dp[i][j] = true;
break;
}
}
}
}
return dp[m][n];
}
这算是一个多重背包问题。我曾经被面到过一个类似的：给一个调色板由一堆颜色组成，每个颜色有RGB三个分量。问能否调出一个目标颜色
19. 生成随机迷宫，高频5次
左上到右下，怎么设计可玩性
maze generation. 输入是int[][] board, int[] start, int[] dest,返回一个int[][] maze. 这题题意比较复杂。简单来说就是让你随机生成一个迷宫，
条件是：
（1）你肯定要生成一些墙，这些墙宽度为1，意思就是board[0][0] - board[0][3]可以是墙，s宽度为1， 长度为4。 但是不能生成board[0][0] - board[1][3]这样的厚墙（2*4)
(2) 要求这个迷宫有且仅有一条路可以从start到达destination， 另外对于那些不是墙的blank cell，也要有可以从start到达它的路径。 也就是说不能有一些孤岛是不能到达的
(3) 后来大哥给我简化了一点，如果输入board里面
已经有一些墙， 用1表示，但是这个迷宫并不是具有通路的，然后让你根据以上条件，生成迷宫。
思路：直接暴力小人DFS瞎走，每次走两步，避免生成没有墙的空地。
(Provider: Sean)
public class GenerateRandomMaze {
public int[][] maze(int n) {
// Assumptions: n = 2 * k + 1, where k > = 0.
int[][] maze = new int[n][n];
// initialize the matrix as only (0,0) is corridor,
// other cells are all walls at the beginning.
// later we are trying to break the walls to form corridors.
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 && j == 0) {
maze[i][j] = 0;
} else {
maze[i][j] = 1;
}
}
}
generate(maze, 0, 0);
return maze;
}
private void generate(int[][] maze, int x, int y) {
// get a random shuffle of all the possible directions,
// and follow the shuffled order to do DFS & backtrack.
Dir[] dirs = Dir.values();
shuffle(dirs);
for (Dir dir: dirs) {
// advance by two steps.
int nextX = dir.moveX(x, 2);
int nextY = dir.moveY(y, 2);
if (isValidWall(maze, nextX, nextY)) {
// only if the cell is a wall(meaning we have not visited before),
// we break the walls through to make it corridors.
maze[dir.moveX(x, 1)][dir.moveY(y, 1)] = 0;
maze[nextX][nextY] = 0;
generate(maze, nextX, nextY);
}
}
}
// Get a random order of the directions.
private void shuffle(Dir[] dirs) {
for (int i = 0; i < dirs.length; i++) {
int index = (int)(Math.random() * (dirs.length - i));
Dir tmp = dirs[i];
dirs[i] = dirs[i + index];
dirs[i + index] = tmp;
}
}
// check if the position (x,y) is within the maze and it is a wall.
private boolean isValidWall(int[][] maze, int x, int y) {
return x >= 0 && x < maze.length && y >= 0 && y < maze[0].length && maze[x][y] ==
1;
}
enum Dir {
NORTH(-1, 0), SOUTH(1, 0), EAST(0, -1), WEST(0, 1);
int deltaX;
int deltaY;
Dir(int deltaX, int deltaY) {
this.deltaX = deltaX;
this.deltaY = deltaY;
}
// move certain times of deltax.
public int moveX(int x, int times) {
return x + times * deltaX;
}
// move certain times of deltaYy.
public int moveY(int y, int times) {
return y + times * deltaY;
}
}
}
高频 4次
1.下围棋，判断棋盘上点是否被包围 follow up test case 各种形状
请问各种形状是指什么？是不是指棋盘的形状？如果是的话，那么是不是不同点在于不同的形状的边界情况就会不一样？
请问：这一题哪一篇帖子有比较详细的题目内容吗？感谢
请问这道题有谁做出来能po出详细的code吗？感激不尽
应该说的是棋子的各种摆放。手动Unit test言之成理即可。主要是要测各种edge case
思路：dfs，碰到空子返回false 没被围死
2。n层map，每层m个node，node和edge都有值，问第一层到最后的minimum cost
思路：遍历+改node值？dijkstra吧？
什么叫N层map? map是stl里面的map吗？e不改node值也行吧，反正就是DFS每一条dge存在于同层的node之间？为什么可以改node的值？可能的路径，到底了就和min cost比较就完事了？
3。拿纸牌游戏， 纸牌上面有值，比如说 100， 1， -1， 2， 200， 1. 然后两个人轮流拿，直到拿完。 但是每次只能拿从左边数起的前三个，但是如果你要拿第三个，就必须前两个都拿了，你要拿第二个，就必须第一个也拿了，大家都最优策略，问最后第一个人能拿多少分。
思路：dp存当前人比另一个人能多拿的数，从后往前拿，每次看三个[谁能给个解法链接]
这个是一个蛮经典的dp问题，lintcode上也有类似的题目 https://www.lintcode.com/problem/coins-in-a-line-ii/description
4。image以byte[][]储存 如果想中心镜像翻转怎么弄
思路：跟reverse words一个思路，先翻转每行的byte，再翻转自身（字节翻转可用位运算能快
可以详细讲一下这里怎么用位运算吗
5。已知screen的高和宽，给你最小和最大的fontSize，要求给定一个string，将string用尽可能大的fontSize显示在screen里。已知两个API getHeight(int fontSize), getWidth(char c, int fontSize)
，可以得到每个character在不同fontSize下的高和宽。和面试官交流后，确认string可以拆分成几行显示在screen中
思路：先提出暴力解法，然后用二分法优化
Provider：Qiaoqian Lin
def fitScreen(screen_width, sucreen_height, num_chars, font_sizes):
def ok_or_not(width, height, screen_width, screen_height, num_chars):
num_chars_per_line = screen_width // width
num_chars_per_column = screen_height // height
num_chars_can_fit = num_chars_per_line * num_chars_per_column
return num_chars_can_fit >= num_chars
lo, hi = 0, len(font_sizes) - 1
while lo < hi:
mid = (lo + hi + 1) // 2
font_size = font_sizes[mid]
width, height = API(font_size)
size_ok = ok_or_not(width, height, screen_width, screen_height, num_chars)
if not size_ok:
hi = mid -1
else:
lo = mid
return lo
屏幕超大，如何speedup?
6。LC803 打砖块
思路：最好方法从后往前补。先把砖块全都打掉，然后用贴天花板的砖块dfs+mark，然后从后往前一个一个往上加，加同时若碰上周围有mark的砖块就主动dfs，dfs出来的就是这次打掉的砖块
7。LC253 给一堆interval，问最多要定多少间会议室
思路：可以用heap常规做，也可以把开始、结束时间分别升序排序，然后2pointer往后走。复杂度一样，就是更快
9。给一堆intervals和一个时间点，问这个时间点是不是空闲。follow up多call优化时间
思路：做一遍merge intervals再来一遍binary search
问：这个不merge，直接所有的往treeset里扔可以吗？
10。iterator of iterator
LC类似题目：
LC281 zigzag iterator
题目描述
Implement an Iterator of Iterators which traverses through an arbitrary number of iterators. IE, an iterator which iterates over three list iterators in the following way: L1 = a1, a2, a3 L2 = b1, b2, b3 L3 = c1, c2, c3 Then the iterator should process them in this order: a1, b1, c1, a2, b2, c2, a3, b3, c3
原题链接：https://www.1point3acres.com/bbs/thread-293238-1-1.html
思路：BFS 没什么好说的。。。
http://massivealgorithms.blogspot.com/2015/06/zigzag-iterator-techinterview.html
Provider(ccc/ddd)
class ZigZagIterator {
public:
ZigZagIterator(vector<vector<int>>& v) {
for (int i = 0; i < v.size(); ++i) {
if (!v.empty()) {
its.push_back({v[i].begin(), v[i].end()});
}
}
current = 0;
}
bool HasNext() {
return !its.empty();
}
int Next() {
auto it = its.begin() + (current % its.size());
int val = *(it->first);
if (it->first + 1 < it->second) {
*it = {it->first + 1, it->second};
} else {
its.erase(it);
}
++current;
return val;
}
private:
int current;
vector<pair<vector<int>::iterator, vector<int>::iterator>> its;
