Merge Hierarchical Trees by Name
Google● MediumFULLTIMEONSITE INTERVIEWProblem statement
Two ordered rooted trees are encoded by parallel names, values, and parents arrays. Nodes are listed in preorder. The root is index 0 with parent -1; each later parent index is smaller than its child index. Sibling order is their order in the arrays.
Merge the two roots. A merged node takes its name from the first tree and its value from the second tree. For each pair of merged parents, children with the same name are paired in occurrence order and merged recursively.
Examples
Example 1
names1 = ["root","a","x","a"]values1 = [1,2,3,4]parents1 = [-1,0,1,0]names2 = ["other","a","y","a","z","b"]values2 = [10,20,30,40,50,60]parents2 = [-1,0,1,0,3,0]return = ["0:root:10","1:a:20","2:x:3","2:y:30","1:a:40","2:z:50","1:b:60"]The first and second a children pair by occurrence. Unmatched first-tree children remain before unmatched second-tree children, and the second-tree b child is appended last.
Unlock this recently reported problem
FastPrep Pro gives you full access to interview problems reported within the last week.
- Full problem statement and constraints
- 1 more worked example, explained
- Guided hints and editorial
- Run your code on real test cases
$99 billed yearly — or $19 month-to-month. Cancel anytime.