Stage 1 of 2: Steps to the nearest DashMart
Background. A city is a grid of cells: streets, blocked cells and DashMarts, DoorDash's own small stores. For many places in the city at once, we want to know how far the nearest DashMart is on foot.
Implement mart_distances(city, locations) in dashmart.py.
cityis a list of 1 to 300 strings, all the same length, 1 to 300 characters each:.is a street,#a blocked cell,Ma DashMart. A cell iscity[row][col], rows counted from the top and columns from the left, both from 0.locationsis a list of 0 to 50,000(row, col)pairs, each inside the city. A pair may appear more than once.- Return a list of ints, one per location and in the same order: the fewest steps from that location to any DashMart.
A step moves up, down, left or right to a neighbouring cell that is not #: never diagonally, never off the city. Streets and DashMarts can both be stepped on. A location on a DashMart is 0 steps away. A location on a # cell gets -1, and so does a location with no DashMart it can walk to, which includes every location in a city with no DashMart.
Every call must return within 2 seconds and use at most 200 MB of memory at the largest sizes above (tests/helpers.py holds the time limit).
Example
city = [
"M..#.",
".#.#.",
"...#M",
"##...",
]
mart_distances(city, [(0, 2), (3, 2), (1, 4), (3, 0), (0, 4)])
# [2, 3, 1, -1, 2]
# (3, 2) walks right and up to the DashMart at (2, 4) in 3 steps; the one at (0, 0) is 5 away.
# (3, 0) is a blocked cell.
Notes
- Inputs are always valid.
- Only the number of steps counts: which DashMart is the nearest never matters.
tests/test_part1_large.pytimes two 300 x 300 cities with 50,000 locations each: one with 40 DashMarts at random places, one with a DashMart on every cell of its top row.- On the starter, all 13 tests in
tests/test_part1.pyand both tests intests/test_part1_large.pyfail.
Done when Submit goes green.
Constraints
- Python 3.12 standard library only
- Editable:
dashmart.py - Read-only:
tests/helpers.pyand alltests/test_*.pyfiles - Inputs are always valid: a city is 1 to 300 rows of 1 to 300 cells, each '.', '#' or 'M', and every (row, col) given is inside it
What comes after stage 1
The next stage opens once the tests for the one before it pass. Each raises the bar, the way an interviewer does in the room.
- Stage 2: The nearest Dasher. Dashers are out on the streets: for every customer, which Dasher can walk there in the fewest steps?
The files you get
- Yours to edit: dashmart.py.
- Read-only: tests/helpers.py.
- Tests you can read and run: tests/test_part1.py, tests/test_part1_large.py. Hidden tests run on Submit.
The round: no AI, an assistant that only answers
DoorDash runs this round without AI. Here the closest format is answer-only: the assistant answers your questions and reviews your code when you ask, the way an interviewer would, and never writes a line of it. The interviewer asks about your decisions as you go, and the report states the format. You can switch to the agent format when you press Begin.
Frequently asked, briefly answered
Is Nearest DashMart free?
It is a Pro problem. Free plan includes one complete problem, plus the first stage of several more, so you can see how a round works before you pay.
Which company asks something like this?
DoorDash. It is modelled on DoorDash's coding round, which runs without AI. Based on candidates' reports of DoorDash interviews. Nyrion wrote this version, so the question you get may differ.
Do I bring my own AI tool?
No. The real round has no AI, so this one opens answer-only: an assistant that answers your questions and can't write code. You can switch to an agent that proposes changes when you press Begin.
What does the interviewer ask?
4 questions along the way about your own code, and one at the end about the whole session. A weak answer gets one follow up. The answers go into the report, which ends with a hire or no hire verdict.
Start the problem
Sign in and the problem opens where you left it. New here? An account takes a minute to create, and the Pro plan starts at the first stage of this problem.
More like it: every practice problem, DoorDash's interviews, the AI coding interview guide.