Katkat
Back

Decompress an encoded string

C3 AIData Scientist · Onsite
MediumData ScientistOnsiteCoding & Algorithms

Last updated

Decompress an encoded string evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Decompress an encoded string

Given an encoded string, return its decoded (decompressed) form.

Use the following encoding rule:

  • A positive integer (k) followed by a bracketed substring means the substring is repeated (k) times.
  • Encodings can be nested.

Examples:

  • Input: "3[a]2[bc]" → Output: "aaabcbc"
  • Input: "3[a2[c]]" → Output: "accaccacc"
  • Input: "2[abc]3[cd]ef" → Output: "abcabccdcdcdef"

Assume:

  • The input is valid.
  • Digits only appear as repeat counts.

Return the decoded string.

Clarifying Questions to Ask

  • Clarify input sizes, value ranges, mutability, return format, and tie-breaking.
  • State the target time and space complexity before coding.
  • Call out edge cases such as empty inputs, duplicates, invalid values, overflow, and boundary sizes.

Follow-up questions

  • How would the approach change if the input were streaming or too large for memory?
  • What invariants would you assert in production code?
  • Which tests would catch off-by-one, duplicate, or tie-breaking bugs?