274. Debugging: Dasher Assignment Service for Order Delivery
Asked in
DoorDash
Debugging: Dasher Assignment Service for Order Delivery
Implement a Dasher Assignment Service for order delivery that maintains a pool of available dashers, assigns dashers to orders, and makes dashers available again after their assigned orders are delivered. Each dasher is represented by an integer dasherId, and each order is represented by an integer orderId. Implement the methods described below.

Methods

Constructor

DasherAssignmentService()
Initialize an empty Dasher Assignment Service containing exactly 16 buckets and no active order assignments.

Add Dasher

void addDasher(int dasherId)
  • Add dasherId to the available pool.
  • If the dasher is already available, ignore the call and leave the service unchanged.
  • If the dasher is currently assigned to an active order, ignore the call and leave the service unchanged.
  • The dasher must be appended to the end of its assigned bucket.

Pick Dasher

int pickDasher(int orderId)
  • Select and remove the next available dasher using the bucket-selection rules.
  • Associate the selected dasher with orderId.
  • Return the selected dasherId.
  • Return -1 when no dasher is available.
  • If orderId already has an active dasher assignment, return -1 and leave the service unchanged.
  • An order is considered active from the time a dasher is successfully selected until orderDelivered is called for that order.

Order Delivered

void orderDelivered(int orderId)
  • Find the dasher currently assigned to orderId.
  • Remove the active assignment between the order and the dasher.
  • Add the freed dasher back to the available pool.
  • The freed dasher must be appended to the end of its assigned bucket.
  • If orderId does not have an active dasher assignment, ignore the call and leave the service unchanged.
  • After an order is delivered, the same orderId may be used again in a later call to pickDasher.

Available Dasher Hash Set

Store available dashers in a custom hash set containing exactly 16 buckets. Each bucket must be a List<Integer>.
Built-in hash maps and hash sets must not be used.
Calculate the bucket index using:
bucketIndex = (int) (((long) dasherId * 31 + 17) % 16)
  • Store available dashers in insertion order within each bucket.
  • Different dasher IDs may be stored in the same bucket.
  • To determine whether a dasher is already available, search only the bucket assigned to that dasherId.
  • A dasher ID must not appear more than once in the available pool.
  • A dasher must not be available while it is assigned to an active order.

Active Order Assignments

The service must maintain the active association between each orderId and its assigned dasherId.
  • An active order may have exactly one assigned dasher.
  • An assigned dasher may be associated with exactly one active order.
  • Only successful calls to pickDasher create active assignments.
  • Calling orderDelivered removes the corresponding active assignment.
  • Built-in hash maps and hash sets must not be used to store active assignments.
  • Active assignments may be stored using lists or another custom data structure.

Dasher Selection Order

  1. Examine buckets from index 0 through 15.
  2. Choose the first bucket containing at least one available dasher.
  3. Remove and select the first dasher from that bucket.
  4. Associate the selected dasher with the supplied orderId.
  5. Begin searching from bucket 0 again for every call to pickDasher.
Therefore, lower bucket indices have higher priority, and dashers within the same bucket are selected in first-in-first-out order.

Dasher Availability Lifecycle

  1. A dasher becomes available when successfully added using addDasher.
  2. A dasher becomes unavailable when selected by pickDasher.
  3. The selected dasher remains unavailable while its assigned order is active.
  4. The dasher becomes available again when orderDelivered is called for the assigned order.
  5. When the dasher becomes available again, it is appended to the end of its assigned bucket.

Constraints

  • 0 ≤ dasherId ≤ 100,000,000
  • 0 ≤ orderId ≤ 100,000,000
  • The custom hash set contains exactly 16 buckets.
  • The implementation must ensure that a dasher ID appears at most once in the available pool.
  • A dasher cannot be both available and assigned to an active order.
  • An order ID cannot have more than one active dasher assignment.
  • Built-in hash maps and hash sets must not be used.

Note

This question, or a similar variant, is asked in a debugging round. In the actual interview, you will receive an incomplete and potentially incorrect implementation instead of implementing the complete service from scratch. You will need to identify logic bugs, incorrect edge-case handling, poor data-structure choices, unnecessary abstractions, and bad coding practices. Prioritize fixing functional and logic bugs before making design or style improvements.

Examples

Example 1: Bucket Priority and Order Completion

Method calls:
  1. DasherAssignmentService service = new DasherAssignmentService();
  2. service.addDasher(dasherId = 12);
  3. service.addDasher(dasherId = 16);
  4. service.addDasher(dasherId = 32);
Dasher 16 and dasher 32 are placed in bucket 1. Dasher 12 is placed in bucket 5.
Method calls and outputs:
  1. service.pickDasher(orderId = 101) returns 16. Dasher 16 is assigned to order 101.
  2. service.pickDasher(orderId = 102) returns 32. Dasher 32 is assigned to order 102.
  3. service.pickDasher(orderId = 103) returns 12. Dasher 12 is assigned to order 103.
  4. service.pickDasher(orderId = 104) returns -1 because no dasher is available.
  5. service.orderDelivered(orderId = 101) completes order 101 and adds dasher 16 back to the end of bucket 1.
  6. service.pickDasher(orderId = 104) returns 16. Dasher 16 is now assigned to order 104.
Bucket 1 is processed before bucket 5, and dashers in the same bucket are selected in first-in-first-out order.

Example 2: Duplicate Dasher and Active Order

Method calls and outputs:
  1. DasherAssignmentService service = new DasherAssignmentService();
  2. service.addDasher(dasherId = 45) adds dasher 45 to the available pool.
  3. service.addDasher(dasherId = 45) is ignored because dasher 45 is already available.
  4. service.pickDasher(orderId = 201) returns 45 and assigns the dasher to order 201.
  5. service.addDasher(dasherId = 45) is ignored because dasher 45 is currently assigned to an active order.
  6. service.pickDasher(orderId = 201) returns -1 because order 201 already has an active dasher assignment.
  7. service.orderDelivered(orderId = 999) is ignored because order 999 does not have an active assignment.
  8. service.orderDelivered(orderId = 201) completes order 201 and makes dasher 45 available again.
  9. service.orderDelivered(orderId = 201) is ignored because order 201 is no longer active.
  10. service.pickDasher(orderId = 202) returns 45.
  11. service.pickDasher(orderId = 203) returns -1 because no dasher is available.

Example 3: Freed Dasher Is Appended to Its Bucket

Method calls and outputs:
  1. DasherAssignmentService service = new DasherAssignmentService();
  2. service.addDasher(dasherId = 16);
  3. service.addDasher(dasherId = 32);
  4. service.pickDasher(orderId = 301) returns 16.
  5. service.orderDelivered(orderId = 301) adds dasher 16 to the end of bucket 1, after dasher 32.
  6. service.pickDasher(orderId = 302) returns 32.
  7. service.pickDasher(orderId = 303) returns 16.
Dasher 16 is selected after dasher 32 because completing an order appends the freed dasher to the end of its bucket.


Please use Laptop/Desktop or any other large screen to add/edit code.