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.

Choose fastest transportation mode on city grid

Company: Databricks

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You live in a city modeled as a 2D grid. Each cell is either: - A transportation mode `1..4` where: - `1 = Walk`, `2 = Bike`, `3 = Car`, `4 = Train` - `S` = source (start) - `D` = destination - `X` = roadblock (cannot enter) You may move only **up, down, left, right** (no diagonals). A trip must use **exactly one transportation mode** for the whole route: - For a chosen mode `m`, you may step from a cell to a neighboring cell only if the neighbor is either `S`, `D`, or has value `m`. - You cannot step onto `X`. For each mode `m`, if there exists a valid path from `S` to `D` using mode `m`, its total travel time and cost are: - `time = (#blocks traversed) * timePerBlock[m]` - `cost = (#blocks traversed) * costPerBlock[m]` Where `#blocks traversed` is the number of moves (edges) along the chosen path. Return the **mode number** (1–4) that yields the **minimum total time**. If multiple modes tie on time, return the one with the **minimum total cost**. If still tied, any tied mode is acceptable. ### Example Grid (rows): ``` |3|3|S|2|X| |3|1|1|2|X| |3|1|1|2|2| |3|1|1|1|D| |3|3|3|3|4| |4|4|4|4|4| ``` `costPerBlock = [0, 1, 3, 2]` (for modes 1..4 respectively) `timePerBlock = [3, 2, 1, 1]` ### Input/Output - **Input:** `grid`, `costPerBlock[4]`, `timePerBlock[4]` - **Output:** an integer in `{1,2,3,4}` indicating the selected mode. ### Notes - You may assume `S` and `D` each appear exactly once. - If a mode cannot reach `D` from `S`, ignore it. - (Optional if needed) If no mode can reach `D`, return `-1`.

Quick Answer: This question evaluates a candidate's ability to model constrained grid movement and perform weighted shortest-path optimization, covering skills in graph traversal, pathfinding, and multi-criteria comparison of time and cost.

You are given a city represented as a 2D grid. Each cell contains one of the following values: '1', '2', '3', '4', 'S', 'D', or 'X'. Here, 'S' is the start, 'D' is the destination, 'X' is a roadblock, and '1'..'4' are transportation modes. You may move only up, down, left, or right. A trip must use exactly one transportation mode for the entire route. If you choose mode m, then from any cell you may move to a neighboring cell only if that neighbor is 'S', 'D', or has value equal to m. You may never enter 'X'. For each mode, if a valid path from 'S' to 'D' exists, its total time is (#moves) * timePerBlock[m] and its total cost is (#moves) * costPerBlock[m], where #moves is the number of edge moves in the path. Return the mode number (1 to 4) with the minimum total time. If multiple modes tie on time, return the one with the minimum total cost. If no mode can reach the destination, return -1.

Constraints

1 <= number of rows, number of columns <= 200
grid contains exactly one 'S' and exactly one 'D'
Each grid cell is one of 'S', 'D', 'X', '1', '2', '3', or '4'
costPerBlock.length == 4 and timePerBlock.length == 4
0 <= costPerBlock[i], timePerBlock[i] <= 10^6

Examples

Input: ([['3', '3', 'S', '2', 'X'], ['3', '1', '1', '2', 'X'], ['3', '1', '1', '2', '2'], ['3', '1', '1', '1', 'D'], ['3', '3', '3', '3', '4'], ['4', '4', '4', '4', '4']], [0, 1, 3, 2], [3, 2, 1, 1])

Expected Output: 2

Explanation: Mode 1 reaches D in 5 moves, so time = 5 * 3 = 15. Mode 2 also reaches D in 5 moves, so time = 5 * 2 = 10. Modes 3 and 4 cannot reach D. Therefore mode 2 is best.

Input: ([['S', '1', 'D'], ['2', '2', '2'], ['X', 'X', 'X']], [5, 1, 7, 9], [2, 1, 3, 4])

Expected Output: 2

Explanation: Mode 1 uses the top row in 2 moves, so time = 4 and cost = 10. Mode 2 uses the second row in 4 moves, so time = 4 and cost = 4. Since times tie, choose the cheaper mode 2.

Input: ([['S', 'D']], [5, 1, 4, 3], [3, 1, 1, 4])

Expected Output: 2

Explanation: Since D is adjacent to S, every mode can reach the destination in exactly 1 move. Modes 2 and 3 both have the minimum time of 1, but mode 2 has lower cost.

Input: ([['S', 'X'], ['X', 'D']], [1, 1, 1, 1], [1, 1, 1, 1])

Expected Output: -1

Explanation: S and D are separated by roadblocks, so no transportation mode can reach the destination.

Input: ([['S', '1', '1', '1', 'D'], ['4', '4', '4', '4', '4']], [1, 10, 10, 2], [3, 5, 5, 1])

Expected Output: 4

Explanation: Mode 1 reaches D in 4 moves, so time = 12. Mode 4 takes a longer path of 6 moves, but time = 6 because it is faster per block. Therefore mode 4 is chosen.

Hints

For a fixed transportation mode, the problem becomes finding the shortest path on an unweighted grid with restricted cells.
There are only 4 modes, so you can run a BFS for each mode independently, then compare total time and total cost.

Quick Overview

This question evaluates a candidate's ability to model constrained grid movement and perform weighted shortest-path optimization, covering skills in graph traversal, pathfinding, and multi-criteria comparison of time and cost.