Coding questions · DoorDash
Design a single-machine LRU cache
This question evaluates a candidate's ability to design an efficient in-memory LRU cache and apply concurrency control, covering eviction semantics, capacity management, key updates, and synchronization for thread safety.
Design an in-memory LRU cache for a single machine using a hash map and a doubly linked list to support O(1) get and put. Explain how you handle capacity, eviction, and key updates. Then make your design thread-safe: discuss lock granularity (global lock vs. per-bucket/segmented locks), readers–writer locks, lock-free alternatives, and how you would prevent race conditions and ensure memory safety. Analyze time and space complexity and outline major pitfalls.
Single-Machine LRU Cache
Simulate get and put for an LRU cache with fixed capacity.
Examples
Example 1
Input: (2, [('put', 1, 1), ('put', 2, 2), ('get', 1), ('put', 3, 3), ('get', 2), ('get', 3)])
Output: [1, -1, 3]
Explanation: Evicts least recently used.
Example 2
Input: (0, [('put', 1, 1), ('get', 1)])
Output: [-1]
Explanation: Zero capacity.