Data Structures & Algorithms

How Big-O, Big-Θ, and Big-Ω measure the way an algorithm's work grows with input size, ignoring constants and hardware so you compare scaling rather than stopwatch times.

Why cache hierarchy and memory locality mean an algorithm with fewer operations can still lose to one that touches memory in a cache-friendly order.

Contiguous memory gives O(1) indexing, and the doubling trick lets a dynamic array fake unlimited growth by reallocating and copying when it fills.

Trading the array's contiguous block for scattered nodes joined by pointers: no O(1) indexing or cache friendliness, but O(1) splicing wherever you already hold a reference.

Access disciplines layered over an array or list, and the ring buffer trick that makes a queue O(1) at both ends without shifting elements.

An array plus a function that turns any key into a slot number, making lookups a single address computation as long as the table stays well-spread and empty enough.

What happens when two keys map to the same bucket: chaining hangs a small list off the bucket, while open addressing probes for the next free slot.

Nodes with up to two children where height drives performance, and how pre-, in-, post-order, and level-order walks decide the order you see the data.

The left-smaller / right-larger rule turns search into a halving descent, but the wrong insertion order quietly collapses the tree into a slow chain.

AVL and red-black trees enforce a height bound after every update and repair violations with rotations: local, constant-time pointer reshuffles that preserve order.

Search trees redesigned around the cost of a disk seek, packing hundreds of keys per page so huge datasets stay three or four levels tall.

A complete tree where every parent out-ranks its children, stored pointer-free in a flat array for O(1) access to the best element and O(log n) insert and remove.

Storing strings character-by-character down shared paths for O(k) lookups and free prefix queries, with radix trees compressing single-child chains to save memory.

Answering range sum, min, and max queries on a changing array in O(log n) by precomputing aggregates over a tree of ranges.

Why any sort that only compares pairs is stuck at Ω(n log n), and how quicksort, mergesort, and heapsort differ in how they split the work and what they trade.

Counting, radix, and bucket sort run in O(n) by reading keys directly instead of comparing them, which only works when the keys are structured.

The hybrid sorts in real standard libraries: Timsort exploits pre-sorted runs, while Introsort runs quicksort but bails to heapsort to dodge the O(n²) spiral.

How storing edges as a matrix or a list decides which questions are cheap, and why adjacency lists win on the sparse graphs that dominate the real world.

BFS and DFS both visit every reachable vertex in O(V + E) and differ by one thing — a queue versus a stack — turning flooding into dive-and-backtrack.

Edge relaxation underpins every shortest-path algorithm; Dijkstra, Bellman-Ford, and A* differ only in the order and conditions under which they relax edges.

Connecting every vertex with V−1 edges of least total weight via two greedy approaches — Kruskal adds the cheapest safe edge anywhere, Prim grows one tree outward.

A disjoint-set forest that answers 'same group?' and 'merge groups' in near-constant time using union by rank and path compression.

Splitting a problem into smaller copies of itself, and using T(n) = a·T(n/b) + f(n) and the Master Theorem to find where the work piles up.

Turning an exponential recursion into a polynomial one by computing each overlapping subproblem once and reusing its stored result.

Building an answer by always taking the best-looking option now, provably optimal only when the problem has the greedy-choice property.

Skip lists layer express lanes over a sorted list for expected O(log n) search, and Bloom filters pack membership into a tiny bit array with no false negatives.