43 — LLD: Decoder Class (Decode String, but as OOP)

Google context: This is LC 394 — "3[a2[c]]" -> "accaccacc" — dressed as an OOP problem. The algorithmic portion is well-known. The LLD twist is: "design a Decoder class so that tomorrow we can add run-length encoding, and next week add Huffman." The signal is whether you can resist cramming everything into one method and instead express the algorithm behind a polymorphic interface. Every piece of duplication you leave behind is one the interviewer will poke at.

Understanding the Problem

You need a class that decodes strings of the form k[encoded_string], where k is a positive integer and encoded_string is any valid encoded string (possibly nested). "3[a2[c]]" decodes to "accaccacc". The OOP layer on top: the decoder should be one implementation of a broader Decoder interface, so the system can support other encoding schemes without a rewrite.

What is this system?

It is a string transformation library. The primary encoding is the LeetCode 394 repetition grammar — k[...]. The library should accept a pluggable decoder and expose a consistent API. The interviewer's follow-ups are always the same: "what if we want run-length encoding instead?", "what about Huffman?", "what if the input is malformed?" Your design should answer all three with code diffs measured in lines, not files.

Requirements

Clarifying Questions

You: The input grammar is k[encoded]. Can k be multiple digits?

Interviewer: Yes. 12[ab] is valid.

You: Can k be zero or negative?

Interviewer: Treat k >= 1. Zero or negative is malformed.

You: Are nested groups arbitrary depth?

Interviewer: Yes. 2[a3[b2[c]]] should work.

You: Can letters appear outside brackets? "abc3[d]e"?

Interviewer: Yes. They decode as themselves.

You: What about unmatched brackets, or letters in place of k?

Interviewer: Malformed input. Throw a clear exception.

So we need explicit error handling. A malformed pattern cannot silently return garbage.

You: Should the class decode in one call, or stream?

Interviewer: One-shot decode for now. decode(string) -> string.

You: You mentioned other encodings — run-length encoding, Huffman. Do I need to implement those today?

Interviewer: Just the repetition one. But design so adding RLE takes minimal change.

You: Case sensitivity? Unicode?

Interviewer: ASCII letters only. Lower and upper case both valid, treat them literally.

Final Requirements

Implement Decoder.decode(input) -> string for the k[...] grammar, supporting arbitrary nesting.
Bare letters outside brackets decode as themselves.
Multi-digit k is supported.
Malformed input raises a specific exception type (DecodingException) with a useful message.
The design accommodates additional decoders (RLE, Huffman stub) via a Decoder interface.
A factory or registry maps format names to implementations.

Out of scope: Streaming, incremental decoding, Unicode normalization, performance tuning beyond O(n) for the repetition decoder.

Deferred tradeoffs: We implement the repetition decoder both iteratively (stack-based) and recursively, and call out when each is preferable. Recursion is cleaner; iteration is safer for adversarial input depth.

Core Entities and Relationships

Decoder — the polymorphic interface. One method: decode(input) -> string.
RepetitionDecoder — LC 394. Stack-based implementation.
RunLengthDecoder — a3b2 -> aaabb. Much simpler; included to demonstrate extensibility.
HuffmanDecoder — stub; real Huffman needs a code table, not fit for the same constructor signature. We show how to wedge it in.
DecoderFactory — maps format names to decoder instances.
DecodingException — one exception type with a descriptive message and the offending position.

Entity	Responsibility
`Decoder`	Interface — `decode(input) -> string`
`RepetitionDecoder`	Decodes `k[...]` grammar
`RunLengthDecoder`	Decodes `a3b2` grammar
`HuffmanDecoder`	Decodes a bitstream with a preloaded code table
`DecoderFactory`	Returns the right decoder for a given format name
`DecodingException`	Signals malformed input with position and reason

The factory keeps the caller decoupled from concrete classes. That makes it one more thing that can be configured externally — useful when deciding which decoder to use is data-driven.

Class Design

Decoder (Interface)

interface Decoder {
    String decode(String input) throws DecodingException;
}

One method, no state. That is deliberate — decoders should be reusable and thread-safe.

RepetitionDecoder

State: None. Pure function.

Methods:

decode(input) — the public entry point. Delegates to the stack-based implementation.

RunLengthDecoder

State: None.

Methods:

decode(input) — parses alternating letter-count pairs.

DecoderFactory

State: registry: Map<String, Decoder>

Methods:

register(name, decoder) — registers a decoder under a name.
get(name) -> Decoder — returns the decoder; throws if unknown.

The factory is intentionally minimal. No DI framework, no reflection. A static registry or a constructor-built map is enough.

DecodingException

State: message, position, input.

Design decisions worth surfacing:

Why is Decoder stateless? Because the input is passed to decode directly. A stateful decoder (e.g., one that accumulates configuration) would be a separate "DecoderBuilder" or a constructor argument — but for the LC 394 grammar, no configuration is needed.
Why a factory rather than a switch at the call site? Because the set of decoders is the exact axis of change the interviewer keeps hinting at. Centralizing the "which decoder for which format" mapping in one class means adding a new decoder is one register() line.
Why does HuffmanDecoder break the pattern (because it needs a code table)? Real Huffman decoding requires a preloaded code table — that is configuration. Either you pass the table at construction time, or decode takes a richer input type. We cover both options in the extensibility section.

Design principles:

Strategy Pattern — Decoder is the strategy, DecoderFactory is the strategy selector.
Open/Closed — existing decoders never change when a new one is added.
Fail-Fast — malformed input throws at the first inconsistency, with position information, not silently at the end.

Implementation

Core Method: `RepetitionDecoder.decode(input)` — stack version

Steps:

Maintain two stacks: a countStack of integers and a stringStack of partial results. Also a current StringBuilder and a currentCount integer.
Scan the input character by character:
- If digit: currentCount = currentCount * 10 + digit.
- If [: push currentCount and current onto their stacks. Reset both.
- If ]: pop count, pop prev. Replace current = prev + (current repeated count times).
- Otherwise (letter): append to current.
At the end, both stacks must be empty. Otherwise, malformed.

Edge cases:

Input starts with ] — no prior [ to match.
Input ends with unclosed [.
Digit followed by non-[ character (e.g., 3a[b]) — malformed.
0[abc] — malformed because we require k >= 1.
Empty input — return empty.

Core Algorithm: why stack over recursion

Bad: Write a recursive descent parser in 50 lines with three states. Works, but the recursion depth equals the nesting depth. Adversarial input could blow the JVM stack.

Good: Recursive descent with clean grammar rules. For most inputs this is fine. Readable, explicit about the grammar.

Great: Iterative stack-based approach. Heap-allocated stacks, no recursion limit. O(n) time, O(n) space. Works for any nesting depth the heap can hold. This is what production decoders use.

I ship the stack version. It is the idiomatic LC 394 solution and avoids the recursion-limit footgun.

Verification

Input: "3[a2[c]]"

Char	`current`	`currentCount`	`stringStack`	`countStack`	Notes
`3`	`""`	`3`	`[]`	`[]`	accumulating count
`[`	`""`	`0`	`[""]`	`[3]`	push and reset
`a`	`"a"`	`0`	`[""]`	`[3]`	letter
`2`	`"a"`	`2`	`[""]`	`[3]`	accumulating count
`[`	`""`	`0`	`["", "a"]`	`[3, 2]`	push and reset
`c`	`"c"`	`0`	`["", "a"]`	`[3, 2]`	letter
`]`	`"acc"`	`0`	`[""]`	`[3]`	pop 2, prev="a", current = "a" + "c"*2 = "acc"
`]`	`"accaccacc"`	`0`	`[]`	`[]`	pop 3, prev="", current = "" + "acc"*3 = "accaccacc"

Final: "accaccacc". Stacks empty. Correct.

Malformed input: "3[ab"

Walk through: we push at [, read ab, end of input. countStack still contains 3 — not empty. Throw DecodingException("Unclosed '[' at position 1", position=1).

Complete Code Implementation

JavaC++TypeScript

java

import java.util.*;

// --- interface ---
public interface Decoder {
    String decode(String input) throws DecodingException;
}

// --- exception ---
public final class DecodingException extends RuntimeException {
    private final int position;
    public DecodingException(String message, int position) {
        super(message + " (position " + position + ")");
        this.position = position;
    }
    public int position() { return position; }
}

// --- repetition decoder ---
public final class RepetitionDecoder implements Decoder {
    @Override
    public String decode(String input) {
        if (input == null) throw new DecodingException("null input", 0);
        Deque<Integer> countStack = new ArrayDeque<>();
        Deque<StringBuilder> stringStack = new ArrayDeque<>();
        StringBuilder current = new StringBuilder();
        int count = 0;

        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);
            if (Character.isDigit(c)) {
                count = count * 10 + (c - '0');
            } else if (c == '[') {
                if (count <= 0) throw new DecodingException("'[' without positive count", i);
                countStack.push(count);
                stringStack.push(current);
                current = new StringBuilder();
                count = 0;
            } else if (c == ']') {
                if (countStack.isEmpty()) throw new DecodingException("']' without matching '['", i);
                int k = countStack.pop();
                StringBuilder prev = stringStack.pop();
                for (int j = 0; j < k; j++) prev.append(current);
                current = prev;
            } else if (Character.isLetter(c)) {
                if (count != 0) throw new DecodingException("letter after count without '['", i);
                current.append(c);
            } else {
                throw new DecodingException("unexpected character '" + c + "'", i);
            }
        }
        if (!countStack.isEmpty()) {
            throw new DecodingException("unclosed '['", input.length());
        }
        return current.toString();
    }
}

// --- run-length decoder ---
public final class RunLengthDecoder implements Decoder {
    @Override
    public String decode(String input) {
        StringBuilder out = new StringBuilder();
        int i = 0;
        while (i < input.length()) {
            char c = input.charAt(i);
            if (!Character.isLetter(c)) throw new DecodingException("expected letter", i);
            i++;
            int count = 0;
            while (i < input.length() && Character.isDigit(input.charAt(i))) {
                count = count * 10 + (input.charAt(i) - '0');
                i++;
            }
            if (count == 0) throw new DecodingException("letter without count", i);
            for (int k = 0; k < count; k++) out.append(c);
        }
        return out.toString();
    }
}

// --- factory ---
public final class DecoderFactory {
    private final Map<String, Decoder> registry = new HashMap<>();
    public DecoderFactory() {
        register("repetition", new RepetitionDecoder());
        register("rle", new RunLengthDecoder());
    }
    public void register(String name, Decoder decoder) { registry.put(name, decoder); }
    public Decoder get(String name) {
        Decoder d = registry.get(name);
        if (d == null) throw new IllegalArgumentException("unknown decoder: " + name);
        return d;
    }
}

cpp

#include <cctype>
#include <memory>
#include <stack>
#include <stdexcept>
#include <string>
#include <unordered_map>

class DecodingException : public std::runtime_error {
    int position_;
public:
    DecodingException(const std::string& msg, int pos)
        : std::runtime_error(msg + " (position " + std::to_string(pos) + ")"),
          position_(pos) {}
    int position() const { return position_; }
};

struct Decoder {
    virtual std::string decode(const std::string& input) = 0;
    virtual ~Decoder() = default;
};

class RepetitionDecoder : public Decoder {
public:
    std::string decode(const std::string& input) override {
        std::stack<int> countStack;
        std::stack<std::string> stringStack;
        std::string current;
        int count = 0;
        for (int i = 0; i < (int)input.size(); ++i) {
            char c = input[i];
            if (std::isdigit(static_cast<unsigned char>(c))) {
                count = count * 10 + (c - '0');
            } else if (c == '[') {
                if (count <= 0) throw DecodingException("'[' without positive count", i);
                countStack.push(count);
                stringStack.push(current);
                current.clear();
                count = 0;
            } else if (c == ']') {
                if (countStack.empty()) throw DecodingException("']' without matching '['", i);
                int k = countStack.top(); countStack.pop();
                std::string prev = stringStack.top(); stringStack.pop();
                for (int j = 0; j < k; ++j) prev += current;
                current = std::move(prev);
            } else if (std::isalpha(static_cast<unsigned char>(c))) {
                if (count != 0) throw DecodingException("letter after count without '['", i);
                current += c;
            } else {
                throw DecodingException(std::string("unexpected character '") + c + "'", i);
            }
        }
        if (!countStack.empty()) throw DecodingException("unclosed '['", (int)input.size());
        return current;
    }
};

class RunLengthDecoder : public Decoder {
public:
    std::string decode(const std::string& input) override {
        std::string out;
        int i = 0;
        while (i < (int)input.size()) {
            char c = input[i];
            if (!std::isalpha(static_cast<unsigned char>(c))) throw DecodingException("expected letter", i);
            ++i;
            int count = 0;
            while (i < (int)input.size() && std::isdigit(static_cast<unsigned char>(input[i]))) {
                count = count * 10 + (input[i] - '0');
                ++i;
            }
            if (count == 0) throw DecodingException("letter without count", i);
            out.append(count, c);
        }
        return out;
    }
};

class DecoderFactory {
    std::unordered_map<std::string, std::unique_ptr<Decoder>> registry_;
public:
    DecoderFactory() {
        registry_["repetition"] = std::make_unique<RepetitionDecoder>();
        registry_["rle"] = std::make_unique<RunLengthDecoder>();
    }
    void register_(const std::string& name, std::unique_ptr<Decoder> d) {
        registry_[name] = std::move(d);
    }
    Decoder* get(const std::string& name) {
        auto it = registry_.find(name);
        if (it == registry_.end()) throw std::invalid_argument("unknown decoder: " + name);
        return it->second.get();
    }
};

typescript

export class DecodingException extends Error {
  constructor(message: string, public readonly position: number) {
    super(`${message} (position ${position})`);
  }
}

export interface Decoder {
  decode(input: string): string;
}

export class RepetitionDecoder implements Decoder {
  decode(input: string): string {
    const countStack: number[] = [];
    const stringStack: string[] = [];
    let current = "";
    let count = 0;

    for (let i = 0; i < input.length; i++) {
      const c = input[i];
      if (c >= "0" && c <= "9") {
        count = count * 10 + (c.charCodeAt(0) - "0".charCodeAt(0));
      } else if (c === "[") {
        if (count <= 0) throw new DecodingException("'[' without positive count", i);
        countStack.push(count);
        stringStack.push(current);
        current = "";
        count = 0;
      } else if (c === "]") {
        if (countStack.length === 0) throw new DecodingException("']' without matching '['", i);
        const k = countStack.pop()!;
        const prev = stringStack.pop()!;
        current = prev + current.repeat(k);
      } else if (/[a-zA-Z]/.test(c)) {
        if (count !== 0) throw new DecodingException("letter after count without '['", i);
        current += c;
      } else {
        throw new DecodingException(`unexpected character '${c}'`, i);
      }
    }
    if (countStack.length !== 0) throw new DecodingException("unclosed '['", input.length);
    return current;
  }
}

export class RunLengthDecoder implements Decoder {
  decode(input: string): string {
    let out = "";
    let i = 0;
    while (i < input.length) {
      const c = input[i];
      if (!/[a-zA-Z]/.test(c)) throw new DecodingException("expected letter", i);
      i++;
      let count = 0;
      while (i < input.length && input[i] >= "0" && input[i] <= "9") {
        count = count * 10 + (input.charCodeAt(i) - "0".charCodeAt(0));
        i++;
      }
      if (count === 0) throw new DecodingException("letter without count", i);
      out += c.repeat(count);
    }
    return out;
  }
}

export class DecoderFactory {
  private registry = new Map<string, Decoder>();
  constructor() {
    this.register("repetition", new RepetitionDecoder());
    this.register("rle", new RunLengthDecoder());
  }
  register(name: string, decoder: Decoder): void { this.registry.set(name, decoder); }
  get(name: string): Decoder {
    const d = this.registry.get(name);
    if (!d) throw new Error(`unknown decoder: ${name}`);
    return d;
  }
}

Recursive alternative — for reference

Some candidates prefer recursion because the grammar maps one-to-one to function calls. It is shorter and clearer but has the recursion-depth caveat.

java

public final class RecursiveRepetitionDecoder implements Decoder {
    public String decode(String input) {
        int[] i = {0};
        return parse(input, i);
    }
    private String parse(String s, int[] i) {
        StringBuilder out = new StringBuilder();
        while (i[0] < s.length() && s.charAt(i[0]) != ']') {
            char c = s.charAt(i[0]);
            if (Character.isDigit(c)) {
                int k = 0;
                while (Character.isDigit(s.charAt(i[0]))) {
                    k = k * 10 + (s.charAt(i[0]) - '0');
                    i[0]++;
                }
                if (s.charAt(i[0]) != '[') throw new DecodingException("expected '['", i[0]);
                i[0]++; // consume '['
                String inner = parse(s, i);
                if (i[0] >= s.length() || s.charAt(i[0]) != ']') throw new DecodingException("unclosed '['", i[0]);
                i[0]++; // consume ']'
                for (int j = 0; j < k; j++) out.append(inner);
            } else {
                out.append(c);
                i[0]++;
            }
        }
        return out.toString();
    }
}

Use this if your interviewer wants to see grammar-driven parsing. Use the stack version if they want production robustness.

Extensibility

1. "Add run-length encoding support."

You answer: "Already done — RunLengthDecoder implements the same Decoder interface, registered in the factory under rle. The call site picks a decoder by name. No existing decoder had to change."

java

DecoderFactory factory = new DecoderFactory();
Decoder d = factory.get("rle");
String out = d.decode("a3b2");   // "aaabb"

Tradeoff: Both decoders return String from String. If a new format needs a different input type (e.g., bytes), you either widen the interface to decode(byte[]) or introduce a parallel BinaryDecoder interface. The former is cleaner if ASCII is a subset of bytes.

2. "Add Huffman decoding — but it needs a code table."

You answer: "Real Huffman needs configuration that repetition and RLE do not. I keep the Decoder interface but pass the code table at construction time, not to decode. For callers that build decoders on the fly, I add a separate HuffmanDecoderBuilder."

java

public final class HuffmanDecoder implements Decoder {
    private final TrieNode root;  // prebuilt from the code table
    public HuffmanDecoder(Map<Character, String> codeTable) {
        this.root = buildTrie(codeTable);
    }
    public String decode(String bits) {
        StringBuilder out = new StringBuilder();
        TrieNode node = root;
        for (int i = 0; i < bits.length(); i++) {
            node = bits.charAt(i) == '0' ? node.left : node.right;
            if (node == null) throw new DecodingException("invalid bit", i);
            if (node.isLeaf()) { out.append(node.ch); node = root; }
        }
        if (node != root) throw new DecodingException("incomplete code at end", bits.length());
        return out.toString();
    }
}

factory.register("huffman", new HuffmanDecoder(myCodeTable));

Tradeoff: Stateful decoders — which Huffman is — complicate the "one instance, many threads" story. RepetitionDecoder has no state and is trivially shareable. HuffmanDecoder has an immutable trie after construction, so it is still safe. Document this explicitly so future maintainers do not assume.

3. "The input might be malformed. Can you be more helpful in errors?"

You answer: "DecodingException already carries a position. I can add the surrounding snippet for better errors. For batch processing, I add a tryDecode variant that returns a Result type — {ok, value} or {err, reason, position} — so the caller can collect all errors instead of throwing on the first."

java

public sealed interface DecodeResult {
    record Ok(String value) implements DecodeResult {}
    record Err(String message, int position) implements DecodeResult {}
}

default DecodeResult tryDecode(String input) {
    try { return new DecodeResult.Ok(decode(input)); }
    catch (DecodingException e) { return new DecodeResult.Err(e.getMessage(), e.position()); }
}

Tradeoff: Return-type-as-error is more verbose at the call site but better for pipelines. Exception-based is idiomatic in Java. Offer both; let callers pick.

What is Expected at Each Level

Level	Expectations
Junior	Writes a monolithic `decode(String)` function using a stack. Gets LC 394 right. When asked about RLE, suggests copying the function and modifying it. Needs a nudge to see the interface.
Mid-level	Introduces the `Decoder` interface before being asked. Recognizes that the decoder is stateless and can be a singleton. Handles error cases with a dedicated exception that carries position. Picks stack over recursion and can justify why.
Senior	Lays out the `Decoder`, `DecoderFactory`, `DecodingException` triad at the whiteboard before writing any code. Names the Strategy pattern explicitly and explains the open/closed benefit. Discusses the subtle issue that Huffman breaks the "stateless decoder" assumption and shows how to accommodate it without warping the interface. Talks through iterative vs. recursive tradeoffs (stack-depth safety). Google signal: the refactoring instinct is visible when they initially write one function, then pause and say "before we add RLE, let me pull out the interface — it is three lines now, it will be thirty after we have two decoders." They refactor before the interviewer prompts them.

43 — LLD: Decoder Class (Decode String, but as OOP) ​

Understanding the Problem ​

Requirements ​

Clarifying Questions ​

Final Requirements ​

Core Entities and Relationships ​

Class Design ​

Decoder (Interface) ​

RepetitionDecoder ​

RunLengthDecoder ​

DecoderFactory ​

DecodingException ​

Implementation ​

Core Method: RepetitionDecoder.decode(input) — stack version ​

Core Algorithm: why stack over recursion ​

Verification ​

Complete Code Implementation ​

Recursive alternative — for reference ​

Extensibility ​

1. "Add run-length encoding support." ​

2. "Add Huffman decoding — but it needs a code table." ​

3. "The input might be malformed. Can you be more helpful in errors?" ​

What is Expected at Each Level ​

43 — LLD: Decoder Class (Decode String, but as OOP)

Understanding the Problem

Requirements

Clarifying Questions

Final Requirements

Core Entities and Relationships

Class Design

Decoder (Interface)

RepetitionDecoder

RunLengthDecoder

DecoderFactory

DecodingException

Implementation

Core Method: `RepetitionDecoder.decode(input)` — stack version

Core Algorithm: why stack over recursion

Verification

Complete Code Implementation

Recursive alternative — for reference

Extensibility

1. "Add run-length encoding support."

2. "Add Huffman decoding — but it needs a code table."

3. "The input might be malformed. Can you be more helpful in errors?"

What is Expected at Each Level