Implement menu parser and serializer
Company: CloudKitchens
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
### 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:
```text
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?
Quick Answer: This question evaluates proficiency in text parsing, hierarchical data modeling, tree construction and serialization, string manipulation, and algorithmic complexity (linear time/space).
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
```python
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`
```python
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`
```python
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:
```python
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:
```python
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:
```python
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.