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 the Best Travel Mode | Databricks Coding Question

Quick Overview

Solve a grid-based pathfinding problem where a traveler must choose the transportation mode with the lowest travel time and cost tie-breakers. The question evaluates BFS, reachability under mode-specific passability rules, tie-breaking logic, and efficient handling of multiple traversal modes.

Choose the Best Travel Mode

Company: Databricks

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given a 2D grid representing a map, a start cell, a destination cell, and several transportation modes. Each mode has a per-step time cost and a per-step monetary cost. A traveler must choose exactly one mode for the entire trip. For a chosen mode, the traveler may move up, down, left, and right through cells that are open for that mode, plus the start and destination cells. Compute which mode reaches the destination with the smallest total travel time. If multiple modes tie on time, choose the one with the smaller total monetary cost. If no mode can reach the destination, return `None`. Design the algorithm so the grid is scanned efficiently instead of running unnecessary repeated work for every direction.

Quick Answer: Solve a grid-based pathfinding problem where a traveler must choose the transportation mode with the lowest travel time and cost tie-breakers. The question evaluates BFS, reachability under mode-specific passability rules, tie-breaking logic, and efficient handling of multiple traversal modes.

You are given a 2D grid representing a map, a start cell, a destination cell, and several transportation modes. Each mode has a per-step time cost and a per-step monetary cost. A traveler must choose exactly one mode for the entire trip. Cells marked `X` are blocked. Cells marked `.` are shared roads that any mode may use. A cell marked with a mode symbol may be used only by that mode. The `S` and `D` cells are always passable. From a cell, the traveler may move up, down, left, or right. Return the mode symbol that reaches the destination with the smallest total travel time. If multiple modes tie on time, choose the lower total monetary cost. If time and cost both tie, choose the lexicographically smallest mode symbol. If no mode can reach the destination, return `None`.

Constraints

1 <= number of rows, columns <= 200
start and destination are valid grid coordinates.
Each mode key is a one-character string that may appear in the grid.
Each mode value is a pair `(time_per_step, cost_per_step)` of positive integers.
The traveler must use exactly one mode for the entire trip.

Examples

Input: (['SAA', '..A', 'BBD'], (0, 0), (2, 2), {'A': (2, 5), 'B': (1, 10)})

Expected Output: 'B'

Explanation: Mode B has lower total time.

Input: (['S..D'], (0, 0), (0, 3), {'A': (1, 5), 'B': (1, 2)})

Expected Output: 'B'

Explanation: Time ties, so cost breaks the tie.

Input: (['SBXD', '.B..'], (0, 0), (0, 3), {'A': (1, 1), 'B': (1, 1)})

Expected Output: 'B'

Explanation: Only mode B can pass through the B-only cells around the blocker.

Input: (['SAXD'], (0, 0), (0, 3), {'A': (1, 1), 'B': (1, 1)})

Expected Output: None

Explanation: The only row is blocked before the destination.

Input: (['S.D'], (0, 0), (0, 2), {'A': (1, 1), 'B': (1, 1)})

Expected Output: 'A'

Explanation: Time and cost tie, so the lexicographically smallest mode wins.

Input: (['S.C', 'XXC', '..D'], (0, 0), (2, 2), {'A': (1, 1), 'C': (3, 1)})

Expected Output: 'C'

Explanation: Mode C is the only mode with a path through the C cells.

Hints

For a fixed mode, this is a shortest-path problem on an unweighted grid, so BFS gives the fewest steps.
After BFS finds the number of steps for a mode, multiply by that mode's time and cost, then apply the tie-breakers.
Shared road cells can be traversed by every mode; cells labeled with another mode cannot.

Quick Overview