## Debug a Random Dasher Registry A registry supports adding dashers and randomly selecting and removing one. It uses a dense array of dasher IDs plus a map from ID to array index so addition, lookup, and swap-delete can be constant time. The implementation has failures around an empty registry, removing the only element, removing the last element, moving the last element into a removed slot without updating its map entry, and overly broad exception handling. Debug the data structure, then discuss concurrent access and slow upstream or downstream services. ### Part 1 — State the Representation Invariant Define the array and map relationship before and after every operation, including the empty state. #### What This Part Should Cover - Exactly one array position and one matching map entry per registered ID. - `indexById[array[i]] == i` for every valid position. - A defined result for add-duplicate and pick-from-empty. - Random-index generation restricted to the current array length. ```hint Write the invariant before the branch cases The one-element and last-element cases become easier to reason about when every successful mutation must restore the same array-map equation. ``` ### Part 2 — Repair Random Selection and Swap-Delete Give safe pseudocode for choosing a random index, returning its ID, removing it, moving the old last ID when necessary, and updating the map. #### What This Part Should Cover - Empty check before random selection. - Capturing removed and last IDs before mutation. - Updating the moved ID's index only when a move occurs. - Removing the chosen ID's map entry exactly once. ```hint Distinguish remove-last from move-last When the chosen slot already is the last slot, there is no surviving element whose index needs to be rewritten. ``` ### Part 3 — Handle Errors and Test Boundaries Replace catch-all exception behavior with explicit expected errors and tests. Include empty, one item, last item, middle item, duplicates, repeated draining, and deterministic random choices. #### What This Part Should Cover - Typed or documented outcomes for empty and duplicate operations. - No partial mutation after an expected failure. - An injectable random-number source for deterministic tests. - Invariant checks after every step of randomized operation sequences. ```hint Do not use exceptions as control flow for corruption An index error caused by a broken invariant should remain visible during testing rather than being converted into an ordinary empty result. ``` ### Part 4 — Add Concurrency and Dependency Resilience Explain how multiple threads safely add or pick dashers and what happens when registering or dispatching requires a slow service call. #### What This Part Should Cover - One atomic critical section for the coupled array and map mutation. - No network call while holding a long-lived registry lock. - Reservation, rollback, or durable state for an ambiguous dispatch outcome. - Timeouts, bounded retries, idempotency, backpressure, and observability. ```hint Keep remote latency outside the lock Reserve local state briefly, perform the slow call without blocking unrelated registry operations, then finalize through a versioned transition. ``` ### What a Strong Answer Covers - Derives the fix from the array-map invariant. - Handles empty, singleton, and last-index cases explicitly. - Uses narrow error handling and deterministic fault-revealing tests. - Preserves atomic local state while treating remote outcomes as potentially uncertain. ### Follow-up Questions 1. How would you support removing a known dasher as well as a random one? 2. Is one mutex sufficient, and when would it become a bottleneck? 3. What happens if dispatch succeeds remotely but the local response times out? 4. How would you make selection weighted while retaining efficient updates?