Google·Software Engineer·Onsite - Coding / Algorithms·Intermediate

Intermediate

May 2026

Summary

Google SWE coding round, one graph problem that looked familiar but had a small twist on the edge weights that nearly tripped me up.

Questions Asked (1)

You have n nodes labeled 1 through n and a list of directed edges, each with a travel time. Given a starting node, find the minimum time for a signal to reach every node. Return -1 if some nodes are unreachable.

Algorithms & Data Structures

Author's notes

Recognized it as a shortest path problem pretty fast, went with Dijkstra.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a single-source shortest path on a directed graph with non-negative edge weights. Use Dijkstra's algorithm with a min-heap to compute the shortest time from the start node to all other nodes, then return the maximum of these times or -1 if any node is unreachable.

Pro tip: Clarify edge cases upfront: if n=1, return 0; if the graph is disconnected, return -1. Also, mention that Dijkstra's algorithm is optimal here because edge weights are non-negative, and discuss potential optimizations like early termination if all nodes are reached.

1. Clarify the problem and constraints

Confirm that edge weights are non-negative, the graph is directed, and that we need the minimum time for the signal to reach all nodes. Ask about input size to determine if Dijkstra's is efficient enough.

2. Choose the algorithm

Select Dijkstra's algorithm because it efficiently finds shortest paths from a single source in a graph with non-negative weights. Mention that BFS would work only if all weights were equal.

3. Implement Dijkstra's algorithm

Initialize distances to infinity, set the start node's distance to 0, and use a min-heap to repeatedly extract the node with the smallest tentative distance and relax its outgoing edges.

4. Compute the result

After the algorithm completes, find the maximum distance among all nodes. If any node still has infinite distance, return -1; otherwise, return that maximum.

5. Analyze complexity and edge cases

State the time complexity O((n + m) log n) using a binary heap, where n is the number of nodes and m is the number of edges. Discuss edge cases like n=1, disconnected graphs, and zero-weight edges.

Key Points to Mention

Dijkstra's algorithm is suitable for non-negative edge weights; if negative weights were possible, Bellman-Ford would be needed.
Use a priority queue (min-heap) to efficiently extract the node with the smallest distance.
Track visited nodes to avoid reprocessing and ensure O((n + m) log n) time complexity.
After computing shortest paths, the answer is the maximum distance; if any node is unreachable, return -1.
Edge cases: single node (return 0), disconnected graph (return -1), and zero-weight edges (handled correctly by Dijkstra).
Space complexity is O(n + m) for storing the graph and distances.

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