Implement menu parser and serializer

Menu parser and serializer

You are given a restaurant menu stored as plain text, where indentation represents a hierarchy of categories and items. Implement logic to convert between this text format and an in-memory tree data structure, and back again.

Text format

• The menu is a multi-line string; each non-empty line describes one menu item.

• Leading indentation (0 or more groups of two spaces) indicates nesting depth relative to top-level categories. Two spaces = one level deeper.

• After the indentation, fields on each line are separated by the | character:

  <type>|<id>|<name>|<price>

  where:

  • type is a string label such as CATEGORY, FOOD, or SIDE. Do not assume only these three types exist; treat type as an arbitrary, opaque string.
  • id is a unique identifier string for this item.
  • name is free text that does not contain the | character.
  • price is a decimal number (e.g., 5.99), or the literal - if the item has no price (e.g., a category).

Example input:

CATEGORY|c1|Burgers|-
  FOOD|f1|Classic Burger|5.99
    SIDE|s1|Fries|1.99
  FOOD|f2|Veggie Burger|6.49
CATEGORY|c2|Drinks|-
  FOOD|f3|Cola|1.50
  FOOD|f4|Water|1.00

This example shows a category > food > side hierarchy, but in general the depth and the item types at each level can vary.

Tree structure

Define a data structure MenuItem (language-agnostic) with at least these fields:

• type: string
• id: string
• name: string
• price: nullable/optional number (null when the text price is -)
• children: an ordered list/array of MenuItem representing nested items

Top-level menu items are those with zero indentation.

Tasks

1. Implement parseMenu(text): take the menu text string and return the tree — a list/array of top-level MenuItem nodes, each with its children populated and in order.
2. Implement serializeMenu(items): take the tree (the list/array of top-level MenuItem nodes) and return a canonical text representation in exactly the format above.

The serializer must:

• Use exactly two spaces per level of indentation deeper than the parent.
• Use | as the field separator.
• Emit - for items whose price is null/absent (and the original decimal text otherwise).
• Emit a depth-first, pre-order traversal: every node is followed immediately by its subtree, with children in stored order.

Together the two functions should satisfy a round-trip property: for any valid input text in canonical form, serializeMenu(parseMenu(text)) reproduces text (modulo a trailing newline convention you define).

Hint: Where to start

Process the text line by line. For each line, separate the leading indentation from the payload first, then split the payload on |. The number of leading spaces divided by 2 gives the node's depth.

Hint: Data structure for nesting

You don't need recursion to build the tree. Keep an explicit stack of ancestor nodes indexed by depth: index d holds the current node at depth d. A line at depth d becomes a child of the node at stack[d-1] (or a top-level root when d == 0). After attaching, set stack[d] = newNode and truncate the stack to length d+1.

Hint: Parsing the payload safely

split('|') with a limit/maxsplit of 3 (so name is captured even if it contained | — though the spec says it won't) and convert price: - → null, otherwise parse as a number. Decide whether to preserve the original price string to make the round-trip exact (e.g. 1.50 vs 1.5).

Hint: Serializing

Recurse (or use an explicit stack) over the tree pre-order, prepending 2 * depth spaces and joining the four fields with |. This mirrors the parse exactly; the two functions are inverses.

Constraints & Assumptions

• The input is always a valid, well-formed tree: no cycles, consistent indentation (depth never jumps by more than one when descending), and at least one top-level item.
• $N$ = number of menu items (lines). Both functions should run in $O(N)$ time and $O(N)$ extra space.
• Indentation is always groups of exactly two spaces; there is no tab/space mixing.
• name never contains |; type and id are non-empty.
• Treat type as opaque — the parser must not special-case CATEGORY/FOOD/SIDE.

Clarifying Questions to Ask

• Price fidelity: must the serialized price match the source byte-for-byte (e.g. 1.50 stays 1.50, not 1.5), or is any numerically-equal representation acceptable? This decides whether I store the original string or a parsed float.
• Blank lines / trailing newline: can the input contain blank lines between items, and should serializeMenu end with a trailing newline?
• Malformed input: the spec says input is always valid — should parseMenu still defend against bad indentation or wrong field counts (throw vs. best-effort), or may I assume validity?
• Numeric type & negative/zero prices: is price always a non-negative decimal, and is integer vs. float distinction meaningful (5 vs 5.00)?
• Encoding of name: could name contain leading/trailing spaces or unicode that I must preserve verbatim?

What a Strong Answer Covers

• Correct, stack-based parse that derives depth from indentation, attaches each node to the right parent in $O(N)$, and builds an ordered tree without recursion-depth risk on deep menus.
• Exact inverse serializer producing a pre-order, two-space-per-level traversal; the candidate explicitly reasons about (and ideally tests) the parse → serialize → parse round-trip and the price-formatting decision that makes it lossless.
• Clean data modeling: a MenuItem with the required fields, null-vs-number price handling, and children preserving insertion order.
• Complexity: argues $O(N)$ time / $O(N)$ space and avoids accidental $O(N^2)$ (e.g. repeated string scanning, or searching the whole tree to find a parent).
• Edge cases: single top-level item, multiple roots, a node with no children, deeply nested chains, prices of -, and the trailing-newline convention.
• Code quality: small helpers (parseLine, formatLine), clear separation of indentation handling from field parsing, and testability.

Follow-up Questions

• How would you make the parser tolerant of malformed input — wrong field count, an indentation jump of more than one level, or a non-numeric price — and report a precise error (line number + reason)?
• The spec forbids | in name. If name (or type) could contain | or newlines, how would you change the format and the parser/serializer (escaping, quoting, or a length-prefixed/JSON encoding) while keeping it human-readable?
• Suppose menus are huge (millions of lines) or streamed. How would you adapt parseMenu/serializeMenu to stream rather than load the whole tree in memory, and what changes for the round-trip guarantee?
• How would you support an edit operation — e.g. move a subtree or reprice an item by id — efficiently, and what auxiliary index (id → node) would you maintain?

Solution

Menu parser and serializer — model solution

1. Approach

The text is a pre-order (depth-first) flattening of a tree, with depth encoded by indentation. So both directions are linear, single-pass walks:

• Parse: read top to bottom. Indentation tells you each line's depth. Keep a stack of the current ancestor at each depth. A line at depth d is a child of stack[d-1] (or a new root when d == 0). This is the standard "build a tree from an indented/pre-order list" trick — no need to search the tree for a parent, so it stays $O(N)$.
• Serialize: pre-order DFS over the tree, prepending 2 * depth spaces and joining the four fields with |. This is the exact inverse of the parse.

The one decision that makes the round-trip lossless is price formatting. The source can write 1.50, 1.5, or 5.00, and parsing to a float then reformatting loses the original spelling (1.50 → 1.5). I therefore keep the original price text alongside the numeric value, so serializeMenu(parseMenu(text)) == text. I expose both: price (the parsed number, per the spec's field list) and a private priceText used only for canonical re-emission. If exact byte-fidelity is not required, you can drop priceText and format the float directly.

2. Data model

from typing import List, Optional

class MenuItem:
    def __init__(self, type: str, id: str, name: str,
                 price: Optional[float], price_text: str):
        self.type = type
        self.id = id
        self.name = name
        self.price = price          # None when text price is "-"
        self.price_text = price_text  # original "-", "1.50", ... (for lossless round-trip)
        self.children: List["MenuItem"] = []

3. Parse — parseMenu

INDENT = "  "  # two spaces per level

def parse_line(line: str) -> MenuItem:
    # split on the first 3 "|" so name can contain "|" defensively;
    # spec says it won't, but maxsplit=3 is free insurance.
    parts = line.split("|", 3)
    if len(parts) != 4:
        raise ValueError(f"expected 4 fields, got {len(parts)}: {line!r}")
    type_, id_, name, price_text = parts
    price = None if price_text == "-" else float(price_text)
    return MenuItem(type_, id_, name, price, price_text)

def depth_of(line: str) -> (int, str):
    """Return (depth, payload). Indentation is groups of exactly two spaces."""
    n = 0
    while line.startswith(" ", n) and line.startswith("  ", n):
        n += 2
    if n % 2 != 0 or line[:n].strip() != "":
        raise ValueError(f"bad indentation: {line!r}")
    return n // 2, line[n:]

def parse_menu(text: str) -> List[MenuItem]:
    roots: List[MenuItem] = []
    # stack[d] = the most recent node seen at depth d
    stack: List[MenuItem] = []

    for raw in text.split("\n"):
        if raw == "" or raw.strip() == "":
            continue  # skip blank lines
        depth, payload = depth_of(raw)
        node = parse_line(payload)

        if depth == 0:
            roots.append(node)
        else:
            if depth > len(stack):
                raise ValueError(f"indentation jumps more than one level: {raw!r}")
            stack[depth - 1].children.append(node)

        # this node is now the current node at `depth`; drop anything deeper
        del stack[depth:]
        stack.append(node)

    return roots

Why it's correct and $O(N)$:

• Each line is processed once; split/indentation scan is linear in the line length, so total work is $O(\text{total chars}) = O(N)$ for fixed-width records.
• stack[depth - 1] is the parent because, in a pre-order listing, the parent of a depth-d node is always the most recently seen depth-(d-1) node — exactly what the stack holds.
• del stack[depth:] then append(node) keeps the stack length at depth + 1, so stack[d] is always the live ancestor at depth d. No tree search ⇒ no $O(N^2)$.

4. Serialize — serializeMenu

def format_line(node: MenuItem, depth: int) -> str:
    indent = INDENT * depth
    return f"{indent}{node.type}|{node.id}|{node.name}|{node.price_text}"

def serialize_menu(items: List[MenuItem]) -> str:
    out: List[str] = []

    def walk(node: MenuItem, depth: int) -> None:
        out.append(format_line(node, depth))
        for child in node.children:
            walk(child, depth + 1)

    for root in items:
        walk(root, 0)

    return "\n".join(out)

• Pre-order DFS: a node is emitted, then its whole subtree, matching the input layout.
• INDENT * depth gives exactly two spaces per level.
• price_text re-emits - or the original decimal verbatim, so the output is canonical.
• $O(N)$ lines, each built once; joining is $O(\text{total chars})$.

If price_text weren't stored, the equivalent lossy line would be:

price_field = "-" if node.price is None else f"{node.price}"  # may print 1.5 not 1.50

— acceptable only when numeric equality (not textual equality) is the round-trip contract.

For an explicit-stack serializer (no recursion, safe on very deep menus), push (node, depth) in reverse-children order:

def serialize_menu_iter(items: List[MenuItem]) -> str:
    out: List[str] = []
    stack = [(n, 0) for n in reversed(items)]
    while stack:
        node, depth = stack.pop()
        out.append(format_line(node, depth))
        for child in reversed(node.children):
            stack.append((child, depth + 1))
    return "\n".join(out)

5. Round-trip property

With price_text preserved:

text = (
    "CATEGORY|c1|Burgers|-\n"
    "  FOOD|f1|Classic Burger|5.99\n"
    "    SIDE|s1|Fries|1.99\n"
    "  FOOD|f2|Veggie Burger|6.49\n"
    "CATEGORY|c2|Drinks|-\n"
    "  FOOD|f3|Cola|1.50\n"
    "  FOOD|f4|Water|1.00"
)
assert serialize_menu(parse_menu(text)) == text   # exact, including 1.50 / 1.00

The two functions are inverses because parse maps "depth + fields" → node and serialize maps node → "depth + fields" using the same indentation unit, separator, and (preserved) price spelling. Define the trailing-newline convention once — here serialize_menu emits no trailing \n; if the source ends with one, either strip it before comparing or have the serializer append one consistently.

6. Complexity

Function	Time	Extra space
parseMenu	$O(N)$ (one pass; stack ops are $O(1)$ amortized)	$O(N)$ for the tree + $O(H)$ stack, $H \le N$
serializeMenu	$O(N)$ (visits each node once)	$O(N)$ output buffer + $O(H)$ recursion/stack

$H$ is the menu's max depth. Using the iterative serializer removes recursion-depth risk for pathologically deep menus.

7. Edge cases handled

• Single root / multiple roots: roots collected whenever depth == 0.
• Leaf with no children: children stays empty; serialize emits just its line.
• Deep chains (category > food > side > …): stack grows with depth, still $O(N)$.
• Null price (-): preserved on both sides via price_text.
• Blank lines: skipped in parse; not re-emitted.
• Name with internal spaces / unicode: preserved verbatim (no trimming of name).

8. Answers to the follow-ups

Malformed input / precise errors. Make depth_of and parse_line raise on (a) field count ≠ 4, (b) indentation not a multiple of two or containing non-space chars, (c) a depth that exceeds len(stack) (a jump of more than one level), and (d) a non--, non-numeric price. Track a 1-based line counter and include it in the message: ValueError(f"line {i}: indentation jumps from {len(stack)} to {depth}"). For a tolerant mode, collect errors into a list and skip offending lines rather than aborting.

If name/type could contain | or newlines. The pipe-delimited line format breaks. Options, cheapest first: (1) escape |, \n, and the escape char itself (\|, \n, \\) and unescape on parse — keeps it human-readable; (2) quote fields (CSV-style with " and doubled quotes); (3) switch to a structured encoding (JSON Lines per node with an explicit depth, or nested JSON) — fully unambiguous but less readable and no longer indentation-driven. With escaping, parse_line must split on unescaped | (a small state machine, not str.split), and format_line must escape on the way out; the round-trip still holds.

Huge / streamed menus. Parsing is already a single forward pass, so it can consume an iterator of lines and yield roots as each top-level subtree completes (a root's subtree is done the moment the next depth-0 line arrives or the stream ends). Serialization streams naturally: do a pre-order DFS and yield/write each formatted line instead of buffering into a list, giving $O(H)$ working memory instead of $O(N)$. The round-trip guarantee is unchanged as long as you keep the same price/indent conventions; you just trade the materialized tree for a streaming pipeline (and lose random access by id).

Efficient edits (move subtree, reprice by id). Maintain an auxiliary dict id → MenuItem (and optionally id → parent) built during parse, so lookups and reprices are $O(1)$. Moving a subtree is then: detach from parent.children (keep a parent pointer or index to make removal $O(\text{siblings})$), validate the move doesn't create a cycle (the new parent must not be inside the moved subtree), and append to the new parent's children. Re-serializing afterward is still a single $O(N)$ pre-order walk. If moves are frequent and sibling lists are large, store children in a structure with cheaper removal, but for typical menu sizes a list is fine.