Google·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026

Summary

Google SWE interview with a graph traversal problem that sounds straightforward until you actually have to talk through all the edge cases out loud. Pretty standard algorithmic round but the blocked nodes wrinkle made it a bit more interesting than your typical BFS question.

Questions Asked (1)

Given a graph with a source node, find the shortest distance from that source to every other node. Some nodes are blocked and should be treated as if they don't exist. Return -1 for any node that's unreachable or blocked. Walk through your algorithm, the data structures you'd use, time and space complexity, and how your approach changes between directed and undirected graphs.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

BFS was the obvious move and I got there fast, but I fumbled a bit when they asked about directed vs undirected.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the problem constraints (e.g., edge weights, graph representation) and then propose BFS for unweighted graphs or Dijkstra for weighted graphs, treating blocked nodes as removed. Walk through the algorithm step-by-step, analyze time and space complexity, and discuss how the approach adapts for directed vs. undirected graphs.

Pro tip: Explicitly state your assumptions about edge weights and graph representation before diving into the algorithm; this shows you think about problem constraints and avoids misunderstandings. Also, mention that blocked nodes are skipped during traversal, and unreachable nodes return -1.

1. Clarify the problem

Ask about edge weights (unweighted vs. weighted), graph representation (adjacency list/matrix), and whether blocked nodes are given as a list or marked in the graph. Confirm that blocked nodes should be excluded from traversal and return -1.

2. Choose the right algorithm

For unweighted graphs, use BFS from the source; for weighted graphs with non-negative weights, use Dijkstra's algorithm. Mention that if negative weights exist, Bellman-Ford is needed, but typically not expected here.

3. Walk through the algorithm

Explain initialization: distance array with infinity, source distance 0, and a queue (BFS) or priority queue (Dijkstra). Describe how to skip blocked nodes and update distances for neighbors.

4. Analyze complexity

For BFS: O(V+E) time, O(V) space. For Dijkstra with binary heap: O((V+E) log V) time, O(V) space. Mention that blocked nodes are simply not processed, so they don't affect complexity.

5. Discuss directed vs. undirected

For undirected graphs, treat each edge as bidirectional; for directed graphs, only follow outgoing edges. The core algorithm remains the same, but adjacency list construction differs.

Key Points to Mention

BFS for unweighted graphs, Dijkstra for weighted graphs with non-negative weights
Use a distance array initialized to infinity, and a queue/priority queue for traversal
Skip blocked nodes: do not add them to the queue or process their edges
Return -1 for nodes that are unreachable or blocked
Time and space complexity: BFS O(V+E), Dijkstra O((V+E) log V), space O(V)
Directed vs. undirected: adjacency list representation and edge traversal direction

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