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 hard 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 Fastest Commute Mode | Databricks Coding Question

Quick Overview

This question evaluates graph traversal and shortest-path reasoning on a constrained 2D grid, including modeling movement rules per transportation mode, reachability analysis, and multi-criteria optimization (minimizing total travel time with cost as a tie-breaker).

Find Fastest Commute Mode

Company: Databricks

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

You are given a 2D city grid containing: - `S`: starting location - `D`: destination - `X`: blocked cell that cannot be entered - `1`, `2`, `3`, `4`: cells usable by Walk, Bike, Car, and Train, respectively Choose exactly one transportation mode for the entire trip; switching modes is not allowed. Starting from `S`, you may move only up, down, left, or right. For a chosen mode: - you may travel through cells labeled with that mode - `S` and `D` are considered enterable for any mode - moving across one block takes `time[i]` minutes and costs `cost[i]` dollars, where `i` corresponds to the chosen mode Return the name of the transportation mode that can reach `D` from `S` with the minimum total travel time. If multiple modes have the same total travel time, return the one with the lower total cost. You may assume at least one mode can reach the destination.

Quick Answer: This question evaluates graph traversal and shortest-path reasoning on a constrained 2D grid, including modeling movement rules per transportation mode, reachability analysis, and multi-criteria optimization (minimizing total travel time with cost as a tie-breaker).

You are given a 2D city grid containing exactly one starting cell 'S' and one destination cell 'D'. The grid may also contain blocked cells 'X' and transportation cells '1', '2', '3', and '4', which correspond to Walk, Bike, Car, and Train. You must choose exactly one transportation mode for the entire trip. Switching modes is not allowed. From 'S', you may move only up, down, left, or right. For a chosen mode: - you may move through cells labeled with that mode - 'S' and 'D' are always enterable for any mode - 'X' and cells of other modes cannot be entered - each move across one block takes time[i] minutes and costs cost[i] dollars, where i = 0,1,2,3 corresponds to Walk, Bike, Car, Train For every mode that can reach 'D', compute its shortest path in number of blocks. Its total travel time is: shortest_blocks * time[i] Its total travel cost is: shortest_blocks * cost[i] Return the name of the mode with the minimum total travel time. If multiple modes have the same total travel time, return the one with the lower total travel cost.

Constraints

1 <= number of rows, number of columns <= 200
grid contains only 'S', 'D', 'X', '1', '2', '3', '4'
There is exactly one 'S' and exactly one 'D'
time and cost each contain exactly 4 positive integers
At least one transportation mode can reach the destination

Examples

Input: (['1111111', 'SXXXXXD', '2222222'], [2, 1, 3, 4], [1, 2, 1, 1])

Expected Output: 'Bike'

Explanation: Walk and Bike are both reachable in 8 blocks. Walk takes 8 * 2 = 16 minutes, while Bike takes 8 * 1 = 8 minutes. Car and Train are unreachable.

Input: (['1111111', 'SXXXXXD', '2222222'], [1, 1, 5, 6], [1, 2, 1, 1])

Expected Output: 'Walk'

Explanation: Walk and Bike both need 8 blocks and both take 8 minutes. Walk costs 8 * 1 = 8, while Bike costs 8 * 2 = 16, so Walk wins the tie.

Input: (['S222D'], [5, 1, 3, 4], [7, 2, 5, 6])

Expected Output: 'Bike'

Explanation: Only Bike can use the cells between S and D. The shortest path is 4 blocks, so Bike is the only valid answer.

Input: (['S44', 'XX4', 'XXD'], [1, 1, 1, 2], [1, 1, 1, 3])

Expected Output: 'Train'

Explanation: Only Train can reach D by following the 4-cells: S -> 4 -> 4 -> 4 -> D, which is 4 blocks.

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

Expected Output: 'Car'

Explanation: S and D are adjacent, so every mode can reach D in 1 block. Bike and Car both take 2 minutes, but Car costs 1 while Bike costs 4.

Hints

For a fixed mode, every move has equal weight, so the best route is the one with the fewest blocks.
Try running a BFS from 'S' to 'D' once for each of the 4 modes, allowing only 'S', 'D', and that mode's cells.

Quick Overview