Debug round-robin, DashMap, and simple cache

Q: Debug round-robin, DashMap, and simple cache

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.

Q: How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

Q: What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at DoorDash.

Q: What role is this question designed for?

This question is commonly asked for Software Engineer candidates at DoorDash during technical interviews.

Question

You are given a service that routes requests to a list of nodes, each marked as either available or unavailable. The pickNode() function is intended to perform round-robin selection while skipping unavailable nodes, but a failing unit test shows it occasionally returns an unavailable node. Debug and fix the implementation:
(
1) maintain a global (thread-safe) index so selection does not reset per call;
(
2) ensure status checks are robust (e.g., use an enum or constant, not fragile string literals);
(
3) define behavior when all nodes are unavailable; and
(
4) update/add a unit test where one node is unavailable and one is available so the selector repeatedly returns the available node. As a separate debugging task, you are given a buggy custom hash map named DashMap. Diagnose and fix issues around key hashing vs equality, collision handling, resizing/rehashing, and iterator behavior. Finally, implement a very simple in-memory cache backed by a map with get/set and optional TTL or size-based eviction, and write basic tests for it.

PracHub · Accepted Answer

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 answer 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

Quick Overview

Solution

Hints

Part 2: Implement and Repair DashMap

Constraints

Examples

Solution

Hints

Part 3: Tiny In-Memory Cache with TTL and LRU Eviction

Constraints

Examples

Solution

Hints

Quick Overview