Minimum Round Trip Lengths
Reported by candidates from Microsoft's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
Microsoft reported this one in June 2026, and the first attempt usually dies on a detail: people find any cycle through a house instead of the shortest one. Minimum Round Trip Lengths gives you a directed weighted graph and asks for the cheapest closed walk from every house back to itself, or 0 if none exists. The hinted pattern is simulation, but it's really shortest paths in disguise. If you've got an OA invite and 48 hours, learn the trick below. StealthCoder sits invisibly as a safety net if you blank on the live assessment.
The problem
A traveling salesperson lives in a country that has road_nodes houses and m roads. The j-th road runs from house x[j] to house y[j] and has a length of t[j]. The roads are directional, meaning it is not possible to travel from house y[j] to house x[j] using the same road. For each house x, where 1 <= x <= road_nodes, find the minimum length of a journey that starts and ends at house x. If no such path exists for a particular house x, return 0 for that house. Note: There are no multiple roads between 2 houses. There can be a road that starts and ends at the same house. All houses may or may not be connected. Function minimumRoundTripLengths(roads_nodes: int, m: int, roads_from: int[], roads_to: int[], roads_weight: int[]) → int[] Examples Example 1 roads_nodes = 4 m = 4 roads_from = [1, 2, 3, 4] roads_to = [2, 3, 1, 3] roads_weight = [14, 23, 23, 30] return = [60, 60, 60, 0] The visible roads are 1 -> 2 with length 14, 2 -> 3 with length 23, 3 -> 1 with length 23, and 4 -> 3 with length 30. Houses 1, 2, and 3 can each travel around the directed cycle 1 -> 2 -> 3 -> 1, whose total length is 14 + 23 + 23 = 60. House 4 has no journey that returns to house 4, so its value is 0.
Reported by candidates. Source: FastPrep
Pattern and pitfall
The trick: the shortest round trip through x is the minimum over every edge u -> x of dist(x, u) + w(u, x). So run a shortest path from x to all nodes, then close the loop with an incoming edge. A self-loop at x is just a cycle of its own weight. The common pitfall is initializing dist[x] = 0 and then reading dist[x] as the answer, which always gives 0. Instead, start from x's outgoing edges, or take the min over incoming edges after Dijkstra. Another pitfall is forgetting that unreachable houses must return 0, not infinity. Dijkstra from every node costs about n * m log n, and Floyd-Warshall works for small n, where you take the min of d[x][x] with the diagonal seeded as infinity. Edges are directional, so don't mirror them. If the live OA freezes your brain, StealthCoder can surface the solution while you keep your head clear.
If you see this problem in your OA tomorrow, the play is to recognize the pattern in 30 seconds. StealthCoder buys you that recognition.
You can drill Minimum Round Trip Lengths cold, or you can hedge it. StealthCoder runs invisibly during screen share and surfaces a working solution in under 2 seconds. The proctor sees the IDE. They don't see what's behind it. Built by an Amazon engineer who passed his OA cold and still thinks the filter is broken.
Get StealthCoderRelated leaked OAs
You've seen the question.
Make sure you actually pass Microsoft's OA.
Microsoft reuses patterns across OAs. Built by an Amazon engineer who passed his OA cold and still thinks the filter is broken. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Minimum Round Trip Lengths FAQ
What's the actual trick in Minimum Round Trip Lengths?+
Treat it as a shortest cycle through each node in a directed graph. Run Dijkstra from x, then add the weight of any edge coming back into x. Take the smallest total. Seed the diagonal as infinity, not 0, or every answer collapses to 0.
Do I need Dijkstra or is Floyd-Warshall fine?+
It depends on the constraints you see. Floyd-Warshall is O(n^3) and is the shortest code to write if n is small. For larger graphs, run Dijkstra from each node. Check the node count first, then pick. Both work if you seed d[i][i] as infinity and then relax.
How do I handle houses with no round trip?+
If the best cycle length stays at infinity, output 0 for that house. In the example, house 4 has an edge out to 3 but nothing leads back to 4, so its answer is 0. Convert infinity to 0 at the very end, not during relaxation.
What edge cases should I test before submitting?+
Test a self-loop, where the answer is just that edge's weight. Test a house with only outgoing edges. Test two cycles through one house, where you need the smaller one. Also test a disconnected graph. The example with answer [60, 60, 60, 0] covers the basic cycle case.
How do I prepare for this in 48 hours?+
Write Dijkstra with a heap from memory once, then write the shortest cycle variant on top of it. Practice reading directed edge lists into an adjacency list. Spend your remaining time on the infinity versus 0 handling, since that's where first attempts fail.