Found in
operating systems
Articles
SRT
Algorithm
Heapsort
A heap right in the array: n log n in the worst case with no extra memory, the insurance of introsort and the Linux kernel's sort.
O(n log n)
2 problems
DS
Data structure
Binary heap
The minimum at hand, insertion and extraction in O(log n): the tree in an array that event calendars live on.
O(log n)
2 problems
DS
Data structure
AVL tree
A search tree where the branch heights at a node differ by at most 1: height up to ~1.44·log₂ n.
O(log n) for search, insertion and deletion
2 problems
STR
Algorithm
Boyer–Moore
Compares from right to left and skips letters: on long patterns it reads only a small part of the text.
O(n + m)
2 problems
TEC
Technique
Bit tricks
A number as a set of flags: masks, the lowest set bit, counting ones and going through subsets without recursion.
O(1) per operation on a word
1 problem
Problems
Often together
classic 4 interviews 4 tree 3 in production 3 heap 2 array 2 sorting 1 in place 1 scheduling 1 simulation 1 science and physics 1 search tree 1