Found in
images
Articles
DS
Data structure
Disjoint set union
Merge two sets and tell whether elements are in the same one, in almost O(1): a forest of parent links and two tricks.
O(α(n))
2 problems
GRA
Algorithm
Bipartite matching
The largest number of pairs in a bipartite graph: Kuhn, Hopcroft–Karp, the theorems of König and Hall.
O(E √V)
2 problems
ML
Algorithm
k-means
Splits points into k groups so that points sit close to the centre of their group.
O(n · k · d) per step
2 problems
ML
Algorithm
Perceptron and backpropagation
Draw a digit: a perceptron from 1958 and a network with a hidden layer, both trained right in the page in a second, read it.
perceptron: O(d) per example; network gradient: O(number of weights) per example
1 problem
TEC
Technique
Cache-friendly data
The same algorithm, a different order of memory accesses: tiling, padded rows and laying data out by field.
the same big O
1 problem
Problems
Often together
classic 3 array 2 interviews 2 iterative 2 disjoint sets 1 connectivity 1 tree 1 amortized 1 offline queries 1 maps and navigation 1 science and physics 1 matching 1