Shortest Path from an Encoded Graph
Updated
Problem statement
You are given an array of strings strArr that models a non-looping Graph.
The array is organized as follows:
- The first element is the number of nodes
N, written as a string. - The next
Nelements are the node names. A node name may contain spaces, such asBrick StreetorMain Street. - Every remaining element describes one connection in the form
nodeA-nodeB. A connection works in both directions. The graph may contain no connections.
Here, non-looping means that a connection cannot join a node to itself. Cycles involving different nodes are allowed.
Return the shortest path from the first listed node to the last listed node, joining the node names with hyphens. There will be only one shortest path. If no path connects the first and last nodes, return -1.
Function
shortestPath(strArr: String[]) → StringExamples
Example 1
strArr = ["4","A","B","C","D","A-B","B-D","B-C","C-D"]return = "A-B-D"The path A-B-D reaches the last listed node in two connections, which is shorter than going through C.
Example 2
strArr = ["7","A","B","C","D","E","F","G","A-B","A-E","B-C","C-D","D-F","E-D","F-G"]return = "A-E-D-F-G"The unique shortest route from A to G is A-E-D-F-G.
Example 3
strArr = ["5","A","B","C","D","F","A-B","A-C","B-C","C-D","D-F"]return = "A-C-D-F"Starting with A-C reaches F through D in three connections.
Example 4
strArr = ["4","X","Y","Z","W","X-Y","Y-Z","X-W"]return = "X-W"The direct connection X-W is the shortest route.
Constraints
- The encoded graph contains at least two nodes.
- Each connection joins two listed nodes and can be traversed in either direction.
- If a path exists, its shortest route is unique.
Source note: The two source slides show the full statement and the visible examples in order.
More Intuit Online Assessment questions
- Employee Promotion OpportunitiesOA · Seen Oct 2026
- Next Pascal Row CoefficientOA · Seen Oct 2026
- Parse Router LogsOA · Seen Oct 2026
- Longest Repeated Letter Block with Adjacent SwapsOA · Seen Oct 2026
- Maximum Square-Free DivisorOA · Seen Oct 2026
- Two Tribes from Taller-Person CountsOA · Seen Oct 2026
- Oldest and Youngest EmployeesOA · Seen Sep 2026
- Pressure-Isolation Shutdown OrderOA · Seen Sep 2026
- Submask Sum QueriesOA · Seen Sep 2026
- Alien DictionaryOA · Seen Sep 2026
Similar questions at other companies
- Delivery Management SystemAkuna Capital · OAAkuna Capital interview questions
- Longest Distance in a Frequency-Limited NetworkBloomberg LP · OABloomberg LP interview questions
- Find Minimum City HopsAmazon · OA
- Grid ExplorationIMC Trading · OAIMC Trading interview questions
- Shortest Route Through a Traced MazeDuolingo · OADuolingo interview questions
- Shortest Path in an Unweighted GraphPeopleStrong · OAPeopleStrong interview questions
- Drone Delivery with Battery Swap StationsCisco · OACisco interview questions
- Fire Station Response BillLinkedIn · ONSITE INTERVIEWLinkedIn interview questions
- Shortest Word Chain Between Two WordsFanatics · PHONE SCREEN
- Shortest Path Node Count Avoiding Broken NodesGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions