Google·Software Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

Jun 2026Remote

Summary

Graph algorithms question at Google for a SWE role. Pretty classic Dijkstra territory but with the twist of counting paths, not just finding the shortest distance. No frills, just code.

Questions Asked (1)

Given a weighted undirected graph with non-negative edge weights, count the total number of shortest paths between a source node and a target node. If the target is unreachable, return 0.

Algorithms & Data Structures

Author's notes

The distance part clicked fast for me since it's basically Dijkstra.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use Dijkstra's algorithm to compute shortest distances from the source to all nodes, while maintaining a count of shortest paths to each node. When relaxing an edge, if a shorter distance is found, update the distance and set the path count to the count of the predecessor; if an equal distance is found, add the predecessor's path count to the current node's count. Finally, return the path count for the target node, or 0 if unreachable.

Pro tip: Mention that path counts can grow exponentially, so use a large integer type (e.g., Python's arbitrary-precision int or Java's BigInteger) or take modulo if the problem specifies it. Also, clarify whether the graph can have zero-weight edges, as that affects the algorithm's correctness.

1. Clarify the problem and constraints

Ask about graph size, edge weight range, whether zero-weight edges exist, and if the count should be modulo something. This ensures you handle edge cases correctly.

2. Choose the right algorithm

Select Dijkstra's algorithm because it efficiently finds shortest paths in graphs with non-negative weights. Mention that BFS works only for unweighted graphs, and Bellman-Ford is overkill.

3. Design the data structures

Use a priority queue for Dijkstra, an array for distances, and an array for path counts. Initialize distances to infinity and path count of source to 1.

4. Implement the relaxation step

For each edge (u, v) with weight w, if dist[u] + w < dist[v], update dist[v] and set count[v] = count[u]. If equal, add count[u] to count[v].

5. Handle unreachable target and return result

After the algorithm, if dist[target] is still infinity, return 0; otherwise return count[target].

Key Points to Mention

Dijkstra's algorithm with a priority queue for O((V+E) log V) time complexity.
Path count propagation: when a shorter path is found, reset count; when an equal-length path is found, add counts.
Use of a large integer type or modulo to handle exponential path counts.
Handling of zero-weight edges: Dijkstra still works, but path counting may need careful ordering to avoid double-counting.
Edge cases: source equals target (should return 1 if no cycles? Actually, if source==target, the shortest path is the trivial path of length 0, so count=1), disconnected graph, and multiple shortest paths.
Space complexity: O(V) for distances and counts, plus O(V) for the priority queue.

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