FastPrepDecode a Bit String With a Code Tree
Problems/Decode a Bit String With a Code Tree

Decode a Bit String With a Code Tree

Google logoGoogle● EasyFULLTIMEONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: A 2026 entry for a Google L4 machine learning engineer onsite lists a coding task among its final-round questions. It has only a short title about tree-based decoding. The free preview was the only readable part, and it adds nothing more.

Two readings fit. One turns a bit string back into letters with a prefix-code tree, as in Huffman coding. The other expands a nested encoded string by walking its parse tree. This version uses the prefix-code reading. The tree comes as node arrays, 0 means left, and 1 means right. Decoding restarts at the root after each letter, and the bits always decode completely. The limits are our choice.

Our version is about 45% the same as the reported question.

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) → String

Examples

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 <= 51
  • left.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 has left[i] == right[i] == -1 and a one-letter lowercase symbol[i], and no two leaves share a letter. Every node except node 0 has exactly one parent.
  • 1 <= bits.length <= 10^4
  • bits contains 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

Interview reports that mention this question

  • Google SWE III ML Interviews: 11 Experiences (Part 1 of 3)

Google interview experiences

  • Google L4 SWE Phone Screen: 1 Experience
  • Google ML Engineering Manager Onsite: 1 Experience
  • Google Experienced SWE First Round and Onsite: 1 Experience
  • Google AI Coding Interview and AI OA: 2 Experiences
  • Google SWE Intern Interview Results Timeline: 13 Experiences
All Google interview questionsSee Google hiring insights
Saved
class Solution {
    public String decodeBits(int[] left, int[] right, String[] symbol, String bits) {
        // Write your code here.
    }
}
Checking account…