Visit Every Listed Attraction Using Each Trail at Most Once
Company: Whatnot
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
A map has `n` attractions, numbered `0` to `n - 1`, joined by two-way trails. `trails[i] = [u, v]` is a trail between attractions `u` and `v`, and several trails may join the same pair of attractions.
You are given a list `targets` of attractions. Return whether a single walk exists that visits every attraction in `targets`, in any order, while using each trail at most once.
### Function Signature
```python
def can_visit_all(n: int, trails: list[list[int]], targets: list[int]) -> bool:
```
### Rules
- The walk may start at any attraction and end at any attraction.
- Each trail may be used at most once, in either direction. Two trails that join the same pair of attractions are different trails, and each can be used once.
- An attraction may be visited any number of times.
- The walk visits an attraction if it starts there, ends there or passes through it. A walk that uses no trail visits only its starting attraction.
- The order of `targets` does not matter, and a target may appear more than once.
### Constraints
- `1 <= n <= 15`
- `0 <= len(trails) <= 15`. Each trail `[u, v]` has `0 <= u, v < n` and `u != v`.
- `1 <= len(targets) <= 15`, and every target `x` satisfies `0 <= x < n`.
### Examples
**Example 1**
```text
Input: n = 4, trails = [[0, 1], [1, 2], [2, 3]], targets = [3, 0]
Output: True
```
The walk `0 -> 1 -> 2 -> 3` uses each trail once and visits both targets.
**Example 2**
```text
Input: n = 4, trails = [[0, 1], [0, 2], [0, 3]], targets = [1, 2, 3]
Output: False
```
Attractions 1, 2 and 3 each have a single trail, leading to 0. A walk can visit such an attraction only where it starts or ends, because passing through would need that trail twice, so at most two of the three can be visited.
**Example 3**
```text
Input: n = 4, trails = [[0, 1], [0, 2], [0, 3], [2, 0]], targets = [1, 2, 3]
Output: True
```
The walk `1 -> 0 -> 2 -> 0 -> 3` uses trails 0, 1, 3 and 2 in that order, each once.
Overview: Given attractions joined by two-way trails, possibly several between the same pair, decide whether a single walk can visit every attraction on a list, in any order, while using each trail at most once. It tests modeling walks on a multigraph and exhaustive search over small inputs.
Read the full Whatnot Software Engineer interview experience this question came from
A map has `n` attractions, numbered `0` to `n - 1`, joined by two-way trails. `trails[i] = [u, v]` is a trail between attractions `u` and `v`, and several trails may join the same pair of attractions.
You are given a list `targets` of attractions. Return `True` (`true` in JavaScript, Java and C++) if a single walk exists that visits every attraction in `targets`, in any order, while using each trail at most once. Otherwise return `False` (`false`).
### Rules
- The walk may start at any attraction and end at any attraction.
- Each trail may be used at most once, in either direction. Two trails that join the same pair of attractions are different trails, and each can be used once.
- An attraction may be visited any number of times.
- The walk visits an attraction if it starts there, ends there or passes through it. A walk that uses no trail visits only its starting attraction.
- The order of `targets` does not matter, and a target may appear more than once.
### Constraints
- `1 <= n <= 15`
- `0 <= len(trails) <= 15`. Each trail `[u, v]` has `0 <= u, v < n` and `u != v`.
- `1 <= len(targets) <= 15`, and every target `x` satisfies `0 <= x < n`.
- No value comes near 2^31 - 1, so 32-bit integers suffice in every language.
### Examples
**Example 1**
```text
Input: n = 4, trails = [[0, 1], [0, 2], [0, 3]], targets = [1, 2, 3]
Output: False
```
Attractions 1, 2 and 3 each have a single trail, leading to 0. A walk can visit such an attraction only where it starts or ends, because passing through it would need that trail twice, so at most two of the three can be visited.
**Example 2**
```text
Input: n = 4, trails = [[0, 1], [0, 2], [0, 3], [2, 0]], targets = [1, 2, 3]
Output: True
```
The walk `1 -> 0 -> 2 -> 0 -> 3` uses trails 0, 1, 3 and 2 in that order, each once. The two trails joining 0 and 2 are different trails, so the walk can pass through 2.
Constraints
- 1 <= n <= 15
- 0 <= len(trails) <= 15
- Each trail [u, v] has 0 <= u, v < n and u != v; several trails may join the same pair of attractions
- 1 <= len(targets) <= 15
- Every target x satisfies 0 <= x < n; targets may repeat and their order does not matter
- No value comes near 2^31 - 1, so 32-bit integers suffice
Examples
Input: (1, [], [0])
Expected Output: True
Explanation: Minimum: one attraction, no trails; a zero-trail walk starting at 0 visits the only target.
Input: (3, [[0, 1]], [2, 2, 2])
Expected Output: True
Explanation: Every target is the same isolated attraction 2, so a walk that starts there and uses no trail suffices.
Hints
- If every entry of targets names the same attraction, the walk does not need to use any trail.
- An attraction that the walk passes through is entered and left on two different trails. What does that mean for a target touched by only one trail?
- The limits are tiny (at most 15 attractions and 15 trails), so an exhaustive search is affordable if each candidate is checked quickly.