Essential Algorithm Cheat Sheet: Sorting, Graph, Greedy, and Bit Operations

Sorting Algorithms

Quick Sort – unstable. Time complexity: best O(n log n), average O(n log n), worst O(n²).

Merge Sort – stable. Time complexity: O(n log n) in all cases.

Bucket Sort – distributes elements into k buckets; each bucket is sorted (often recursively). Time complexity: best Ω(n + k), average Θ(n + k), worst O(n²).

Radix Sort – processes digits (or bits) of keys and uses bucket sort internally; no final per‑bucket sort. Time complexity: best Ω(n·k), average Θ(n·k), worst O(n·k) where k is the number of digit positions.

Graph Algorithms

Depth‑First Search (DFS) – explores a graph by going as deep as possible before backtracking. Time complexity O(|V| + |E|).

Breadth‑First Search (BFS) – explores vertices level by level. Time complexity O(|V| + |E|).

Topological Sort – linear ordering of vertices in a directed acyclic graph such that for every edge u→v, u appears before v. Time complexity O(|V| + |E|).

Dijkstra’s algorithm – single‑source shortest paths for non‑negative edge weights. Simple array implementation O(|V|²); with a binary heap O((|V|+|E|) log |V|).

Bellman‑Ford algorithm – single‑source shortest paths that also handles negative‑weight edges (detects negative cycles). Worst‑case time complexity O(|V||E|), best O(|E|) when no relaxation is needed.

Floyd‑Warshall algorithm – all‑pairs shortest paths in weighted graphs (negative edges allowed, no negative cycles). Time complexity O(|V|³).

Minimum Spanning Tree (MST)

Prim’s algorithm – grows the MST by repeatedly adding the cheapest edge from the tree to a vertex outside. Simple array implementation O(|V|²); with a binary heap O(|E| log |V|).

Kruskal’s algorithm – sorts all edges by weight and adds them to the forest if they do not create a cycle (using Union‑Find). Time complexity O(|E| log |V|).

Greedy Algorithms

Greedy methods make the locally optimal choice at each step. They are applicable when the problem exhibits optimal substructure and the greedy‑choice property.

Example – Coin Change (V = 41)

Choose the largest coin ≤ V (25¢). Remaining V = 16.

Choose 10¢. Remaining V = 6.

Choose 5¢. Remaining V = 1.

Choose 1¢. Remaining V = 0.

Total coins used: 4.

Bit Manipulation

Test k‑th bit: s & (1 << k) Set k‑th bit: s |= (1 << k) Clear k‑th bit: s &= ~(1 << k) Toggle k‑th bit: s ^= (1 << k) Multiply by 2ⁿ: s << n Divide by 2ⁿ: s >> n Intersection: s & t Union: s | t Difference: s & ~t Extract lowest set bit: s & (-s) Extract lowest zero bit: ~s & (s + 1) Swap two integers without a temporary variable:

x ^= y; y ^= x; x ^= y;

Asymptotic Notations

Big O (O) – upper bound describing worst‑case growth.

Little o (o) – strict upper bound; the function grows strictly slower.

Big Omega (Ω) – lower bound describing best‑case growth.

Little ω (ω) – strict lower bound; the function grows strictly faster.

Theta (Θ) – tight bound representing both upper and lower limits.

Source Repository

Algorithm implementations and interview resources are hosted at https://github.com/kdn251/interviews.