Tag: algorithms

Reservoir Sampling:One Pass When You Do Not Know n Up Front

Keep the first k items, then for each later index i (1-based), replace a slot with probability k/i — a uniform sample of k from a stream of unknown length.

Algorithms

Binary Exponentiation:pow(base, exp) in Logarithmic Multiplies

Square the base and consume the exponent bit by bit — O(log exp) multiplies instead of a loop of exp products, for integers or modular pow.

Algorithms

Fisher-Yates:Shuffle in Place Without Bias

For i from n-1 down to 1, swap a[i] with a uniform index in 0..i — every permutation equally likely, which is what Collections.shuffle already runs.

Algorithms

Euclid GCD:Subtract, Then Mod, Then Extended Coefficients

Replace repeated subtraction with remainder, then back-substitute for Bézout coefficients — gcd, lcm, and a modular inverse when gcd is 1.

Algorithms

Count-Min Sketch:Approximate Frequencies When Exact Maps Do Not Fit

d × w counters and the min over hashes: over-estimate frequencies on purpose when a HashMap of every key will not fit.

Algorithms

Aho-Corasick:Many Patterns, One Pass Over the Text

Build a trie of all needles, add failure links like KMP on a forest, then scan the haystack once — every pattern that ends at the current character reports.

Algorithms

HyperLogLog:Approximate Distinct Count in Tiny Memory

Estimate cardinality with a handful of registers and a harmonic mean — plus-or-minus is the point, not a HashSet of every key.

Algorithms

Boyer-Moore:Skip Ahead When the Mismatch Is Near the End

Align the pattern at the window end, use a bad-character skip (and the good-suffix idea) so a late mismatch jumps the haystack instead of sliding by one.

Algorithms

Raft:Elect a Leader and Replicate a Log (Awareness, Not a From-Scratch Cluster)

Raft terms, leader election, and log replication at awareness depth — enough to know what etcd and Kafka-adjacent consensus are doing, not enough to ship your own cluster.

Algorithms

Rabin-Karp:Rolling Hash When You Need Many Pattern Checks

Slide a window hash in O(1), compare hashes first, then verify characters — the procedure for one needle or many needles against the same haystack.

Algorithms

Two-Phase Commit:All Prepare, Then All Commit — and Why It Blocks

A coordinator asks every participant to prepare, then commit or abort together — and why a crashed coordinator leaves the cluster stuck.

Algorithms

Exponential Backoff:Retry With Jitter Instead of a Thundering Herd

Wait base × 2^attempt after a failure, cap the wait, and add jitter so retries do not stampede the same instant.

Algorithms

Leaky Bucket:Smooth Bursts Into a Steady Drain

Queue work into a bucket that leaks at a constant rate — overflow is dropped or the caller waits. Smooth output, not a stored burst of tokens.

Algorithms

KMP:Find a Pattern Without Sliding Back on the Text

Build the LPS prefix table, then scan the text once — on a mismatch the pattern jumps using already-matched prefix, so the text index never retreats.

Algorithms

Token Bucket:Allow Bursts, Then Enforce an Average Rate

Refill tokens at a steady rate, spend one per request, and allow a burst up to bucket capacity — then reject or wait.

Algorithms

Prim:Grow an MST From a Seed Vertex

Grow a min-heap of crossing edges from a seed until every vertex is in the tree — a Dijkstra-shaped frontier for an MST, not distances from a source.

Algorithms

Consistent Hashing:Move Few Keys When a Node Joins or Dies

Place keys on a ring so adding or removing a node remaps only its neighbors — not every key — with virtual nodes to even the load.

Algorithms

Backtracking:Search With Undo When the Next Choice Depends on the Last

Choose, recurse, undo: search a decision tree with pruning when the next pick depends on the path — not a second knapsack table.

Algorithms

Interval Scheduling:Always Take the Finish That Frees the Room Soonest

Pick a maximum subset of non-overlapping intervals by earliest finish time — greedy that throws ranges away, not merge-intervals.

Algorithms

LZ77 and DEFLATE:Sliding-Window Compression Behind zip and gzip

Find repeated phrases in a sliding window as length-distance pairs, then Huffman-code the tokens — that pairing is DEFLATE, not Huffman alone.

Algorithms

Huffman Coding:Build a Prefix Code From Frequencies

Build a prefix-free code from symbol frequencies with a heap: greedy merges, why it is optimal here, and why this is not DEFLATE.

Algorithms

Edit Distance:Insert, Delete, Substitute as a Costed Grid

Levenshtein distance on a DP grid: insert, delete, substitute, and recover one alignment — related to LCS, a different job.

Algorithms

LIS:Longest Increasing Subsequence in n log n

Longest increasing subsequence: the O(n²) best-ending-here table, then patience / tails plus binary search for n log n.

Algorithms

LCS:Longest Shared Subsequence Without Requiring Contiguous

Find the longest common subsequence of two strings with a DP grid: match or skip, then reconstruct one shared sequence.

Algorithms

Coin Change:Unbounded Combinations When the Item Can Repeat

Make change when each denomination may be used again: min-coins and count combinations, and why this is not 0/1 knapsack.

Algorithms

0/1 Knapsack:Pick or Skip When Each Item Exists Once

Fill a capacity with pick-or-skip DP: each item once, a 2D table or a 1D roll, and how to reconstruct which items went in.

Algorithms

Kruskal:Grow an MST by Cheapest Edge That Does Not Cycle

Sort every undirected edge cheapest-first, skip endpoints already in the same Union-Find component, accept the rest until n-1 edges — an MST that is not a shortest path from a source.

Algorithms

A-Star:Dijkstra Plus a Heuristic When You Can Estimate Remaining Cost

Order the heap by f = g + h, settle toward a goal when h never overestimates remaining cost, and skip stale pairs like Dijkstra — the same procedure with a heuristic that may guess low, never high.

Algorithms

Floyd-Warshall:All-Pairs When n Is Small Enough for n³

Fill a dense distance matrix by relaxing every triple (k, i, j) — all-pairs shortest paths when n³ is the bill you can pay, and a negative on the diagonal is a negative cycle.

Algorithms

Bellman-Ford:Shortest Path When a Negative Edge Is Allowed

Relax every edge V-1 times, then one more pass for a negative cycle — single-source shortest path when a weight is allowed to be negative.

Algorithms

Dijkstra:Shortest Path When Every Edge Weight Is Non-Negative

Grow a min-heap frontier by current distance, settle each vertex once, and lazy-repush instead of decrease-key — the weighted cousin of BFS when every edge weight is non-negative.

Algorithms

Strongly Connected Components:Collapse a Directed Graph to a DAG

DFS to record finish order, transpose the digraph, DFS again in reverse finish order — each second-pass tree is a strongly connected component, and the condensation is a DAG.

Algorithms

Topological Sort:Order a DAG Before You Run the Work

Emit each vertex only after its predecessors — Kahn with indegree and a queue, or DFS reverse finish times — and treat leftover vertices as a cycle.

Algorithms

Cycle Detection:Directed, Undirected, and the Color/Parent Trick

Detect a directed cycle with 3-color DFS (gray means on the recursion stack) and an undirected cycle by skipping the parent — a visited flag alone is the diamond trap.

Algorithms

DFS:Finish Times, Recursion vs an Explicit Stack, and What a Cycle Looks Like

Walk a graph with DFS, stamp finish times, run the same walk on an ArrayDeque, and recognize a back edge as the shape of a cycle.

Algorithms

BFS:Level Order, Shortest Unweighted Path, and Why the Frontier Is a Queue

Visit vertices in hop order with a FIFO queue — level order and unweighted shortest path — and see why a stack is the wrong frontier.

Algorithms

External Sort:K-Way Merge When the File Does Not Fit in RAM

Sort RAM-sized chunks, write runs to disk, then k-way merge with a heap of heads — the in-memory merge-sort cousin when the file cannot be loaded.

Algorithms

Timsort:What `Arrays.sort` Actually Runs on Objects

Natural runs, insertion on short runs, then merge — what object Arrays.sort and Collections.sort actually run, and why you should not hand-roll it.

Algorithms

Radix Sort:Digit Passes When Comparison Is the Wrong Primitive

LSD digit passes as counting sort, when integer or string keys have a digit layout, and why Arrays.sort is not this.

Algorithms

Counting Sort:Rank by Frequency When the Key Universe Is Small

Histogram, prefix of counts, and a stable place-from-the-right pass when keys come from a small universe.

Algorithms

Heapsort:Sort With a Heap When You Need O(n log n) and Little Extra Memory

Build a max-heap and extract the max into the tail — guaranteed O(n log n), little extra memory, and why PriorityQueue poll-all is not this procedure.

Algorithms

Quicksort:Partition in Place and Why the Pivot Policy Is the Algorithm

Partition around a pivot and recurse — and why last-element vs random vs median-of-three vs dual-pivot is the algorithm, not textbook Lomuto as Arrays.sort.

Algorithms

Merge Sort:Stable Divide-and-Conquer When You Can Afford the Extra Array

Split, sort the halves, merge two sorted runs — why the extra array buys a guaranteed O(n log n) bound and stability, and what object Arrays.sort actually runs.

Algorithms

Quadratic Sorts:Insertion, Selection, and Why Bubble Survives Only in Interviews

Insertion still earns a seat on small or nearly-sorted ranges; selection swaps the min into place; bubble is a whiteboard name — none of them are the production default.

Algorithms

Merge Intervals:Collapse Overlaps Instead of Sorting the Same Range Twice

Sort by start, sweep, and merge overlapping calendar or busy ranges — and when this is not interval scheduling.

Algorithms

Kadane:Maximum Subarray Without Trying Every Slice

Running best ending here, empty-array and all-negative pitfalls, and why this is one pass of DP you do not need to name as a table.

Algorithms

Prefix Sums:Answer a Range in O(1) After One Precompute

Inclusive vs exclusive prefixes, a 2D sketch, difference arrays for range updates, and when a Fenwick or segment tree is the next bill.

Algorithms

Sliding Window:Grow and Shrink a Range Without Restarting the Scan

Fixed and variable windows, the add-right / drop-left invariant, and why this is not the same thing as a rate-limit window.

Algorithms

Two Pointers:One Pass From Both Ends Instead of a Nested Loop

Opposite-end, pair-sum on sorted data, and fast/slow — when two indexes replace O(n²) and when they are just two indexes.

Algorithms

Binary Search:Cut the Space in Half When the Data Is Already Ordered

The sorted invariant, lower and upper bound, off-by-one, and what Arrays.binarySearch encodes when the key is missing.

Algorithms

Algorithms Roadmap:Pick the Procedure for the Job You Have

A map of search, sort, graphs, strings, DP, and systems algorithms — what job each one solves, when to skip it, and a living index of every post in this series.