← Databricks Interview Insights

Databricks·Software Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say
Jun 2026

Summary

Round 2 at Databricks was a grid-based coding problem with a few layers to it. Nothing too exotic on the surface, but the follow-up added enough complexity that I had to switch from coding to just describing the approach.

Questions Asked (2)

Q1

Given a 2D grid with a start, destination, obstacles, and cells labeled with transportation modes (walk, bike, car, train), each mode having its own cost and time arrays, find the fastest single-mode path from start to destination. Break ties by cheapest cost. Movement is horizontal/vertical only.

Algorithms & Data Structures
Author's notes

My first instinct was to run four separate BFS passes, one per mode, then compare results.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the grid as a weighted graph where each cell is a node and edges connect adjacent cells, with edge weights depending on the transportation mode. Since the question asks for the fastest single-mode path, run Dijkstra's algorithm separately for each mode, using time as the primary weight and cost as a tie-breaker. Compare the resulting paths across all modes to find the overall fastest, breaking ties by cost.

Pro tip: Clarify upfront whether 'single-mode' means the entire path must use one mode, and confirm tie-breaking rules (e.g., if times are equal, choose lower cost). This shows attention to detail and avoids incorrect assumptions.

1. Clarify requirements and constraints

Ask clarifying questions about single-mode interpretation, tie-breaking, and grid size to ensure you understand the problem correctly.

2. Model as a graph

Represent each cell as a node, with edges to adjacent cells. For each mode, assign edge weights based on the mode's time array, and store cost as a secondary attribute.

3. Run Dijkstra per mode

For each transportation mode, run Dijkstra's algorithm from start to destination, using time as the primary key and cost as the secondary key for tie-breaking.

4. Compare and select best path

Collect the shortest path for each mode, then select the one with minimum time; if tied, choose the one with minimum cost.

5. Analyze complexity and optimize

Discuss time and space complexity (O(M * N log(MN)) per mode) and consider optimizations like early termination or multi-source Dijkstra if needed.

Key Points to Mention

  • Dijkstra's algorithm for shortest path with non-negative weights
  • Graph representation of grid with adjacency (4-directional)
  • Tie-breaking by cost: use a priority queue that orders by (time, cost)
  • Handling obstacles: treat as blocked nodes
  • Time and space complexity analysis
  • Edge cases: unreachable destination, start equals destination, multiple modes with same time

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.

Q2

Extend the previous grid problem to allow switching transportation modes mid-path, with a penalty for each switch. Then further restrict the total number of allowed switches.

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

I did not code this one up.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a state-space search where each state includes the current cell, the current transportation mode, and the number of switches used so far. Use Dijkstra's algorithm on this expanded graph, where edge weights include the base travel cost plus a penalty when the mode changes. To enforce the switch limit, either prune states that exceed the allowed switches or add a dimension to the state for the switch count.

Pro tip: Clarify the problem constraints early: ask whether the penalty is per switch or per unit time, and whether the switch limit is a hard constraint or a soft cost. This shows you think about edge cases and trade-offs before coding.

1. Define the expanded state

Identify that the state must include the current cell, the current mode of transportation, and the number of switches used so far. This captures all necessary information to make optimal decisions.

2. Model transitions and costs

For each move, determine the cost: if staying in the same mode, cost is the base edge weight; if switching, add the penalty. Ensure the switch count increments only when the mode changes.

3. Choose the algorithm

Use Dijkstra's algorithm on the expanded graph since edge weights are non-negative. Alternatively, if the grid is small, BFS with a priority queue or dynamic programming can work.

4. Enforce the switch limit

Prune states where the switch count exceeds the allowed maximum. This keeps the state space bounded and ensures the solution respects the constraint.

5. Analyze complexity and optimize

Discuss time and space complexity: O(V * M * K) where V is number of cells, M is number of modes, and K is max switches. Consider optimizations like early termination or bidirectional search if needed.

Key Points to Mention

  • State representation: (cell, mode, switches_used)
  • Dijkstra's algorithm for non-negative weighted edges
  • Penalty application only on mode change
  • Switch limit as a hard constraint via state pruning
  • Time complexity: O(V * M * K log(V * M * K))
  • Trade-offs: memory vs. time, and potential for A* with admissible heuristic

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.