兔兔森森面筋

Intern

1. 一个有序序列有N个数，随机替换其中k个，求复杂度< O(NlogN)的算法使替换后数组重新有序。
   Stack+MergeSort. 可以分成k个sorted list然后merge k list， 也可以找出2k个异常点（发现异常后两个值都拿出来）对2k个排序，然后再和剩下的n-2k个有序序列merge。写完之后给了几个follow up优化了一下
   && coding完之后问了下双向队列底层是怎么实现的，和队列比有啥区别。
   (deque的实现比较复杂，内部会维护一个map（注意！不是STL中的map容器）即一小块连续的空间，该空间中每个元素都是指针，指向另一段（较大的）区域，这个区域称为缓冲区，缓冲区用来保存deque中的数据。因此deque在随机访问和遍历数据会比vector慢。)
2. 华容道移动，给出棋盘的初始状态和结束状态，求移动的最少步数。
   基本是leetcode773题，只是修改了一下棋盘的大小，变成了4 * 4
   一开始用的是BFS的方式写的，面试官提示了程序中的一点错误，修改了之后问了下优化的方法，正好这学期的AI课程学了一些search的方法，然后就说了下用双向BFS来节省空间，A * 的方法来进一步减少分支。
   然后又问了下这道题用A * 的话使用什么heuristics比较好，回答了对应点的hamming距离之和。之后面试官说A * 的方法就不写了
   解法: A* algorithm, follow up可以在O(n*m)的时间根据奇偶性判断(https://www.cs.bham.ac.uk/~mdr/t ... lesSolvability.html)
3. lc 233 变种
4. lc 480的变种。输入是一个数组array 还有一个整数k。10<=k<=array.length. k代表滑动窗口的宽度。需要求每个滑动滑动窗口内的 去掉前10%大和前10%小的数之后剩下数的平均值 并把平均值放在一个数组里返回。【BST是最优解】
5. 先修课程，类似lc210 拓扑排序
6. 给一个start string和target string，允许的操作是：每次可以把start string中的全部某个字符变为另一个字符，可以变成“ * ”，但“ * ”只是中间变量，最后还要变到target string。给定两个string返回最小的操作次数，不能变返回-1。力扣好像有类似的我记不清了。
   follow up 1: 给定一个符号"", 字符可以先转换成""再转换成其他字符，
   "abb"->"baa" return true, "a"->"", "b"-"a", ""->"b".
   follow up 2: 没有"*", 不限字符转换次数，即可以先将一个字符转换成中间字符，再对中间字符转换。
   "abb"->"baa" return true, "a"->"c", "b"->"a", "c"->"b"
   求转换次数

Template
int MinOpTimes(string str1, string str2) {
//...
};
Examples
Example 1:
str1: accs, str2: eeec
operation 1: change 'a'->'e'; // str1: eccs
operation 2: change 'c'->'e'; // str1: eees
operation 3: change 's'->'c'; // str1: eeec
return 3;
Example 2:
str1: accs, str2: efec
return -1;
Example 3:
str1: abb , str2: baa
operation 1: change 'a'->'*'; // str1: *bb
operation 2: change 'b'->'a'; // str1: *aa
operation 3: change '*'->'b'; // str1: baa
return 3;

7. 给一个函数，input是0到9，output是下一步能走的位置一个list，list的范围也是0-9。给定你这个要走K个step和一个初始值(0-9), 问你最后能走出多少种走法
8. 一个sliding window。给一个数组，求所有k个连续的数当中的最小值。
9. 一个双向链表和二叉搜索树互相转化
   类似lc109，把双向链表转化为二叉平衡数
   写出了 O(n log n) 的算法，followup 问怎么优化到 O(n)，应该是先把二叉平衡数存入数组就可以了。
   用递归，每次找到那个root节点然后对左右子树继续进行递归就好，不过最好先遍历一遍链表，然后用数组存，每次递归传入这个数组和对应的index范围，最后时间复杂度O(N)，空间复杂度也是，反向转化的话也是类似思路
10. 两条线段是否相交，先求交点，然后判断交点范围可解，可以思考的是处理斜率为无限大的直线的时候如何简化代码....
11. 给一个是通过对BST做BFS得到的一个序列（层次遍历得到的序列），如何判断能否生成对应的BST，有点类似lc255，返回true or false。
    思路是用queue存当前可以插值的范围，依次遍历序列里的值，如果queue前端的范围不合适就pop，合适的话将该范围扩成两个新的范围push进队列末尾。如果queue为空就return false。Follow up是返回构造的BST， 这个很简单，只要用queue存pair<pair<int, int>, TreeNode*>>就行了，插入范围的时候判断是插在左孩子还是右孩子。
12. 给了一个字符串，包含了若干大写字母和小写字母，然后要求将字符串的小写字母移到字符串的前面，大写字母移到字符串的后面，顺序无所谓。感觉好像还是leetcode的原题，但是没有找到。
    用了两个指针来做，第一个指针遍历整个字符串，第二个指针记录index最小的大写字母，每次遍历到小写字母的时候，如果index大于指针记录的大写字母的位置就交换，然后再去找下一个大写字母。
    感觉有一点brute force，可能还有更好的方法吧。然后问了下复杂度，因为两个指针的位置都是递增的，所以应该是O(n)，然后又问了下认为哪些test case比较好，随便说了一下就结束了。
13. 给了一列数字，要求返回每个数字的左边的最后一个比他大的数字的坐标，如果没有就返回-1。例如5 4 2 1 3，就返回-1 0 1 2 1。
    有点类似leetcode的739题，主要是用stack来解决。一开始是用的顺序遍历来做的，然后面试官给了一个反例，想了一会就在面试官要提示的时候想出来应该逆序来操作，然后改了下代码写出来了。
14. lc207
15. 比如abcdabefexy分割成abcdab efe x y，和其他的子字符串没有重复字母，思路就是存每个字母最右边的index，然后遍历数组，不断扩大右边界，如果发现合法字符串，就截断
16. 平面上N个点，找出所有的正方形，时间复杂度越低越好。
17. 实现一个fixed size的queue. 输入是queue的size，需要实现push pop两个方法，push的时候假如queue已经满了的话需要pop队首，只能用基本的数据结构实现，比如array, linkedlist。
    楼主先说要用linkedlist做，面试官问楼主为什么不用array，然后讨论了下array和linkedlist实现的优缺点，最后在面试官的要求下采用array实现。 代码写完后，面试官看了没问题后，问了几个followup，首先问了下我多线程的问题，就是假如queue需要支持多线程，需要怎么做，楼主说用读写锁，写了加读写锁的代码。问了下什么是reentrantlock，多线程问完后，又问了下如果queue要支持扩容和压缩该怎么做，就是相当于resize怎么实现，讨论完后写了代码
18. lc857
19. lc996
20. lc361
21. 给一棵树，节点除了左右孩子指针还有邻居指针用来指向右边第一个非空节点，给一棵树的根节点，需要把每个节点的邻居节点值都赋上，用来指向别的地方
    一开始给了个bfs的解法，follow up是把space优化到O(1)，我是利用遍历邻居指针继续对下一层的节点做相应操作。
22. 给一个tree的preorder traverse的数组，问是否是valid tree
23. lc76
24. 字典树
    字符串匹配1 ： 正常版 =>KMP/RK
    字符串匹配2 ： 模版串可以shuffle （abc 可以匹配bca）
    字符串匹配3 ： 模版串可以shuffle + mapping （abc 可以匹配321 abc => cba => 321）
    字符串匹配4 ： AC自动机
25. 给n个点和m个区间，一个点最多匹配几个区间 问最多匹配几个区间和点 ： 堆+扫描线 需要证明正确性 貌似用二分图？
    给n的点形成一条折线，求k等分点 ： 二分
26. 多线程知识 + 实现多线程队列 + OS
27. 有n个object 两两之间可以有三种关系(相同种类1,不同种类2,不知道2) 给m个三元组（object1， object2，relation 1/2/3）假设不存在矛盾 求问给定一些二元组（object1，object2） 输出他们的关系
    A B 1
    A C 1
    A D 2
    C F 1
    D E 2
    则输出 B D => 2 A E => 3 A F =>1
    并查集建点（same relation） + 图遍历建边（different relation）
28. 给你一个字符串，你可以增加或者删除，要尽可能的balance，也就是和原来的字符串要尽可能的相似，你要怎么做（这里我们认为添加是+1 删除是-1 然后想办法让操作完之后接近0），要返回回文字符串
29. 就是n个点在2D平面上，return k等分点的位置并返回。基本就是presum
30. 有n枚硬币，每个硬币掷一次正面朝上的概率各不相同，假定第i个概率为pi。如果把所有硬币都掷一次，求k个硬币正面朝上的概率。
    一开始想的是DFS，面试小哥说复杂度太高了，后来想到用DP。然后被问复杂度，follow up是问空间复杂度怎么优化到O(n)。
31. 很简单的二叉树题，判断树的所有节点value是不是都相同。
32. 给一个都是1和0的数组，比如说[1,1,0,0,1,0]，和一个integer n，你可以选任意0到n个0变成1，求变完以后最长连续1的长度。比如这题如果n是2，答案就是5。followup就是只能连续变。
33. 给array of integers, 裡面有一个数字是单独出现 其他都会出现两次(而且一起出现)
    ex: [1,2,2,3,3]
    要判断哪个数字是单独出现的
    以这个例子的话就是 1
    LZ 一开始先说了用HashMap 去记出现几次, 面试官说有没有不用额外空间的方式, 我说 那就用XOR 去算吧 剩下来的那个就是单独出现的了 複杂度是O(N), 面试官说可以，但是希望再想其他方式可以优化的 比如说O(logN)複杂度. 看到logN就想到binary serach了,不过一时没有想到怎麽个search法,面试官给了提示才推出来的,结论就是用index是基数或偶数 来判断 search砍半时应该往前找或往后找 (多找两个例子就可以看出来了),然后是一些corner case的讨论, 最后写case直接跑 面试官说想看看面试者会怎麽想Case验证这个solution
34. 考binary tree
    给你一棵树 问是不是uniform tree (也就是 整棵树的值都一样)
    follow-up: 问这棵树有几个subtree是uniform tree
    两题都是divide & conquer recursive写的
35. 给一个数组 裡面只有 0和1
    问最少次数把0换成1 或把1换成0 可以让 0都在左边 1都在右边 (或者0都在右边 1都在左边) [0,1,0,1]的话就是把第一个1换成0 可以达到分边
36. 给定N，请通过从小到大输出，分母不超过N的真分数序列。比如给定5，就输出1/5,1/4, 1/3,5/2,....等
    先开始想了一个用PriorityQueue的算法，因为不超过N的序列中，以分母归类，以n=5为例,
    1/5 2/5 3/5 4/5
    1/4 2/4 3/4
    1/3 2/3
    1/2
    首先把每一行的第一个元素加入PriorityQueue，再poll出来，poll到的数用一个指针往后移动，这样时间是O(nlogn)。
    后来面试官给提示说，这其实是一个从左到右，从上到下都递增的序列，每次只需要比较右边的和下边的谁大就可以了。
37. 一个4*4的棋盘，O代表空位，X或者Y代表棋子。每次可以移动一步，求问最少多少次可以移动至胜利。胜利的条件是，存在排成一列的或者一行或者一条斜线的X(或者Y)。
    OXXY
    XOOY
    XXXY
    YYOO
    我先说了DFS，后来觉得应该是BFS，通过Hash值来保存棋盘的状态。
38. 两堆石子(m,n)，两个人A和B，每次只能取(0,k)或者(k,0)或者(k,k)，其中k<=min(m,n)。求问如果A先取，A有没有必胜策略。
    首先想的是迭代，边界条件是如果m=n，那么A必定赢了。
    初步的想法是，f(m,n) = f(m-k,n-k) || f(m-k,n) || f(m,n-k) 等等 0<k<min(m,n)
    时间复杂度是3的min(m,n)次方。
    后来又说能不能提升复杂度，想到了记忆化搜索。但是最后面试官说可以达到O(m)的复杂度
39. 假设有很多张图片，图片之间有遮挡关系，找到最底层的图片
    follow up1：假设所有的图片都是矩形，给你俯视图，如何找到图片之间的遮挡关系，提一下就好，不用写
    follow up2：给出一个possible的从最底层到最外层的图片顺序，就是topological sorting，因为我当时时间还够就写了一下
40. lc28
41. lc20
42. 有n个城市，每个城市之间可能有路径相连，如果有路径，这个路径会有一个weight，代表的是最大能够承受的车的重量，另外有不同重量的车，能走的路不能超过最大承重，每条路通过路费1元，预算k元，写函数求能够从s开到t的车的最大重量。follow up，如何优化
43. lc4
44. lc44 wildcard matching中的字符串改成多级文件路径，每一级的*都只能作用于这一级，判断两个路径是否match
45. 一个数轴上，有n个点(x1,x2,...,xn)和m个区间(a1_b1),(a2_b2),...,(am,bm)。每一个点只能匹配一个区间，每一个区间也只能匹配一个点。匹配的必要条件是点包含在区间之内
    也就是对于(ai,bi)，当ai<=x<=bi时，可以进行匹配，当然也可以选择不匹配，把这个区间让给其他的点。求最多可以有多少个区间被匹配到。
46. 貼了Hashmap的Class和希望我實現的constructor/destructor/function大約10個
    然後強調主要想看我先寫如果Hashmap要resize的部份怎麼實現
    剩下部分就盡可能在時間內寫完，寫多少就是多少
    大致上就是已知：

class Key{
...
};
class Value {
...
};
實現以下:
class Hashmap {
    Hashmap();
    Hashmap(int capacity);
    Key* getKey();
    bool resize();
    ...
};

48. lc 215，但是不能用priority queue，必须用quick sort来写，利特扣得上有答案我就不多说了. 1point3acres

49. lc53，这是个easy题很快就写好了，但是followup是找出两个subarray，使他们sum最大，这里我用的是两个数组保存每个位置左边的maximum subarray和右边的maximum subarray。然后找两个数组对应位置sum最大的就行了

50. 给文件列表List<File> files, 实现一个gitignore, 可以过滤掉gitignore里出现的文件，需要满足gitignore的规则。
    gitignore规则：
    如果是，则表示同通配0个或者任意字符。比如 /path/to/file。/path/to/abcdefile满足(任意)，/path/to/file满足（0）。
    如果是?，则表示通配一个字符。比如/path/to/?file。/path/to/zfile, /path/to/xfile等满足。
    如果是[]，则表示满足括号里的任意一个字符。比如/path/to/[abcde]file，则/path/to/afile, /path/to/bfile等满足。
    重点是，“/”不能匹配

51. 给一个pixel matrix，matrix可以理解为照相得到，不同颜色的pixel组成不同的广告牌，判断广告牌之间的遮挡关系 如下
    [1,1,1,1]
    [1,1,2,2]
    [1,1,2,3]
    不同的数字代表不同的颜色。例如此表示有
    [1,1,1,1]
    [1,1,1,1]
    [1,1,1,1]
    [2,2]
    [2,2]
    [3]
    求距离最远的广告牌的颜色。

52. 给定一个BST。implementBST节点的get_weight方法，其中weight定义为此二叉树中value大于此节点value 的其他所有节点的最大深度
    input:
    5
    / \
    3 7
    / \
    1 4
    返回
    2
    / \
    3 -1(因为7为最大）
    /\
    3 2

53. 题目是给一个N-ary tree，如何将其转化为一个二叉树?
    转化规则为左孩子，右兄弟，就是左儿子不变，右孩子变为自己右侧最近的那个非空兄弟。
    follow up:任意给一个二叉树，可以还原成N-ary tree吗？如果不能，满足什么样条件的可以呢？？
    原题我是用hashmap+level-order traversal做的，然后follow up是不能，需要满足根节点没有右子树且其任意节点的右儿子深度不超过N，第二个条件我开始也没想出来，我可能表达的也不是很准确，其实就是root = root->right，然后直到null停下来，这个深度不能超过N，因为子节点数量有限。

54. lc907

55. merge k binary search tree

56. 给定若干点坐标，连成折线。要求将折线长度k等分，返回等分点的坐标数组列表。

57. 给一个正整数集合，求一个和最大且能被3整除的子集。Follow up: 如果集合里有正有负，怎么做。

58. lc136 变体，如果出现两次的数总是相邻的，有没有比异或一遍更高效的做法。

59. 钥匙

Full-time

1. 有哪些常用的数据结构
2. Map 和 HashMap的区别是什么，内部都是怎么实现的
3. Implement a fixed size queue， 支持pop(), push()，如果超过capacity就直接return false
4. lc 武士流
5. followup：给两个Array of intervals， 每个array内部是无序的，也可能有overlap。求这两个array所覆盖的区域之间有没有overlap
6. 给出Union tree的定义：自己和所有child的value都一样。求一个tree里面有多少个union tree，比如以下这个就有6个：
   1
   1 2
   1 1 2 2
   除了顶点的1以外，以其他点为顶点的tree都符合Union tree
7. 同样问了Map和HashMap的实现，并问了HashMap的地址冲突的解决方案。还问了当HashMap中的地址冲突是用开放地址法解决的时候，删除一个key时的操作
8. 合并n个BST。讲了讲我的设计，并问了时间复杂度，没有让我写代码，只让我写了一个TreeNode to array的函数。
9. 给出tree的一个节点的weight的定义: the biggest depth of nodes whose values are greater than A。求一个Tree的每一个node的weight值
10. 给一个N-array Tree (Undirected graph), 找出最长的路径。不一定要从root开始。Node没有value，edge有value。
11. leetcode 935
12. 给无向图判断是否能成二叉树