FastPrepFind Nodes with Invalid Parent Levels

Find Nodes with Invalid Parent Levels

Zip logoZip● EasyNEW GRADONSITE INTERVIEW
Learn

Problem statement

Each row in nodes has the form [id, parentId, level]. Every id is unique, level is a non-negative decimal integer, and an empty parentId marks a root.

A root is valid only at level 0. A non-root node is valid only when its parent ID appears in nodes and its claimed level equals its parent's claimed level plus one. Return the IDs of all invalid nodes in their original input order.

Validate each row directly against its named parent. An invalid parent's children are not automatically invalid when their own parent reference and relative level are correct.

Function

findInvalidNodes(nodes: String[][]) → String[]

Examples

Example 1

nodes = [["root","","0"],["a","root","1"],["b","root","2"],["orphan","missing","1"]]return = ["b","orphan"]

Node b should be at level 1, and orphan names a parent that is absent. The first two rows are valid.

Example 2

nodes = [["r1","","1"],["r2","","0"],["c","r2","1"]]return = ["r1"]

An empty parent marks a root, so r1 is invalid because its claimed level is not 0. The second tree is valid.

Example 3

nodes = [["child","bad-root","2"],["bad-root","","1"]]return = ["bad-root"]

The root is invalid, but child directly names that present parent and its level is exactly one greater, so invalidity does not cascade.

Constraints

  • 0 <= nodes.length <= 100000.
  • nodes[i].length == 3.
  • Each id is a distinct non-empty string.
  • Each parentId is empty or a non-empty string different from that row's id.
  • Each level is the decimal representation of an integer from 0 through 10^9.
  • The combined length of all IDs and parent IDs is at most 10^6.

More Zip problems

See Zip hiring insights
public String[] findInvalidNodes(String[][] nodes) {
    // Write your code here.
}
nodes[["root","","0"],["a","root","1"],["b","root","2"],["orphan","missing","1"]]
expected["b", "orphan"]
Checking account…