Find Shortest Wiki Click Path
SnowflakeSoftware Engineer · Technical ScreenLast updated
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.
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:
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:
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, return0. - If
target_uricannot 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.
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.