How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Databricks.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Databricks during technical interviews.

Find the Best Commute Mode | Databricks Coding Question

Find the Best Commute Mode

Company: Databricks

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given a 2D grid representing a city commute map. The grid contains exactly one start cell `S` and exactly one destination cell `D`. Each other cell is one of: - `1`, `2`, `3`, or `4`: a road usable only by that commute mode. - `X`: blocked and cannot be used by any commute mode. There are four commute modes, numbered `1` through `4`. For each mode `i`, you are also given: - `time[i]`: time required to move one step using mode `i`. - `cost[i]`: cost required to move one step using mode `i`. A commute mode may move up, down, left, or right. Mode `i` may move through cells labeled `i`, and may also enter `S` and `D`. It cannot move through cells labeled with other mode numbers or through blocked cells. For each commute mode that can reach `D` from `S`, compute: - total time = number of steps in its shortest path multiplied by `time[i]` - total cost = number of steps in its shortest path multiplied by `cost[i]` Return the commute mode that has the smallest total time. If multiple modes have the same total time, return the one with the smallest total cost. If there is still a tie, return the smallest mode number. If no commute mode can reach the destination, return `-1`.

Quick Answer: This question evaluates competency in grid-based pathfinding, graph traversal, and multi-criteria optimization of path time and cost within the Coding & Algorithms domain.

You are given a 2D grid representing a city commute map. The grid contains exactly one start cell 'S' and exactly one destination cell 'D'. Every other cell is either '1', '2', '3', or '4' for a road usable only by that commute mode, or 'X' for a blocked cell. For each commute mode i from 1 to 4, you are given a per-step time and per-step cost. A mode may move up, down, left, or right, and may travel only through cells labeled with its own mode number, plus 'S' and 'D'. It cannot pass through other mode numbers or blocked cells. For every mode that can reach 'D' from 'S', compute the number of steps in its shortest path, then multiply that step count by its per-step time and per-step cost. Return the mode with the smallest total time. If multiple modes tie on total time, return the one with the smallest total cost. If there is still a tie, return the smallest mode number. If no mode can reach the destination, return -1.

Constraints

1 <= number of rows, number of columns <= 200
All rows in grid have the same length
grid contains exactly one 'S' and exactly one 'D'
Each cell is one of 'S', 'D', 'X', '1', '2', '3', or '4'
time and cost each contain exactly 4 positive integers

Examples

Input: (['S11','X1D','222'], [2,1,5,5], [3,4,1,1])

Expected Output: 1

Explanation: Mode 1 can reach D in 3 steps: S -> 1 -> 1 -> D. Its total time is 3*2 = 6 and total cost is 3*3 = 9. No other mode can reach the destination.

Input: (['SD'], [3,3,3,3], [5,2,4,2])

Expected Output: 2

Explanation: S and D are adjacent, so all modes can reach in 1 step. All total times are 3, so compare total cost. Modes 2 and 4 both have cost 2, and the smaller mode number is 2.

Input: (['SX','XD'], [1,1,1,1], [1,1,1,1])

Expected Output: -1

Explanation: From S, every orthogonally adjacent cell is blocked, so no mode can reach D.

Input: (['S3D','444'], [9,9,2,1], [9,9,5,2])

Expected Output: 4

Explanation: Mode 3 reaches D in 2 steps for total time 4 and total cost 10. Mode 4 reaches D in 4 steps for total time 4 and total cost 8. The total time ties, so mode 4 wins on lower total cost.

Input: (['S111D','1XXX1','11111'], [2,5,5,5], [7,1,1,1])

Expected Output: 1

Explanation: Only mode 1 can move through the grid. Its shortest path is the straight top row from S to D in 4 steps, so mode 1 is the answer.

Hints

Treat each mode as a separate shortest-path problem. Since every move has equal step count, BFS gives the minimum number of steps for that mode.
After finding the shortest step count for a mode, compare candidates using a tuple like (total_time, total_cost, mode_number).

Quick Overview

This question evaluates competency in grid-based pathfinding, graph traversal, and multi-criteria optimization of path time and cost within the Coding & Algorithms domain.