Design data structure similar to LRU cache
Company: Google
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
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.
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.
Input: (3, [('put', 1, 1), ('put', 2, 2), ('put', 3, 3), ('pin', 2), ('get', 1), ('unpin', 2), ('put', 4, 4), ('get', 1), ('get', 2), ('get', 3), ('get', 4)])
Expected Output: [1, 1, 2, -1, 4]
Explanation: After `unpin(2)`, key 2 re-enters as most recent among unpinned keys. Inserting key 4 then evicts key 3.
Input: (1, [('get', 5), ('put', 5, 50), ('pin', 5), ('put', 6, 60), ('get', 5), ('unpin', 5), ('put', 6, 60), ('get', 5), ('get', 6)])
Expected Output: [-1, 50, -1, 60]
Explanation: With capacity 1, inserting key 6 while key 5 is pinned does nothing. After unpinning key 5, inserting key 6 evicts key 5.
Input: (2, [('put', -1, 5), ('pin', 99), ('put', -1, 7), ('get', -1), ('pin', -1), ('put', 2, 2), ('unpin', -1), ('put', 3, 3), ('get', -1), ('get', 2), ('get', 3)])
Expected Output: [7, 7, -1, 3]
Explanation: Updating an existing key changes its value. Pinning a missing key does nothing. Later, key 2 is evicted when key 3 is inserted.
Solution
def solution(capacity, operations):
class Node:
__slots__ = ('key', 'value', 'pinned', 'prev', 'next')
def __init__(self, key, value):
self.key = key
self.value = value
self.pinned = False
self.prev = None
self.next = None
head = Node(0, 0) # dummy head: least recent unpinned is head.next
tail = Node(0, 0) # dummy tail: most recent unpinned is tail.prev
head.next = tail
tail.prev = head
def remove(node):
node.prev.next = node.next
node.next.prev = node.prev
node.prev = None
node.next = None
def add_to_tail(node):
prev_node = tail.prev
prev_node.next = node
node.prev = prev_node
node.next = tail
tail.prev = node
def move_to_tail(node):
remove(node)
add_to_tail(node)
def pop_lru():
if head.next is tail:
return None
node = head.next
remove(node)
return node
cache = {}
result = []
for op in operations:
action = op[0]
if action == 'get':
key = op[1]
node = cache.get(key)
if node is None:
result.append(-1)
else:
if not node.pinned:
move_to_tail(node)
result.append(node.value)
elif action == 'put':
key, value = op[1], op[2]
node = cache.get(key)
if node is not None:
node.value = value
if not node.pinned:
move_to_tail(node)
else:
if len(cache) == capacity:
lru = pop_lru()
if lru is None:
continue
del cache[lru.key]
new_node = Node(key, value)
cache[key] = new_node
add_to_tail(new_node)
elif action == 'pin':
key = op[1]
node = cache.get(key)
if node is not None and not node.pinned:
remove(node)
node.pinned = True
elif action == 'unpin':
key = op[1]
node = cache.get(key)
if node is not None and node.pinned:
node.pinned = False
add_to_tail(node)
return resultTime complexity: O(m), where m is the number of operations; each individual operation is O(1). Space complexity: O(capacity).
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.