Practice question · Multiple choice
A cache needs fast lookup by key and eviction of the least recently used entry. No single structure does both. What is the standard solution?
Hints
- Ask which structure gives O(1) lookup, and which gives O(1) removal from the middle.
- What would each map entry need to hold for the list operation to avoid a search?
Show the answer
A. Compose two, a hash map for lookup and a linked list for recency
Why
Neither structure alone suffices, so you keep both over the same entries and cross-link them: the map finds the node, the list moves it to the front. It is the composed-structure pattern with a real consistency obligation, every operation must update both, and the LRU cache is the canonical interview problem for exactly that reason.
Practise Choosing a Data Structure by Workload
The app has 5 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.
More questions on Choosing a Data Structure by Workload
- The lesson's rule is to choose a structure by which operations dominate the workload. Why is 'which structure…
- A hash table serves a workload of 90% lookups by key and 10% requests for the smallest key well, because the…
- Sort each requirement by whether a hash table alone is enough for it.
- Order the steps of choosing a data structure by workload, as the lesson describes it.
- Select every statement the lesson supports about choosing structures.