~/problems / Simulation & OOP design / Object-oriented design and extensible simulations

OA: Debug the dasher picker, then hash-ring it

medium 2 levels ~60 min DoorDash

Level 1 Fix the dasher picker

The starter file has a DasherPicker that a teammate wrote. It hands out orders to dashers and has several bugs. Read the whole class before you change anything, reproduce each bug with a tiny example, then fix it. You don't have to rewrite it from scratch.

Here's what it's meant to do.

Dashers sit in a list of slots. A dict maps each dasher to their slot index, so every operation is O(1).

  • DasherPicker(seed=None): creates an empty picker. Two pickers never share state. It also creates one random.Random(seed) that later calls reuse.
  • add(dasher) -> bool: puts a new dasher in a new slot at the end and returns True. If the dasher is already present, returns False.
  • remove(dasher) -> bool: returns False if the dasher is absent. Otherwise it moves the last slot's dasher into the removed dasher's slot, shrinks the list by one and returns True. The moved dasher's index must be updated. Removing the dasher who is already in the last slot just shrinks the list.
  • pick() -> str | None: round robin. Returns None if there are no dashers. Otherwise, if the cursor is past the end of the list, it wraps to 0. It then returns the dasher at the cursor and moves the cursor forward one slot. Removals don't touch the cursor. The first pick returns slot 0.
  • pick_random() -> str | None: returns None when empty. Otherwise it returns slots[r.randrange(len(slots))], where r is the picker's single Random. That is exactly one randrange call per pick.
  • dashers() -> list[str]: a copy of the slots in order. len(picker) and dasher in picker work too.
p = DasherPicker()
for d in ["ann", "bo", "cy"]:
    p.add(d)
[p.pick() for _ in range(4)]   # ["ann", "bo", "cy", "ann"]
p.remove("ann")                # "cy" moves into slot 0
p.dashers()                    # ["cy", "bo"]
p.pick()                       # "bo"   (cursor was at slot 1)

Level 2 unlocks when level 1 passes.

Topic: Object-oriented design and extensible simulations. Classes that survive new requirements: games, payments, subscriptions, refactors.

0:00
Ctrl ' run · Ctrl ↵ submit
esc