Airbnb Software Engineer - Entry Level Interview Preparation Guide

Direct answer. Put a single translation layer between "whatever actually broke internally" and "what the client sees," so every internal exception passes through one place that decides the client-facing status code and message, rather than letting internal error text leak out through whichever handler happened to catch it.

The translation layer's job. Catch exceptions at the boundary (a global exception handler, or a dedicated error-mapping function every route calls into), and for each KNOWN category of internal failure, map it to a specific, safe, client-facing error: a database unique-constraint violation becomes a 409 Conflict with a generic "this resource already exists" message, not the raw constraint name and table structure; an internal service timeout becomes a 503 with a retryable flag, not the internal service's hostname or the exact RPC that failed; anything UNRECOGNIZED (a genuine bug, not a known failure category) becomes a generic 500 with no detail beyond a correlation id, specifically because an unrecognized exception is the one case where you cannot be confident that its message does not accidentally contain something sensitive (a query with embedded user data, a file path, a partial credential).

Preserving the real error for debugging. The translation layer logs the FULL original exception (stack trace, internal service name, the real error text) server-side, tagged with the same correlation id that goes back to the client in the sanitized response. An SRE or engineer investigating an incident looks up that correlation id in the logs and gets everything; the client only ever sees the generic, safe version plus that same id to hand back for support.

Why an allow-list of known mappings, not a deny-list of things to strip. Trying to scrub specific sensitive PATTERNS out of an arbitrary internal error message (strip anything that looks like a file path, strip anything that looks like a hostname) is a losing game against an internal system that can produce arbitrarily-shaped error text; the safe default has to be "unless this exception is on our known, reviewed list, the client gets a generic message," not "leak everything except what we thought to filter."

Trade-offs and pitfalls. The most common near-miss is mapping the KNOWN error categories correctly but forgetting that a catch-all handler for UNKNOWN exceptions defaults to including the exception's own message in the response "to help debugging," which reintroduces exactly the leakage this whole layer exists to prevent, the first time an unanticipated internal error happens to contain something sensitive.

Direct answer. Extract the common shape (try/fetch, 404 handling, error handling) into one small higher-order function, and let each caller supply only the piece that actually differs: how to map the fetched row into a response body.

Before

async function getUser(req, res, db) {
  try {
    const row = await db.find('users', req.params.id);
    if (!row) return res.status(404).json({ error: 'not found' });
    res.status(200).json({ id: row.id, name: row.full_name, email: row.email_address });
  } catch (e) {
    res.status(500).json({ error: 'internal error', detail: e.message });
  }
}
// getOrder duplicates the same try/404/500 shape with a different mapping

After

function makeGetByIdHandler(db, table, mapRow) {
  return async function handler(req, res) {
    try {
      const row = await db.find(table, req.params.id);
      if (!row) return res.status(404).json({ error: 'not found' });
      res.status(200).json(mapRow(row));
    } catch (e) {
      res.status(500).json({ error: 'internal error', detail: e.message });
    }
  };
}
const getUser = (db) => makeGetByIdHandler(db, 'users',
  (row) => ({ id: row.id, name: row.full_name, email: row.email_address }));
const getOrder = (db) => makeGetByIdHandler(db, 'orders',
  (row) => ({ id: row.id, total: row.total_amount, status: row.order_status }));

Verified against a fake db/response harness: both the success path (200 with mapped body) and the not-found path (404) produce byte-identical responses before and after the refactor.

Why an abstraction, not just a copy-paste tweak

The part that varies (table name, row-to-response mapping) is passed IN as data/functions; the part that's identical (control flow: try, 404 check, catch, 500) lives in exactly one place. If the error-handling shape needs to change later (say, adding a request ID to the 500 response), it changes once, and every endpoint built on makeGetByIdHandler gets the fix automatically instead of needing the same edit copy-pasted into every handler.

Preserving clarity per caller

Each concrete handler (getUser, getOrder) still reads as a short, self-contained declaration of WHAT it maps, not HOW the request/response machinery works -- the abstraction doesn't hide the caller's own logic, only the boilerplate every caller would otherwise repeat.

Trade-offs and pitfalls

• This is a good abstraction only because the two callers' DIFFERENCES (the mapping function) are cheap to express as a parameter; if the endpoints started needing genuinely different control flow (one needs a second DB lookup, one needs caching), forcing them through the same higher-order function would make the abstraction leak and become harder to read than the duplication it replaced.
• Watch for the abstraction picking up special-case parameters over time ('handle table X differently') -- that's the sign the shared function is trying to do two things and should split back into two.
• Extracting too early, on the FIRST occurrence of similar code (rather than the second or third), risks guessing wrong about which parts are truly invariant.

Direct answer

A trie (prefix tree) stores strings by sharing common prefixes as a path through a tree of characters: each node holds child pointers keyed by the next character, plus a marker for "a word ends here". insert, search, and startsWith all walk that path one character at a time, so each costs $O(L)$ where $L$ is the length of the word or prefix, independent of how many other words are stored. That's exactly what beats a hash set once the workload shifts to prefix queries: a hash set can tell you whether one exact string is a member in $O(L)$, but it has no way to answer "give me everything starting with pre" except scanning every stored string.

Approach

• Each TrieNode holds a dictionary of child nodes keyed by character, plus an is_word flag.
• insert(word): walk from the root, creating a child node for each character not already present, then mark the final node's is_word as true.
• search(word): walk the same path; if any character is missing, the word isn't stored. If the path exists, the word is present only if the final node's is_word is true (this is what distinguishes an exact match from merely being a prefix of something else).
• startsWith(prefix): identical walk, but the answer is simply whether the path exists at all; is_word is irrelevant.

class TrieNode:
    __slots__ = ("children", "is_word")

    def __init__(self):
        self.children: dict[str, "TrieNode"] = {}
        self.is_word = False


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_word = True

    def _walk(self, prefix: str):
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

    def search(self, word: str) -> bool:
        node = self._walk(word)
        return node is not None and node.is_word

    def startsWith(self, prefix: str) -> bool:
        return self._walk(prefix) is not None


if __name__ == "__main__":
    trie = Trie()
    trie.insert("apple")
    print(trie.search("apple"))     # True
    print(trie.search("app"))       # False: "app" was never inserted as a word
    print(trie.startsWith("app"))   # True: it's a valid prefix path
    trie.insert("app")
    print(trie.search("app"))       # True: now it's an inserted word too

Running this prints True, False, True, True, showing the exact distinction between a prefix existing in the tree and a full word being marked at that node.

Key points

• Sharing prefixes is the whole benefit: "app", "apple", and "application" only pay for the divergent suffixes once "app" has been walked.
• Trie versus hash table, concretely: reach for a trie when the workload needs prefix queries, autocomplete, or longest-prefix matching (for example IP routing or URL routing tables), since a hash set has no ordering by prefix at all. Reach for a hash set when you only ever need exact-match membership and words rarely share prefixes, since a trie pays a real per-character node overhead that a flat hash set avoids.
• Deletion (not shown above) needs care: unmark is_word at the target node, then optionally prune nodes back up toward the root, but only while a node has no children and isn't itself marking a shorter stored word.

Complexity

insert: $O(L)$ time, up to $O(L)$ new nodes in the worst case (no shared prefix). search: $O(L)$ time, $O(1)$ extra space. startsWith(prefix): $O(P)$ time where $P$ is the prefix length. Overall trie space is $O(\text{total characters across all stored words})$ in the worst case, less whenever words share prefixes.

Edge cases

• Empty string: insert("") marks the root itself as a word; search("") and startsWith("") should both be true afterward.
• A prefix longer than any stored word simply fails the walk partway through and returns the correct negative.
• Re-inserting the same word is idempotent (no duplicate storage, is_word just gets set again).
• Large alphabets (Unicode) increase the practical memory cost per node since the child dictionary can hold far more distinct keys; a compressed trie (radix/PATRICIA tree, collapsing single-child chains) reduces node count when words rarely branch.

Direct answer

An API is a set of rules that lets two pieces of software ask each other for things and get a response back, the same way a restaurant menu lets you ask the kitchen for a specific dish without needing to know how it's cooked. For support, the practical version is: our product and some other company's system talk to each other automatically over the internet, in a fixed, agreed format, and when that conversation fails, it looks like "the app is broken" even though our code and their code may both be working correctly on their own.

Walking through the request/response flow, and what to leave out

• Client asks, server answers. Frame every API call as one system asking a narrow question ("what is this customer's order status?") and the other giving a narrow answer. Don't teach REST verbs or endpoint names to a support audience, they need the shape of the interaction, not the vocabulary.
• Name the four things that can go wrong, because that's what a support rep actually needs on the spot: the question was asked wrong (a bug on our side), the other system refused to answer (their outage, or our access was revoked), the answer came back garbled or incomplete (a partial failure), or the answer took too long and we gave up waiting (a timeout). Mapping a customer's symptom to one of these four buckets is the real skill being taught here, not the word "API" itself.
• Decide what to omit on purpose: authentication and rate limits are real and matter to engineers, but for a support rep they collapse into one sentence, sometimes the connection itself needs permission or is being used too much, and that shows up looking like the same kind of failure as an outage. Don't walk through how tokens work, it adds vocabulary without adding troubleshooting power.
• Check understanding with a real ticket, not a definition. Hand them a recent "the button doesn't do anything" ticket and ask which of the four failure buckets it fits.

Worked example

Say a customer reports our order-status page came back empty. Behind the scenes, when they loaded that page, our app sent a request to our shipping partner's system asking, in effect, "what's the status of order 48213?" Two things can happen: the shipping partner answers with the status and our page displays it, or something breaks in that exchange, their system is down, our request had a typo, or the token proving we're allowed to ask has expired, and our page has nothing to show, so it renders blank instead of an error message. For the support rep, the API is the reason "our website" and "the shipping company's website" can disagree at the exact same moment: they're two separate systems, and this blank page is what it looks like when the conversation between them fails partway through, not when either system is fundamentally broken.

Trade-offs and pitfalls

The waiter analogy earns its keep for the request/response shape, but it breaks down the moment a rep asks "so can I just call them and ask directly?", real APIs are automated, high-volume, and machine-to-machine, there's no waiter to flag down. Say that limit out loud rather than let them assume a human process exists behind it. The bigger pitfall is oversimplifying past the point of being useful: a support rep who can only say "it's an API problem" can't triage a ticket. The four-bucket failure model above is close to the minimum depth that turns the definition into something actionable, cut much further and the explanation stays clear but becomes useless.

Direct answer
Beyond the standard empty/single/two-element/target-at-boundaries/not-present/duplicates cases, binary search has one classic implementation-specific bug: computing the midpoint as (low + high) / 2 overflows a fixed-width signed integer once low + high exceeds the type's maximum, silently producing a negative or wrapped midpoint; the fix is low + (high - low) / 2, which can never overflow because the intermediate value stays within the array's index range.

Structured elaboration and worked example (executed; the original draft's while/if/elif/else body was flattened to a single indent level and did not parse as Python at all, fixed below)

def binary_search_safe(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = low + (high - low) // 2  # overflow-safe
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

Edge cases and results, all executed and passing:

• Empty array: binary_search_safe([], 5) == -1
• One element (found and not found): binary_search_safe([7], 7) == 0, binary_search_safe([7], 3) == -1
• Two elements, target at boundaries: binary_search_safe([1,5], 1) == 0, binary_search_safe([1,5], 5) == 1
• Target at first/last index of a larger array: confirmed on [1,3,5,7,9,11,13]
• Not present: binary_search_safe([1,3,5,7,9,11,13], 4) == -1
• Repeated elements: binary_search_safe([2,2,2,2,2], 2) returns SOME correct index (any is acceptable unless the contract specifies first/last occurrence, which needs its own explicit test if required)

Mid-calculation overflow, demonstrated concretely
Python integers never overflow, so the overflow bug can't reproduce natively in Python; it was simulated explicitly as it would behave in a 32-bit signed language (Java int, C int):

low, high = 1_500_000_000, 1_500_000_000 # low+high = 3,000,000,000 > INT32_MAX (2,147,483,647)
correct_mid = low + (high - low) // 2 # = 1,500,000,000
# simulated 32-bit signed wraparound of (low+high)//2:

Executed result: low+high = 3000000000 (exceeds INT32_MAX = 2147483647); the overflow-safe formula correctly computes mid = 1500000000; the simulated 32-bit-signed-wraparound formula instead produces mid = -647483648, a NEGATIVE index. In a real Java or C implementation using (low + high) / 2 on int, this specific input (a large array with both low and high above roughly 1.07 billion, achievable in an array with more than ~2.1 billion elements, or more realistically whenever low and high are both large due to a huge search space) would compute a negative or otherwise invalid midpoint and crash with an out-of-bounds access or return an incorrect result, a bug that famously shipped in real production binary-search implementations (documented in Java's own Arrays.binarySearch history) for years before being fixed.

Trade-offs & pitfalls
This bug is specifically invisible on small test arrays: any array under roughly a billion elements never drives low + high past INT32_MAX, so a test suite exercising only 'reasonable-sized' arrays (which is the overwhelming majority of real test suites) will never catch it; the only reliable way to test for it is to reason about the arithmetic directly (as done here) rather than trying to construct an actual multi-gigabyte array, which is why this is one of the rare cases where an ANALYTICAL proof of the formula's safety is the practical test, not an executed one at full scale.

Direct answer

Normalize when write correctness and storage efficiency matter most: each fact lives in exactly one place, so an update touches one row and there is no duplicate copy to drift out of sync. Denormalize when read speed matters most: copying a value into the table that needs it removes a join at read time, at the cost of extra storage and extra write work to keep every copy consistent. The decision is really about where you are willing to pay a cost: on the write path (normalized) or on the read path (denormalized).

Structured elaboration

What normalization buys you

• A single source of truth for each fact (a customer's name lives in one row in the customers table). Rename a customer once, and every order referencing that customer's ID sees the new name immediately, because nothing else stored a copy.
• No update anomalies: you cannot end up with two rows disagreeing about the same customer's e-mail address, because there is only one row.
• Smaller row sizes and less redundant storage, since each attribute is stored once.

What it costs

• Reads that need a full picture (an order plus the customer's name and the product's title) require joining across multiple tables. As the number of tables in the join grows, so does read latency and database load per request.

What denormalization buys you

• Fast reads: a single table scan or index lookup returns everything the page needs, no join required. This matters most for read-heavy, latency-sensitive paths (a product listing page, an order-history feed).
• Fewer round-trips and less join computation on the database, which matters at high read volume.

What it costs

• Duplicated data: the same fact (a product's name, a customer's e-mail) now lives in more than one row.
• Write amplification and staleness risk: change the source fact once, and every duplicate copy must also be updated, or the duplicates drift and become wrong. If you skip updating one copy, you now have silently inconsistent data.
• More total storage, since the same bytes are stored multiple times.

How to actually decide

1. Estimate the read:write ratio on the specific table or field in question, not the system as a whole. A field read a thousand times for every write is a strong denormalization candidate; a field written as often as it is read is not.
2. Ask how often the would-be-duplicated value actually changes. A product's category ID rarely changes; a live inventory count changes constantly. Denormalizing something that changes constantly multiplies your write cost and your staleness risk.
3. Ask how expensive staleness is if a duplicate briefly lags. A denormalized display name that is a few seconds stale is usually fine; a denormalized account balance is usually not.
4. Consider partial solutions before going fully one way: a materialized view or a cached read model gives you denormalized-shaped reads without hand-maintaining duplicate columns in the source tables, at the cost of a refresh lag you must define and tolerate.

Worked example

Take an orders schema. Normalized (third normal form): an orders table (order ID, customer ID, timestamp), an order_items table (order ID, product ID, quantity, unit price), a customers table, and a products table. Rendering an order-detail page means joining order_items to products (for the product name and image) and joining orders to customers (for the customer's name), a three- to four-way join.

Suppose the system processes 1,000,000 orders a month, averaging 3 line items per order, so 3,000,000 order_items rows are written per month. A normalized order_items row (order ID, product ID, quantity, unit price as fixed-width fields) is roughly 28 bytes. A denormalized version that also copies in the product name (about 24 bytes), product category (about 12 bytes), customer name (about 20 bytes), and customer e-mail (about 24 bytes) adds about 80 bytes per row:

At 3,000,000 rows a month, that is:

of pure duplicate data added every month, before counting index overhead or replication. That is the storage side of the cost. The write side shows up when a product gets renamed: if that product already appears in 50,000 historical order_items rows, a normalized schema needs a single row updated in products; a denormalized schema that copied the product name into order_items needs all 50,000 rows updated (or accepts that historical order rows show the old name, which is a legitimate choice for orders specifically, since an order should arguably show the name as it was at purchase time, not the current name).

That last point is the real lesson: denormalizing an order line item's product name is often correct, not just a performance hack, because an order is a historical record and should not silently change when a product is renamed later. Denormalizing a customer's current e-mail address into the same row would be the wrong call, because you want that field to always reflect the customer's latest value, and a copy will drift.

Trade-offs & pitfalls

• Over-normalizing a read-heavy path (a product catalog page hit thousands of times a second) forces the database to redo the same multi-table join on every request, which is real, measurable load that a single denormalized read model would remove.
• Over-denormalizing a field that changes often multiplies write cost for a marginal read benefit, and creates a data-integrity bug class (stale duplicates) that is easy to miss in testing and expensive to debug in production.
• A common pitfall is denormalizing before measuring the actual read:write ratio, based on an assumption that reads are always dominant. Analytics and reporting schemas intentionally denormalize heavily (star-schema fact and dimension tables in an online analytical processing, OLAP, warehouse), because they are overwhelmingly read-heavy and batch-loaded; the live transactional path behind an online transaction processing (OLTP) system usually should not copy that pattern wholesale.
• The strongest senior answer treats this as a per-field decision, not a whole-schema philosophy: a single table can normalize some columns and denormalize others based on how each specific column is actually read and written.

Direct answer: The core trade-off is: spend memory now (precompute, cache, or store a lookup table) to save time later, or spend time recomputing on demand to save memory. Which way to lean depends on three factors: how often the result is reused, how tolerant the system is of stale/out-of-date results, and how much memory is actually available.

Structured elaboration

Classic precompute-vs-on-demand examples:

• A lookup table of precomputed values (e.g. factorials up to 1000, or a static configuration derived from rarely-changing source data) trades O(table size) memory for O(1) lookup, versus recomputing each value in whatever time the computation naturally takes.
• A cache of expensive function results (e.g. a memoization cache, or an application-level cache in front of a slow downstream service) trades memory for avoiding repeated work, valuable when the SAME inputs recur.

The decision criteria:

1. Reuse frequency: if a value is computed once and never needed again, caching it wastes memory for no benefit; if it's requested repeatedly, caching pays for itself quickly.
2. Staleness tolerance: if the underlying data changes and the cached/precomputed value must reflect changes promptly, you need invalidation logic (itself a real engineering cost) or must accept some staleness window.
3. Available memory: precomputing an entire table only works if it fits in your memory budget - for a combinatorially large input space, on-demand computation (possibly with a bounded LRU (least-recently-used) cache for the hot subset) is the only option.

Worked example

Consider a service computing an expensive per-user recommendation score, requested on average 5 times per user session. Precomputing (caching) the score after the first computation means requests 2-5 are O(1) lookups instead of paying the full computation cost again - a 5x reduction in total compute for that session, at the cost of holding the cached score in memory for the session's duration. If instead each user only ever requested the score ONCE, caching would add memory overhead (allocating and eventually evicting a cache entry) with zero reuse benefit - the "precompute and cache" decision is only a net win when the reuse count exceeds roughly the overhead ratio of caching versus recomputing, which for a cheap computation might mean caching isn't worth it at all.

Trade-offs & pitfalls

• Caching introduces a NEW correctness concern (staleness/invalidation) that a pure recompute-on-demand approach doesn't have - "correct but occasionally slow" is sometimes preferable to "fast but occasionally wrong," depending on the domain (financial data usually can't tolerate staleness; a recommendation score usually can).
• Precomputing a full table only makes sense when the input space is small/bounded enough to enumerate - for an unbounded or combinatorially large input space, you need either an on-demand approach or a BOUNDED cache (with an eviction policy) covering just the hot subset.
• The "free lunch" case is when precomputation happens once, amortized across many users/requests, and the underlying data changes rarely (e.g. compiling a regex once at startup rather than on every request) - here there's essentially no downside, which is why this specific pattern (compute-once-at-startup) is nearly always a correct default when applicable.

Direct answer
When a postmortem produces more action items than the team can implement soon, prioritize using a small set of explicit criteria rather than gut feel: expected reduction in likelihood or blast radius of recurrence, implementation effort, whether the item is a quick mitigation versus a deeper systemic fix, and dependencies between items. Make the criteria and the resulting order visible to stakeholders rather than deciding quietly, since the trade-offs being made are legitimate business decisions, not just engineering housekeeping.

Structured elaboration
A practical framework: score each action item on (1) risk reduction, how much it lowers the chance or impact of recurrence, (2) effort, roughly how much engineering time it needs, (3) urgency, whether related incidents are already recurring or a related SLO is close to breach, and (4) dependencies, whether it blocks or is blocked by other items. High risk-reduction, low-effort items go first almost automatically. High risk-reduction, high-effort items get scheduled deliberately into a near-term roadmap rather than deferred indefinitely, since these are usually the systemic fixes that actually stop the incident class from recurring. Low risk-reduction items, however well-intentioned, get explicitly deprioritized or dropped rather than left open forever accumulating as unaddressed debt nobody looks at again.

Communicating this to stakeholders matters as much as the framework itself: present the ranked list with the reasoning, not just the outcome, so a product or business stakeholder understands why a lower-effort item shipped before a higher-impact one that needed more time, and can weigh in if they disagree with the trade-off.

Worked example
A postmortem for a payments-processing outage produces five action items: (1) add a canary stage to the deploy pipeline for this service, medium effort, high risk reduction; (2) fix a specific null-pointer bug that triggered this incident, low effort, low risk reduction since it only prevents this exact trigger; (3) build a full chaos-engineering test suite for the payments stack, very high effort, high risk reduction but slow to deliver; (4) update the on-call runbook with a faster rollback procedure, low effort, medium risk reduction; (5) rewrite the payments service in a different language for 'long-term resilience,' very high effort, speculative risk reduction. A reasonable prioritization: (2) and (4) ship this week since they are cheap and net-positive even though their impact is modest; (1) gets scheduled into the next sprint as the highest-value item that's actually achievable soon; (3) gets scoped and put on a quarterly roadmap rather than blocking anything else; (5) gets explicitly declined with a documented reason, since its risk-reduction claim is speculative relative to its cost.

Trade-offs and pitfalls
The most common failure is treating every action item as equally mandatory because it came out of a postmortem, which either overloads the team or causes items to silently rot unimplemented. The second most common failure is prioritizing purely by effort (cheapest first) without weighing risk reduction, which ships a lot of low-value busywork while the systemic fix that would actually prevent recurrence keeps slipping.

Direct answer

Split every log into its identifier (everything before the first space) and its content (everything after), and route each log into one of two buckets based on the first character of its content: if that character is a digit, it is a digit-log and goes untouched into a bucket that preserves the input's original relative order; otherwise it is a letter-log and goes into a bucket that gets sorted by content first, falling back to identifier only to break ties. The final result concatenates the sorted letter-logs followed by the untouched digit-logs.

Structured elaboration

Classifying each log. The identifier is the substring before the first space; the content is everything after it. The classification rule looks at the FIRST CHARACTER of the content, not the identifier: if it is a digit character, the whole log is a digit-log, otherwise it is a letter-log. A common bug is checking whether the identifier looks numeric instead of the content; the identifier's own characters (letters, digits, or a mix) carry no bearing on the classification.

Sorting letter-logs with a two-key comparator. The requirement is content first, identifier second as a tiebreaker, both compared as ordinary lexicographic string comparisons. Rather than chaining two separate sorts, a single comparator that compares content first and only falls back to identifier when the contents are equal achieves the same result in one pass, and works correctly regardless of whether the underlying sort is stable, because the tiebreak is explicit rather than relied upon implicitly.

Leaving digit-logs untouched. The digit-log bucket is never sorted or reordered; it is simply the digit-logs collected in the same relative order they appeared in the original input. This is the detail most likely to be implemented wrong: if the whole array were sorted with a single comparator without first partitioning by log type, digit-logs would end up compared as TEXT alongside letter-logs, which both violates the requirement and produces a nonsensical ordering for logs whose content is meant to be treated as opaque data, not sortable text.

Complexity. Partitioning the array into the two buckets is a single O(n) pass (n = total logs). Sorting the letter-logs bucket is O(k log k) comparisons (k = number of letter-logs), and each comparison itself costs up to O(L) where L is the length of the longer of the two contents or identifiers being compared, so a fully precise bound is O(k log k * L); the headline complexity interviewers usually want stated is O(n + k log k). Because digit-logs are never sorted, they cost only the O(n) partition pass, not an additional O((n-k) log(n-k)).

Worked example

function reorderLogFiles(logs) {
  const letterLogs = [];
  const digitLogs = [];
  for (const log of logs) {
    const spaceIdx = log.indexOf(" ");
    const identifier = log.slice(0, spaceIdx);
    const content = log.slice(spaceIdx + 1);
    if (content[0] >= "0" && content[0] <= "9") {
      digitLogs.push(log);
    } else {
      letterLogs.push({ identifier, content, original: log });
    }
  }
  letterLogs.sort((a, b) => {
    if (a.content !== b.content) return a.content < b.content ? -1 : 1;
    return a.identifier < b.identifier ? -1 : a.identifier > b.identifier ? 1 : 0;
  });
  return letterLogs.map((e) => e.original).concat(digitLogs);
}

const logs = ["dig1 8 1 5 1", "let1 art can", "let2 own kit dig", "let3 art zero"];
console.log(reorderLogFiles(logs));

Output:

[ 'let1 art can', 'let3 art zero', 'let2 own kit dig', 'dig1 8 1 5 1' ]

Tracing why: the letter-logs' contents are "art can" (let1), "own kit dig" (let2), and "art zero" (let3); sorted lexicographically, "art can" precedes "art zero" (both share the "art " prefix, then 'c' sorts before 'z'), and both precede "own kit dig" ('a' sorts before 'o'), giving let1, let3, let2. The single digit-log (dig1) is appended unchanged at the end. A second test with two digit-logs (a1 and zo4) confirmed they retain their OWN original relative order (a1 before zo4) in the output, which is the part a partition-then-sort-only-one-bucket implementation must get right.

Trade-offs and pitfalls

The most consequential bug is applying a single comparator to the whole array without partitioning first: because digit-log content looks like ordinary text to a string comparator, it would get sorted as if it were letter-log content, silently violating the "digit-logs keep their original order" requirement while still producing a plausible-looking, fully-sorted array. A second common bug is sorting letter-logs by content alone and relying on the underlying sort's stability to "happen to" preserve original relative order for ties, rather than implementing the identifier tiebreak explicitly; this can pass on test data that has no true content ties and then fail once two letter-logs share identical content but different identifiers. A third pitfall is misidentifying the classification signal itself, checking the identifier for digits instead of the content's first character, which is wrong precisely because identifiers are free-form and can contain digits regardless of whether the log is a letter-log or digit-log.

The idea

Level-order (breadth-first) traversal visits the root, then all nodes one edge below it, then all nodes two edges below, and so on. A generator is a function that uses yield to hand back one value at a time and stays suspended between requests, so the caller pulls nodes only as needed. Nothing has to be built up front.

The only state a level-order walk needs is the frontier: nodes you have discovered but not yet yielded. Pop a node from the front, push its children onto the back, yield it. Because children are appended behind everything already waiting, the queue empties one level at a time. Heights and depths count edges (an empty tree is -1, a single node 0), so level k holds the nodes at depth k.

Brute force and why it is not enough

The textbook version builds a whole list of nodes for each level and joins the lists, or collects the entire traversal into a result list and returns it. Both are O(n) memory and nothing is available to the caller until the traversal finishes. The generator below stores only the frontier.

Approach

1. Start with a deque (a double-ended queue with O(1) work at both ends) holding the root, or nothing for an empty tree. A Python list.pop(0) shifts every waiting element one place left, so a pop costs time proportional to the frontier instead of O(1); a list is the wrong container here.
2. Loop while the deque is non-empty: pop from the left, append the left then right child if present, then yield the node.
3. When the caller stops asking, the generator is suspended at the yield. When it asks again, the loop continues exactly there.

Code

The tree used in the trace and in the resume demos:

      1
     / \
    2   3
   / \   \
  4   5   6

import pickle
import random
from collections import deque
from itertools import islice


class Node:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right


def level_order(root, stats=None, trace=None):
    """Yield nodes level by level; only discovered-but-not-yet-yielded nodes are stored."""
    frontier = deque([root] if root else [])
    while frontier:
        node = frontier.popleft()
        if node.left:
            frontier.append(node.left)
        if node.right:
            frontier.append(node.right)
        if stats is not None:
            stats["peak"] = max(stats["peak"], len(frontier))
        if trace is not None:
            trace.append(f"yield {node.val}, stored {[n.val for n in frontier]}")
        yield node


class LevelOrderCursor:
    """Counts what it has produced, so a new cursor can continue from that count."""

    def __init__(self, root, skip=0):
        self._nodes = islice(level_order(root), skip, None)   # replays and discards `skip` nodes
        self.produced = skip

    def __iter__(self):
        return self

    def __next__(self):
        node = next(self._nodes)
        self.produced += 1
        return node


class FrontierCursor:
    """Level-order cursor whose whole state is the ids of the nodes still waiting.
    `fetch(id)` returns the live node with that id (in a real system, a database read)."""

    def __init__(self, fetch, waiting):
        self.fetch, self.waiting = fetch, deque(waiting)

    def next(self):
        node = self.fetch(self.waiting.popleft())
        for child in (node.left, node.right):
            if child:
                self.waiting.append(child.val)       # a node's value serves as its id here
        return node

    def checkpoint(self):
        return list(self.waiting)                    # at most twice the widest level of ids


def by_levels(root):
    """Textbook version for comparison: builds a whole list per level."""
    order, level = [], [root] if root else []
    while level:
        order += [n.val for n in level]
        level = [c for n in level for c in (n.left, n.right) if c]
    return order


tree = Node(1, Node(2, Node(4), Node(5)), Node(3, None, Node(6)))
steps = []
print("order:", [n.val for n in level_order(tree, trace=steps)])
print("\n".join(steps))

stats = {"peak": 0}
list(level_order(tree, stats))
levels, level = [], [tree]
while level:
    levels.append(len(level))
    level = [c for n in level for c in (n.left, n.right) if c]
print("level widths:", levels, "| most nodes stored at once:", stats["peak"])

# pause and resume inside one process: the generator object keeps its own place
gen = level_order(tree)
first_three = [next(gen).val for _ in range(3)]
print("\nfirst three:", first_three, " (caller does other work here)")
print("resumed    :", [n.val for n in gen])

# pause, persist a count, resume in a "new process" by replaying
cursor = LevelOrderCursor(tree)
seen = [next(cursor).val for _ in range(4)]
saved = cursor.produced
resumed = LevelOrderCursor(tree, skip=saved)
print("\nstopped after", saved, "nodes:", seen, "| new cursor continues:", [n.val for n in resumed])

# a generator object cannot be saved
try:
    pickle.dumps(level_order(tree))
except TypeError as err:
    print("\npickle.dumps(generator):", err)

# pause, save only the ids of the waiting nodes, resume from them (the dict stands in for a database)
store = {1: tree, 2: tree.left, 3: tree.right, 4: tree.left.left, 5: tree.left.right, 6: tree.right.right}
cursor = FrontierCursor(store.__getitem__, [tree.val])
seen = [cursor.next().val for _ in range(4)]
saved = cursor.checkpoint()
print("\nyielded", seen, "| checkpoint (ids still waiting):", saved)
store[7] = Node(7)
store[5].left = store[7]            # child added under 5, which has not been yielded yet
store[8] = Node(8)
store[4].left = store[8]            # child added under 4, which was already yielded
resumed = FrontierCursor(store.__getitem__, saved)
rest = []
while resumed.waiting:
    rest.append(resumed.next().val)
print("rebuilt deque from the ids and continued:", rest, "(7 is seen, 8 is missed)")
store[4].left = None                # restore the tree for the checks below
store[5].left = None

# random trees against the textbook version
rng = random.Random(3)
distinct = set()
for _ in range(300):
    vals = rng.sample(range(1000), rng.randint(1, 40))
    nodes = [Node(v) for v in vals]
    for i in range(1, len(nodes)):
        while True:
            p = nodes[rng.randrange(i)]
            side = rng.choice(("left", "right"))
            if getattr(p, side) is None:
                setattr(p, side, nodes[i])
                break
    got = [n.val for n in level_order(nodes[0])]
    assert got == by_levels(nodes[0])
    distinct.add(tuple(got))
print("random trees checked:", len(distinct), "distinct orders")

# empty and single-node trees
print("empty tree yields:", [n.val for n in level_order(None)], "| single node yields:", [n.val for n in level_order(Node(7))])

# memory: how many nodes are stored at once


def perfect(depth):
    if depth < 0:
        return None
    return Node(depth, perfect(depth - 1), perfect(depth - 1))


def chain(n):
    root = cur = Node(0)
    for i in range(1, n):
        cur.left = Node(i)
        cur = cur.left
    return root


for name, t, total, width in (("perfect tree, height 12", perfect(12), 2 ** 13 - 1, 2 ** 12),
                              ("left chain, 100,000 nodes", chain(100_000), 100_000, 1)):
    stats = {"peak": 0}
    count = sum(1 for _ in level_order(t, stats))
    print(f"{name}: {count:,} nodes yielded, widest level {width:,}, peak stored {stats['peak']:,}")

Output

Printed by Python 3.12. The wording of the pickle.dumps error line is that version's.

order: [1, 2, 3, 4, 5, 6]
yield 1, stored [2, 3]
yield 2, stored [3, 4, 5]
yield 3, stored [4, 5, 6]
yield 4, stored [5, 6]
yield 5, stored [6]
yield 6, stored []
level widths: [1, 2, 3] | most nodes stored at once: 3

first three: [1, 2, 3]  (caller does other work here)
resumed    : [4, 5, 6]

stopped after 4 nodes: [1, 2, 3, 4] | new cursor continues: [5, 6]

pickle.dumps(generator): cannot pickle 'generator' object

yielded [1, 2, 3, 4] | checkpoint (ids still waiting): [5, 6]
rebuilt deque from the ids and continued: [5, 6, 7] (7 is seen, 8 is missed)
random trees checked: 300 distinct orders
empty tree yields: [] | single node yields: [7]
perfect tree, height 12: 8,191 nodes yielded, widest level 4,096, peak stored 4,096
left chain, 100,000 nodes: 100,000 nodes yielded, widest level 1, peak stored 1

Reading the trace

• Each line shows what the deque holds at the moment a node is yielded. After yielding 1, the children 2 and 3 are stored. After yielding 2 the deque holds [3, 4, 5]: the rest of level 1 followed by the first nodes of level 2.
• At no point does the deque contain anything beyond the next level, which is why memory depends on the tree's width and not on its total size.
• The perfect tree of height 12 (8,191 nodes) peaks at 4,096 stored nodes, the width of its bottom level. The left chain of 100,000 nodes never stores more than 1 and runs without recursion, so it needs no stack at all.

How a caller resumes after a pause

• Within one process: do nothing special. A generator keeps its local variables, including the deque, while it is suspended. The caller keeps the generator object, goes off to do other work (the point marked after the first three line), and calls next() again later. The output shows [1, 2, 3] followed by [4, 5, 6] from the same generator.
• Across a restart, a queue message or a network hop: a generator object cannot be saved (pickling, Python's standard way of turning an object into bytes for storage, fails: the output shows cannot pickle 'generator' object), so the state has to be explicit. The cursor class keeps a count of the nodes produced. Saving that count and constructing a new cursor with skip=count replays and discards that many nodes (islice(iterator, skip, None) throws away the first skip items and passes on the rest) and continues. The run above stops after 4 nodes and the new cursor continues with [5, 6].
• The cost of that checkpoint: one integer to store, but resuming takes O(k) time to replay k nodes (memory stays at the frontier size), and it is only correct if the tree is unchanged during the pause.
• Checkpointing the frontier itself: if the tree can change, save the ids of the nodes still waiting (a checkpoint is a saved copy of the progress). FrontierCursor in the program does this: its entire state is the deque of ids, checkpoint() returns them, and a new cursor is built from that list by looking each id up with fetch (a database read in a real system; the dict stands in for it). In the run, after yielding [1, 2, 3, 4] the checkpoint is [5, 6]. While paused, a child 7 was added under node 5 (not yet yielded) and a child 8 under node 4 (already yielded). The resumed cursor continues with [5, 6, 7]: 7 is seen because 5's children are read when 5 is yielded, and 8 is missed because 4's children were already read, and found empty, when 4 was yielded before the pause. The saved list is at most twice the widest level of ids, never the whole tree.

Complexity

• Time O(n): each node is pushed once, popped once and yielded once, all O(1) deque operations.
• Space O(w), where w is the maximum number of nodes stored, which is at most the sum of two adjacent level widths (the unyielded rest of the current level plus the children found so far), so at most twice the widest level. On the example tree the level widths are 1, 2 and 3, the most nodes ever stored is 3 (printed), and twice the widest level is 6. It is O(n) for a perfect tree (the last level holds about half the nodes) and O(1) for a chain.
• No recursion, so depth is irrelevant: the 100,000-node chain works where a recursive traversal would exceed Python's default limit of 1000 frames.

Edge cases and common mistakes

• Empty tree: the generator yields nothing, and a single node yields exactly one node (both are printed in the output). Without the if root else [] guard the deque would start holding None and the first pop would fail on None.left.
• Enqueuing children after the yield instead of before it. A caller that stops right after a yield and checkpoints the frontier would then be missing the children of the node it just received. The code enqueues first, so the stored frontier is always complete. This mistake leaves the order unchanged, so the comparison with the textbook version cannot catch it; the trace does: with the enqueue moved after the yield, the yield 1 line would read stored [] instead of stored [2, 3].
• Using list.pop(0), where each pop shifts every waiting element, so a step costs time proportional to the frontier size. On a perfect tree, where the frontier reaches about n/2, the traversal becomes quadratic; on a chain the frontier is 1 and nothing changes. It gives the same order and the same trace, so only a cost count would reveal it; none of the printed lines does.
• Making the generator yield the whole level as one list when the question asks for nodes: a wide level then costs O(w) at once.
• Starting a new for loop over an exhausted generator and getting nothing: a generator is single-use, so a fresh call to level_order(root) is needed.
• Changing the tree while a traversal is paused and expecting a snapshot: the walk follows the live pointers.

Running the code

python3.12 level_order_generator.py

Save the code block as level_order_generator.py. Standard library only (collections, itertools, pickle, random).