← Microsoft Interview Insights

Microsoft·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Apr 2026

Summary

Microsoft SWE interview with a graph problem that looked clean on the surface but had a few moving parts worth thinking through carefully.

Questions Asked (1)

Q1

Given an undirected graph where exactly one cycle exists, find the shortest distance from every node to the cycle. Nodes on the cycle should return 0.

Algorithms & Data Structures
Author's notes

I knew BFS was involved but fumbled the first step a bit.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, identify the unique cycle in the undirected graph using degree-based pruning (topological sort). Then, perform a multi-source BFS from all cycle nodes to compute the shortest distance to the cycle for every node.

Pro tip: Mention that this approach runs in O(V+E) time and O(V) space, which is optimal. Also, clarify that the graph is connected and has exactly one cycle, so the cycle is unique and all nodes are reachable from it.

1. Understand the problem and constraints

Confirm that the graph is undirected, connected, and contains exactly one cycle. The goal is to compute the shortest distance from each node to any node on the cycle.

2. Identify the cycle nodes

Use a degree-based pruning approach (similar to topological sort): repeatedly remove nodes with degree 1 and update their neighbors' degrees. The remaining nodes with degree ≥2 form the cycle.

3. Compute distances via multi-source BFS

Initialize a queue with all cycle nodes (distance 0) and perform BFS. For each neighbor not yet visited, set its distance to current distance + 1 and enqueue it.

4. Return the distances

After BFS completes, the distance array contains the shortest distance from each node to the cycle. Nodes on the cycle have distance 0.

Key Points to Mention

  • Degree-based pruning to find cycle nodes in O(V+E) time
  • Multi-source BFS from all cycle nodes simultaneously
  • Time complexity O(V+E) and space complexity O(V)
  • Handling of undirected graph edges (avoid revisiting parent)
  • Correctness: BFS guarantees shortest path in unweighted graph
  • Edge cases: graph with exactly one cycle, all nodes reachable

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