Design data structure similar to LRU cache
Company: Google
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
You are asked to design and implement a data structure that behaves similarly to an LRU (Least Recently Used) cache, but with a small variation:
- The data structure stores key–value pairs.
- It has a fixed capacity `capacity`.
- When inserting a new key and the cache is full, it should evict an existing key according to a modified eviction rule (a variant of LRU). For example, assume the rule is:
- Normally evict the least recently used key, **except** that keys explicitly "pinned" by the user should not be evicted until they are unpinned.
Your data structure must support the following operations in average O(1) time:
- `get(key) -> value or -1`
Return the value associated with `key` if it exists; otherwise return `-1`. Accessing a key counts as using it recently.
- `put(key, value)`
Insert or update the value of `key`. If inserting and the number of stored keys exceeds `capacity`, evict one key according to the modified eviction rule described above.
- `pin(key)`
Mark an existing key as pinned so that it cannot be evicted while pinned.
- `unpin(key)`
Remove the pinned status from a key so that it can again be evicted according to the LRU policy.
Assume:
- `1 <= capacity <= 10^5`
- Keys and values are integers.
- The total number of operations is up to `10^5`.
Describe the data structure you would use and implement the four operations with the required time complexity.
Quick Answer: This question evaluates understanding of data structures and algorithmic design for cache eviction policies, specifically the ability to implement an LRU-like cache with support for pinned entries while preserving average O(1) operations for get, put, pin, and unpin.
Design a cache that behaves like an LRU cache with a pin/unpin feature. The cache stores integer key-value pairs and has a fixed capacity.
To make the behavior precise, use these rules:
- Only unpinned keys participate in the LRU eviction order.
- `get(key)` returns the value for `key`, or `-1` if it does not exist. If the key exists and is unpinned, it becomes the most recently used unpinned key.
- `put(key, value)` inserts or updates a key.
- If the key already exists, update its value. If it is unpinned, it becomes the most recently used unpinned key.
- If the key is new and the cache is full, evict the least recently used unpinned key.
- If the cache is full and every stored key is pinned, ignore the insertion.
- `pin(key)` marks an existing key as pinned and removes it from the eviction order.
- `unpin(key)` removes the pinned status from an existing key and makes it the most recently used unpinned key.
- Calling `pin` or `unpin` on a missing key does nothing.
You are given `capacity` and a list of operations. Return the results of all `get` operations in order.
Constraints
- 1 <= capacity <= 10^5
- 1 <= len(operations) <= 10^5
- Keys and values are integers
- Each operation should run in O(1) average time
Examples
Input: (2, [('put', 1, 10), ('put', 2, 20), ('get', 1), ('put', 3, 30), ('get', 2), ('get', 1), ('get', 3)])
Expected Output: [10, -1, 10, 30]
Explanation: After `get(1)`, key 1 becomes most recent, so inserting key 3 evicts key 2. The outputs come from the four `get` calls.
Input: (2, [('put', 1, 1), ('put', 2, 2), ('pin', 1), ('put', 3, 3), ('get', 1), ('get', 2), ('get', 3)])
Expected Output: [1, -1, 3]
Explanation: Key 1 is pinned, so when key 3 is inserted, key 2 is the least recently used unpinned key and gets evicted.
Hints
- A hash map gives O(1) access to a key, but you also need a way to update recency in O(1).
- Keep only unpinned keys in the LRU order. When a key is pinned, remove it from that order; when it is unpinned, append it as most recent.