Katkat

Find Shortest Wiki Click Path

SnowflakeSoftware Engineer · Technical Screen

Last 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, 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.