How should I practice Parent-Child Deletion Order?

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

Is Parent-Child Deletion Order associated with Google?

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

Parent-Child Deletion Order

Google● MediumFULLTIMEONSITE INTERVIEW

Learn

Problem statement

There are n resources numbered from 0 to n - 1. Each row [parent, child] in parentChild means that child must be deleted before parent.

The dependency graph is a directed acyclic graph. A resource may have more than one parent, and disconnected resources are allowed.

Return a valid deletion order containing every resource exactly once. When more than one resource can be deleted next, choose the resource with the smallest number. This tie rule makes the answer deterministic.

Function

deletionOrder(n: int, parentChild: int[][]) → int[]

Examples

Example 1

n = 5parentChild = [[0,1],[0,2],[2,3],[2,4]]return = [1,3,4,2,0]

Resources 1, 3, and 4 initially have no remaining children. Choosing the smallest available resource at each step yields [1,3,4,2,0].

Example 2

n = 4parentChild = [[0,2],[1,2],[1,3]]return = [2,0,3,1]

Deleting shared child 2 unlocks parent 0 but not parent 1, which still depends on child 3. The smallest available choice is therefore 0.

Example 3

n = 3parentChild = []return = [0,1,2]

All resources are immediately deletable, so the smallest-ID rule returns them in ascending order.

Constraints

1 <= n <= 100000
0 <= parentChild.length <= 200000
Every relation has the form [parent, child].
0 <= parent, child < n and parent != child.
The relation pairs are unique and form a directed acyclic graph.