Personal-Notes

一些套路

既有题目思路

1. 不贪图运行时间最快，但算法复杂度需要尽可能低
2. 思路要易于理解，代码要尽可能短，每条思路所对应的代码最好要形成模板

新题套路

1. Problem Solving：把新题解释成既有套路的过程
   1. 遇到没思路的新题先举栗子找规律
2. Code Writing：熟练掌握既有套路
   1. BFS -- 熟练度高
   2. DFS / Backtracking
   3. Binary Search
   4. Linked List
   5. Tree
   6. Two Pointer

面试技巧

1. 当你面试时，你在白板上写，写完之后，面试官很可能就立刻开始给你指bug了，你这时有的bug，都算bug！所以，在写完最后一句话前，最好做个大停顿，过一下之前写的，快速检查下。当然你嘴上可以给面试官解释你现在是在做最终检查，不是说卡住不会了。
2. 最好不要说完思路就动笔就写，需要思考不同的解法，并与面试官交流明确：
   1. 要熟悉刷题网站提供的标准解法
   2. 要准备一个面试友好的解法
   3. 要准备时间空间权衡的分析：有的解法可能时间复杂度不高，但空间复杂度很不错

面试流程

1. 问题分析
2. 交流阶段：厘清各种条件
3. 提出各种方案，满足面试官要求
4. 如果方案不能再规定时间内写完，与面试官交流选定一个方案
5. coding
6. test & debug
   1. 考虑corner case，做各种assumption
7. follow up: doc, unit test, regression test, performance tuning, benchmarking

DP

简而言之 DP有六部曲 个人建议面试时写在白板上 清楚明了 一步都不能少 基本上你写出这些 implement起来也非常简单了

1. 定义：dp[j]表示什么含义，比如largest subarray sum ending at arr, and must include arr. 注意语言描述, 包括还是不包括arr/matrix[j]
2. 归纳法则：dp 的 dependency 是怎么样的，依赖于dp[i-1] 还是 dp[i+1] 还是 dp[k] for all k < i or all k > i 等等，试着过几个小例子推导一下
3. 初始态：往往是dp[0]，二维往往是第一行，第一列，也就是dp[0], dp[0][j], dp[i][0]
4. 结果：往往的dp[n], max(dp) 等等, 从definition 出发
5. 填充顺序：从induction rule 的 dependency出发 判断的从左到右 还是 从左上到右下
6. 优化: 分为时间和空间两方面。
   1. 时间的比较难，因为往往需要你重新define dp state 和 induction rule。
   2. 空间比较简单，可以根据induction rule看出来，比如斐波那契数列: dp = dp[i - 1] + dp[i - 2], 那么dp 只依赖于前两个元素，就不需要create 整个 dp array，两个variable即可，空间可以从O(n)优化到O(1)。

最后, 多总题多总结多积累小tips，熟能生巧后dp其实是非常简单，也非常有套路的，一些induction rule 的常见pattern 你一眼就能看出来了。

String基本操作

s2 = "shaunwei"
s2[-3:] = "wei"
s2[5:8] = "wei"
s2.index('w') = 5  # if not found, return -1

链表

链表的技巧不多，主要是记忆操作顺序太繁琐，现想其实也是有时间的。

1. 翻转链表
2. 删除节点
3. Dummy Node
4. 快慢指针

Tree

遍历：DFS和BFS

1. 前序
2. 中序
3. 后序
4. BFS

Sorting

选择排序最好理解，每次迭代都从子数组里寻找最小值即可，第k次迭代抽出来的即是第k小值

def swap(self, arr, i, j):
    temp = arr[j]
    arr[j] = arr[i]
    arr[i] = temp


def selectSort(self, arr):
    l = len(arr)
    for i in range(0, l):
        min = 2 ** 31
        m = 0
        for j in range(i, l):
            if arr[j] < min:
                min = arr[j]
                m = j
        self.swap(arr, i, m)
    return arr

插入排序的话需要假设前面第i-1个数字是排好序的，然后把第i个数字插到已经排好序的数组里的恰当位置；既然是插入那么其实用链表比用数组要经济

def insertSort(self, arr):
    l = len(arr)
    for i in range(1, l):
        temp = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > temp:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = temp
    return arr

合并排序很容易理解，要点是每排完一个数组就把另一个数组剩余值贴后面

def merge(self, arr1, arr2):
    arr = []
    [l1, l2] = [len(arr1), len(arr2)]
    [i1, i2] = [0, 0]
    while i1 < l1 and i2 < l2:
        if arr1[i1] < arr2[i2]:
            arr.append(arr1[i1])
            i1 += 1
        else:
            arr.append(arr2[i2])
            i2 += 1
    if i1 == l1:
        arr += arr2[i2:]
    else:
        arr += arr1[i1:]
    return arr

def mergeSort(self, arr):
    l = len(arr)
    if l == 1:
        return arr
    elif l == 2:
        if arr[0] > arr[1]:
            self.swap(arr, 0, 1)
        return arr
    else:
        l1 = l // 2
        m1 = self.mergeSort(arr[0:l1])
        m2 = self.mergeSort(arr[l1:])
        return self.merge(m1, m2)

快速排序没什么好说的

def quickSort(self, arr):
    l = len(arr)
    if l <= 1:
        return arr
    pivot = arr[int(random.random() * 200) % l]
    a = []
    b = []
    c = []
    for i in arr:
        if i < pivot:
            a.append(i)
        elif i == pivot:
            b.append(i)
        else:
            c.append(i)
    return self.quickSort(a) + b + self.quickSort(c)

Union-find

Quick-find: 确定两个点是否处在同一个连通集里：遍历所有的边(p, q)，每次都把id[p]改成id[q]

class UF:
    id = []
    count = 0

    def __init__(self, N):
        self.count = N
        for i in range(0, N):
            self.id.append(i)

    def dump(self):
        temp = ""
        for i in range(0, self.count):
            temp += (" " + str(i))
        print(temp)
        temp = ""
        for i in self.id:
            temp += (" " + str(i))
        print(temp)
        print()

    def find(self, p):
        return self.id[p]

    def quick_find(self, arr):
        for i in arr:
            pID = self.find(i[0])
            qID = self.find(i[1])
            if pID == qID:
                continue
            else:
                print(pID, qID)
                for j in range(0, self.count):
                    if self.id[j] == pID:
                        self.id[j] = qID
                self.dump()

Hash Table

1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution.

从头至尾检索一遍数组，如果Hashmap里没有(target - nums[i])就丢进去{nums[i], i}，否则的话就是遇到了结果，返回(target - nums[i])的角标 （Hashmap.get(target - nums[i])）和当前角标。

public int[] twoSum(int[] nums, int target) {
    if (nums == null || nums.length == 0)
            return new int[]{0, 0};
    Map<Integer, Integer> hashmap = new HashMap<Integer, Integer>();
    int index1 = 0, index2 = 0;
    for (int i = 0; i < nums.length; i++) {
        if (hashmap.containsKey(target - nums[i])) {
            index1 = hashmap.get(target - nums[i]);
            index2 = i;
            return new int[]{index1, index2};
        } else {
            hashmap.put(nums[i], i);
        }
    }
    return new int[]{0, 0};
}