Debug round-robin, DashMap, and simple cache
Company: DoorDash
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
Quick Answer: This question evaluates skills in concurrent programming and stateful selection logic (round-robin load balancing), data structure invariants and debugging (custom hash map hashing vs equality, collision resolution, resizing and iterator correctness), simple in-memory caching strategies with TTL or size-based eviction, and unit test design.
Part 1: Round-Robin Available Node Selector
Constraints
- 0 <= len(nodes) <= 200000
- 0 <= len(operations) <= 200000
- Each node_id is unique
- Each status is either 0 or 1
Examples
Input: ([('A', 0), ('B', 1)], [('pick',), ('pick',), ('pick',)])
Expected Output: ['B', 'B', 'B']
Explanation: Only B is available, so every pick returns B.
Input: ([('A', 1), ('B', 1), ('C', 1)], [('pick',), ('pick',), ('set', 'B', 0), ('pick',), ('pick',), ('set', 'A', 0), ('set', 'C', 0), ('pick',)])
Expected Output: ['A', 'B', 'C', 'A', -1]
Explanation: The pointer keeps moving forward across picks. After all nodes become unavailable, pick returns -1.
Input: ([], [('pick',), ('pick',)])
Expected Output: [-1, -1]
Explanation: With no nodes at all, every pick fails.
Input: ([('A', 1), ('B', 0), ('C', 1)], [('pick',), ('pick',), ('pick',)])
Expected Output: ['A', 'C', 'A']
Explanation: The selector wraps around and keeps skipping the unavailable node B.
Solution
def solution(nodes, operations):
n = len(nodes)
if n == 0:
return [-1 for op in operations if op and op[0] == 'pick']
ids = []
id_to_index = {}
status = [0] * n
for i, (node_id, state) in enumerate(nodes):
ids.append(node_id)
id_to_index[node_id] = i
status[i] = 1 if state == 1 else 0
size = 1
while size < n:
size *= 2
tree = [0] * (2 * size)
for i, val in enumerate(status):
tree[size + i] = val
for i in range(size - 1, 0, -1):
tree[i] = tree[2 * i] + tree[2 * i + 1]
def update(idx, val):
pos = size + idx
tree[pos] = val
pos //= 2
while pos:
tree[pos] = tree[2 * pos] + tree[2 * pos + 1]
pos //= 2
def range_sum(left, right):
if left > right:
return 0
left += size
right += size
total = 0
while left <= right:
if left % 2 == 1:
total += tree[left]
left += 1
if right % 2 == 0:
total += tree[right]
right -= 1
left //= 2
right //= 2
return total
def find_first(left, right):
if left > right:
return -1
def dfs(node, node_left, node_right):
if node_right < left or node_left > right or tree[node] == 0:
return -1
if node_left == node_right:
return node_left
mid = (node_left + node_right) // 2
res = dfs(node * 2, node_left, mid)
if res != -1:
return res
return dfs(node * 2 + 1, mid + 1, node_right)
res = dfs(1, 0, size - 1)
return res if 0 <= res < n else -1
pointer = 0
answer = []
for op in operations:
if not op:
continue
kind = op[0]
if kind == 'set':
node_id, new_state = op[1], op[2]
idx = id_to_index[node_id]
new_val = 1 if new_state == 1 else 0
if status[idx] != new_val:
status[idx] = new_val
update(idx, new_val)
elif kind == 'pick':
if tree[1] == 0:
answer.append(-1)
continue
if range_sum(pointer, n - 1) > 0:
idx = find_first(pointer, n - 1)
else:
idx = find_first(0, pointer - 1)
answer.append(ids[idx])
pointer = (idx + 1) % n
return answerTime complexity: O((n + q) log n), where n is the number of nodes and q is the number of operations. Space complexity: O(n).
Hints
- Keep one pointer that survives across all pick operations instead of restarting at index 0 each time.
- A segment tree or other indexed structure can help find the next available node quickly after updates.
Part 2: Implement and Repair DashMap
Constraints
- 0 <= initial_capacity <= 10000
- 0 <= len(operations) <= 20000
- Keys are strings of length 0 to 100
- Values are integers
Examples
Input: (2, [('put', 'ab', 1), ('put', 'ba', 2), ('get', 'ab'), ('get', 'ba'), ('items',)])
Expected Output: [1, 2, [('ab', 1), ('ba', 2)]]
Explanation: 'ab' and 'ba' have the same hash under the given function, so this checks collision handling.
Input: (4, [('put', 'aa', 1), ('put', 'aa', 5), ('get', 'aa'), ('items',)])
Expected Output: [5, [('aa', 5)]]
Explanation: Inserting the same key again should update the existing entry, not create a duplicate.
Input: (2, [('put', 'a', 1), ('put', 'b', 2), ('put', 'c', 3), ('put', 'd', 4), ('get', 'c'), ('remove', 'b'), ('get', 'b'), ('items',)])
Expected Output: [3, True, None, [('a', 1), ('c', 3), ('d', 4)]]
Explanation: This forces resizing and then verifies that all remaining entries are still retrievable and iterable.
Input: (4, [('get', 'x'), ('remove', 'x'), ('items',)])
Expected Output: [None, False, []]
Explanation: Edge case with an empty map.
Solution
def solution(initial_capacity, operations):
capacity = max(2, initial_capacity)
buckets = [[] for _ in range(capacity)]
size = 0
def hash_key(key, mod):
total = 0
for ch in key:
total += ord(ch)
return total % mod
def find_in_bucket(bucket, key):
for i, (k, v) in enumerate(bucket):
if k == key:
return i
return -1
def rehash(new_capacity):
nonlocal buckets, capacity
old_buckets = buckets
capacity = max(2, new_capacity)
buckets = [[] for _ in range(capacity)]
for bucket in old_buckets:
for k, v in bucket:
idx = hash_key(k, capacity)
buckets[idx].append((k, v))
answer = []
for op in operations:
if not op:
continue
kind = op[0]
if kind == 'put':
key, value = op[1], op[2]
idx = hash_key(key, capacity)
bucket = buckets[idx]
pos = find_in_bucket(bucket, key)
if pos != -1:
bucket[pos] = (key, value)
else:
bucket.append((key, value))
size += 1
if size > capacity * 0.75:
rehash(capacity * 2)
elif kind == 'get':
key = op[1]
idx = hash_key(key, capacity)
bucket = buckets[idx]
pos = find_in_bucket(bucket, key)
answer.append(bucket[pos][1] if pos != -1 else None)
elif kind == 'remove':
key = op[1]
idx = hash_key(key, capacity)
bucket = buckets[idx]
pos = find_in_bucket(bucket, key)
if pos == -1:
answer.append(False)
else:
bucket.pop(pos)
size -= 1
answer.append(True)
elif kind == 'items':
items = []
for bucket in buckets:
for k, v in bucket:
items.append((k, v))
items.sort(key=lambda pair: pair[0])
answer.append(items)
return answerTime complexity: Average O(1) for each put/get/remove operation, and O(n log n) for each items call because the output is sorted. Space complexity: O(n).
Hints
- A matching hash is not enough; inside a bucket you still need to compare actual keys for equality.
- When capacity changes, bucket indices change too, so every existing entry must be inserted again using the new modulus.
Part 3: Tiny In-Memory Cache with TTL and LRU Eviction
Constraints
- 0 <= capacity <= 100000
- 0 <= len(operations) <= 100000
- Operation timestamps are non-decreasing
- ttl is either None or an integer >= 1
Examples
Input: (2, [('set', 'a', 1, None, 0), ('set', 'b', 2, None, 1), ('get', 'a', 2), ('set', 'c', 3, None, 3), ('get', 'b', 4), ('keys', 4)])
Expected Output: [1, None, ['a', 'c']]
Explanation: After 'get a', A becomes most recently used, so inserting C evicts B.
Input: (2, [('set', 'x', 10, 2, 0), ('get', 'x', 1), ('get', 'x', 2), ('keys', 2)])
Expected Output: [10, None, []]
Explanation: The entry for X expires exactly at time 2.
Input: (2, [('set', 'a', 1, 5, 0), ('set', 'b', 2, None, 1), ('set', 'a', 7, None, 2), ('get', 'a', 6), ('keys', 6)])
Expected Output: [7, ['b', 'a']]
Explanation: Overwriting A removes the old TTL logically and keeps A as the most recently used key.
Input: (0, [('set', 'a', 1, None, 0), ('get', 'a', 1), ('keys', 1)])
Expected Output: [None, []]
Explanation: With zero capacity, nothing can be stored.
Solution
def solution(capacity, operations):
from collections import OrderedDict
import heapq
data = {}
order = OrderedDict()
expiry_heap = []
version = 0
answer = []
def cleanup(now):
while expiry_heap and expiry_heap[0][0] <= now:
exp_time, exp_version, key = heapq.heappop(expiry_heap)
current = data.get(key)
if current is None:
continue
value, current_exp, current_version = current
if current_exp == exp_time and current_version == exp_version and current_exp is not None and current_exp <= now:
del data[key]
if key in order:
del order[key]
for op in operations:
if not op:
continue
kind = op[0]
if kind == 'set':
key, value, ttl, now = op[1], op[2], op[3], op[4]
cleanup(now)
if capacity <= 0:
if key in data:
del data[key]
if key in order:
del order[key]
continue
version += 1
exp_time = None if ttl is None else now + ttl
data[key] = (value, exp_time, version)
order[key] = None
order.move_to_end(key)
if exp_time is not None:
heapq.heappush(expiry_heap, (exp_time, version, key))
if len(data) > capacity:
old_key, _ = order.popitem(last=False)
del data[old_key]
elif kind == 'get':
key, now = op[1], op[2]
cleanup(now)
if key not in data:
answer.append(None)
else:
value, exp_time, current_version = data[key]
order.move_to_end(key)
answer.append(value)
elif kind == 'keys':
now = op[1]
cleanup(now)
answer.append(list(order.keys()))
return answerTime complexity: Amortized O(log n) per operation, where n is the number of live keys. Space complexity: O(n + t), where t is the number of pending TTL heap entries.
Hints
- Use a hash map for fast lookup and another structure to track recency order for LRU eviction.
- For TTL, a min-heap of expiration times works well if you attach a version number so stale heap entries can be ignored.