Posts tagged “algorithms”
23 posts Subscribe by RSS
23 posts
Project Euler 5: Building the Smallest Number Divisible by 1 to 20 from Least Common Multiples
Build the smallest number divisible by 1 to 20 by folding lcm(a, b) = a / gcd(a, b) × b with Euclid's algorithm, plus a correctness proof, overflow notes, and C++17 and Python 3 code.
Jump consistent hash: picking a shard number without a lookup table, and what it assumes
Growing from 10 to 12 shards, hash mod n moves 5/6 of the keys; only 1/6 has to move. Lamping and Veach's code, why it works, and what adding or removing buckets does.
Boyer–Moore majority vote: one candidate, one counter, and why you need a second pass
MJRTY (Boyer and Moore, 1980) picks a majority candidate with one value and one counter. Its rules, why it works, the wrong answer when no majority exists, and the second pass.
Project Euler 4: Searching Products from the Top for the Largest Palindrome
Find the largest palindrome product of two 3-digit numbers by searching big products first and pruning, with a proof the pruning is safe, the link to 11, and C++17 and Python 3 code.
Union-find path compression and weighting: which implementation the α(n) bound belongs to
How size weighting, path compression and path halving change a union-find parent array, and which bound, worst-case Θ(log n) or O(m α(n)) per sequence, algs4 gives each implementation.
Project Euler 3: Finding the Largest Prime Factor by Dividing It Out
Find the largest prime factor of a 12-digit number by trial division. Covers why the leftover value is prime, the √n iteration bound, 64-bit integer range, and C++17 and Python 3 code.
The KMP failure function: where the pattern goes after a mismatch
How KMP string search picks the pattern position to compare after a mismatch: the f and next tables, how to build them, and why the search is linear, from the 1977 paper and Princeton's code.
Project Euler 2: Adding Only the Even Fibonacci Numbers
Prove every third Fibonacci term is even, derive the even-only recurrence E(k) = 4E(k−1) + E(k−2), and sum even terms up to four million, with C++17 and Python 3 code and a correctness proof.
Project Euler 1: Summing Multiples of 3 or 5 in O(1)
Add up every number below 1000 divisible by 3 or 5 without a loop, using inclusion–exclusion and the arithmetic series formula. C++17 and Python 3 code, a correctness proof and integer-range notes.
The Linux kernel rbtree: a red-black tree with embedded nodes and no stored comparator
Linux's red-black tree never stores a comparator. Embedded nodes, your own search loop, helpers taking per-call compare functions, colour bits, cached and augmented trees, lockless lookup in v6.17.
Skip lists: how coin-flip levels give O(log n) expected search
Why does adding random-level pointers to a sorted linked list make search O(log n) expected? Pugh's algorithms, what 'expected' covers, and what Java's ConcurrentSkipListMap docs promise.
Picking k random items from a stream of unknown length: reservoir sampling (Algorithm R)
Reservoir sampling picks k random items in one pass over data of unknown size. Why each item enters with probability k/i, proofs of k/n and uniform k-subsets, and a common off-by-one.
Median of Medians (BFPRT): Finding the k-th Smallest in Worst-Case Linear Time
How the PICK algorithm from the 1973 paper by Blum, Floyd, Pratt, Rivest, and Tarjan selects the k-th smallest value in worst-case linear time, and where the group size of five comes from.
When is a hash table not O(1)? Collisions, O(n²) inserts and hash flooding
dict and HashMap are O(1) in expectation. Why n keys with one hash value need at least n(n−1)/2 comparisons. Python hash randomization and PYTHONHASHSEED, Rust's SipHash, Java's Comparable fallback.
Topological Sort and Cycle Detection: Ordering by In-Degree and Finding What Got Stuck
Implement topological sort by counting in-degrees, see what is left over when the graph has a cycle, and learn how Python's graphlib TopologicalSorter and CycleError behave.
Why a Bloom filter is only ever sure about "no"
Why a Bloom filter answers only "definitely not" or "possibly", the conditions behind its no-false-negative guarantee, the false positive formula, and why deleting bits breaks it.
Why sort(() => Math.random() - 0.5) is not a fair shuffle, and what Fisher–Yates does instead
A random comparator doesn't shuffle evenly, and the ECMAScript spec says why. How Fisher–Yates makes every permutation equally likely, and the random-number pitfalls it still depends on.
When does quicksort hit O(n²)? How standard sorts avoid the worst case
Sorted input, median-of-3 killers and adversarial comparators can push quicksort to quadratic time. This article explains introsort’s depth limit and what C++, Rust, Go and Java actually guarantee.
Why Dijkstra's algorithm fails with negative edge weights
The greedy assumption that a negative edge breaks, a three-edge counterexample, and when Bellman–Ford or a DAG shortest-path algorithm fits instead.
A heap is not a sorted list: priority queue order and the 0-based index formulas
Why doesn't a printed heapq list or PriorityQueue look sorted? The heap invariant, 0-based parent/child formulas, costs versus a sorted list, and equal priorities.
Binary search insertion points: what bisect, lower_bound and binarySearch return
What Python bisect, C++ lower_bound and Java Arrays.binarySearch return for missing and duplicate keys, and what each assumes about its input, per the official docs and the C++ standard.
Why appending to a dynamic array is O(1): capacity, growth and amortized time
Append sometimes copies the whole array, yet it counts as O(1). Capacity, amortized cost, what the Java, C++, Rust and Go docs promise, and reserving space.
What is a stable sort? Keeping ties in their original order
What stable sorting means, why it matters when you sort by more than one key, and what the standard sorts in Python, JavaScript, Java and C++ actually guarantee.
No posts match. Try another word.