Card 06/ 07
Practice: Naming the Pattern for Five Problems
A bookshelf, a playlist, a cinema's seats, a recipe book and a train: name each one's pattern and the property that points to it.
Naming the pattern for a problem means naming the property that points to it and saying why the nearest alternative is worse. For each of the five problems below, write all three before opening the answer.
- Books stand on a shelf in a row. For each book, find the nearest book to its right that is taller.
- A radio station's plays arrive one at a time through the day. Keep the five longest songs played so far.
- A cinema's seating plan marks each seat empty or taken. Count the groups of empty seats that touch at the front, back or side.
- Some recipes need other recipes made first. Find an order to make them all, or show that none exists.
- Each carriage of a train is coupled to the next. Decide whether the train loops back on itself, using no extra memory.
Show the patterns
Each answer names the property first, because the property is what makes the pattern right.
| Problem | Property | Pattern | Why not the nearest alternative |
|---|---|---|---|
| Nearest taller book | For each item, the nearest larger one on one side | Monotonic stack, O(n) | Scanning right from each book is O(n²) on a shelf whose books get shorter |
| Five longest songs | The k largest from anywhere, arriving one at a time | A min-heap of five, O(n log 5) | Sorting the day needs every play first, and costs O(n log n) |
| Groups of empty seats | A map of cells, with movement between cells that touch | Grid traversal by flood fill, O(rows · columns) | Union-find also works, but builds links the grid already gives |
| Recipes before recipes | Links in pairs and an order that respects prerequisites | Graph modelling with a topological sort | A breadth-first search from one recipe reaches the others but does not order them |
| A train that loops | A linked list, a question about a loop, constant memory | Fast and slow pointers | A set of carriages seen also finds the loop, but costs O(n) memory |
The recipe book is the course plan of the Graph Modelling topic in another kitchen: a recipe is a course, and needing another made first is a prerequisite. The train rules out the hash set only because the problem forbids extra memory; without that condition, the set is a correct and simpler answer.
← → move through sections and cards