Implement a Capacity-Bounded Cache
Company: Shopify
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement an in-memory key-value cache with a fixed capacity. The cache must support the following operations in constant time on average:
- `get(key)`: Return the value associated with `key` if it exists; otherwise return `-1`.
- `put(key, value)`: Insert or update the value for `key`. If inserting a new key would exceed the cache capacity, evict the item that has been unused for the longest time.
Accessing or updating a key makes it the most recently used item.
You should be prepared to explain the underlying data structures, especially how a hash map and a doubly linked list can be combined to support both fast lookup and fast eviction.
Quick Answer: This question evaluates a candidate's ability to design and implement an efficient capacity-bounded in-memory key-value cache, assessing understanding of performance constraints such as average-case constant-time get/put operations and eviction behavior.
Simulate get and put for a fixed-capacity cache that evicts the least recently used key.
Constraints
- get returns -1 when missing
Examples
Input: (2, [('put', 1, 1), ('put', 2, 2), ('get', 1), ('put', 3, 3), ('get', 2), ('get', 3)])
Expected Output: [1, -1, 3]
Explanation: Standard eviction.
Input: (0, [('put', 1, 1), ('get', 1)])
Expected Output: [-1]
Explanation: Zero capacity.
Input: (1, [('put', 1, 1), ('put', 1, 2), ('get', 1)])
Expected Output: [2]
Explanation: Update existing key.
Hints
- Use a hash map plus recency order.