Katkat
Back

Reconstruct a Pallet Repacking Lineage and Render It as a Branch Tree

StripeSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

Rebuild which warehouse pallets were repacked from which other pallets out of an unordered event log, then print the lineage as an indented tree with branch connectors. Tests careful spec-reading, tree construction independent of input order, and exact output formatting.

A warehouse logs two kinds of pallet events to one unordered file:

  • created events: a brand-new pallet is built from incoming freight. Fields: id, name, ts.
  • repacked events: a pallet's contents are split out of an existing pallet. Fields: id, name, ts, source_id (the id of the pallet it was repacked from).

A pallet's lineage traces every pallet back to the original created pallet it ultimately came from. Events can appear in the log in any order, so a repacked event may be read before the created event for its source_id.

Part 1 — Build the lineage map

Parse the event log into a structure that, for every pallet, lists the pallets repacked directly from it, plus the set of origin pallets (pallets with no source, i.e. created events).

A repack event for pallet B pointing at source A can appear before or after A's own event in the file.

What This Part Should Cover

  • A map from each pallet to its direct children, and a list of origins, correct regardless of event order
  • A clear decision for: a repacked event whose source_id matches no known pallet (treat it as its own origin, and record a warning), two events sharing the same id (reject as an error), and a cycle of source_id pointers (reject as an error)
  • Time and space cost of building the map

Part 2 — Render the lineage as a tree

Print each origin pallet and everything repacked from it as an indented tree. An origin pallet's name is printed with no connector. Among a pallet's direct children, every child except the last is printed after "├── ", and the last child is printed after "└── ". Deeper lines carry a running prefix of "│ " or " " from each ancestor, depending on whether that ancestor was itself a last child.

Children of the same pallet must be printed in ascending order of their own ts.

Pallet P1 (origin)
├── Pallet P4 (repacked)
│   └── Pallet P7 (repacked)
└── Pallet P9 (repacked)

That shape comes from: P1 is an origin; P4 and P9 were both repacked from P1 (P4 first, so it is not last); P7 was repacked from P4 and is P4's only child, so it is last.

The connector depends only on a node's position among its siblings. The prefix before the connector depends only on whether each ancestor was a last child.

Constraints

  • Up to 5 * 10^4 events.
  • Lineages can nest arbitrarily deep.
  • Pallet names never contain newlines.

Hints

Hint 1

Do a first pass just to collect every pallet by id, so a repack event's source doesn't need to exist yet when you see it.

Hint 2

Build a children map keyed by source id, and separately track which ids never got claimed as a parent — those plus declared origins are your roots.

Hint 3

Sort each pallet's children list by ts once, after the whole map is built, rather than trying to insert in sorted order as you parse.

Hint 4

For the renderer, pass down a string prefix and a boolean 'is this node a last child' — don't try to compute connectors from indices alone during recursion.

Follow-up questions

  • How would you support streaming events, where you must answer 'print the tree so far' before the log is known to be complete?
  • A pallet can now be split into several repacked pallets *and* later merged back — how does that change the data model?
  • If two sibling pallets have the exact same ts, what tie-break would you add, and why does it need to be deterministic?
  • How would you adapt the renderer to emit JSON nesting instead of text, and would you reuse the same traversal?