Solve Array Distance and Wiki Navigation
Company: Snowflake
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
You are given two independent coding tasks. For each task, clarify edge cases, implement the function, and write meaningful test cases.
### Task 1: Minimum Distance Between a Person and a Cake
You are given a one-dimensional array `arr` where each element is one of:
- `0`: empty space
- `1`: a person
- `2`: a cake
Return the minimum absolute distance between any person and any cake. The distance between positions `i` and `j` is `abs(i - j)`.
If the array does not contain at least one person and at least one cake, return `-1`.
Example:
```text
Input: [0, 1, 0, 0, 2, 0, 1]
Output: 2
Explanation: The closest person-cake pair is at indices 4 and 6.
```
### Task 2: Minimum Clicks Between Wiki Pages
A wiki page can contain links to other wiki pages. Given a `startPage` and a `targetPage`, return the minimum number of clicks needed to navigate from `startPage` to `targetPage` by following links.
You should also implement a simulator for retrieving all outgoing links from a wiki page. For example, you may model the wiki as an in-memory directed graph and implement:
```text
getLinks(page) -> list of pages directly linked from page
```
Requirements:
- Each click follows exactly one outgoing link.
- If `startPage == targetPage`, return `0`.
- If the target page is unreachable, return `-1`.
- The graph may contain cycles, so avoid revisiting pages.
- Write tests covering reachable pages, unreachable pages, cycles, and the same start and target page.
Quick Answer: This question evaluates array-processing and graph-algorithm skills, specifically minimum-distance computation between marked elements in a one-dimensional array and shortest-path navigation in a directed link graph, plus edge-case reasoning and test-case design.
Part 1: Minimum Distance Between a Person and a Cake
Given a one-dimensional array `arr`, each element is one of: `0` for empty space, `1` for a person, and `2` for a cake. Return the minimum absolute distance between any person and any cake. The distance between indices `i` and `j` is `abs(i - j)`. If the array does not contain at least one person and at least one cake, return `-1`.
Constraints
- `0 <= len(arr) <= 10^5`
- Each `arr[i]` is one of `0`, `1`, or `2`
- Return `-1` if there is no person or no cake
Examples
Input: ([0, 1, 0, 0, 2, 0, 1],)
Expected Output: 2
Explanation: The closest person-cake pair is at indices 4 and 6, with distance 2.
Input: ([1, 2],)
Expected Output: 1
Explanation: The person and cake are adjacent.
Hints
- Scan from left to right and remember the most recent index of a person and the most recent index of a cake.
- Whenever you see a `1` or `2`, check whether the opposite type has already appeared and update the best distance.
Part 2: Minimum Clicks Between Wiki Pages
You are given a directed graph of wiki pages. Each page links to zero or more other pages. Starting from `startPage`, return the minimum number of clicks needed to reach `targetPage`, where each click follows exactly one outgoing link. If `startPage == targetPage`, return `0`. If the target page is unreachable, return `-1`. The graph may contain cycles, so your solution must avoid revisiting pages. You may simulate `getLinks(page)` by reading from the input graph.
Constraints
- `0 <= number of pages <= 10^5`
- `0 <= total number of links <= 2 * 10^5`
- Page names are strings
- The graph is directed and may contain cycles
- Pages absent from `graph` have no outgoing links
Examples
Input: ({'Home': ['A', 'B'], 'A': ['Target'], 'B': [], 'Target': []}, 'Home', 'Target')
Expected Output: 2
Explanation: One shortest path is Home -> A -> Target.
Input: ({'A': ['B'], 'B': ['C', 'A'], 'C': ['D'], 'D': []}, 'A', 'D')
Expected Output: 3
Explanation: The graph contains a cycle A -> B -> A, but the shortest route to D is A -> B -> C -> D.
Hints
- Model the wiki as an unweighted directed graph. In such graphs, breadth-first search finds the shortest path in number of edges.
- Use a `visited` set so cycles do not cause infinite loops or repeated work.