今天我刷题了

今天刷的题
1. function exclusive time:
这个题要理解函数调用栈的特殊性。只需要把start event的id存入栈中即可。另外需要维护一个全局globaltimestamp，用以计算时间
2. 一个数字字符床，加入+-*运算符，哪些可以算出目标值
刚开始想暴力，算出所有的运算法，再对表达式求值。这样会非常慢，而且表达式求值也不容易做。
这道题要边dfs表达式，边求值。加减还好说，遇到乘法时，需要知道前一个factor是什么。建议实际面试中，先把+-的情况做出来，再扩展到支持*运算符
3. read4
这道题，需要一个读指针，一个写指针，还有个cache
当读，写指针指向一处时，需要调用read4函数，refill cache。
注意，写指针为调用read4的返回值。当返回值为0时，后面所有的读操作都返回0

1. 朋友request
这个题，需要按年龄把人分组，然后分别计算组内的request，和发到组外的request。
因为年龄是有限多个的，所以会快很多。
注意，<15岁的组，不会发任何request

2. 二叉树垂直遍历
这里，主要要求是，如果列相同，则depth浅的排前边。如果行列都相同，按value排序。
推荐用dfs。遍历的时候，把排序的key社为depth和value，这样后面整理结果就会容易很多。

今天就刷了一道：
1. 132模式：for i < j < k, a[i] < a[k] < a[j]
这个题，
第一步要想到遍历坐标j，就是找一个可以作为3的candidate。
那么我们想要左边尽可能小。
求左边最小，就是一遍dp

第二步，要想到如果一个数大于左边最小，那么就是一个可能满足条件的3。我们需要从他的右边，找到比它小的，但是又是尽可能大的k，这样才最有可能大于a[i]
这样子有两种方法：
方法一：直接从j+1开始遍历，直到找到一个k，满足132模式。找到就return true，找不到继续遍历j。这是个O(n^2)的解法
方法二：单调栈解法。这个解法虽然能做到O(N)，但是普适性不强。方法是从右边开始scan，维护一个递减的栈。当遍历到j时，就把栈里面所有比a[j]小的元素都pop出来，那么最后一个被pop出来的数，就是j右边比a[j]小的最大的数。可以证明，虽然这个方法无法一次遍历，找到所有元素的右边比自身小的最大元素（比如[5, 8, 9, 2, 7], 8 的那个元素是7，但是遍历9的时候，已经把7pop出来了，所以求不出8的那个元素），但是还是可以用于解132模式这道题。因为，以[5, 8, 9, 2, 7]为例，虽然找不到8的那个元素，但是9比8大，所以9比8更有可能是a[j]的候选值。

今天有面试。
两道简单题，但是第二道没有一遍过，出了个小bug，要interviewer提示了两次才get到。这样不好，要赶紧改，认真听interviewer的反馈。
做题速度要加快。争取把fb前50掐着时间再刷一遍。

1. union find 模版
def __init__(self):
        self.father = {}
        self.number_components = 0

    def union(self, a, b):
        fa, fb = self.find(a), self.find(b)
        if fa != fb:
            self.father[fa] = fb
            self.provinces -= 1

    def find(self, a):
        if self.father[a] == a:
            return a

        self.father[a] = self.find(self.father[a])
        return self.father[a]

今天刷的题：
1. max path sum in binary tree:
这道题，注意可以维持一个全局最大值。不用使用两个helper函数
2. curency exchange
这道题，就是一个spfa问题。要注意将图合适的表达出来。
3. valid palindrome 2
这道题，就是简单的dfs。使用双指针，当左右指针不等时，可以试着将左边或者右边删除，递归求解。
暴力解法：每次删除一个字符，看剩下的是不是回文。O(N^2)
dfs: 不管删除左边，还是右边，都不需要重复遍历。所以是O(N)。而且，dfs容易扩展为删除k个字符的情况

1. insert into cyclic ordered linked list
这道题，首先要找到insertion point。
总共有三处：
一是 a <= x <= b,
二是a > b, 且 x > a or x < b, 这里，x比原来的最大值大，或者比原来的最小值还小。
三是遍历回到了原来的node，比如 2->2->2->2, insert 也是2. 或者原来只有一个数， 2 -> 自己

2. clone 图
这道题分成两步。第一步克隆节点，简单的bfs，注意不要忘记判断是否visited过。可以使用mapping来判断是否visited过。
第二步克隆邻居。简单loop
3. leftmost column with at least a one
第一种解法是binary search, nlogm
第二种解法是类似搜索2d array，从右上角出发，如果是0，则往下走，如果是1，则往左边走。

1. corner rectangle 的个数。corner rectangle就是四个角是1，其他地方不管。
这个题，粗看很难，其实很简单。
对任意两行，看看这两行，有多少列都是1，假设有k列。那么这两行的corner rectangle个数就是 k * (k - 1) // 2.
枚举所有的两行都计算下就可以了。复杂度是 O(rows^2 * cols)
对于spart array，可以将每行哪些列是1的坐标记录到set中。枚举任意两行时，计算下两个set的交集即可。

2. 循环数组的两个基本技巧
一是直接将循环数组延长一倍，arr = arr * 2.
二是转化，例如求循环数组 [0, 1, 2, ...., n] 最大子数组，那么最大子数组要么在i, j 之间 （0 <= i < j < len(arr)), 要么在j ... len(arr) - 1 ... i 这里。对于第二种情况，可以转化为求i, j 之间 （0 <= i < j < len(arr))的最小子数组。

1. 最长无重复字符的子串，最长最多k个unique字符的子串
模版一套，搞定

2. 外星人字典，课程表
拓扑排序。
几个步骤：
- 构建图，indegree，outdegree等
- 将indegree为0的节点放入queue
- bfs，同时更新indegree，不断将indegree为0的节点放入queue
- queue为空时退出循环，检查是否有环。检查方法：是不是所有的节点都放在了结果集里面
- return

3. calendar
判断两个区间[start1, end1] 和 [start2, end2]是否overlap的最简单方法：
max(start1, start2) > min(end1, end2)
这个系列题，都可以用扫面线解决


补充内容 (2021-04-21 13:27 +8:00):
max(start1, start2) <= min(end1, end2)

1. interval list intersection
这道题双指针来做。
注意不要把判断两个区间是否overlap的条件写错了

2. valid number
状态机太牛了。面试如果遇到，起码把状态机的框架写对

1. connect 4
挺好写的。注意边写边测试，早点发现错误。
测试是否能赢，只需要在当前点周围扩展即可。不需要检查整个board

2. merge account
只是照着模版抄了一遍。
要点是，先写好union 和 find的函数，很好写，只要写对father这个map，就成功了一半。
注意father的key和value都是email地址。
明天早上在复习把

今天拿了三个onsite，激动的没有刷题