Algorithms and data structues


Core algorithms deployed
Algorithms: Design Techniques and Analysis
The Algorithm Design Manual 2nd Edition


如果问连通性,静态就是 DFS,BFS,动态就 UF
如果问依赖性就 topo sort
DAG 的问题就 dfs+memo
矩阵和 Array 通常都是 DP
问数量的通常都是 DP
问是否可以,也很有可能 DP
求所有解的,基本 backtracking


最终我觉得像word search12, word break12,word ladder12,LIS,sort color,LRU,insert & delete in O1,rob house123,234sum这种题要达到闭眼秒杀的程度,min/max heap,bucket sort,topological sort,binary pre/in/post/level 遍历,combination/permutation这种东西要做梦都梦到

Why do we have to solve leetcode problems?

尤其是在北美,Google,Facebook,Microsoft,Amazon 等等大公司,无一不考刷题,以算法面试为主。而无论是北美留学生,还是工作几年的上班族,想进大公司,唯一的出路就是刷题。
Leetcode 分类顺序表第二版

Computational complexity theory

Core conceptions

Linked list

Static linked list

Reprented in an array.

Internal vs external liked

Sometimes, SLUB put freelist in object

kernel doubly linked list operations


  • kernel version
    next->prev = new;
    new->next = next;
    new->prev = prev;
    prev->next = new;


  • kernel version
    next->prev = prev;
    WRITE_ONCE(prev->next, next);
    entry->next = LIST_POISON1;
    entry->prev = LIST_POISON2;

    BL list

    kernel: add bl_list - 4e35e6070b1ceed89c3bba2af4216c286fb1dafd

Double linked list

Associative array

Essentials: Brian Kernighan on Associative Arrays - Computerphile
vs indexed array


  • trade-off
    a) Checking more places takes more power and chip area,
    b) and potentially more time. On the other hand, caches with more associativity suffer fewer misses
    fully associative - the best miss rates, but practical only for a small number of entries
    N-way set associative cache: 8 is a common choice for later implementations
    direct-mapped cache - if two locations map to the same entry, they may continually knock each other out. anti-fragmantion worsens this case.

Judy array


A generic hash table
hash function


In-order traversal
postfix and prefix and sort


Depth first sarch


Interval tree in kernel

anonymous page: anon_vma_interval_tree_insert


Trie is prefix tree.
Trees only store keys.
Trie Data Structure
Trie with numeric key
* terms very confused
Radix tree vs Trie, check radix meaning
Patricia is compact trie or Patricia is radix = 2 trie?

Radix tree in kernel not wikipedia

page cache: page_cache_tree_insert
Wikipedia: Radix tree looks like a compact trie.
Kernel: Radix tree was more like a Multi-level index associative arrya or judy array.
Trees I: Radix trees
Enhancing the Linux Radix Tree
The design and implementation of the XArray
A multi-order radix tree
radix_tree_init_maxnodes(): height is 11 in kernel?
radix_tree_create() add one page
radix_tree_lookup_slot: find one page


Data property: unique key, indexed
Search data structure
Sequencial array: binary search
Associative array

Which algorithm?

Advantages of BST over Hash Table
1. Can get all keys in sorted order by just doing in-order traversal of BST
2. Doing order statistics, finding closest lower and greater elements, doing range queries are easy to do with BSTs.
3. BSTs are easy to implement compared to hashing.
4. With Self Balancing BSTs, all operations are guarnateed to work in O(logN) time.

Replacement polices



Leetcode 146 LRU cache
Order items by access times

Pseudo LRU/2 - Second chance and queue

type: Reclaim
Order items by enqueueing sequence

Second chance and 2Q

Page reclaim algorithm
type: Reclaim

Ring buffer or Circular buffer

Redblack tree

gap between linar node can be optimized by argument rb tree. O(n) -> O(log n)
mm: augment vma rbtree with rb_subtree_gap d37371870ceb1d2165397dc36114725b6dca946c
Rank-Balanced Trees
Left-Leaning Red-Black Trees


AVL tree, B-tree, symmetric binary B-tree or 2–3–4 tree, red–black tree
2-3-4 Trees and RedBlack Trees