Design an O(1) recency-evicting cache
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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.
Quick Answer: 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.
Simulate get/put for a fixed-capacity LRU cache and return get outputs.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: (2, [["put",1,1],["put",2,2],["get",1],["put",3,3],["get",2]])
Expected Output: [1, -1]
Explanation: Least-recently accessed item is evicted.
Input: (1, [["put","x",5],["put","y",6],["get","x"],["get","y"]])
Expected Output: [-1, 6]
Explanation: Capacity one keeps only the newest key.
Hints
- Clarify edge cases before coding.
- Keep the return value deterministic.