Decode a Bit String With a Code Tree
Updated
Problem statement
A prefix code is stored as a binary tree with nodes numbered 0 to n - 1, and node 0 is the root. An inner node i has children left[i] and right[i] and an empty symbol[i]. A leaf has left[i] == right[i] == -1 and holds one letter in symbol[i].
The code of a letter is the path from the root to its leaf: a 0 for each step to a left child and a 1 for each step to a right child. No code is the start of another code, because letters only sit at leaves.
Decode bits: start at the root and follow one bit at a time. When you reach a leaf, write down its letter and go back to the root. Return the decoded string.
Node numbers say nothing about the shape of the tree. A child can have a smaller number than its parent.
Function
decodeBits(left: int[], right: int[], symbol: String[], bits: String) → StringExamples
Example 1
left = [1,-1,3,-1,-1]right = [2,-1,4,-1,-1]symbol = ["","a","","b","c"]bits = "0101100"return = "abcaa"Node 0 is the root. Going left (0) reaches leaf a; going right (1) reaches node 2, whose children are b (0) and c (1). So the codes are a = 0, b = 10 and c = 11. Reading 0 10 11 0 0 gives abcaa.
Example 2
left = [1,2,-1,-1,5,-1,7,-1,-1]right = [4,3,-1,-1,6,-1,8,-1,-1]symbol = ["","","t","e","","s","","x","z"]bits = "100111011100"return = "sexzt"The codes are t = 00, e = 01, s = 10, x = 110 and z = 111. The bits split as 10 01 110 111 00, which spells sexzt. Codes have different lengths, so the split is found by walking the tree, not by cutting fixed-size pieces.
Constraints
3 <= left.length <= 51left.length == right.length == symbol.length-1 <= left[i], right[i] <= left.length - 1- The arrays form one tree rooted at node 0, and node 0 is an inner node. Every inner node has two different children and
symbol[i] == "". Every leaf hasleft[i] == right[i] == -1and a one-letter lowercasesymbol[i], and no two leaves share a letter. Every node except node 0 has exactly one parent. 1 <= bits.length <= 10^4bitscontains only'0'and'1'and decodes completely: the walk is back at the root after the last bit.
More Google Onsite Interview questions
- Delete Nodes and Return Forest RootsONSITE INTERVIEW · Seen Nov 2026
- Dice-Walk Winning ProbabilityPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- First and Last Target Position in a Mountain ArrayONSITE INTERVIEW · Seen Nov 2026
- Lowest Common Ancestor in an N-ary TreePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- 0/1 Knapsack with Weight and Volume LimitsONSITE INTERVIEW · Seen Nov 2026
- Batched Subsequence Word MatchesONSITE INTERVIEW · Seen Nov 2026
- Course Schedule Cycle DetectionPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Filesystem Entity Total SizeONSITE INTERVIEW · Seen Nov 2026
- Longest Subarray Within an Absolute-Difference LimitONSITE INTERVIEW · Seen Nov 2026
- Reach a Destination Through Scheduled FlightsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
Similar questions at other companies
- Find Nodes with Invalid Parent LevelsZip · ONSITE INTERVIEWZip interview questions
- In-Memory Filesystem CommandsPerplexity AI · PHONE SCREEN · ONSITE INTERVIEWPerplexity AI interview questions
- JSON Path Lookup with Implicit Array WildcardsMongoDB · ONSITE INTERVIEWMongoDB interview questions
- Serialize and Deserialize an N-Ary TreeUber · ONSITE INTERVIEWUber interview questions
- Parse Nested HTML into a TreeApple · ONSITE INTERVIEWApple interview questions
- Filesystem Hash TreeCursor · PHONE SCREEN · ONSITE INTERVIEWCursor interview questions
- N-Ary Tree Codec OperationsLinkedIn · ONSITE INTERVIEWLinkedIn interview questions
- Dictionary Records to an Editable XML TreeSnap Inc. · ONSITE INTERVIEWSnap Inc. interview questions
- Serialize and Deserialize a Binary TreeMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Lexicographically Smallest Root-to-Leaf StringBloomberg LP · ONSITE INTERVIEWBloomberg LP interview questions