How should I practice Uniformly Sample a Node from a Large Tree?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Meta onsite interview problems in FastPrep.

Is Uniformly Sample a Node from a Large Tree associated with Meta?

FastPrep tags this as a Meta onsite interview coding practice problem when the problem catalog has that company and stage context.

Uniformly Sample a Node from a Large Tree

Meta● MediumFULLTIMEONSITE INTERVIEW

Learn

Problem statement

You are given a rooted tree whose nodes are numbered from 0 to n - 1. Node 0 is the root, and children[u] lists the children of node u in traversal order.

Visit the nodes in depth-first preorder without first copying all nodes into a flat list or computing subtree sizes. At the i-th visited node (using zero-based i), draws[i] is a recorded uniformly chosen integer from 0 through i, inclusive. If the draw is 0, replace the one-node sample with the current node; otherwise retain the earlier sample.

Return the sampled node number after visiting every node. The recorded draws make one run deterministic for judging; with genuinely uniform independent draws, the described one-pass rule chooses each node with probability 1/n. Use an iterative traversal so a very deep tree does not depend on the call stack.

Function

sampleUniformTreeNode(children: int[][], draws: int[]) → int

Examples

Example 1

children = [[1,2],[3],[],[]]draws = [0,1,0,2]return = 3

The preorder is 0, 1, 3, 2. The draw at visit index 2 is 0, so node 3 replaces the earlier sample. The last draw is not 0.

Example 2

children = [[1,2,3],[],[],[]]draws = [0,0,1,0]return = 3

Nodes are visited as 0, 1, 2, 3. Draws of 0 select nodes 0, 1, and finally 3.

Example 3

children = [[]]draws = [0]return = 0

The only node is the root, and its only valid draw is 0.

Constraints

1 <= n = children.length <= 100000.
children defines a valid rooted tree: every node other than 0 occurs in exactly one child list, node 0 occurs in none, and all nodes are reachable from 0.
Child lists contain no duplicate node numbers, and the sum of their lengths is n - 1.
draws.length == n, and 0 <= draws[i] <= i for every i.