Matrices, string matching and design

A cache that got slower as it got fuller

Every payment looks up the merchant's profile: fees, limits, settlement account. From the database that costs 20 ms, so the payments API keeps the 10,000 most recently used profiles in memory and throws out the least recently used one when it is full.

The first version kept the keys in a Python list, most recent first. A hit did keys.remove(k) and keys.insert(0, k). A miss on a full cache popped the last key. It passed every test.

In the load test, at 3,000 payments a second, p99 latency climbed from 4 ms to 90 ms as the cache filled. The profiler put almost all the time in remove and insert: each one walks the list, up to 10,000 entries. Work it out: 3,000 hits a second, each walking up to 10,000 keys, is about 30 million steps a second spent only on keeping the keys in order.

A dict finds a key in O(1), but it does not know which key is oldest. The list knows the order, but it cannot find a key without walking. Each structure is fast at exactly what the other is slow at.

Pause and predict Which combination makes get, move-to-front and evict-oldest all O(1)?

One invariant per tool

This unit has three parts: grids changed in place, text searched without reading a letter twice, and classes whose every operation is O(1). Each part rests on one invariant, and each problem applies that invariant.

In-place grids: read before you overwrite

"In place" means the answer is written over the input. The danger is always the same: a cell is overwritten while some later step still needs its old value.

Pause and predict Rotate a square grid 90 degrees clockwise, in place. Which two moves do it?

String matching: never move back in the text

The naive search tries each starting position in the text and compares up to m letters: O(nm). After a failed try it starts again one letter later and re-reads text it has already seen. But it already knows what those letters are, because they matched the start of the pattern.

KMP keeps j, the length of the part of the pattern that has matched so far, ending at the current text position. When the next letter does not match, it asks: what is the longest shorter prefix of the pattern that also ends here? That depends only on the pattern, so it is computed once, in the failure table: fail[k] is the longest proper prefix of P[0..k] that is also its suffix.

Pause and predict For P = abaab, what is the last entry of the failure table: the longest proper prefix of the whole pattern that is also its suffix?

In abaabaabab, KMP with P = abaab finds matches at 0 and 3. After the first match it keeps j = 2 instead of resetting to 0, and that is why it finds the second match, which overlaps the first.

Shortest Palindrome uses the table for a different purpose. A prefix of s is a palindrome exactly when it equals the suffix of reverse(s) of the same length. So the last entry of the failure table of s + "#" + reverse(s) is the length of the longest prefix of s that is a palindrome. For aabba it is 2 (aa), so the reverse of bba goes in front: abbaabba. Without the #, the border can run across the point where the two strings meet: on aabba it would be 6, longer than s itself.

A rolling hash is the other way to compare windows quickly. In Repeated DNA Sequences there are four letters, so a 10-letter window is exactly 20 bits, and shifting in a letter is h = ((h << 2) | code) & mask. That code has no collisions: 4¹⁰ = 2²⁰. A plain set of 10-letter substrings is also correct and costs 10 times more per step. In an interview, say so, then offer the rolling code.

Design: choose the structures from the operations

A design question lists operations and a required cost for each. No single structure gives them all, so you combine two, and each one does quickly what the other cannot. LRU Cache is the model, and it is the cache from the opening: a map finds a key in O(1) but does not know the order of use, and a list keeps the order but cannot find a key without walking.

Every operation keeps it true with a constant number of pointer writes. A hit moves the node to the front: unlink it, then insert it just after head. A new key gets a new node at the front. When the cache goes over capacity, tail.prev is the least recently used node: unlink it and delete its key from the map, which is why each node stores its key.

The list needs prev links, because a node can leave from the middle. It also needs sentinels: a dummy head and a dummy tail that are never removed. With them, every real node always has a node on each side, so unlink is two writes and push is four, with no null checks for an empty list or the first and last node.

The other classes follow the same method: list the operations, then find two structures that are each fast where the other is slow. Choose one to see it:

How to recognise it

There is one signal for each part: "in place" or "O(1) extra memory" on a grid; "find a substring" with a demand for linear time; and "design a class" with a required cost for each operation.

Pause and predict You must design a set with insert, remove and getRandom, each in O(1). Which pair of structures works?

Problems that only look like it

• When one lookup structure is enough, as for "seen before", counts or grouping, that is hashing. A design problem begins when a second requirement, such as an order, a random pick or an eviction, needs a second structure.
• When the task is rewiring a list for its own sake, such as reversing or reordering it, that is linked lists. In this unit the list is a tool inside a class.
• When you need the longest or shortest window that satisfies a condition, that is sliding window. KMP only finds exact copies of one fixed pattern.
• When you need the k best items of a stream, use heaps. Twitter's feed uses a heap as one part of a larger design.
• When a grid question is about regions, flooding or distances, use BFS and DFS. The grid tricks in this unit only rearrange cells.

Where it bites

Pause and predict Java: List<Integer> vals = new ArrayList<>(List.of(10, 20, 30)); vals.remove(1); What is left?

• Overwriting a marker before reading it. In Set Matrix Zeroes, zero the first row and column last.
• Falling back to 0 in KMP. Fall back through the failure table instead; searching aaaaab for aaab, a reset to 0 misses the match.
• No separator in Shortest Palindrome. Without the #, the border can run across the point where s and its reverse meet.
• No sentinels in LRU. Without them, every unlink needs separate checks for the first node, the last node and an empty list.
• A node without its key. The eviction then cannot find which map entry to delete.
• A modular rolling hash without a check. Two different windows can have the same hash, so confirm each match by comparing the strings.