Debug and refactor a legacy module
Company: DoorDash
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
Given a legacy module named DasherPicker and a failing test suite, systematically debug and refactor the code while following a provided review checklist. Identify and fix issues in naming conventions, exception handling, input validation, and code structure so that all tests pass. Then outline a plan to make the module safe for multi-threaded execution (e.g., immutability, confinement, synchronization, concurrent data structures) and describe how you would validate correctness under concurrency (tests, stress tools, and diagnostics).
Quick Answer: This question evaluates debugging, refactoring, naming and exception handling, input validation, code structure, and concurrency-safety design skills within a legacy codebase, requiring both hands-on code changes and higher-level reasoning about immutability, confinement, synchronization, and concurrent data structures.
Part 1: Refactor DasherPicker Selection Logic
Refactor the `DasherPicker` selection logic so it assigns each delivery order to the single best eligible dasher, using deterministic tie-breaking, strict input validation, and no mutation of the caller's data.
### Implement
```
def solution(dashers, orders):
...
```
Return a **list of integers** — one entry per order, in the same order the orders are given. Each entry is either the **id of the chosen dasher** or `-1` if no dasher could be assigned. When `orders` is empty, the natural result is an empty list `[]` (there are no orders to assign).
### Input format
- **`dashers`** — a list of dasher records. Each record is `[id, x, y, rating, capacity, active]` (a list or tuple), where:
- `id` is a positive, unique integer
- `x`, `y` are the dasher's coordinates
- `rating` is the dasher's rating
- `capacity` is how many more orders the dasher can take
- `active` is `1` if the dasher is active, `0` if inactive
- **`orders`** — a list of orders. Each order is `[x, y, min_rating]` (a list or tuple), where `x`, `y` are the order's location and `min_rating` is the minimum rating required.
### What to do
Process the orders **from left to right** (first to last). For each order, choose exactly one **eligible** dasher.
A dasher is **eligible** for an order when **all** of the following hold:
1. The dasher is active (`active == 1`).
2. The dasher has **remaining capacity greater than `0`**.
3. The dasher's `rating` is **at least** the order's `min_rating` (`rating >= min_rating`).
Among the eligible dashers, pick the best one by this priority:
1. **Smallest Manhattan distance** to the order location, where distance `= |dasher_x - order_x| + |dasher_y - order_y|`.
2. If still tied, the **higher `rating`**.
3. If still tied, the **smaller `id`**.
Append the chosen dasher's `id` to the result. Then **decrease only that dasher's remaining capacity by `1`** (tracked internally, so later orders see the updated capacity). If **no** dasher is eligible for an order, append `-1` for that order and leave all capacities unchanged.
### Important rules
- **Do not mutate the input.** Capacity must be tracked on internal copies; the original `dashers` list and its records must be unchanged when the function returns.
- Each order is independent only in choice — capacity consumed by earlier orders carries forward to later orders.
### Validation — return `[]` on any invalid input
If **any** part of the input is malformed or out of range, return an **empty list** `[]` instead of raising an exception. (Note that `[]` is also the natural result when `orders` is empty — see the examples below.) The input is invalid if any of these fail:
- `dashers` and `orders` must each be a list.
- Every dasher record must be **exactly 6 integers**: `[id, x, y, rating, capacity, active]`. Booleans are **not** accepted as integers.
- Every order record must be **exactly 3 integers**: `[x, y, min_rating]`. Booleans are **not** accepted as integers.
- Dasher `id` values must be **positive and unique** (a duplicate id makes the whole input invalid).
- All coordinates `x`, `y` (for both dashers and orders) must satisfy `-10^6 <= x, y <= 10^6`.
- `rating` and `min_rating` must satisfy `0 <= value <= 500`.
- `capacity >= 0`.
- `active` must be either `0` or `1`.
### Constraints
- `0 <= len(dashers) <= 1000`
- `0 <= len(orders) <= 1000`
### Examples
- `dashers = [[1, 0, 0, 500, 1, 1], [2, 10, 0, 400, 2, 1]]`, `orders = [[0, 0, 0], [1, 0, 0], [9, 0, 0], [0, 0, 450]]` → `[1, 2, 2, -1]`.
- Order `[0,0,0]`: dasher 1 is closest → assign `1`, its capacity drops to 0.
- Order `[1,0,0]`: dasher 1 is out of capacity, so dasher 2 is chosen → `2` (capacity now 1).
- Order `[9,0,0]`: dasher 2 is closest → `2` (capacity now 0).
- Order `[0,0,450]`: requires rating `>= 450`; dasher 1 is out of capacity and dasher 2's rating is too low → `-1`.
- `dashers = [[1, 0, 0, 500, 1, 1], [1, 1, 1, 400, 1, 1]]`, `orders = [[0, 0, 0]]` → `[]` (duplicate dasher id — invalid input).
- `dashers = [[1, 0, 0, 500, 1, 1]]`, `orders = []` → `[]` (no orders, so the result is the empty assignment list).
Constraints
- 0 <= len(dashers) <= 1000
- 0 <= len(orders) <= 1000
- Each dasher record must have exactly 6 integers: [id, x, y, rating, capacity, active].
- Each order record must have exactly 3 integers: [x, y, min_rating].
- Dasher ids must be positive and unique.
- -10^6 <= x, y <= 10^6
- 0 <= rating <= 500 and 0 <= min_rating <= 500
- capacity >= 0
- active must be either 0 or 1
- Invalid input must return [] rather than throwing an exception.
Examples
Input: ([[101, 0, 0, 480, 2, 1], [102, 2, 1, 500, 1, 1], [103, 1, 1, 450, 1, 0], [104, 1, 0, 480, 1, 1]], [[1, 0, 470], [2, 1, 490], [0, 0, 470]])
Expected Output: [104, 102, 101]
Explanation: Order 1 chooses dasher 104 because distance is 0. Order 2 requires rating 490, so dasher 102 is chosen. Order 3 then chooses dasher 101.
Input: ([[1, 0, 0, 450, 1, 1], [2, 0, 0, 500, 1, 1], [3, 1, 0, 500, 1, 1]], [[0, 0, 400], [1, 0, 400]])
Expected Output: [2, 3]
Explanation: For the first order, dashers 1 and 2 are equally close, so higher rating wins. For the second order, dasher 2 has no capacity left, so dasher 3 is selected.
Input: ([[1, 0, 0, 500, 1, 1], [2, 10, 0, 400, 2, 1]], [[0, 0, 0], [1, 0, 0], [9, 0, 0], [0, 0, 450]])
Expected Output: [1, 2, 2, -1]
Explanation: Capacity is consumed over time. The last order requires rating 450, but dasher 1 is full and dasher 2 has rating 400.
Input: ([[1, 0, 0, 500, 1, 1]], [])
Expected Output: []
Explanation: Edge case: there are no orders to process.
Input: ([[1, 0, 0, 500, 1, 1], [1, 1, 1, 400, 1, 1]], [[0, 0, 0]])
Expected Output: []
Explanation: Invalid input because dasher ids must be unique.
Solution
def solution(dashers, orders):
def is_int(value):
return isinstance(value, int) and not isinstance(value, bool)
if not isinstance(dashers, list) or not isinstance(orders, list):
return []
coord_limit = 10 ** 6
seen = set()
workers = []
for record in dashers:
if not isinstance(record, (list, tuple)) or len(record) != 6:
return []
if not all(is_int(v) for v in record):
return []
dasher_id, x, y, rating, capacity, active = record
if dasher_id <= 0 or dasher_id in seen:
return []
if not (-coord_limit <= x <= coord_limit and -coord_limit <= y <= coord_limit):
return []
if rating < 0 or rating > 500 or capacity < 0 or active not in (0, 1):
return []
seen.add(dasher_id)
workers.append([dasher_id, x, y, rating, capacity, active])
assignments = []
for order in orders:
if not isinstance(order, (list, tuple)) or len(order) != 3:
return []
if not all(is_int(v) for v in order):
return []
ox, oy, min_rating = order
if not (-coord_limit <= ox <= coord_limit and -coord_limit <= oy <= coord_limit):
return []
if min_rating < 0 or min_rating > 500:
return []
best_index = -1
best_key = None
for i, worker in enumerate(workers):
dasher_id, x, y, rating, capacity, active = worker
if active != 1 or capacity <= 0 or rating < min_rating:
continue
distance = abs(x - ox) + abs(y - oy)
key = (distance, -rating, dasher_id)
if best_key is None or key < best_key:
best_key = key
best_index = i
if best_index == -1:
assignments.append(-1)
else:
assignments.append(workers[best_index][0])
workers[best_index][4] -= 1
return assignmentsExplanation
The solution separates **validation** from **assignment**, which is the crux of the "refactor" task.
**Validation (fail-fast to `[]`).** A local `is_int` rejects `bool` (since `True`/`False` are `int` subclasses in Python). Every dasher record must be a length-6 list/tuple of ints with a positive, *unique* `id` (tracked in a `seen` set), coordinates within `±10^6`, `0 ≤ rating ≤ 500`, `capacity ≥ 0`, and `active ∈ {0,1}`. Orders are validated similarly (length 3, in-bounds coords, valid `min_rating`). Any malformed record makes the function return `[]` immediately instead of throwing.
**Non-mutating copy.** Each valid dasher is appended to `workers` as a *fresh* list `[id, x, y, rating, capacity, active]`. Capacity is decremented on these copies, so the caller's input is never mutated.
**Greedy per-order selection.** Orders are processed left to right. For each order, the code linearly scans `workers`, skipping any dasher that is inactive, out of capacity (`capacity <= 0`), or under-rated (`rating < min_rating`). For eligible dashers it builds the comparison key
`(distance, -rating, dasher_id)` where `distance = |x-ox| + |y-oy|` (Manhattan).
Picking the lexicographically smallest key encodes all three tie-breakers exactly: smallest distance first, then **higher** rating (via the negation), then smaller id. The winner's id is appended and its copied capacity is decremented by 1; if no dasher qualifies, `-1` is appended.
This is correct because the key ordering mirrors the spec's priority list, and capacity is consumed per assignment so later orders see updated remaining capacity.
Time complexity: O(O*D). Space complexity: O(D).
Hints
- Turn the selection rule into a tuple comparison: distance, negative rating, then id.
- Copy the mutable dasher state before processing orders so that caller-owned input is not modified.
Part 2: Classify a Concurrency Safety Plan
Implement `solution(resources, operations)` that produces a deterministic concurrency-safety plan for a module being prepared for multi-threaded execution.
Instead of writing prose, you must encode a fixed classification rule: for each declared resource decide a single thread-safety **strategy**, then assemble a **validation checklist**.
## Input
Two arguments, each a list:
- **`resources`** — a list of `[name, kind]` records describing the module's resources. `kind` is one of:
- `value` — a scalar or immutable-style value
- `counter` — a numeric counter
- `collection` — a map/set/queue/cache/list-like resource
- `composite` — a multi-field object whose fields may carry invariants
- **`operations`** — a list of `[resource_name, thread_id, op]` records describing operations threads performed. `op` is one of:
- **Non-mutating:** `read`, `iterate`
- **Mutating:** `write`, `inc`, `put`, `remove`
Each record may be given as a list or a tuple, but must have exactly the length shown (2 for a resource, 3 for an operation).
## Output
Return a list of exactly two lists: `[strategy_lines, validation]`.
### `strategy_lines`
One entry per resource, **in the same order the resources were given**, formatted as the string `"<name>:<strategy>"` (the resource name, a colon, then the chosen strategy).
For each resource, pick the **first** strategy whose condition holds, checking the rules **in this order**:
1. **`immutable`** — the resource has **no** mutating operations.
2. **`confined`** — the resource has at least one mutating operation, but every operation referencing it comes from a single (one) `thread_id`.
3. **`atomic`** — the resource is a `counter`, is touched by more than one thread, and **every** mutating operation on it is `inc`.
4. **`concurrent_collection`** — the resource is a `collection` touched by more than one thread (and is not covered by the rules above).
5. **`synchronized`** — any remaining resource that is mutated and shared across more than one thread.
A resource counts as **shared** when more than one distinct `thread_id` appears in its operations. Only mutating operations count toward "has mutations"; `read` and `iterate` never make a resource mutable but they **do** count toward how many distinct threads touched it.
### `validation`
A checklist list, built in this exact order:
- Always include `unit_tests`.
- If **at least one** resource was classified as `atomic`, `concurrent_collection`, or `synchronized`, append (in order) `stress_tests`, then `race_detector`.
- If **at least one** resource was classified as `synchronized`, append `deadlock_diagnostics` next.
- If **at least one** resource was classified as `atomic`, `concurrent_collection`, or `synchronized`, append `contention_metrics` last.
(So the only sources added beyond `unit_tests` are tied to the presence of shared, mutable resources, and `deadlock_diagnostics` appears only when something is `synchronized`, positioned before `contention_metrics`.)
## Invalid input
Return `[[], ['invalid_input']]` if any of the following is violated:
- `resources` and `operations` must each be a list, and every record must have the correct shape (a list/tuple of length 2 for `[name, kind]`, a list/tuple of length 3 for `[resource_name, thread_id, op]`).
- Each resource `name` must be a **non-empty string** and **unique** across resources.
- Each resource `kind` must be one of `value`, `counter`, `collection`, `composite`.
- Every operation must reference an **existing** resource name.
- Each `thread_id` must be a non-empty string.
- Each `op` must be one of `read`, `iterate`, `write`, `inc`, `put`, `remove`.
## Constraints
- `0 <= len(resources) <= 200000`
- `0 <= len(operations) <= 200000`
## Examples
**Resource declared but never operated on** (e.g. a `counter` with no operations) has no mutating operations, so it is `immutable`.
**Empty input** (`resources = []`, `operations = []`) is valid and returns `[[], ['unit_tests']]`.
Constraints
- 0 <= len(resources) <= 200000
- 0 <= len(operations) <= 200000
- Resource names must be non-empty strings and unique.
- Resource kind must be one of: value, counter, collection, composite.
- Each operation must reference an existing resource.
- Thread ids must be non-empty strings.
- Operation type must be one of: read, iterate, write, inc, put, remove.
- Invalid input must return [[], ['invalid_input']].
Examples
Input: ([['config', 'value'], ['cache', 'collection'], ['load', 'counter'], ['routeState', 'composite']], [['config', 'T1', 'read'], ['config', 'T2', 'read'], ['cache', 'T1', 'put'], ['cache', 'T2', 'read'], ['cache', 'T3', 'remove'], ['load', 'T1', 'inc'], ['load', 'T2', 'read'], ['load', 'T3', 'inc'], ['routeState', 'T1', 'write'], ['routeState', 'T2', 'read']])
Expected Output: [['config:immutable', 'cache:concurrent_collection', 'load:atomic', 'routeState:synchronized'], ['unit_tests', 'stress_tests', 'race_detector', 'deadlock_diagnostics', 'contention_metrics']]
Explanation: The config is read-only, cache is a shared mutable collection, load is a shared increment-only counter, and routeState is shared mutable composite state requiring synchronization.
Input: ([['queue', 'collection'], ['scratch', 'composite']], [['queue', 'worker1', 'put'], ['queue', 'worker1', 'remove'], ['scratch', 'worker1', 'write'], ['scratch', 'worker1', 'read']])
Expected Output: [['queue:confined', 'scratch:confined'], ['unit_tests']]
Explanation: Both mutable resources are accessed only by worker1, so thread confinement is sufficient.
Input: ([['settings', 'value'], ['catalog', 'collection'], ['unused', 'counter']], [['settings', 'T1', 'read'], ['catalog', 'T2', 'iterate']])
Expected Output: [['settings:immutable', 'catalog:immutable', 'unused:immutable'], ['unit_tests']]
Explanation: All resources have no mutating operations. A resource with no operations is also classified as immutable.
Input: ([['count', 'counter']], [['missing', 'T1', 'inc']])
Expected Output: [[], ['invalid_input']]
Explanation: The operation references an unknown resource.
Input: ([], [])
Expected Output: [[], ['unit_tests']]
Explanation: Edge case: an empty module still has a minimal validation checklist.
Solution
def solution(resources, operations):
def invalid():
return [[], ['invalid_input']]
allowed_kinds = {'value', 'counter', 'collection', 'composite'}
mutating_ops = {'write', 'inc', 'put', 'remove'}
allowed_ops = mutating_ops | {'read', 'iterate'}
if not isinstance(resources, list) or not isinstance(operations, list):
return invalid()
names = []
kinds = {}
threads_by_resource = {}
mutations_by_resource = {}
for record in resources:
if not isinstance(record, (list, tuple)) or len(record) != 2:
return invalid()
name, kind = record
if not isinstance(name, str) or not name:
return invalid()
if not isinstance(kind, str) or kind not in allowed_kinds:
return invalid()
if name in kinds:
return invalid()
names.append(name)
kinds[name] = kind
threads_by_resource[name] = set()
mutations_by_resource[name] = []
for record in operations:
if not isinstance(record, (list, tuple)) or len(record) != 3:
return invalid()
resource_name, thread_id, op = record
if not isinstance(resource_name, str) or resource_name not in kinds:
return invalid()
if not isinstance(thread_id, str) or not thread_id:
return invalid()
if not isinstance(op, str) or op not in allowed_ops:
return invalid()
threads_by_resource[resource_name].add(thread_id)
if op in mutating_ops:
mutations_by_resource[resource_name].append(op)
strategy_lines = []
strategy_values = []
for name in names:
mutations = mutations_by_resource[name]
thread_count = len(threads_by_resource[name])
kind = kinds[name]
if len(mutations) == 0:
strategy = 'immutable'
elif thread_count <= 1:
strategy = 'confined'
elif kind == 'counter' and all(op == 'inc' for op in mutations):
strategy = 'atomic'
elif kind == 'collection':
strategy = 'concurrent_collection'
else:
strategy = 'synchronized'
strategy_values.append(strategy)
strategy_lines.append(f'{name}:{strategy}')
validation = ['unit_tests']
shared_mutable_strategies = {'atomic', 'concurrent_collection', 'synchronized'}
has_shared_mutable = any(strategy in shared_mutable_strategies for strategy in strategy_values)
has_synchronized = any(strategy == 'synchronized' for strategy in strategy_values)
if has_shared_mutable:
validation.append('stress_tests')
validation.append('race_detector')
if has_synchronized:
validation.append('deadlock_diagnostics')
validation.append('contention_metrics')
return [strategy_lines, validation]Explanation
The solution makes two validating passes, then classifies each resource by a strict priority of rules.
**Pass 1 — index resources.** For each `[name, kind]` it checks the shape, that `name` is a non-empty unique string, and that `kind` is in `{value, counter, collection, composite}`. It records `kinds[name]`, and initializes an empty `threads_by_resource[name]` set and an empty `mutations_by_resource[name]` list. Any violation returns `[[], ['invalid_input']]`.
**Pass 2 — fold operations.** For each `[resource_name, thread_id, op]` it validates the shape, that the resource exists, that the thread id is a non-empty string, and that `op` is in the allowed set. Then it adds `thread_id` to that resource's thread set and, if `op` is mutating (`write/inc/put/remove`), appends it to the resource's mutation list. This collects exactly the two facts each rule needs: *how many distinct threads touched it* and *which mutations occurred*.
**Classification (order matters).** Per resource, in original order:
- no mutations → `immutable`
- mutated but `thread_count <= 1` → `confined`
- shared `counter` with every mutation `inc` → `atomic`
- shared `collection` → `concurrent_collection`
- otherwise → `synchronized`
Checking rules in this fixed order encodes the required precedence directly, so the first matching rule wins.
**Checklist.** Always `unit_tests`. If any resource is `atomic`/`concurrent_collection`/`synchronized` (shared-mutable), it also adds `stress_tests`, `race_detector`, and `contention_metrics`; if any is `synchronized`, it inserts `deadlock_diagnostics` before `contention_metrics`, matching the expected ordering.
It is correct because each strategy depends only on the aggregated thread-count and mutation facts, which are computed exhaustively before classification.
Time complexity: O(R + O). Space complexity: O(R + O).
Hints
- For each resource, track the set of accessing threads and the list or count of mutating operation types.
- Apply the strategy rules in the given order; for example, a read-only counter is immutable, not atomic.