Clone a Binary Tree with Random Links
Updated
Problem statement
Node i is nodes[i]=[value,leftID,rightID,randomID]. IDs are row indices, -1 means no link, and node 0 is the root. Left and right links form a binary tree containing every row. Random links may point to any node, including themselves, and may form cycles. Values may repeat.
Make an independent copy of the complete node table, preserving every value and ID-labelled link. Then change only the original node at probeIndex: set its value to replacementValue and its random link to replacementRandom. The copied table must retain its pre-probe contents.
Return a matrix of 2N rows: the first N rows are the original table after the probe, and the last N rows are the copied table after the probe. Each half uses its own ID namespace 0..N-1; do not offset the copied link IDs. This finite observation distinguishes independent row copies from a shallow outer-array copy.
Function
cloneWithProbe(nodes: int[][], probeIndex: int, replacementValue: int, replacementRandom: int) → int[][]Examples
Example 1
nodes = [[7,1,2,2],[7,-1,-1,0],[9,-1,-1,1]]probeIndex = 1replacementValue = 100replacementRandom = 2return = [[7,1,2,2],[100,-1,-1,2],[9,-1,-1,1],[7,1,2,2],[7,-1,-1,0],[9,-1,-1,1]]Original node 1 changes, while copied node 1 retains value 7 and random ID 0. Equal values on nodes 0 and 1 do not merge their identities.
Example 2
nodes = [[4,-1,-1,0]]probeIndex = 0replacementValue = 5replacementRandom = -1return = [[5,-1,-1,-1],[4,-1,-1,0]]The copied node keeps its original self-random link after the original loses that link.
Constraints
1 <= nodes.length <= 200.- Each row has exactly 4 entries.
-1000000000 <= every table entry, replacementValue <= 1000000000.0 <= probeIndex <= 199.-1 <= replacementRandom <= 199.- probeIndex and replacementRandom are smaller than nodes.length.
- Columns 1 and 2 contain -1 or valid IDs and form one acyclic root-0 binary tree containing all rows. Column 3 is -1 or a valid node ID.
More Expedia Onsite Interview questions
- Scramble StringONSITE INTERVIEW · Seen Sep 2026
- Smallest Sufficient TeamONSITE INTERVIEW · Seen Sep 2026
- Check Anagram Pairs Index by IndexONSITE INTERVIEW · Seen Oct 2025
- Fresh Oranges Left After Rotting StopsONSITE INTERVIEW · Seen Oct 2025
- Longest Increasing SubsequenceONSITE INTERVIEW · Seen Oct 2025
- Lowest Common Ancestor with Repeated and Missing ValuesONSITE INTERVIEW · Seen Oct 2025
- Shortest Substring with Exactly K OnesONSITE INTERVIEW · Seen Oct 2025
- Middle Element of a Linked ListONSITE INTERVIEW · Seen Nov 2024
- Minimum in a Rotated Sorted ArrayONSITE INTERVIEW · Seen Sep 2024
- Mirror Image Binary TreesONSITE INTERVIEW · Seen Sep 2024
Similar questions at other companies
- Top-Down Employee Reporting ForestOkta · ONSITE INTERVIEWOkta interview questions
- Find the Root of a Directed TreeAmazon · ONSITE INTERVIEW
- Everyone Under a ManagerAdobe · PHONE SCREENAdobe interview questions
- N-ary Index-Path Encoder and DecoderBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Delete Nodes and Return Forest RootsGoogle · ONSITE INTERVIEWGoogle interview questions
- In-Memory Filesystem CommandsPerplexity AI · PHONE SCREEN · ONSITE INTERVIEWPerplexity AI interview questions
- Filter Undesired Comments and Their DescendantsReddit · PHONE SCREEN · ONSITE INTERVIEWReddit interview questions
- JSON Path Lookup with Implicit Array WildcardsMongoDB · ONSITE INTERVIEWMongoDB interview questions
- Validate and Resolve Evaluation ChainsPlaid · PHONE SCREEN · ONSITE INTERVIEWPlaid interview questions
- Hierarchical Permission CheckeBay · ONSITE INTERVIEWeBay interview questions
Interview reports that mention this question
Expedia interview experiences
- Expedia Intern Final Round in 2021: 28 Experiences (Part 4 of 6)
- Expedia Intern Finals Before 2020: 14 Experiences (Part 6 of 6)
- Expedia Intern Final Round in 2020: 24 Experiences (Part 5 of 6)
- Expedia Intern Final Round in 2022: 15 Experiences (Part 3 of 6)
- Expedia Intern Final Round in 2023: 17 Experiences (Part 2 of 6)