Longest Common Subsequence: The Classic DP Problem, Explained
Learn the longest common subsequence algorithm from scratch: recurrence, DP table walkthrough, space optimization, and 14 language implementations.
Page 15 of 61 · Ideas for curious minds in tech.
Back to the archiveLearn the longest common subsequence algorithm from scratch: recurrence, DP table walkthrough, space optimization, and 14 language implementations.

Learn the edit distance algorithm (Levenshtein distance): the DP recurrence, table tracing, O(m·n) time, O(n) space trick, and what LeetCode 72 actually tests.

Learn how the rolling hash algorithm achieves O(n+m) string search by updating window hashes in O(1). Covers formula, modular arithmetic, collisions, and LeetCode patterns.

Square root decomposition solves range queries in O(√n) with O(1) point updates. Learn the block structure, optimal block size proof, and a 25-line implementation.

Binary lifting precomputes 2^j-th ancestors for O(log n) k-th ancestor and LCA queries. Learn the table, recurrence, and LeetCode 1483.

Learn the lowest common ancestor of a binary tree: the 7-line recursive solution, BST shortcut, complexity table, and 14 language implementations.

A cache eviction policy decides what leaves when your cache is full. Learn LRU, LFU, FIFO, and the O(1) LRU implementation every interview expects.
A skip list achieves O(log n) search and insert without tree rotations, using coin flips. Includes 14 language implementations and interview patterns.
An ordered map keeps keys sorted for O(log n) range queries and floor/ceiling lookups. Here's how it works and where it appears in coding interviews.

Python mutable vs immutable: why string concat in a loop is O(n²), the backtracking path bug explained, and how hashability connects to immutability.

Pass by value vs pass by reference explained: Python, JavaScript, Java, C++, Go, and Rust. The backtracking copy bug and aliasing traps, demystified.

A sentinel node is a dummy node that eliminates linked list edge cases. Learn how it works with remove, merge, and LRU cache problems in coding interviews.

What is a loop invariant? Learn the CLRS three-condition proof, why binary search off-by-one bugs are invariant failures, and how to design correct loops.

Logarithmic time complexity (O(log n)) means doubling the input adds just one step. Here's why it works and how to recognize it in a coding interview.

Learn what exponential time complexity means, why O(2^n) explodes past n=40, and how to recognize it and escape with dynamic programming.
Polynomial time complexity decides what's solvable in practice. Learn the definition, examples, and how to move from exponential to polynomial in interviews.

The P vs NP problem asks if every verifiable problem is also quickly solvable. Here's what it means for algorithms, cryptography, and coding interviews.

What is NP-hard? Explains NP-hardness vs NP-complete, P vs NP, why these problems are hard, and how to recognize and tackle them in coding interviews.

NP-completeness explained for engineers: what P vs NP means, why some problems have no fast solution, and how to spot them in coding interviews.

The bucket sort algorithm sorts in O(n) average time by skipping comparisons entirely. Learn how it works, when it breaks, and how to spot it in interviews.

Radix sort sorts integers in O(n) by reading digits, not comparing. What is radix sort, how it works, time complexity, and when to use it in interviews.

Counting sort runs in O(n+k) without comparing elements. See how the counting sort algorithm works, when interviews expect it, and code in 14 languages.

A comparison sort decides order purely by comparing elements. No such algorithm can beat O(n log n). Here's the proof and what it means in interviews.

An in-place algorithm modifies input with only O(1) extra space. Learn the real definition, where quicksort fits, and four patterns coding interviews test.