Validate Evaluation Chains and Resolve Boolean Outcomes
Company: Plaid
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
A collection of evaluations forms directed chains. Each evaluation points either to another evaluation or directly to the terminal value `true` or `false`. A chain is invalid if following its pointers enters a cycle.
Determine the outcome of every evaluation, including evaluations in disconnected components.
### Function Contract
Implement `evaluate_chains(targets) -> list[int]`, where `targets` is an integer array of length `n`. Evaluation identifiers are `0` through `n - 1`.
- `targets[i] == -2` means evaluation `i` points directly to `true`.
- `targets[i] == -1` means evaluation `i` points directly to `false`.
- Otherwise, `targets[i]` is the identifier of the next evaluation.
Return an integer array of length `n` in evaluation-identifier order:
- `1` if the chain starting at that evaluation reaches `true`.
- `0` if it reaches `false`.
- `-1` if it enters a cycle, whether the starting evaluation belongs to the cycle or merely leads into it.
All evaluations are valid exactly when the returned array contains no `-1`. A valid chain that ends at `false` is different from an invalid chain.
### Constraints and Clarifications
The integer identifiers and terminal encodings are explicit interface choices for this exercise.
- `0 <= n <= 200000`.
- Each target is `-2`, `-1`, or an integer from `0` through `n - 1`; there are no missing evaluation references.
- Every evaluation has exactly one target. Several evaluations may share a target.
- Self-loops are cycles, and disconnected components must all be checked.
- For an empty collection, return `[]`; the collection has no invalid evaluations.
- Aim for `O(n)` total time and `O(n)` additional space.
### Examples
```text
targets = [1, -2, -1]
Output: [1, 1, 0]
```
Evaluation `0` reaches `true` through evaluation `1`. Evaluation `2` forms a separate chain ending at `false`.
```text
targets = [1, 2, 1, -1, 3]
Output: [-1, -1, -1, 0, 0]
```
Evaluations `1` and `2` form a cycle. Evaluation `0` leads into that cycle. Evaluations `3` and `4` remain valid and both resolve to `false`.
```hint Distinguish current paths from completed paths
Reaching a node already on the current unresolved path means something different from reaching a node whose final outcome has already been established.
```
Overview: Resolve Boolean evaluation chains, detect cycles and paths into cycles, and handle disconnected components with a linear-time graph traversal.
Read the full Plaid Software Engineer interview experience this question came from
A collection of `n` evaluations forms directed chains. Evaluation identifiers are `0` through `n - 1`, and every evaluation points to exactly one target, given by the integer array `targets` of length `n`:
- `targets[i] == -2` means evaluation `i` points directly to the terminal value `true`.
- `targets[i] == -1` means evaluation `i` points directly to the terminal value `false`.
- Otherwise `targets[i]` is the identifier of the next evaluation in the chain, an integer from `0` through `n - 1`.
Following an evaluation's pointers therefore either reaches a terminal value or enters a cycle. A chain is invalid exactly when following its pointers enters a cycle.
Implement `evaluate_chains(targets)`. Return an integer array of length `n` in evaluation-identifier order, where position `i` describes evaluation `i`:
- `1` if the chain starting at that evaluation reaches `true`.
- `0` if it reaches `false`.
- `-1` if it enters a cycle, whether the starting evaluation belongs to the cycle or merely leads into it.
Several evaluations may share a target, self-loops are cycles, and evaluations in disconnected components must all be checked. All evaluations are valid exactly when the returned array contains no `-1`; a valid chain that ends at `false` (result `0`) is different from an invalid chain (result `-1`). For an empty collection, return `[]`; such a collection has no invalid evaluations.
Every value involved fits in a signed 32-bit integer: inputs range from `-2` to `n - 1` and results are always `-1`, `0`, or `1`, so no 64-bit type is needed.
### Example 1
```text
targets = [1, -2, -1]
Output: [1, 1, 0]
```
Evaluation `0` reaches `true` through evaluation `1`. Evaluation `2` forms a separate chain ending at `false`.
### Example 2
```text
targets = [1, 2, 1, -1, 3]
Output: [-1, -1, -1, 0, 0]
```
Evaluations `1` and `2` form a cycle. Evaluation `0` leads into that cycle, so it is invalid as well. Evaluations `3` and `4` remain valid and both resolve to `false`.
Constraints
- 0 <= n <= 200000, where n is the length of targets.
- Each target is -2, -1, or an integer from 0 through n - 1; there are no missing evaluation references.
- Every evaluation has exactly one target. Several evaluations may share a target.
- Self-loops are cycles, and disconnected components must all be checked.
- For an empty collection, return []; the collection has no invalid evaluations.
- Each returned value is -1, 0, or 1; every input and output value fits in a signed 32-bit integer.
- Aim for O(n) total time and O(n) additional space.
Examples
Input: ([],)
Expected Output: []
Explanation: Empty collection: there are no evaluations, so the result is empty and the collection has no invalid evaluations.
Input: ([-2],)
Expected Output: [1]
Explanation: Smallest non-empty input: the single evaluation points directly at true, so it resolves to 1.
Hints
- Every evaluation has exactly one target, so an evaluation's outcome is fully determined by the outcome of the single evaluation or terminal it points at.
- Reaching a node that is still part of the path you are currently following means something different from reaching a node whose final outcome has already been established.
- The stated O(n) bound means each evaluation should be touched a constant number of times overall, and chains can be up to 200000 long, so avoid deep recursion.