How should I practice Perfect AND Tree Leaf Updates?

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

Is Perfect AND Tree Leaf Updates associated with Pure Storage?

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

Problem · Tree

Perfect AND Tree Leaf Updates

Learn this problem

● Medium

Pure StorageFULLTIMEONSITE INTERVIEW

Problem statement

A perfect binary tree has binary values. Its leaves are given left to right in leaves, and every internal node is the bitwise AND of its two children: it is 1 exactly when both children are 1.

Process each row of operations in order. A row is ["SET", index] or ["CLEAR", index], using a zero-based leaf index. SET changes that leaf to 1; CLEAR changes it to 0. Repair every ancestor after the leaf change.

Return the root value after each operation.

Function

applyAndTreeUpdates(leaves: int[], operations: String[][]) → int[]

Examples

Example 1

leaves = [1,1,1,1]operations = [["CLEAR","2"],["SET","2"],["CLEAR","0"]]return = [0,1,0]

Clearing leaf 2 makes one ancestor and the root zero. Setting it restores an all-one tree; clearing leaf 0 makes the root zero again.

Example 2

leaves = [0,1]operations = [["SET","0"],["CLEAR","1"],["SET","1"]]return = [1,0,1]

With two leaves, the root is their AND after every update.

Constraints

1 <= leaves.length <= 131072, and leaves.length is a power of two.
Every leaf value is either 0 or 1.
1 <= operations.length <= 200000.
Every operation is SET or CLEAR followed by a valid zero-based leaf index.