Office to Home Walk
Updated
Problem statement
A city has n junctions labeled from 0 to n - 1. Each roads[i] = [a, b] is a two-way road between junctions a and b. A woman starts at junction office and wants to reach junction home. She travels in moves, and each move has two steps:
- Chosen step: she picks any road at her current junction and walks along it. If this brings her to
home, she is done. - Random step: otherwise, she walks along a random road at her new junction, but never the road she just used. If the junction has no other road, she skips this step and stays there. If the random step brings her to
home, she is done as well.
She cannot control the random steps, so she wants a plan for her chosen steps that gets her home no matter how the random steps turn out. Return the smallest number of moves within which some plan is sure to get her home, even if every random step is as bad as possible for her. If no plan can promise that she reaches home, return -1.
Function
minimumGuaranteedMoves(n: int, roads: int[][], office: int, home: int) → intExamples
Example 1
n = 5roads = [[0,1],[1,2],[1,3],[2,4],[3,4]]office = 0home = 4return = 2Her only road from junction 0 goes to junction 1. The random step from junction 1 cannot use that road again, so it goes to junction 2 or junction 3.
Both junction 2 and junction 3 have a road to home, so on the second move she walks straight home. One move is never enough, because junction 1 has no road to home. The answer is 2.
Example 2
n = 5roads = [[0,1],[1,2],[2,3],[3,0],[0,4]]office = 1home = 4return = -1Junctions 0, 1, 2 and 3 form a loop, and home hangs off junction 0. She can only get home by starting a move at junction 0, or by a random step from junction 0.
- From junction 1, if she walks to junction 0, the random step can take her to junction 3 instead of home. If she walks to junction 2, the random step must continue to junction 3.
- From junction 3, the same thing happens the other way round, and the random step can always bring her back to junction 1.
So the random steps can keep her moving between junctions 1 and 3 forever, and the answer is -1.
Example 3
n = 6roads = [[2,5],[0,5],[1,2],[4,5],[0,3]]office = 2home = 3return = 3Home (junction 3) hangs off junction 0, and junction 0's only other road goes to junction 5. Junctions 1 and 4 are dead ends.
- Move 1: she walks from junction 2 into the dead end 1. There is no other road, so she skips the random step and stays at junction 1.
- Move 2: she walks back to junction 2. The random step cannot use the road to junction 1 again, so it must go to junction 5.
- Move 3: she walks from junction 5 to junction 0. The random step's only choice is the road to junction 3, which is home.
Walking from junction 2 straight to junction 5 is worse, because the random step can send her into the dead end 4, and from there she needs 4 more moves. No plan is sure to finish in 2 moves. If her first chosen step goes to junction 5, the random step can put her at junction 4. If it goes into the dead end 1, she is at junction 1, and from there she still needs 2 more moves. The answer is 3.
Constraints
2 <= n <= 10^40 <= roads.length <= 2 * 10^4roads[i].length == 20 <= roads[i][0], roads[i][1] <= n - 1androads[i][0] != roads[i][1]- No two roads connect the same pair of junctions.
0 <= office, home <= n - 1andoffice != home
More Nutanix Online Assessment questions
- Good SubsequencesOA · Seen Jul 2026
- Min Cost to Connect All PointsOA · Seen Jun 2026
- Digit Changes for a Multiple of 9OA · Seen Aug 2025
- Gas Station Loop StartOA · Seen Aug 2025
- Number of Players (for MTS2)OA · Seen Oct 2024
- Work Schedules (for MTS2)OA · Seen Oct 2024
- Minimum Operations to Convert ArrayOA · Seen Apr 2024
- No Adjacent CharactersOA · Seen Apr 2024
- Build a BST From a ListOA · Seen Nov 2022
- Delete Even-Valued Nodes From a Linked ListOA · Seen Nov 2022
Similar questions at other companies
- Lowest Common Ancestor with a Changing RootInfosys · OAInfosys interview questions
- Minimum Tree Diameter After Removing K LeavesMathWorks · OAMathWorks interview questions
- Minimum Numeric Code TransformationAdobe · OAAdobe interview questions
- Drone Delivery with Battery Swap StationsCisco · OACisco interview questions
- Special Diameter EndpointsAgoda · OAAgoda interview questions
- Satellite Network Message PropagationOptiver · OAOptiver interview questions
- Thread Count (Also for Infra Automation Intern)Snowflake · OASnowflake interview questions
- Avoiding the Obstacles (IMC Sydney 🦪)IMC Trading · OAIMC Trading interview questions
- Delivery Management SystemAkuna Capital · OAAkuna Capital interview questions
- Minimize CommuteDatabricks · OA · PHONE SCREENDatabricks interview questions