How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Snowflake.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Snowflake during technical interviews.

Find Shortest Wiki Click Path | Snowflake Coding Question

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.

Input: ({'/A': ['/B'], '/B': [], '/C': ['/D'], '/D': []}, '/A', '/D')

Expected Output: -1

Explanation: There is no directed path from /A to /D, so the target is unreachable.

Input: ({'/A': ['/B'], '/B': ['/C', '/D'], '/C': ['/A'], '/D': ['/E'], '/E': []}, '/A', '/E')

Expected Output: 3

Explanation: Although there is a cycle /A -> /B -> /C -> /A, the shortest route to /E is /A -> /B -> /D -> /E.

Input: ({'/A': ['/B', '/B'], '/B': ['/C']}, '/A', '/C')

Expected Output: 2

Explanation: Duplicate links should not affect the answer. The shortest path is /A -> /B -> /C, which takes 2 clicks. /C is not a key, so it is treated as having no outgoing links.

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.

Quick Overview

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.