Design a single-machine LRU cache
Company: DoorDash
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
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.
Quick Answer: 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.