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

SeniorPrefer not to say

May 2026

Summary

Fourth and final round of a Google SWE loop, purely algorithmic. The problem was graph-based and deceptively short to describe but easy to get subtly wrong in implementation.

Questions Asked (1)

Given a directed graph and a specific node v, find the length of the shortest cycle that passes through v. Return -1 if no such cycle exists.

Algorithms & Data Structures

Author's notes

The bug I almost shipped: I marked v as visited right at the start of BFS, which completely blocks it from ever being rediscovered.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Remove node v from the graph, then run BFS from each outgoing neighbor of v to find the shortest path back to v. The shortest cycle through v is 1 + the minimum of these distances. If no path exists, return -1.

Pro tip: Clarify whether the graph is unweighted (BFS) or weighted (Dijkstra), and mention that the cycle must be simple (no repeated nodes) to avoid trivial cycles. Also, consider edge cases like self-loops or multiple edges.

1. Clarify assumptions

Confirm if the graph is directed, unweighted or weighted, and whether cycles are simple. Ask about constraints on graph size and edge weights.

2. Remove v and initialize

Temporarily remove node v from the graph to prevent trivial cycles. Initialize a variable to track the minimum cycle length.

3. BFS from each outgoing neighbor

For each neighbor u of v, run BFS (or Dijkstra if weighted) from u to find the shortest path back to v without passing through v again.

4. Compute cycle length

For each path found, the cycle length is 1 (edge v->u) plus the path length from u to v. Keep the minimum over all neighbors.

5. Return result

If no cycle is found, return -1; otherwise, return the minimum cycle length.

Key Points to Mention

Breadth-First Search (BFS) for unweighted graphs to find shortest paths.
Dijkstra's algorithm for weighted graphs with non-negative weights.
Removing node v to avoid trivial cycles and ensure the cycle is simple.
Time complexity: O(V+E) for unweighted, O(E log V) for weighted per neighbor, total O(deg(v)*(V+E)) or O(deg(v)*E log V).
Edge cases: self-loops, multiple edges, disconnected graphs, and no cycle.
Space complexity: O(V) for BFS queue and visited set.

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