How should I practice Subtree Access Overrides?

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

Is Subtree Access Overrides associated with Pinterest?

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

Problem · Array

Subtree Access Overrides

Learn this problem

● Hard

PinterestFULLTIMEPHONE SCREEN

Problem statement

A service has n regions numbered from 0 to n - 1. The array parent describes one rooted tree: parent[0] = -1, and for every other region v, parent[v] is its parent.

Every region initially has no access. Process the operations in order. operations[i] is paired with regions[i]:

GRANT grants access to the named region and every region in its subtree.
DENY denies access to the named region and every region in its subtree.
CHECK records whether the named region currently has access.

A later grant or denial overrides every earlier operation that applies to the same region. Equivalently, a check uses the most recent grant or denial issued at the queried region or any of its ancestors. If none exists, the result is false.

Return the boolean results of all CHECK operations in encounter order.

Function

resolveRegionAccess(parent: int[], operations: String[], regions: int[]) → boolean[]

Examples

Example 1

parent = [-1,0,0,1,1,2]operations = ["CHECK","GRANT","CHECK","CHECK","DENY","CHECK","CHECK"]regions = [3,0,4,5,1,3,5]return = [false,true,true,false,true]

The grant at the root reaches every region. The later denial at region 1 removes access only from that subtree, so region 3 is denied while region 5 remains granted.

Example 2

parent = [-1,0,0,1,1]operations = ["GRANT","DENY","CHECK","GRANT","CHECK","CHECK"]regions = [0,1,3,3,3,4]return = [false,true,false]

The denial at region 1 overrides the root grant for its subtree. Granting region 3 later restores access only there; its sibling region 4 stays denied.

Example 3

parent = [-1,0,1,2]operations = ["GRANT","DENY","CHECK","GRANT","CHECK","CHECK"]regions = [0,2,3,0,3,2]return = [false,true,true]

The denial at region 2 first overrides the earlier root grant for regions 2 and 3. The later root grant then becomes the newest applicable operation for the entire tree.

Constraints

1 <= parent.length <= 200000.
parent[0] = -1, and parent describes one valid tree rooted at region 0.
1 <= operations.length = regions.length <= 200000.
Every operation is GRANT, DENY, or CHECK.
0 <= regions[i] < parent.length.
There is at least one CHECK operation.