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.