← BNSF Interview Insights

BNSF·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
Apr 2026

Summary

Interviewed for a software engineer role at BNSF Railway and got a graph problem that was more straightforward than I expected once I stopped overthinking it.

Questions Asked (1)

Q1

Given an undirected unweighted graph with a set of source nodes, find the shortest distance from every node to its nearest source.

Algorithms & Data Structures
Author's notes

My first instinct was to run BFS from each source separately and merge results, which would've been way slower.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Recognize this as a multi-source shortest path problem on an unweighted graph and solve it with a multi-source BFS. Initialize a queue with all source nodes at distance 0, then perform BFS to propagate distances to all reachable nodes. This runs in O(V + E) time, which is optimal for unweighted graphs.

Pro tip: Mention that multi-source BFS is equivalent to adding a super-source connected to all sources with zero-weight edges, which elegantly handles the problem. Also note that if the graph is disconnected, unreachable nodes should be marked as infinity or -1.

1. Clarify the problem and constraints

Confirm that the graph is undirected and unweighted, and ask about the number of nodes, edges, and sources. Clarify how to represent unreachable nodes (e.g., -1 or infinity).

2. Choose the algorithm

Select multi-source BFS because it efficiently computes shortest distances from multiple sources in O(V+E) time. Explain why Dijkstra or repeated BFS from each source would be less efficient.

3. Initialize data structures

Create a distance array initialized to infinity (or -1) and a queue. Set distance of each source to 0 and enqueue all sources.

4. Run multi-source BFS

While the queue is not empty, dequeue a node, and for each unvisited neighbor, set its distance to current distance + 1 and enqueue it.

5. Return and analyze

Return the distance array. Analyze time complexity O(V+E) and space complexity O(V), and discuss handling of disconnected components.

Key Points to Mention

  • Multi-source BFS is optimal for unweighted graphs with multiple sources.
  • Time complexity O(V+E) and space complexity O(V) for the queue and distance array.
  • Initialization: all sources enqueued with distance 0.
  • Handling unreachable nodes by leaving distance as infinity or -1.
  • Comparison with alternatives: Dijkstra (O(E log V)) or repeated BFS (O(S*(V+E))).
  • The super-source equivalence: adding a dummy node connected to all sources with zero-weight edges.

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