How should I practice Merge N-Ary Trees by Key?

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

Is Merge N-Ary Trees by Key associated with LinkedIn?

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

Problem · Tree

Merge N-Ary Trees by Key

Learn this problem

● Medium

LinkedInFULLTIMEONSITE INTERVIEW

Problem statement

Two immutable rooted N-ary trees are encoded by keys1, parents1, keys2, and parents2. For either tree, keys[i] is the key of node i. The root is node 0 and has parent -1; every later node has a parent index smaller than its own index.

Perform one sequential merge. The roots have the same key and become one root. Under two already-merged parent nodes, children with the same key become one child and their descendants are merged by the same rule. A child key that appears under only one of those parents is copied with its entire subtree. Equal keys under different parent paths are different nodes and do not merge.

Return a canonical description of the merged tree as every root-to-node key path, including the root path. Join adjacent keys in a path with /, then return all paths in lexicographic order.

Function

mergeNaryTrees(keys1: String[], parents1: int[], keys2: String[], parents2: int[]) → String[]

Examples

Example 1

keys1 = ["a","b","d","c"]parents1 = [-1,0,1,0]keys2 = ["a","b","e","d"]parents2 = [-1,0,1,0]return = ["a","a/b","a/b/d","a/b/e","a/c","a/d"]

The two a/b nodes merge because both their parent path and key match. Their children d and e are both retained. The root children c and d occur in only one input tree.

Example 2

keys1 = ["r","a","x","b","k"]parents1 = [-1,0,1,0,3]keys2 = ["r","a","k","b","x"]parents2 = [-1,0,1,0,3]return = ["r","r/a","r/a/k","r/a/x","r/b","r/b/k","r/b/x"]

Keys k and x each occur below both a and b across the two trees. They stay separate because matching is relative to already-merged parent nodes.

Constraints

1 <= keys1.length, keys2.length <= 2000
keys1.length == parents1.length and keys2.length == parents2.length.
Each key contains only lowercase English letters and has length from 1 through 20.
For each tree, parents[0] == -1, and 0 <= parents[i] < i for every i > 0.
Children of the same parent have distinct keys.
keys1[0] == keys2[0].
The total length of all returned path strings fits in memory.