Optimal Commute · Databricks AI coding interview practice

Stage 1 of 3: One mode all the way

Background. A city is a grid of cells: a start S, a destination D, blocked cells X, and cells marked 1 to 4. There are four travel modes, numbered 1 to 4, and a cell marked with a digit belongs to that mode.

Implement best_mode(city, step_time, step_cost) in commute.py. A trip from S to D uses one mode for every step. Return the mode, 1 to 4, with the best trip, or -1 when no mode reaches D.

city is a list of equal-length strings, with exactly one S and one D.
A step goes up, down, left or right to a neighbouring cell of the grid, never diagonally. In mode m a step may enter a cell marked m, or D. S and X are never entered.
A step in mode m takes step_time[m - 1] and costs step_cost[m - 1]; a trip's total time and total cost are the sums over its steps.
A mode's trip is its fastest trip from S to D. A mode with no trip to D takes no part.
The best mode is the one whose trip has the least total time; among equal total times, the least total cost; among equal times and costs, the smaller mode number.

Example

city = [
    "S11X44",
    "3X1XX4",
    "3X111D",
    "3222X3",
    "333333",
]
best_mode(city, [3, 1, 2, 1], [2, 1, 1, 5])  # 1

Mode 1 arrives in 7 steps (time 21, cost 14) and mode 3 in 11 (time 22, cost 11). Modes 2 and 4 cannot leave S.

Notes

A city has 1 to 18 rows and 1 to 18 columns. Step times are 1 to 1,000 and step costs 0 to 1,000. Inputs are always valid.
Every call answers within 2 seconds (tests/helpers.py holds the limit).
On the starter, all 13 tests in tests/test_part1.py fail.

Done when Submit goes green.

Constraints

Python 3.12 standard library only
Editable: commute.py
Read-only: tests/helpers.py and all tests/test_*.py files
A city is 1 to 18 rows of 1 to 18 cells, each S, D, X, 1, 2, 3 or 4, with exactly one S and one D; inputs are always valid
Step times are 1 to 1,000 and step costs 0 to 1,000
Every call answers within 2 seconds

What comes after stage 1

The next stages open once the tests for the one before them pass. Each raises the bar, the way an interviewer does in the room.

Stage 2: Changing modes. A trip may now change mode on the way, and every change costs time.
Stage 3: A limit on changes. Only so many changes are allowed on one trip.

The files you get

Yours to edit: commute.py.
Read-only: tests/helpers.py.
Tests you can read and run: tests/test_part1.py. Hidden tests run on Submit.

The round: an agent in the editor

The assistant here works like the one in the interview IDE. It reads your files, runs code and proposes changes, and you accept or reject each one. It doesn't volunteer ideas, so what gets built is what you asked for. Along the way the interviewer asks about your decisions, and at the end the report says what you checked and what you accepted unread.

Frequently asked, briefly answered

Is Optimal Commute 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?

Databricks. Based on candidates' reports of Databricks interviews. Nyrion wrote this version, so the question you get may differ.

Do I bring my own AI tool?

No. The assistant is in the editor, same as in the interview IDEs at Meta, Stripe and Amazon. What you choose at Begin is the format: an agent that proposes changes you accept or reject, or an answer-only assistant that can't write code.

What does the interviewer ask?

6 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.

Start this problem → Sign in

More like it: every practice problem, how Databricks runs its AI round, the AI coding interview guide.