Katkat
Back

Reconstruct a Warehouse Pick-List From a Dropped Scanner Feed

Listen LabsSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Write a function that turns a scanner feed cut off mid-transmission into the best pick-list it can represent so far, recovering half-written labels and unfinished bin groupings. Tests careful state-machine parsing of truncated nested data.

A warehouse robot scans items into nested storage bins and reports its progress over a radio link using a tiny text format: item labels are written in double quotes, and a bin's contents are written inside square brackets, with bins allowed to nest inside other bins. There are no numbers, no booleans, nothing else -- just quoted labels and bracketed groups of them.

The radio link is unreliable and can die at literally any byte. Your job is to take whatever bytes made it through and reconstruct the best pick-list that data can represent, filling in nothing the robot didn't actually send.

Function Signature

def reconstruct_picklist(feed: str) -> str | list:

Rules

  • feed always begins with " or [, and is guaranteed to be an exact prefix of some complete, validly-formed value built only from quoted labels and bracketed groups.
  • Labels never contain a quote character or a backslash, so there is nothing to escape.
  • If the feed cuts off while a label's closing quote hasn't arrived yet, that label keeps exactly the characters that did arrive (the empty string if none did).
  • If the feed cuts off right after a comma inside a bin, that trailing comma does not create an extra, empty entry.
  • Any bin that never reached its closing bracket is still reported, holding whatever entries it had already collected.
  • The entire feed can itself be nothing but a single label, with no bins at all.
  • If feed happens to already be a complete, fully-closed value, return it exactly as parsed.

Interviewers here often also ask you to name the edge cases your own tests would hit before you write any code -- a few are listed in the hints.

Example 1

Input:  feed = '["bolts", ["wash'
Output: ['bolts', ['wash']]

The outer bin has received one full label and one still-open inner bin; the inner label only got as far as wash.

Example 2

Input:  feed = '[["a", "b"], "c", '
Output: [['a', 'b'], 'c']

Transmission cut out just past a separating comma, before any further label began, leaving the outer bin with only its first two entries.

Example 3

Input:  feed = '['
Output: []

Only the opening bracket arrived, so the result is an empty bin.

Constraints

  • 1 <= len(feed) <= 10^5
  • feed[0] is " or [.
  • Characters inside a label are printable ASCII other than " and \.
  • Outside of labels, the only characters that appear are [, ], ,, " and the space character.
  • Bins can nest up to 500 levels deep.

Hints

Hint 1

Walk the feed once, left to right, keeping a stack of in-progress bins instead of trying to validate the whole string up front.

Hint 2

Track whether you're currently inside a label separately from the bin stack -- an unterminated label just means 'take whatever characters were already read.'

Hint 3

You never need to look ahead. Whatever the scanner was doing when the feed stopped tells you exactly what's still incomplete.

Hint 4

Good test feeds to write: cut mid-label, cut right after an opening quote, cut right after '[', cut right after a comma, and a feed that is already fully closed.

Follow-up questions

  • How would you extend this to support a third token type, like a quoted numeric label, without restructuring the core scanning loop?
  • If the scanner inserts a heartbeat byte mid-label just to keep the radio link alive, how would you adapt the parser to ignore it?
  • How would you parse a feed that keeps growing over time, reusing the work from a previous call instead of rescanning from the start each time?
  • What's the smallest set of unit tests that would pin down every truncation point described in the rules?