Follow One-Way Links to the Endpoint Node or the Last Node Before a Loop Closes
Company: OpenAI
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
A simple network is made of nodes joined by one-way links. Each node links to at most one other node, in a single forward direction. Starting from a given node and following the links, find the endpoint of the network: the last node the walk reaches. If the walk runs into a loop instead, return the last node traversed before the loop closes.
### Function Signature
```python
def compute(start_node_id: int, from_ids: list[int], to_ids: list[int]) -> int:
```
`from_ids` and `to_ids` have the same length and describe the links: for every `i`, node `from_ids[i]` links to node `to_ids[i]`.
### Rules
- The walk starts at `start_node_id`, which counts as visited.
- If the current node has no outgoing link (its id does not appear in `from_ids`), the walk ends and the current node is the answer. In particular, if `start_node_id` has no outgoing link, the answer is `start_node_id`.
- Otherwise, look at the node the current node links to. If that target has not been visited yet, the walk moves to it and marks it visited.
- If the target has already been visited, following the link would close a loop. The walk ends without following it, and the answer is the current node, that is, the last node traversed before the loop closes.
- The loop does not have to contain `start_node_id`; the walk may pass through other nodes before it enters the loop.
### Constraints
- Every node id, including `start_node_id`, is an integer with `1 <= id < 5000`.
- Node ids are not necessarily ordered or contiguous; some ids in that range may not appear in the network at all.
- `len(from_ids) == len(to_ids)` and `0 <= len(from_ids) <= 4999`.
- The values in `from_ids` are pairwise distinct, since each node has at most one outgoing link. Several nodes may link to the same node.
- `from_ids[i] != to_ids[i]` for every `i`: no node links directly to itself.
### Examples
**Example 1**
```text
Input: start_node_id = 2, from_ids = [1, 7, 3, 4, 2, 6, 9], to_ids = [3, 3, 4, 6, 6, 9, 5]
Output: 5
```
The walk is `2 -> 6 -> 9 -> 5`. Node `5` has no outgoing link, so it is the endpoint. Every other starting node in this network also ends at `5`, for example `1 -> 3 -> 4 -> 6 -> 9 -> 5`. Node `8` does not exist in this network.
**Example 2**
```text
Input: start_node_id = 1, from_ids = [1, 2, 3], to_ids = [2, 3, 1]
Output: 3
```
The walk visits `1 -> 2 -> 3`. The link from `3` leads back to `1`, which was already visited, so the loop closes there and the answer is `3`.
**Example 3**
```text
Input: start_node_id = 7, from_ids = [7, 4, 5, 6], to_ids = [4, 5, 6, 4]
Output: 6
```
The walk visits `7 -> 4 -> 5 -> 6`. The link from `6` leads to `4`, which was already visited, so the answer is `6`. Node `7` leads into the loop but is not part of it.
Overview: Given one-way links in which every node has at most one outgoing link, follow the links from a start node and return the endpoint where the walk stops, or the last node visited before the walk would revisit a node. Tests single-successor graph traversal, visited-node bookkeeping and loop edge cases.
A simple network is made of nodes joined by one-way links. Each node links to at most one other node, in a single forward direction. Starting from a given node and following the links, find the endpoint of the network: the last node the walk reaches. If the walk runs into a loop instead, return the last node traversed before the loop closes.
Implement `compute(start_node_id, from_ids, to_ids)`. The arrays `from_ids` and `to_ids` have the same length and describe the links: for every index `i`, node `from_ids[i]` links to node `to_ids[i]`. Links may be listed in any order.
### Rules
- The walk starts at `start_node_id`, which counts as visited.
- If the current node has no outgoing link (its id does not appear in `from_ids`), the walk ends and the current node is the answer. In particular, if `start_node_id` has no outgoing link, the answer is `start_node_id`.
- Otherwise, look at the node the current node links to. If that target has not been visited yet, the walk moves to it and marks it visited.
- If the target has already been visited, following the link would close a loop. The walk ends without following it, and the answer is the current node, that is, the last node traversed before the loop closes.
- The loop does not have to contain `start_node_id`; the walk may pass through other nodes before it enters the loop.
Return the answer as an integer node id. These rules give exactly one answer for every valid input. Every id is below 5000, so all values fit in a 32-bit signed integer.
### Example 1
```text
Input: start_node_id = 2, from_ids = [1, 7, 3, 4, 2, 6, 9], to_ids = [3, 3, 4, 6, 6, 9, 5]
Output: 5
```
The walk is `2 -> 6 -> 9 -> 5`. Node `5` has no outgoing link, so it is the endpoint. Starting from `1` instead also ends at `5`: `1 -> 3 -> 4 -> 6 -> 9 -> 5`.
### Example 2
```text
Input: start_node_id = 7, from_ids = [7, 4, 5, 6], to_ids = [4, 5, 6, 4]
Output: 6
```
The walk visits `7 -> 4 -> 5 -> 6`. The link from `6` leads to `4`, which was already visited, so the walk stops and the answer is `6`. Node `7` leads into the loop but is not part of it.
### Constraints
- Every node id, including `start_node_id`, is an integer with `1 <= id < 5000`.
- Node ids are not necessarily ordered or contiguous; some ids in that range may not appear in the network at all.
- `len(from_ids) == len(to_ids)` and `0 <= len(from_ids) <= 4999`.
- The values in `from_ids` are pairwise distinct, since each node has at most one outgoing link. Several nodes may link to the same node.
- `from_ids[i] != to_ids[i]` for every `i`: no node links directly to itself.
Constraints
- Every node id, including start_node_id, is an integer with 1 <= id < 5000.
- Node ids are not necessarily ordered or contiguous; some ids in that range may not appear in the network at all.
- len(from_ids) == len(to_ids) and 0 <= len(from_ids) <= 4999.
- The values in from_ids are pairwise distinct, since each node has at most one outgoing link. Several nodes may link to the same node.
- from_ids[i] != to_ids[i] for every i: no node links directly to itself.
Examples
Input: (5, [], [])
Expected Output: 5
Explanation: Minimum valid: there are no links, so the start node has no outgoing link and is the answer.
Input: (3, [1, 2], [3, 3])
Expected Output: 3
Explanation: Degenerate: start 3 is the target of two links but has no outgoing link itself, so the walk ends at once at 3.
Hints
- Each node has at most one outgoing link, so from any node the next step is fully determined. Think about how to find a node's link target quickly when the links come in arbitrary array order.
- The walk can stop in only two ways: at a node with no outgoing link, or just before it steps onto a node it has already visited. Remember that the start node counts as visited.
- A loop does not have to pass through the start node, so watching only for a return to the start is not enough.