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

IntermediatePrefer not to say

May 2026Remote

Summary

Microsoft OA with a graph problem that looked manageable at first glance but has some real complexity hiding in the edge cases. The approach matters a lot because the hidden test cases apparently punish naive solutions hard.

Questions Asked (1)

Given a weighted graph with n nodes and m edges, for each node v find the minimum-weight cycle that starts and ends at v while visiting at least one other node. Return an array where each index holds the answer 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, but that falls apart because you have to be careful not to reuse the edge you came in on.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

For each node v, remove v and compute the shortest path between each pair of its neighbors; the minimum cycle through v is the minimum over neighbors u,w of dist(u,w) + weight(v,u) + weight(v,w). To optimize, run Dijkstra from each node on the graph without that node, or use a modified Floyd-Warshall that tracks the minimum cycle through each intermediate node.

Pro tip: Mention that the problem is essentially finding the shortest cycle through each vertex, and that for dense graphs a modified Floyd-Warshall is O(n^3) while for sparse graphs running Dijkstra from each node is O(n(m log n)). Discuss the trade-off based on graph density.

1. Clarify the problem and constraints

Confirm that cycles must have at least 3 nodes (since visiting at least one other node implies a cycle of length >= 3 in a simple graph). Ask about graph properties: directed/undirected, positive weights, n and m bounds.

2. Brute-force approach and its complexity

For each node v, remove v and compute all-pairs shortest paths among its neighbors. The minimum cycle through v is min_{u,w in N(v)} dist(u,w) + w(v,u) + w(v,w). This is O(n * (m log n + n^2)) if using Dijkstra per node, or O(n^3) with Floyd-Warshall.

3. Optimize with Floyd-Warshall variant

Use Floyd-Warshall where before updating with intermediate node k, consider cycles through k: for each pair (i,j) with i,j < k, cycle weight = dist[i][j] + w(i,k) + w(k,j). Update answer for k. This finds the shortest cycle through each node in O(n^3).

4. Handle edge cases and return results

If no cycle exists for a node, return 0. Ensure cycles are simple (no repeated vertices except start/end). Consider disconnected graphs and nodes with degree < 2.

5. Analyze trade-offs and discuss alternatives

Compare the Floyd-Warshall variant (O(n^3), good for dense graphs) with running Dijkstra from each node (O(n(m log n)), better for sparse graphs). Mention that for undirected graphs, the shortest cycle through v can be found by removing v and finding the shortest path between any two neighbors.

Key Points to Mention

The problem reduces to finding the shortest cycle through each vertex, which can be solved by considering each vertex as the 'highest' node in the cycle.
Floyd-Warshall can be adapted to track the minimum cycle through each intermediate node by checking cycles before updating distances with that node.
For sparse graphs, running Dijkstra from each node after removing the target node is more efficient than Floyd-Warshall.
Edge cases: nodes with degree less than 2 cannot be part of a cycle; disconnected components; zero-weight edges (if allowed).
Time complexity: O(n^3) for Floyd-Warshall variant, O(n(m log n)) for Dijkstra-based approach; space complexity O(n^2) for distance matrix.
The answer for each node is the minimum over all cycles containing that node; if none, return 0.

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