Coding questions · Meta
Design an O(1) recency-evicting cache
This question evaluates the ability to design an in-memory fixed-capacity cache that maintains access recency while delivering average O(1) get and put operations, focusing on data structure design, correctness of update semantics, and algorithmic time and space complexity analysis.
Design and implement a fixed-capacity in-memory cache that supports get(key) and put(key, value) in average O(1) time. When capacity is exceeded, evict the least-recently accessed item. Describe the data structures you will use, how you update access recency on reads and writes, and analyze time and space complexity. Provide code for the core operations.
O(1) Recency Evicting Cache
Simulate get/put for a fixed-capacity LRU cache and return get outputs.
Examples
Example 1
Input: (2, [["put",1,1],["put",2,2],["get",1],["put",3,3],["get",2]])
Output: [1, -1]
Explanation: Least-recently accessed item is evicted.
Example 2
Input: (1, [["put","x",5],["put","y",6],["get","x"],["get","y"]])
Output: [-1, 6]
Explanation: Capacity one keeps only the newest key.
Hints
- Clarify edge cases before coding.
- Keep the return value deterministic.