缺大米的请参加这个刷题/Mock interview活动

开始刷题第三天，感觉还是很慢。每天只能2-3题。

Day 6 (Maybe..? I lose count) (Actually it's Day7)
Did 5 problems yesterday, forgot to post it.

前天的3道+shadow mock。做天的3道。
晚点要把前天的shadow note整理出来。BW, 面试官和面试者水平都较高(Tech and English)，围观起来真心舒服 :)
然后今天的卡就晚上睡觉前再打喽

day6 3题sql
1.求中位数的一种方法-- row_number()

Day 6 打卡, 三道题

补了几天基础知识, 继续打卡

378 有序矩阵中第K小的元素        中等       
240 搜索二维矩阵 II        中等

这两道题都是有类似关系的矩阵, 再检索时可以从最后一行开始, 如果当前值大于目标, 则退后一行, 否则前进一列.
同时, 在这个区间上可以用二分法优化

73 矩阵置零
类似炸弹人,或者N皇后,  0 所在位置的行列都需要被置零, 因为题目要求in place, 所以我们可以利用矩阵的0行,0列
来保存需要变零的行列信息做一次扫描, 需要注意的是, 如果0行, 0列自己如果有0, 我们需要额外的额两个变量来做记录

重新做了一下binary search的一道题，然后还有找重复的数，这个需要在一个链表里找到一个loop，还要学习一下他的方法。

06.11.2020
刷题第二天 打卡第二天
1. sunk all the websites
建立一个ArrayList去hold三个子ArrayList，每个子list都需要填上每个web'所占据的位置对应的String
注意：handle每个web的一部分被击毙的时候，就把它从对应的list上面移除；

2.remove characters I
使用two pointers 不match的情况就可以update

3.remove characters II
和上题非常类似，也是使用two pointers
注意：在更新的时候需要满足以下两种情况
a. array[fast]!= array[slow]
b. array[fast] == array[slow] && array[slow - 1] != array[fast];

此处打卡第四天，今日3题
第一题278. First Bad Version，考察折半查找，注意最后返回low
第二题380. Insert Delete GetRandom O(1)，要求设计满足要求的数据结构，通过结合ArrayList的O(1)随机访问特性和HashMap的O(1)的get、remove、put特性完成设计，设计remove时，若要删的不是最后一个数，则将其与最后一个数交换后，再删除目前最后的这个数，这样避免了ArrayList的copy
第三题381. Insert Delete GetRandom O(1) - Duplicates allowed，为上面这题的follow-up，此题增加了存储重复值的要求，所以在记录数值的下标时不能简单用HashMap<Integer,Integer>了，考虑到仍旧要求O(1)时间，所以使用HashMap<Integer,LinkedHashSet<Integer>>，这样的话随机访问array、从 hashmap中get, 或者对LinkedHashSet add/remove，这些所有操作都是O(1)。

连续第 8 天打卡，完成 4 道 Sort, Dynamic Programming 题：(3/4)
1. Sort Colors
2. Sort List
3. Coin Change
5. Coin Change 2

Tips 总结：
1. 在 sort 有限 range 的 integers 时，请条件反射 counting sort，速度快！不解释！！；
2. Backtracking 是 DFS 在 Array 这种 linear data structure 上的应用，万物之本；
3. Dynamic Programming 就是用一个 array 去存储 subproblems 的 optimal solution，然后以其去解 major problem 的 optimal solution；
3. Backtracking with memo 称为 Dynamic Programming Top Down，解决了重复 computation 的问题，非常可以；
4. Dynamic Programming 还有一种 Bottom Up 的写法，较前者容易实现，但是本质上是相同的；

Day 6
0611

三道题：

复习了一下 minimum window substring, 倒腾指针的时候有点卡住了，还是要看着例子慢慢搞
confusing number， 就是倒过来比一下
range sum query mutable。学了一下线段树。这里update比我想的复杂一点。但是都是传进来node，然后比index选择往左还是往右，不难