Find Shortest Wiki Click Path
Company: Snowflake
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement a function that computes the minimum number of clicks needed to navigate from one wiki page to another.
You are given two page URIs, `start_uri` and `target_uri`. The wiki can be viewed as a directed graph: if page `A` links to page `B`, then there is a directed edge from `A` to `B`.
You may use the following API:
```python
from typing import List
def get_linked_pages(uri: str) -> List[str]:
"""Returns the list of pages directly linked from the given page."""
```
Write a function:
```python
def shortest_click_distance(start_uri: str, target_uri: str) -> int:
```
Return the length of the shortest path from `start_uri` to `target_uri`, where each click follows one outgoing link.
Requirements:
- If `start_uri == target_uri`, return `0`.
- If `target_uri` cannot be reached, return `-1`.
- The graph may contain cycles.
- A page may be reachable through multiple different paths.
The goal is to return only the shortest distance, not the actual path.
Quick Answer: This question evaluates understanding of graph traversal and shortest-path concepts, testing competencies in algorithm design, handling cycles, complexity analysis, and integration with external link-retrieval APIs.
A wiki can be modeled as a directed graph where each page URI is a node, and a link from page A to page B is a directed edge A -> B. In the original interview setting, outgoing links are fetched with an API like get_linked_pages(uri). For this self-contained version, you are given the wiki graph directly as an adjacency list.
Write a function that returns the minimum number of clicks needed to navigate from start_uri to target_uri by following outgoing links.
Rules:
- If start_uri == target_uri, return 0.
- If target_uri cannot be reached, return -1.
- The graph may contain cycles.
- Multiple paths may exist; only the shortest distance matters.
- If a page does not appear as a key in the dictionary, treat it as a page with no outgoing links.
Constraints
- 0 <= number of pages in wiki_graph <= 10^5
- 0 <= total number of directed links <= 2 * 10^5
- The graph is directed and may contain cycles
- Pages may appear in link lists even if they are not keys in wiki_graph
Examples
Input: ({'/A': ['/B', '/C'], '/B': ['/D'], '/C': ['/D', '/E'], '/D': ['/F'], '/E': ['/F'], '/F': []}, '/A', '/F')
Expected Output: 3
Explanation: The shortest paths are /A -> /B -> /D -> /F and /A -> /C -> /E -> /F, both requiring 3 clicks.
Input: ({'/A': ['/B']}, '/A', '/A')
Expected Output: 0
Explanation: The start and target pages are the same, so no clicks are needed.
Hints
- This is a shortest-path problem on an unweighted graph, so think about breadth-first search.
- Mark pages as visited when you add them to the queue to avoid revisiting nodes in cycles.