Design & Data Structures

Design problems hand you an interface and a complexity target, usually O(1), and ask you to build the class behind it. A Premium question is one of Amazon's three most-asked coding questions. (LRU is short for least-recently-used: a fixed-size store that evicts whatever you touched longest ago.) Know it cold. Amazon rarely states it as the textbook puzzle, though. They wrap it in a product story: track a customer's recently viewed items, cap the history, keep lookups instant.

Every one of these is the same move. Compose two data structures so each operation lands on its required speed. Almost always the pairing is a hash map plus one more structure. A map gives instant lookup and little else. So you bolt on whatever covers the operation it cannot do: a linked list for recency, a heap for the largest few. The workflow is mechanical. List the operations. Mark the speed each one needs, then pick the partner structure that fills the gap.