Count the Nodes in a Chain Reachable Only Through Left and Right Links
Company: Apple
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
A chain of nodes is linked in a line. Each node can reach only its two neighbors, the node on its left and the node on its right; there is no head pointer, no stored length and no list of all nodes. You are handed one node somewhere in the chain. Count the nodes in the whole chain.
For this console, nodes are numbered, and the nodes of several separate chains are given together. `links[i] = [left, right]` holds the numbers of node `i`'s left and right neighbors, with `-1` where there is no neighbor on that side. Starting from node `start`, return the number of nodes in the chain that contains it.
The interviewer also expected you to write your own test cases.
### Function Signature
```python
def count_chain_nodes(links: list[list[int]], start: int) -> int:
```
### Rules
- The links are consistent: for any two nodes `i` and `j`, `links[i][1] == j` exactly when `links[j][0] == i`. In words, `j` is the right neighbor of `i` exactly when `i` is the left neighbor of `j`.
- Every chain is a straight line with two ends. Following right links from any node ends at a node whose right neighbor is `-1`, and following left links ends at a node whose left neighbor is `-1`; no chain closes into a loop.
- A node whose two neighbors are both `-1` forms a chain of one node.
- The count includes `start` itself.
### Constraints
- `1 <= n <= 10^5`, where `n = len(links)`
- Each `links[i]` has exactly two entries; each entry is `-1` or an integer in `[0, n - 1]`, and never equals `i`
- `0 <= start < n`
### Examples
**Example 1**
```text
Input: links = [[-1, 1], [0, 2], [1, 3], [2, -1]], start = 2
Output: 4
```
From node 2, the left side holds nodes 1 and 0 and the right side holds node 3, so the chain is 0, 1, 2, 3.
**Example 2**
```text
Input: links = [[2, -1], [-1, 3], [4, 0], [1, -1], [-1, 2]], start = 0
Output: 3
```
Node 0 has no right neighbor; to its left are node 2 and then node 4, which has no left neighbor. The chain is 4, 2, 0. Nodes 1 and 3 form a separate chain and are not counted.
**Example 3**
```text
Input: links = [[-1, -1]], start = 0
Output: 1
```
Overview: Starting from one node of a chain in which every node links only to its left and right neighbors, count the nodes in the whole chain. It tests traversal in both directions from an arbitrary node, handling of chain ends and single-node chains, and the design of your own test cases.
Read the full Apple Software Engineer interview experience this question came from
A chain of nodes is linked in a line. Each node can reach only its two neighbors: the node on its left and the node on its right. There is no head pointer, no stored length and no list of all nodes. You are handed one node somewhere in the chain; count the nodes in the whole chain.
The nodes are numbered, and the nodes of several separate chains are given together. `links[i] = [left, right]` holds the numbers of node `i`'s left and right neighbors, with `-1` where there is no neighbor on that side. Starting from node `start`, return the number of nodes in the chain that contains `start`.
Rules:
- The links are consistent: for any two nodes `i` and `j`, `links[i][1] == j` exactly when `links[j][0] == i`. In words, `j` is the right neighbor of `i` exactly when `i` is the left neighbor of `j`.
- Every chain is a straight line with two ends. Following right links from any node ends at a node whose right neighbor is `-1`, and following left links ends at a node whose left neighbor is `-1`; no chain closes into a loop.
- A node whose two neighbors are both `-1` forms a chain of one node.
- The count includes `start` itself.
- Node numbers need not follow the order of the nodes along a chain, and nodes of other chains are not counted.
The answer is a single integer between 1 and n. Every value in the input and the output fits in a signed 32-bit integer.
Example 1:
Input: links = [[-1, 1], [0, 2], [1, 3], [2, -1]], start = 2
Output: 4
From node 2, the left side holds nodes 1 and 0 and the right side holds node 3, so the chain is 0, 1, 2, 3.
Example 2:
Input: links = [[2, -1], [-1, 3], [4, 0], [1, -1], [-1, 2]], start = 0
Output: 3
Node 0 has no right neighbor; to its left are node 2 and then node 4, which has no left neighbor. The chain is 4, 2, 0. Nodes 1 and 3 form a separate chain and are not counted.
Constraints:
- 1 <= n <= 10^5, where n = len(links)
- Each links[i] has exactly two entries; each entry is -1 or an integer in [0, n - 1], and never equals i
- 0 <= start < n
- The links satisfy the consistency and no-loop rules above
Constraints
- 1 <= n <= 10^5, where n = len(links)
- Each links[i] has exactly two entries; each entry is -1 or an integer in [0, n - 1], and never equals i
- 0 <= start < n
- The links are consistent: links[i][1] == j exactly when links[j][0] == i
- Every chain is a straight line with two ends and no loop; a node whose two neighbors are both -1 is a chain of one node
Examples
Input: ([[-1, -1]], 0)
Expected Output: 1
Explanation: Minimum valid input: n = 1, one isolated node is a one-node chain.
Input: ([[-1, -1], [-1, -1], [-1, -1], [-1, -1], [-1, -1]], 2)
Expected Output: 1
Explanation: Every node is isolated; start 2 in the middle of the array counts only itself, not n = 5.
Hints
- The count includes start itself; make sure start is counted exactly once.
- -1 means there is no neighbor on that side, while 0 is an ordinary node number.
- Only the chain that contains start is counted, and a single chain can hold all 10^5 nodes.