Minimum Clicks Between Wiki Pages
Problem statement
Complete the function below. The function receives the full standard input as a single string and must return the exact standard output lines for the described problem.
Problem Minimum Clicks Between Wiki Pages with Link Fetch Simulator
You have a set of wiki pages where each page may link to other pages. You must implement a link fetch simulator and then compute the minimum number of clicks needed to navigate from start to target (one click follows one outgoing link).
Tasks
Implement get_links(page): return the list of pages directly reachable from page.
Using get_links, compute the minimum clicks from start to target:
If start == target, the answer is 0
If target is unreachable, return -1
Input (for this simulator-based problem)
Line 1: integer m, number of directed links
Next m lines: two strings u v meaning a link from u to v
Last line: two strings start target
get_links(page) should behave as: return all x such that an input edge page -> x exists.
Output
One line: the minimum click count, or -1
Constraints 1 <= m <= 2*10^5
Page names are whitespace-free strings
Sample Tests (5)
Input:
5
A B
B C
A D
D C
C E
A C
Output:
2
Input:
3
A B
B C
C D
A D
Output:
3
Input:
2
A B
C D
A D
Output:
-1
Input:
1
A A
A A
Output:
0
Input:
4
A B
A C
B D
C D
A D
Output:
2
Example Input
5
A B
B C
A D
D C
C E
A C
Output
2
Function
solveMinimumWikiClicks(input: String) → String[] Complete solveMinimumWikiClicks. It has one parameter, String input, containing the full stdin payload. Return the stdout payload as an array of lines, without trailing newline characters.
Discussion follow-ups
The judged task remains the finite directed-graph simulator above. Discuss how the same shortest-click search changes when link retrieval is remote or many searches share a graph snapshot.
- Parallel BFS: process one complete distance frontier at a time, fetch its outgoing links with bounded concurrency, and atomically deduplicate newly discovered pages. Finish the current frontier before expanding the next. An arbitrary worker finishing first is not evidence of the shortest route; preserve level ordering and compare only correctly labeled distances. Treat retrieval failures separately from an empty outgoing-link list, with bounded retries and an explicit incomplete-search outcome rather than a false unreachable answer.
- Directed bidirectional search: search outgoing links from the start and incoming links from the target. The target-side search needs a reverse-link index or a complete known graph; outgoing get_links alone does not supply predecessors. Expand complete levels, compare valid forward-plus-backward distance candidates, and stop only when the remaining frontier depths cannot improve the best candidate. Following outgoing links from the target, or returning the first unsynchronized worker intersection, is not a valid general replacement.
- Caching: cache outgoing links by page and graph snapshot/version, and cache route answers by snapshot, start and target. Pin a consistent version during a search; invalidate affected entries or use a new version after link changes. A TTL is a freshness policy, not proof of exact answers for a changing graph. Do not cache an API failure as an empty page or an unreachable route. These discussion choices add no new judged input, output or network dependency.
Examples
Example 1
input = "5\nA B\nB C\nA D\nD C\nC E\nA C"return = ["2"]The returned string array must match the expected standard output lines for the sample input.
Constraints
- Use the limits and requirements stated in the prompt.