Reconstruct the Root Stream
Updated
Problem statement
A perfect binary tree distributes a root data stream to its leaves. The internal nodes appear in level order in distributionNodes:
- Type
0is a splitting node. It sends the first half to its left child and the remaining half to its right child. For an odd-sized stream, the left child receives one more item. - Type
1is a parallelizing node. It sends items at positions0, 2, 4, ...to its left child and items at positions1, 3, 5, ...to its right child.
streamAtLeaves lists the streams received by the leaves from left to right. Rows may be padded with -1; ignore those padding values.
Reconstruct and return the original stream at the root.
Function
reconstructRootStream(distributionNodes: int[], streamAtLeaves: int[][]) → int[]Examples
Example 1
distributionNodes = [0,1,1]streamAtLeaves = [[1,3],[2,4],[5,7],[6,8]]return = [1,2,3,4,5,6,7,8]Each type-1 child pair reconstructs to [1,2,3,4] and [5,6,7,8]. The type-0 root concatenates those halves.
Example 2
distributionNodes = [1,0,0]streamAtLeaves = [[10],[20],[30],[40]]return = [10,30,20,40]The type-0 nodes reconstruct [10,20] and [30,40]. Alternating those at the type-1 root gives [10,30,20,40].
Constraints
1 <= distributionNodes.length <= 10^4.- Every entry of
distributionNodesis0or1. - The number of leaf rows equals
distributionNodes.length + 1. - The total number of non-padding values is at most
10^6. - Every stream value is positive;
-1is reserved for padding.
More Arcesium Online Assessment questions
- City Infection NumberOA · Seen Jul 2025
- Minimum Tunnel Crossing TimeOA · Seen Jul 2025
- Product of Subset MaximaOA · Seen Jul 2025
- Add DigitsOA · Seen Aug 2023
- Binary Tree Maximum Path SumOA · Seen Aug 2023
- Detect a Cycle in Directed Hate RelationshipsOA · Seen Aug 2023
- Reverse First K Characters in Every 2K BlockOA · Seen Aug 2023
- Robo Data Sharing DirectionOA · Seen Jul 2023
- Capital Gains Tax from TradesOA · Seen Feb 2021
- K-th Character in an Infinite StringOA · Seen Aug 2020
Similar questions at other companies
- Render a Comment HierarchyAmazon · ONSITE INTERVIEW
- Render a Stable Comment HierarchyBobyard · PHONE SCREEN
- Subtree Access OverridesPinterest · PHONE SCREENPinterest interview questions
- Capping Portfolio WeightsCapstone Investment Advisors · OA
- Sum of Binary Tree Boundary NodesSnowflake · OA · PHONE SCREENSnowflake interview questions
- Repeated Mirror XORMathWorks · OAMathWorks interview questions
- Stacked Item and Category DiscountsPalantir · OAPalantir interview questions
- Stabilize Student Test ScoresVirtu Financial · OAVirtu Financial interview questions
- Compress Editor Actions into Operational Transform OperationsReplit · OA · PHONE SCREEN · ONSITE INTERVIEW
- Minimize Task Resource ConsumptionNVIDIA · OANVIDIA interview questions