Katkat
Back

Debug a Random Dasher Registry

DoorDashSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

Debug a random dasher registry backed by a dense array and an ID-to-index map. Repair empty and swap-delete edge cases, preserve representation invariants, narrow error handling, and extend the design for concurrency and slow dependencies.

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.

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.

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.

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.

Hints

Hint 1

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.

Hint 2

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.

Hint 3

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.

Hint 4

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.

Follow-up questions

  • How would you support removing a known dasher as well as a random one?
  • Is one mutex sufficient, and when would it become a bottleneck?
  • What happens if dispatch succeeds remotely but the local response times out?
  • How would you make selection weighted while retaining efficient updates?