How should I practice Independent Level Iterators Over a Shared Binary Tree?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Google phone screen problems in FastPrep.

Is Independent Level Iterators Over a Shared Binary Tree associated with Google?

FastPrep tags this as a Google phone screen coding practice problem when the problem catalog has that company and stage context.

Independent Level Iterators Over a Shared Binary Tree

Google● MediumNEW GRADPHONE SCREEN

Learn

Problem statement

A read-only binary tree is encoded by a node table nodes. Row i is [value, leftIndex, rightIndex], row 0 is the root, and -1 means that a child is absent.

Several independent streaming iterators share this tree. The array iteratorIds describes calls to next(). The first occurrence of an ID creates an iterator positioned before the root level. Each call returns the next level's values from left to right. Calls after that iterator is exhausted return an empty array.

Return one output row per call. Iterators must keep independent traversal state and must not precompute the complete traversal.

Function

sharedLevelIteratorOutputs(nodes: int[][], iteratorIds: int[]) → int[][]

Examples

Example 1

nodes = [[1,1,2],[2,3,4],[3,-1,5],[4,-1,-1],[5,-1,-1],[6,-1,-1]]iteratorIds = [0,0,1,0,1,1,0]return = [[1],[2,3],[1],[4,5,6],[2,3],[4,5,6],[]]

Iterator one starts later but traverses the same immutable tree independently.

Example 2

nodes = [[9,-1,-1]]iteratorIds = [2,2,2]return = [[9],[],[]]

The iterator is exhausted after the root level.

Example 3

nodes = []iteratorIds = [0,1]return = [[],[]]

Every iterator over an empty tree is immediately exhausted.

Constraints

0 <= nodes.length <= 200000.
Each node row has exactly three integers, and every nonnegative child index is valid.
Every node is reachable exactly once from row 0 when the tree is nonempty.
0 <= iteratorIds.length <= 200000, and every ID is nonnegative.
The total number of returned node values across all calls is at most 200000.