Katkat
Back

Implement menu parser and serializer

CloudKitchensSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates proficiency in text parsing, hierarchical data modeling, tree construction and serialization, string manipulation, and algorithmic complexity (linear time/space).

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).

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?

Hints

Hint 1

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 2

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 3

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 4

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.

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?