← Microsoft Interview InsightsSoftware Engineer

Microsoft·Software Engineer·Online Assessment (OA)·Intermediate

Intermediate
Jun 2026

Summary

Microsoft OA with a graph problem that looked manageable until the hidden test cases started timing out. The complexity requirements aren't spelled out anywhere so you kind of have to guess what they expect.

Questions Asked (1)

Q1

Given a weighted graph with n nodes and m edges, for each node v find the minimum-weight cycle that passes through v (visiting at least one other node before returning). Return an array where each entry is the minimum cycle weight for that node, or 0 if no cycle exists.

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

My first instinct was to just run Dijkstra from every node and call it done.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

For each node v, remove v from the graph and compute the shortest path between every pair of its neighbors; the minimum cycle through v is the minimum over all neighbors u,w of dist(u,w) + weight(v,u) + weight(v,w). This can be done efficiently by running Dijkstra from each neighbor of v on the graph without v, or by using a modified all-pairs shortest path approach. Alternatively, run Dijkstra from each node and consider the shortest cycle formed by the two shortest paths from the source to each neighbor.

Pro tip: Mention that for dense graphs, Floyd-Warshall with cycle detection might be simpler, but for sparse graphs, repeated Dijkstra from each neighbor is more efficient; also note that handling negative weights requires Bellman-Ford, but typically weights are positive.

1. Clarify assumptions and edge cases

Confirm whether the graph is directed or undirected, weights are positive, and whether self-loops or multiple edges are allowed. Discuss handling of nodes with degree less than 2 (return 0).

2. Define the cycle condition

A cycle through v must enter and leave v via two distinct edges (or the same edge if multigraph) and visit at least one other node. So it consists of two edge-disjoint paths from v to some node u, or equivalently a path between two neighbors of v that does not pass through v.

3. Choose an algorithm

For each node v, remove v and run Dijkstra from each neighbor of v to find shortest paths to all other neighbors; the minimum cycle is the minimum sum of two such paths plus the connecting edges. Alternatively, run Dijkstra from each node s and for each edge (u,v) not in the shortest path tree, consider dist(s,u)+w(u,v)+dist(v,s) as a cycle through s.

4. Analyze complexity and optimize

Naive approach: O(n * (m log n + m)) using Dijkstra from each neighbor. For sparse graphs this is acceptable. For dense graphs, consider Floyd-Warshall O(n^3) and then for each v, find min over u,w of dist(u,w)+w(v,u)+w(v,w) with u,w != v. Discuss trade-offs.

5. Implement and test

Code the chosen algorithm, ensuring to handle disconnected graphs and nodes with no cycle. Test with small graphs, including cases with multiple edges and self-loops if allowed.

Key Points to Mention

  • Cycle through v = two edge-disjoint paths from v to some node u, or a path between two neighbors of v avoiding v.
  • For each v, remove v and compute shortest paths between all pairs of its neighbors.
  • Use Dijkstra for non-negative weights; Bellman-Ford if negative weights are possible.
  • Time complexity: O(n * (m log n)) for sparse graphs using Dijkstra from each neighbor; O(n^3) for Floyd-Warshall.
  • Space complexity: O(n^2) for all-pairs distances, or O(n+m) for repeated Dijkstra.
  • Edge cases: nodes with degree < 2, disconnected graphs, self-loops (if allowed, they form a cycle of weight w(v,v)).

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