← Google Interview InsightsMachine Learning Engineer

Google·Machine Learning Engineer·Technical Phone Screen·Senior

Senior
Jun 2026

Summary

Google ML Engineer interview with a graph problem that felt straightforward until the follow-up flipped the whole thing. Classic algo round, nothing too surprising on the surface.

Questions Asked (2)

Q1

Given a weighted graph, determine whether a source node can reach a target node, and if so, return the shortest distance between them.

Algorithms & Data Structures
Author's notes

Pretty much a direct Dijkstra problem.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify graph properties (directed/undirected, non-negative weights) and then apply Dijkstra's algorithm with a priority queue to find the shortest path from source to target, stopping early if the target is reached. If negative weights are possible, use Bellman-Ford or mention that Dijkstra's is invalid.

Pro tip: Emphasize early termination when the target is popped from the priority queue, and discuss handling unreachable nodes by returning a sentinel like -1 or infinity.

1. Clarify graph assumptions

Ask about directed vs. undirected, weight ranges (negative?), and graph size to choose the right algorithm.

2. Choose algorithm

For non-negative weights, select Dijkstra's algorithm; for negative weights, use Bellman-Ford or mention that Dijkstra's is unsuitable.

3. Implement with priority queue

Use a min-heap to efficiently extract the node with the smallest tentative distance, updating distances of neighbors.

4. Early termination and unreachable handling

Stop when the target is popped from the heap; if the heap empties without reaching the target, return a sentinel indicating unreachable.

5. Analyze complexity

State time complexity O((V+E) log V) with a binary heap and space complexity O(V+E) for the graph and distance array.

Key Points to Mention

  • Dijkstra's algorithm for non-negative weights
  • Priority queue (min-heap) implementation
  • Early termination when target is reached
  • Handling unreachable target (return -1 or infinity)
  • Time and space complexity analysis
  • Alternative algorithms for negative weights (Bellman-Ford)

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

Q2

Follow-up: how would your approach change if the path from source to target must pass through a specific intermediate node?

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

This is where I fumbled a bit.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Explain that the problem decomposes into finding the shortest path from source to intermediate node and from intermediate to target, then combining them. Discuss how this changes the algorithm choice and complexity, and mention any caveats like avoiding cycles or reusing nodes.

Pro tip: Emphasize that the decomposition is valid only if the shortest path from source to target through the intermediate node does not revisit nodes; in graphs with negative edges, this may require more careful handling. Also, mention that running Dijkstra twice is often more efficient than modifying the graph.

1. Decompose the problem

State that the shortest path from source to target that passes through a specific node can be found by computing the shortest path from source to the intermediate node and from the intermediate node to the target, then summing the distances.

2. Choose appropriate algorithms

For non-negative weights, use Dijkstra's algorithm from the source to the intermediate and from the intermediate to the target. For negative weights, consider Bellman-Ford or Floyd-Warshall, noting that the decomposition may fail if negative cycles exist.

3. Handle constraints and edge cases

Discuss whether the paths can share nodes (other than the intermediate) and how to avoid cycles. Mention that if the graph is directed, the direction matters; if undirected, the two runs are symmetric.

4. Analyze complexity

Compare the complexity of running two shortest-path searches versus a modified single search. For Dijkstra with a binary heap, it's O((V+E) log V) per run, so overall O((V+E) log V) for two runs, which is efficient.

5. Consider alternative approaches

Mention that one could also modify the graph by splitting the intermediate node or adding a large weight, but the two-run approach is simpler and often more efficient.

Key Points to Mention

  • Decomposition into two shortest path problems: source to intermediate and intermediate to target.
  • Algorithm choice: Dijkstra for non-negative weights, Bellman-Ford for negative weights, and Floyd-Warshall for all-pairs if needed.
  • Complexity analysis: two Dijkstra runs is O((V+E) log V) with a binary heap, which is efficient.
  • Edge cases: negative cycles, directed vs undirected graphs, and whether paths can share nodes.
  • Alternative: modifying the graph (e.g., node splitting) but noting it's often unnecessary.
  • Practical consideration: in ML engineering, such graph problems may arise in model pipelines or knowledge graphs, so efficiency matters.

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