Approach verbose data-structure design
Company: Hudson River Trading
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
Quick Answer: This question evaluates a candidate's ability to design and implement complex data structures, testing algorithmic reasoning, time/space complexity analysis, state modeling, and organization of code and tests.
Constraints
- 0 <= capacity <= 100000
- 0 <= len(operations) <= 200000
- Each operation is either [1, key, value] or [2, key]
- -1000000000 <= key, value <= 1000000000
- The intended solution should run each operation in O(1) average time
Examples
Input: (2, [[1, 1, 1], [1, 2, 2], [2, 1], [1, 3, 3], [2, 2], [1, 4, 4], [2, 1], [2, 3], [2, 4]])
Expected Output: [1, -1, -1, 3, 4]
Explanation: GET 1 returns 1 and makes key 1 most recent. Adding key 3 evicts key 2. Adding key 4 later evicts key 1.
Input: (2, [[1, 1, 1], [1, 2, 2], [1, 1, 10], [1, 3, 3], [2, 1], [2, 2], [2, 3]])
Expected Output: [10, -1, 3]
Explanation: Updating key 1 changes its value to 10 and makes it most recent, so key 2 is evicted when key 3 is inserted.
Input: (0, [[1, 1, 1], [2, 1], [1, 2, -5], [2, 2]])
Expected Output: [-1, -1]
Explanation: A cache with capacity 0 cannot store any keys, so all GET operations miss.
Input: (1, [[2, 5], [1, 5, -10], [2, 5], [1, 6, 0], [2, 5], [2, 6]])
Expected Output: [-1, -10, -1, 0]
Explanation: The first GET misses. Key 5 is stored with a negative value. Inserting key 6 into a capacity-1 cache evicts key 5.
Input: (3, [])
Expected Output: []
Explanation: There are no operations, so there are no GET results.
Solution
def solution(capacity, operations):
class Node:
__slots__ = ('key', 'value', 'prev', 'next')
def __init__(self, key=0, value=0):
self.key = key
self.value = value
self.prev = None
self.next = None
cache = {}
# Sentinel nodes: left.next is least recently used, right.prev is most recently used.
left = Node()
right = Node()
left.next = right
right.prev = left
def remove(node):
prev_node = node.prev
next_node = node.next
prev_node.next = next_node
next_node.prev = prev_node
def insert_most_recent(node):
prev_node = right.prev
prev_node.next = node
node.prev = prev_node
node.next = right
right.prev = node
results = []
for op in operations:
if op[0] == 2:
key = op[1]
node = cache.get(key)
if node is None:
results.append(-1)
else:
remove(node)
insert_most_recent(node)
results.append(node.value)
else:
if capacity == 0:
continue
key = op[1]
value = op[2]
node = cache.get(key)
if node is not None:
node.value = value
remove(node)
insert_most_recent(node)
else:
node = Node(key, value)
cache[key] = node
insert_most_recent(node)
if len(cache) > capacity:
least_recent = left.next
remove(least_recent)
del cache[least_recent.key]
return resultsTime complexity: O(m), where m is the number of operations. Each GET and PUT is O(1) average time.. Space complexity: O(capacity), excluding the output list..
Hints
- Use a hash map to find a key's stored node in O(1) time.
- Use a doubly linked list to maintain least-recently-used to most-recently-used order, and move nodes to the end when they are accessed.