Databricks·Software Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

Jun 2026Remote

Summary

Databricks software engineering interview with a pretty involved graph/algorithm design question. The problem was well-constructed but had a few layers that took me a while to untangle, especially the constraint around not using Dijkstra and keeping the final selection step in linear time without sorting.

Questions Asked (1)

You're building a city route planner over an undirected graph with N intersections and M roads. Each road has a list of allowed transportation modes (walk, bike, drive, etc.), and each mode has a fixed time and cost per edge. For each mode, find the shortest path (by edge count) from a source to a destination using only roads that allow that mode, then pick the best mode by minimizing total time first, then cost. If no mode can reach the destination, return an unreachable signal. Describe your approach, complexity, and implement it.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

The BFS part clicked pretty fast since all edges within a given mode are uniform weight, so edge count is the right thing to minimize.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify that the problem requires, for each transportation mode, a BFS over the subgraph of edges allowing that mode to find the shortest path by edge count, then compute total time and cost for that path. Compare the resulting paths across modes by minimizing time first, then cost, and return the best or unreachable. Implement by grouping edges by mode, running BFS per mode, and tracking the best path.

Pro tip: Mention that you can avoid rebuilding the graph per mode by pre-grouping edges by mode, and that BFS is optimal for unweighted edge-count shortest paths. Also note that if multiple paths have the same edge count, you should still compute time and cost for the specific path found by BFS, but if there are multiple shortest paths, you might need to consider all to find the one with minimal time/cost—clarify this ambiguity with the interviewer.

1. Clarify requirements and assumptions

Confirm that 'shortest path by edge count' means unweighted BFS, and that time and cost are summed over the edges of that path. Ask whether multiple shortest paths exist and if so, whether to optimize time/cost among them or just take any shortest path.

2. Preprocess edges by mode

Build an adjacency list for each transportation mode by iterating over all edges and adding the edge to the list for each allowed mode. This allows efficient BFS per mode without scanning all edges repeatedly.

3. Run BFS for each mode

For each mode, perform BFS from the source over the mode-specific adjacency list to find the shortest path (by edge count) to the destination. Track the path (e.g., via parent pointers) and compute total time and cost along that path.

4. Select best mode

Compare the paths from all reachable modes: first minimize total time, then total cost. If no mode reaches the destination, return an unreachable signal.

5. Analyze complexity and implement

State that preprocessing takes O(M * average modes per edge) time and O(M * average modes per edge) space. Each BFS takes O(N + M_mode) time, so total O(sum over modes (N + M_mode)) = O(K*N + M*avg_modes) where K is number of modes. Implement in code with clear data structures.

Key Points to Mention

BFS is the correct algorithm for unweighted shortest path by edge count.
Preprocessing edges by mode avoids repeated filtering and improves efficiency.
Time and cost are summed along the specific path found by BFS; if multiple shortest paths exist, clarify whether to optimize among them.
Complexity: O(K*N + M*avg_modes) time, where K is number of modes, and O(M*avg_modes) space for adjacency lists.
Edge cases: source equals destination, disconnected graph, modes with no edges, and ties in time/cost.
Implementation details: use queue for BFS, parent array to reconstruct path, and handle unreachable by returning null or a sentinel.

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