Route Graph Reachability with a Broken Link
Updated
Problem statement
A web app describes its pages as a route configuration, much like a front-end router: each route has a path and a list of child paths. The same path can be listed under more than one parent, and a child can point back to an earlier route, so the configuration is really a graph.
You are given routes. In each row, routes[i][0] is a route path and the remaining entries are its child paths, each written in full. Every child entry is a link from routes[i][0] to that child.
- Every path that appears anywhere in
routesis a route, even if it only ever appears as a child. A row with no children adds the route and no links. - The same path may start more than one row. Its children from all of those rows add up.
- A child may be listed more than once, and a route may list itself. Paths match only as exact text, so
/usersand/users/are different routes.
Answer every query in queries, in order. Each query is [type, from, to]:
"REACH": returntrueif you can start atfromand arrive attoby following links only from parent to child."CONNECTED": returntrueiffromandtoare connected when every link can be used in both directions."ALTERNATE":fromandtoare different routes. Break the direct link between them: remove every link fromfromtotoand every link fromtotofrom, including repeated listings. Returntrueif the two routes are still connected using links in both directions. If there is no direct link between them, nothing is removed.
Every route reaches itself and is connected to itself. A break applies only to its own query: later queries see the full configuration again.
Return a boolean array with one answer per query.
Function
answerRouteQueries(routes: String[][], queries: String[][]) → boolean[]Examples
Example 1
routes = [["/","/home","/users"],["/users","/users/list","/users/edit"],["/users/edit","/users"],["/admin","/users/list"],["/home","/users/list"],["/help"]]queries = [["REACH","/","/users/list"],["REACH","/users/list","/users"],["REACH","/admin","/home"],["CONNECTED","/admin","/home"],["CONNECTED","/help","/"],["ALTERNATE","/users","/users/edit"],["ALTERNATE","/","/users"]]return = [true,false,false,true,false,false,true]Following links from parent to child, / reaches /users/list through /users. Nothing is listed under /users/list, so it reaches no other route, and /admin only reaches /users/list, so it cannot reach /home.
With two-way links, /admin and /home are connected: /admin, /users/list, /home. /help has no links at all, so it is not connected to /.
/users lists /users/edit and /users/edit lists /users. Breaking their direct link removes both listings, and /users/edit has no other link, so the answer is false. Breaking the link from / to /users still leaves /, /home, /users/list, /users, so that answer is true.
Example 2
routes = [["/a","/b","/b"],["/b","/c"],["/c"]]queries = [["ALTERNATE","/a","/b"],["REACH","/a","/b"],["ALTERNATE","/a","/c"],["REACH","/c","/c"],["REACH","/c","/a"]]return = [false,true,true,true,false]/a lists /b twice. Breaking the direct link between them removes both listings, and /a has no other link, so the first answer is false.
The break lasted only for that query: /a still reaches /b in the second query. /a and /c have no direct link, so the third query removes nothing, and they are connected through /b.
Every route reaches itself, so /c reaches /c. /c has no children, so it cannot reach /a.
Example 3
routes = [["/x","/y"],["/y/"],["/x","/z"]]queries = [["REACH","/x","/z"],["CONNECTED","/y","/z"],["CONNECTED","/y","/y/"],["ALTERNATE","/x","/z"]]return = [true,true,false,false]/x starts two rows. Their children add up, so /x links to both /y and /z, and /y and /z are connected through /x.
/y and /y/ are different paths because only exact text matches, and /y/ has no links. Breaking the direct link between /x and /z leaves /z with no link, so the last answer is false.
Constraints
1 <= routes.length <= 20001 <= routes[i].length <= 101- The total number of strings across all rows of
routesis at most10^4. - Every path has
1to30characters: a/followed by lowercase English letters, digits,/or-. 1 <= queries.length <= 200queries[i].length == 3- Every string in
querieshas1to30characters. queries[i][0]is"REACH","CONNECTED"or"ALTERNATE", andqueries[i][1]andqueries[i][2]are paths that appear inroutes.- For an
"ALTERNATE"query,queries[i][1] != queries[i][2].
More Figma Phone Screen questions
- Rich Text Parser Part 3 (Depth Tokens)PHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Rich Text Parser Part 2 (Parse Nested Groups)PHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Rich Text Parser Part 1 (Validate Tokens)PHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Layer History with Batch Undo and RedoOA · PHONE SCREEN · Seen Sep 2026
- Recursive Display SortPHONE SCREEN · ONSITE INTERVIEW · Seen Aug 2026
- Table Selection and Color UpdatesPHONE SCREEN · ONSITE INTERVIEW · Seen Aug 2026
- Topmost Accessible NodesPHONE SCREEN · ONSITE INTERVIEW · Seen Jan 2025
- Intersection of Two RectanglesPHONE SCREEN · Seen Aug 2024
- Sparse Canvas Paint HistoryPHONE SCREEN · Seen Sep 2023
- Shell Path AutocompletePHONE SCREEN · ONSITE INTERVIEW · Seen May 2022
Similar questions at other companies
- Best Currency Round Trip Over Two DaysRippling · PHONE SCREENRippling interview questions
- Page Referrer ReachabilityAmazon · ONSITE INTERVIEW
- Reachable Nodes in a Directed GraphSoFi · ONSITE INTERVIEWSoFi interview questions
- Task Build Order and File-Change RerunsVanta · PHONE SCREEN
- Word Chain Jumps in a GridGoogle · PHONE SCREENGoogle interview questions
- Linked Merchants Within Two HopsStripe · PHONE SCREENStripe interview questions
- Resolve Variable Equations with Dependency ErrorsApplied Intuition · PHONE SCREENApplied Intuition interview questions
- Evaluate DivisionApple · PHONE SCREENApple interview questions
- Nested Substitutions with Cycle DetectionKikoff · PHONE SCREENKikoff interview questions
- Validate and Resolve Evaluation ChainsPlaid · PHONE SCREEN · ONSITE INTERVIEWPlaid interview questions