Implement a recent-use eviction cache
Company: Snapchat
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Design a fixed-capacity key-value cache that removes the least recently accessed item when it becomes full.
Implement a class with the following operations:
- `Cache(int capacity)`: Initialize the cache with a positive capacity.
- `int get(int key)`: Return the value associated with `key` if it exists; otherwise return `-1`. A successful `get` marks the key as the most recently used item.
- `void put(int key, int value)`: Insert or update the value for `key`. If the cache is already at capacity and the key does not already exist, evict the least recently used key before inserting. Updating an existing key also marks it as the most recently used item.
Requirements:
- Both `get` and `put` should run in average `O(1)` time.
- Keys and values are integers.
Example behavior:
1. `Cache(2)`
2. `put(1, 10)`
3. `put(2, 20)`
4. `get(1)` returns `10` and makes key `1` most recently used.
5. `put(3, 30)` evicts key `2` because it is the least recently used.
6. `get(2)` returns `-1`.
Quick Answer: This question evaluates a candidate's ability to design and implement a fixed-capacity key-value cache with a recent-use eviction policy, emphasizing data structure design, state management, and meeting average O(1) time constraints for get and put operations.
Simulate get and put for a fixed-capacity least-recently-used cache.
Examples
Input: (2, [('put', 1, 10), ('put', 2, 20), ('get', 1), ('put', 3, 30), ('get', 2), ('get', 3)])
Expected Output: [10, -1, 30]
Explanation: Prompt behavior.
Input: (1, [('put', 1, 1), ('put', 1, 2), ('get', 1)])
Expected Output: [2]
Explanation: Update key.
Input: (0, [('put', 1, 1), ('get', 1)])
Expected Output: [-1]
Explanation: Zero capacity edge.