How should I practice Part 2: Batch Access Review?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Scale AI online assessment problems in FastPrep.

Is Part 2: Batch Access Review associated with Scale AI?

FastPrep tags this as a Scale AI online assessment coding practice problem when the problem catalog has that company and stage context.

Part 2: Batch Access Review

Scale AI● HardFULLTIMENEW GRADINTERNOA

Problem statement

A secure network has n devices arranged in a delegation hierarchy. The devices have IDs from 0 to n - 1. Each device owns a key that unlocks itself and all devices below it.

The array delegatedBy describes the hierarchy: delegatedBy[i] is the device that directly grants access to device i. The root has parent -1.

The security team receives a list of access requests. Each request contains two or more device IDs. For each request, return the owner of the narrowest-scoped key that unlocks every listed device. This is the deepest common ancestor of those devices.

A device is its own ancestor.
The order of device IDs in a request does not change the answer.
The hierarchy stays the same for all requests. Preprocess it once; tracing full parent chains separately for every request may be too slow.
Return one device ID per request, in the same order as requests.

This is Part 2 of the same exercise. For a single request with two devices, try Part 1: The Narrowest Key.

Function

findSharedKeys(delegatedBy: int[], requests: int[][]) → int[]

Examples

Example 1

delegatedBy = [-1,0,0,1,1,2,2,4]requests = [[3,7],[3,5,6],[4,7],[3,4,7]]return = [1,0,4,1]

Devices 3 and 7 share key 1. Devices 3, 5, 6 span both branches of the root, so they need key 0. Device 4 is an ancestor of 7, so [4,7] needs key 4. Devices 3, 4, 7 all lie below device 1, so the last answer is 1.

Example 2

delegatedBy = [-1,0,0,1,1]requests = [[3,4],[1,3,4],[2,4]]return = [1,1,0]

Devices 3 and 4 are children of device 1. Adding device 1 to that request leaves the answer at 1, because a device is its own ancestor. Devices 2 and 4 lie in different root branches, so their narrowest shared key belongs to device 0.

Constraints

1 <= n = delegatedBy.length <= 200000.
delegatedBy describes one valid rooted tree: exactly one entry is -1, every other entry is a valid device ID, and all devices are connected without cycles.
1 <= requests.length <= 200000.
2 <= requests[i].length.
The sum of all request sizes is at most 200000.
Every device ID in a request is between 0 and n - 1, inclusive.