Spotify Software Engineer (Junior Level) Interview Preparation Guide 2026

Direct answer

Don't optimize the layer that looks slow, instrument the request path end to end first. Get a latency budget broken into per-hop numbers (network, serialization, database, business logic) that actually sum to the 200 ms observed, then attack the hop with the best ratio of milliseconds saved to effort required, re-measuring after every change rather than assuming which layer is guilty before the data says so.

Structured elaboration

Method, in order:

1. Baseline with distributed tracing across the full request path, capturing per-hop timing, not just a total.
2. Form one hypothesis per layer (network/TLS overhead, serialization cost, database query time, business logic compute) and check it against the trace data rather than intuition.
3. Rank candidate fixes by (milliseconds likely saved) divided by (implementation effort and risk), not by which one is technically most interesting.
4. Ship the highest-ranked fix, re-measure the full trace, and repeat, because fixing the biggest hop changes which hop is now biggest.

Isolation checks, when tracing alone doesn't localize it: compare with keep-alive/connection pooling on versus off to isolate network/TLS overhead, compare payload size before and after trimming to isolate serialization cost, and compare with and without a query cache or added index to isolate the database's contribution.

Worked example

Assume tracing on the current 200 ms path yields this breakdown (illustrative numbers, chosen to sum to the measured total):

Reproducing the arithmetic: current total $40+15+100+45=200\text{ms}$, matching the measured baseline. Target total $10+5+25+10=50\text{ms}$, matching the 50 ms goal, and the sum of savings $30+10+75+35=150\text{ms}$ accounts for exactly the gap ($200-50=150$). The database hop is the largest single lever (75 ms, half the total savings) and gets prioritized first for that reason, not because it's assumed to be the culprit before measuring.

Trade-offs & pitfalls

• Jumping straight to rewriting business logic when tracing shows the database is half the budget is solving the wrong problem first, always rank by measured contribution, not by which layer is the most familiar to fix.
• Not re-measuring after each change stacks unverified assumptions, a fix that looked good in isolation can interact badly with the next one.
• Chasing 90% of the theoretical win on the hardest 10% of the effort (a protocol rewrite) before taking the cheap 30 ms keep-alive win first wastes the easiest gains.
• Caching for latency introduces a correctness trade-off (staleness) that needs an explicit owner and time-to-live (TTL), "just add a cache" without that ownership is a common wrong turn.
• Reserve architectural changes (removing a network hop entirely, changing the protocol) for after the low-risk, high-yield fixes are exhausted, they carry more deployment and compatibility risk and should be justified by the remaining gap, not reached for first.

Metrics to track to forecast the spikes

• Request rate over time, to see the actual shape and onset speed of each spike, not just its peak magnitude.
• CPU utilization trend as a spike approaches, to confirm compute is tracking the traffic curve as expected.
• Latency percentiles (p95/p99, meaning the response time that the slowest 5% and 1% of requests exceed), an early sign of saturation before outright failures appear.
• Queue length or backlog depth, which for a data-serving fleet is often the earliest leading indicator: a queue growing faster than it's draining signals the fleet can't keep up before latency or error rates show it.

Pre-warming versus reserving on standby

Because these are recurring, predictable seasonal spikes with historical data behind them (unlike a one-off event with no track record), I'd favor pre-warming ahead of the known window over holding idle standby capacity year-round: scale up and warm caches shortly before the historically observed onset time, rather than paying for capacity that sits unused most of the year. Reserving idle standby makes more sense when the timing itself is unpredictable and there's no reliable lead-time signal to pre-warm against.

Cost versus availability risk, worked example

Say the baseline fleet costs $15K/month. Holding the full 10x capacity in standby year-round would add roughly $80K/month, about $960K/year. Pre-warming that same capacity only for the known spike windows, say 6 weeks total across the year, costs closer to $80K x (6/4.33), where 4.33 is the average number of weeks in a month (52 weeks / 12 months), which is about $110K for the year. Pre-warming into known windows is dramatically cheaper, but it only works if the timing is predictable enough to trust and there's enough lead time to actually warm the fleet (populate caches, ramp connection pools) before the spike arrives.

The availability risk to watch for

The main risk with pre-warming is being late: if warming starts even a little after the spike's real onset, the fleet hits the spike cold, and for a data-serving fleet specifically, a backlog that starts forming under a 10x load compounds quickly rather than draining. I'd build in a safety lead-time buffer, starting the warm-up a fixed amount of time before the earliest historically observed onset, not the average onset, so a slightly-early spike doesn't catch the fleet unprepared.

Direct answer

I treat the two weeks as two checkpoints with different jobs: week one proves I can build something small and correct end to end, and week two proves I can be trusted near production, with an explicit go or no-go gate between them rather than one long ramp checked only at the deadline. What I want to show at the end of each week is a real, working artifact, not a status update, and before touching anything real users depend on I want a second pair of eyes from someone who already knows the tool, a working rollback path, and evidence the artifact has already survived review.

Structured elaboration

• What has to be true before touching real users: someone who already knows the tool has reviewed the specific change, not just "the tool" in general; there is a tested rollback or feature flag; and I can explain the tool's real failure modes, not just its happy path.
• Defer anything the task does not need in week one; if week one slips, the cut comes out of the deliverable's scope, not the readiness gates in week two.
• If the ramp overlaps an existing delivery commitment, say so honestly up front rather than quietly running both at full pace, and name what gets lower priority for the two weeks.
• Some ramps are really about a regulatory or compliance standard rather than a piece of software, learning it well enough to run a gap analysis; the same two-checkpoint shape applies, with review from someone who knows the standard replacing review from someone who knows the tool.
• If the ramp is also about rebuilding a stakeholder's confidence after an earlier miss, the week-one deliverable is chosen to be visible and verifiable to that specific stakeholder, not just technically correct.
• When two comparable tools could plausibly have been chosen, spend part of day one comparing how steep each one's learning curve looks against the actual task, rather than assuming the standardized pick is automatically the easy one.

Worked example

The team standardized on a new workflow-orchestration tool to replace ad hoc scheduled scripts, and I had never used it. Day one and two: got access and ran the tool's own quickstart against a real, non-production pipeline definition from our own repository rather than the tool's sample data, so I hit our actual quirks immediately. By end of week one, a small, real pipeline was migrated and running correctly in staging, reviewed by a teammate on another team who had used the tool for a year; that review caught that I had misunderstood how retries interacted with idempotency, which would have silently double-run a step on failure. In week two, before touching the production pipeline, I confirmed three things had to be true: someone experienced had reviewed the specific migration diff, I had a tested way to fail back to the old script if the new pipeline misbehaved, and I could explain what happens to in-flight work if the orchestrator restarts mid-run. I migrated the lowest-risk pipeline first as a pilot rather than everything at once, watched it under real load, then moved the rest.

Trade-offs and pitfalls

• Treating the two weeks as one long ramp checked only at the deadline hides problems until it is too late to recover; splitting into a week-one proof and a week-two readiness gate surfaces gaps early enough to fix.
• Skipping the review-by-someone-experienced step to save time is the single most common way a technically working migration causes a production incident, since a newcomer's blind spots are exactly what a veteran user has already learned to check for.
• If week one runs long, cutting the readiness gates instead of the deliverable's scope trades a manageable delay for an unmanageable production risk.

The idea in plain words

A binary search tree (BST) keeps smaller keys to the left and larger keys to the right, so an in-order walk (left subtree, node, right subtree) visits keys in sorted order. Sorted inserts turn the tree into a chain, so a lookup walks about half of the chain on average. The fix needs one insight. Many different trees hold the same sorted keys: the keys 1 to 7 can form a chain with root 1 (height 6) or a tree with root 4 (height 2), and both read 1, 2, 3, 4, 5, 6, 7 in order. So a BST is fully determined by its in-order sequence plus the choice of root for each range of keys, and if you pick the middle element as the root of every range, the height is as small as possible. The rebuild is therefore: flatten the tree into a sorted list, then rebuild by repeatedly taking the middle.

Heights here count edges: the empty tree has height -1 and a single node has height 0.

Brute force and why it is not enough

Re-inserting the sorted keys one by one into a fresh tree reproduces the chain (the same sorted order that caused the problem) and costs O(n^2). Inserting in a shuffled order gives an average node depth that grows like 1.39 log2 n (the leading term of the textbook result for random insertion orders), but with no guarantee for a given order; the checking program below measures it. Picking the middle element each time gives the guaranteed minimum height, floor(log2 n), in O(n).

Approach

1. Walk the tree in order with an explicit stack (not recursion, because a chain of 5000 nodes exceeds CPython's default limit of 1000 frames) and collect the Node objects themselves, not only their keys.
2. Recursively build over the half-open index range [lo, hi) (it includes index lo but not index hi, so [0,7) is indexes 0 to 6 and [2,2) is empty): the middle node becomes the root, [lo, mid) builds its left subtree, [mid+1, hi) its right. The +1 skips the middle itself, and the two ranges differ in size by at most one, which is why neither side can be much taller than the other. This recursion is only about log2 n frames deep, so it is safe at any size.
3. Reusing the same Node objects means any extra per-node data (here payload) travels with its key and nothing needs copying. Every left and right pointer is overwritten, so no stale link survives.

Code

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


def insert(root, key, payload=None):
    """Plain BST insert (iterative, so a long chain never hits the recursion limit)."""
    node = Node(key, payload)
    if root is None:
        return node
    cur = root
    while True:
        if key < cur.key:
            if cur.left is None:
                cur.left = node
                break
            cur = cur.left
        else:
            if cur.right is None:
                cur.right = node
                break
            cur = cur.right
    return root


def height(root):
    """Height in edges: empty tree -1, single node 0. Iterative (level by level)."""
    if root is None:
        return -1
    h, level = -1, [root]
    while level:
        h += 1
        level = [c for n in level for c in (n.left, n.right) if c]
    return h


def inorder_nodes(root):
    """Iterative in-order walk: returns the Node objects in ascending key order."""
    out, stack, cur = [], [], root
    while stack or cur:
        while cur:
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()
        out.append(cur)
        cur = cur.right
    return out


def build_balanced(nodes, lo, hi, log=None, depth=0):
    """Make nodes[lo:hi] into a tree rooted at the middle node; relinks the existing Node objects."""
    if lo >= hi:
        return None
    mid = (lo + hi) // 2
    if log is not None:
        log.append(f"{'  ' * depth}range [{lo},{hi}) -> root {nodes[mid].key}")
    node = nodes[mid]
    node.left = build_balanced(nodes, lo, mid, log, depth + 1)
    node.right = build_balanced(nodes, mid + 1, hi, log, depth + 1)
    return node


def rebalance(root, log=None):
    nodes = inorder_nodes(root)
    return build_balanced(nodes, 0, len(nodes), log)


def draw(root):
    """Sideways text drawing: right subtree on top, root at the left margin."""
    lines = []
    def walk(n, depth):
        if n is None:
            return
        walk(n.right, depth + 1)
        lines.append("    " * depth + str(n.key))
        walk(n.left, depth + 1)
    walk(root, 0)
    return "\n".join(lines)


if __name__ == "__main__":
    # Sorted inserts make a chain. Each node carries extra data (payload).
    root = None
    for k in [1, 2, 3, 4, 5, 6, 7]:
        root = insert(root, k, payload=f"user-{k}")
    print("before, height", height(root))
    print(draw(root))
    keys_before = [n.key for n in inorder_nodes(root)]
    print("sorted keys:", keys_before)
    log = []
    root = rebalance(root, log)
    print("\n".join(log))
    print("after, height", height(root))
    print(draw(root))
    print("payload kept:", [(n.key, n.payload) for n in inorder_nodes(root)][:3], "...")

    # Larger check: 5000 sorted inserts, then compare against the minimum possible height.
    big = None
    for k in range(5000):
        big = insert(big, k, payload=k * 10)
    print("chain of 5000: height", height(big))
    big = rebalance(big)
    print("rebalanced: height", height(big), "minimum possible", (5000).bit_length() - 1)
    assert [n.key for n in inorder_nodes(big)] == list(range(5000))
    assert all(n.payload == n.key * 10 for n in inorder_nodes(big))

    # A recursive in-order walk fails on the same chain (CPython default limit is 1000 frames).
    chain = None
    for k in range(5000):
        chain = insert(chain, k)
    def recursive_inorder(n, out):
        if n:
            recursive_inorder(n.left, out)
            out.append(n.key)
            recursive_inorder(n.right, out)
    try:
        recursive_inorder(chain, [])
    except RecursionError:
        print("recursive in-order on the chain: RecursionError")

Output:

before, height 6
                        7
                    6
                5
            4
        3
    2
1
sorted keys: [1, 2, 3, 4, 5, 6, 7]
range [0,7) -> root 4
  range [0,3) -> root 2
    range [0,1) -> root 1
    range [2,3) -> root 3
  range [4,7) -> root 6
    range [4,5) -> root 5
    range [6,7) -> root 7
after, height 2
        7
    6
        5
4
        3
    2
        1
payload kept: [(1, 'user-1'), (2, 'user-2'), (3, 'user-3')] ...
chain of 5000: height 4999
rebalanced: height 12 minimum possible 12
recursive in-order on the chain: RecursionError

Worked trace

The seven sorted inserts give the chain drawn first (the drawing is sideways: the right subtree is above its parent, the root is at the left margin). The log lines show which index range each call handles and which node becomes its root: [0,7) picks index 3 (key 4), then [0,3) picks key 2 and [4,7) picks key 6, and the single-element ranges finish the leaves. Height drops from 6 to 2, which is floor(log2 7). The 5000-node chain drops from 4999 to 12, equal to the minimum possible height floor(log2 5000).

Complexity

• Time: O(n). The in-order walk touches each node once, and the build creates each node's links once.
• Memory: O(n) extra. The list of n node references is the cost. The walk's stack is at most h entries (up to n on a left-leaning chain: the checking program shows 5000 entries for a 5000-node chain, next to a list of the same length), and the build recursion is O(log n). No new Node objects are allocated.
• Copying out (key, payload) pairs and allocating new nodes instead would roughly double the node memory while both trees exist; reusing the nodes avoids that.

Edge cases and common mistakes

• Empty tree: the list is empty, build_balanced returns None, and the height is -1.
• One node: returns that node with height 0.
• Duplicate keys (inserted to the right here) keep their order because the walk is in order and the build never compares keys. The checking program rebuilds 300 lists with many repeated keys and finds the same keys and arrival tags in the same order.
• Using a recursive in-order walk: it works on a balanced tree and raises RecursionError on the chain, as the last output line shows.
• Rebuilding from keys only: any payload attached to a node is silently lost.
• Choosing mid = lo + (hi - lo) // 2 or (lo + hi) // 2 are both fine in Python; in a fixed-width language the sum lo + hi can overflow, so use the first form.
• Forgetting to reset left and right on a reused node: the old links keep pointing at nodes that now sit elsewhere, so a walk reaches nodes a second time. The last two lines of the checking program show 0 repeats with the reset and 3 repeats without it, for seven keys.

Checking the claims and one rotation

The program below shows a rotation on three keys, measures the average node depth for random insertion orders against the middle-rooted tree, checks that every middle split leaves halves that differ by at most one, counts the stack and list sizes when walking a left-leaning chain of 5000 nodes, rebuilds lists with many repeated keys, and compares a rebuild that resets the links with one that does not:

import math
import random


class Node:
    def __init__(self, key, tag=None):
        self.key = key
        self.tag = tag               # stands in for the extra per-node data
        self.left = self.right = None


def insert(root, key, tag=None):
    node = Node(key, tag)
    if root is None:
        return node
    cur = root
    while True:
        side = "left" if key < cur.key else "right"
        nxt = getattr(cur, side)
        if nxt is None:
            setattr(cur, side, node)
            return root
        cur = nxt


def preorder(node):
    return [] if node is None else [node.key] + preorder(node.left) + preorder(node.right)


def rotate_right(node):
    """The left child moves up; the old root becomes its right child."""
    top = node.left
    node.left, top.right = top.right, node
    return top


def rotate_left(node):
    top = node.right
    node.right, top.left = top.left, node
    return top


# Same in-order sequence 1, 2, 3 in two different shapes: a rotation changes only the shape.
chain = Node(3)
chain.left = Node(2)
chain.left.left = Node(1)
print("left-leaning chain, preorder:", preorder(chain))
balanced = rotate_right(chain)
print("after one right rotation at the root, preorder:", preorder(balanced))
print("root", balanced.key, "children", balanced.left.key, balanced.right.key)
back = rotate_left(balanced)
print("one left rotation undoes it, preorder:", preorder(back))


def average_depth(keys_in_order):
    root = None
    for k in keys_in_order:
        root = insert(root, k)
    total, stack = 0, [(root, 0)]
    while stack:
        node, d = stack.pop()
        total += d
        for c in (node.left, node.right):
            if c:
                stack.append((c, d + 1))
    return total / len(keys_in_order)


def balanced_order(lo, hi):
    """Keys lo..hi-1 listed so that inserting them in this order builds the middle-rooted tree."""
    if lo >= hi:
        return []
    mid = (lo + hi) // 2
    return [mid] + balanced_order(lo, mid) + balanced_order(mid + 1, hi)


n = 1023
rng = random.Random(11)
trials = 100
mean_random = sum(average_depth(rng.sample(range(n), n)) for _ in range(trials)) / trials
print(f"\nn = {n} keys, average node depth (edges):")
print(f"  random insertion orders, mean of {trials}: {mean_random:.2f}")
print(f"  1.39 * log2(n): {1.39 * math.log2(n):.2f}")
print(f"  middle-rooted tree: {average_depth(balanced_order(0, n)):.2f}")


def halves_differ_by_at_most_one(lo, hi):
    if hi - lo <= 1:
        return True
    mid = (lo + hi) // 2
    return (abs((mid - lo) - (hi - mid - 1)) <= 1
            and halves_differ_by_at_most_one(lo, mid) and halves_differ_by_at_most_one(mid + 1, hi))


print("every range of every size 0..2000 splits into halves that differ in size by at most 1:",
      all(halves_differ_by_at_most_one(0, size) for size in range(2001)))

# Memory: walking a left-leaning chain keeps every node on the stack at once.
size = 5000
chain = None
for k in range(size, 0, -1):
    chain = insert(chain, k)
stack, cur, deepest, collected = [], chain, 0, 0
while stack or cur:
    while cur:
        stack.append(cur)
        cur = cur.left
    deepest = max(deepest, len(stack))
    cur = stack.pop()
    collected += 1
    cur = cur.right
print(f"descending inserts of {size} keys: the in-order stack reaches {deepest} entries, the node list {collected}")


# Repeated keys and stale links. Same rebuild as the main listing, with a switch to skip the link reset.
def inorder_nodes(root):
    out, stack, cur = [], [], root
    while stack or cur:
        while cur:
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()
        out.append(cur)
        cur = cur.right
    return out


def build(nodes, lo, hi, reset=True):
    if lo >= hi:
        return None
    mid = (lo + hi) // 2
    node = nodes[mid]
    left = build(nodes, lo, mid, reset)
    right = build(nodes, mid + 1, hi, reset)
    if reset or left:
        node.left = left
    if reset or right:
        node.right = right
    return node


def height(root):
    h, level = -1, [root] if root else []
    while level:
        h += 1
        level = [c for n in level for c in (n.left, n.right) if c]
    return h


rng = random.Random(3)
good = True
for _ in range(300):
    keys = [rng.randint(0, 4) for _ in range(rng.randint(0, 40))]      # few distinct values, many repeats
    root = None
    for i, k in enumerate(keys):
        root = insert(root, k, tag=i)                                  # tag = arrival position
    before = [(n.key, n.tag) for n in inorder_nodes(root)]
    nodes = inorder_nodes(root)
    root = build(nodes, 0, len(nodes))
    after = [(n.key, n.tag) for n in inorder_nodes(root)]
    good = good and before == after and height(root) == (len(keys).bit_length() - 1 if keys else -1)
print("300 lists with many repeated keys: same keys and tags in the same order, height floor(log2 n):", good)


def times_reached(root):
    """How many times a walk from the root reaches nodes it has already seen (0 in a proper tree)."""
    seen, repeats, stack = set(), 0, [root]
    while stack:
        node = stack.pop()
        if id(node) in seen:
            repeats += 1
            continue
        seen.add(id(node))
        stack.extend(c for c in (node.left, node.right) if c)
    return repeats


for reset in (True, False):
    chain = None
    for k in range(1, 8):
        chain = insert(chain, k)
    nodes = inorder_nodes(chain)
    rebuilt = build(nodes, 0, len(nodes), reset)
    print(f"reset links = {reset}: nodes reached a second time = {times_reached(rebuilt)}")

Output:

left-leaning chain, preorder: [3, 2, 1]
after one right rotation at the root, preorder: [2, 1, 3]
root 2 children 1 3
one left rotation undoes it, preorder: [3, 2, 1]

n = 1023 keys, average node depth (edges):
  random insertion orders, mean of 100: 11.08
  1.39 * log2(n): 13.90
  middle-rooted tree: 8.01
every range of every size 0..2000 splits into halves that differ in size by at most 1: True
descending inserts of 5000 keys: the in-order stack reaches 5000 entries, the node list 5000
300 lists with many repeated keys: same keys and tags in the same order, height floor(log2 n): True
reset links = True: nodes reached a second time = 0
reset links = False: nodes reached a second time = 3

A right rotation at the root of the chain 3, 2, 1 lifts 2 to the root with 1 and 3 as children; the in-order sequence 1, 2, 3 is unchanged and only the shape differs. For 1,023 keys the middle-rooted tree has the minimum possible average depth, while a random insertion order averages about 11 levels. The leading term 1.39 log2 n overshoots the measured average by a constant, since it ignores lower-order terms.

Follow-ups and how the answer changes

• To rebalance in O(1) extra memory, use the Day-Stout-Warren algorithm (a rebalancing method built only from rotations): rotate the tree into a right-leaning chain, then do rounds of left rotations. It is still O(n) time but needs no list. A rotation is a local change of two links that moves one node up and one down while keeping the in-order sequence; the checking program shows one on three nodes. Day-Stout-Warren is extension reading; a typical interview needs the list-and-middle rebuild above and a one-line mention of rotations.
• If other threads are reading the tree during the rebuild, relinking the live nodes breaks them: build a copy and swap the root pointer instead.
• To avoid rebuilds altogether, use a self-balancing tree (AVL or red-black) that restores balance on every insert.

Running the code

Save the listing as bst_rebuild.py and run python3 bst_rebuild.py (Python 3.12, standard library only). The checking program is self-contained: save it as rebuild_checks.py and run it the same way.

Architecture: client SDKs emit signed usage events to an ingestion service; ingestion writes to an append-only, partitioned event store (e.g., Kafka) for immutability; a metering service consumes events to aggregate usage per account, persisting metrics to a billing DB and exposing a reconciliation API; fraud prevention: rate limits, signature verification, anomaly detection (sudden spikes, impossible geography), and delayed reprocessing windows; transparency: customer-facing usage dashboard with raw events, aggregated metrics, and billing projections; reconciliation & dispute flow with exportable CSVs and audit logs. Failure modes: ingestion loss (use durable queues, retries, dead-letter queue), double-counting (idempotent event IDs and dedup), billing service outage (grace period and buffered aggregates), and SDK tampering (signatures and server-side validation).

Direct answer

An entity-relationship (ER) model has four building blocks: entities (the things you track, like Customer or Order), attributes (their properties), relationships (how entities associate with each other), and cardinality (how many instances of one entity associate with how many of another). A weak entity is one that cannot be uniquely identified by its own attributes alone and borrows part of its identity from an owning entity.

Structured elaboration

• Entities: independent objects or concepts in the domain (Customer, Order, Product). Drawn as rectangles; each instance is a row once the model becomes a table.
• Attributes: properties of an entity or relationship. They can be simple (atomic, like email), composite (address split into street/city/zip), multivalued (phone_numbers), or derived (age computed from birth_date). Exactly one attribute (or a combination) is chosen as the identifying key.
• Relationships: associations between entity instances (a Customer places an Order). Relationships can be unary (an Employee manages another Employee), binary (the common case), or n-ary (rarer, involving three or more entities at once, such as Supplier-Part-Warehouse).
• Cardinality and participation: cardinality states the maximum number of instances on each side of a relationship (one-to-one, one-to-many, many-to-many); participation states whether that side is mandatory (every instance must participate) or optional.
• Weak entities: an entity with no candidate key of its own. It is existence-dependent on an owning ("strong") entity and its identifier is a composite of the owner's key plus a partial key of its own. Example: OrderLine cannot be identified without knowing which Order it belongs to, so its real key is (order_id, line_number).

Worked example

Consider a simple domain: Customer, Order, and OrderLine.

erDiagram
    CUSTOMER ||--o{ ORDER : places
    ORDER ||--|{ ORDER_LINE : contains
    CUSTOMER {
        int customer_id PK
        string email
        string name
    }
    ORDER {
        int order_id PK
        int customer_id FK
        date placed_at
    }
    ORDER_LINE {
        int order_id FK
        int line_number
        int product_id
        int quantity
    }

Mapping this ER model to a normalized relational schema is mechanical:

1. Every strong entity becomes a table; its identifying attribute becomes the primary key. Customer and Order are strong entities here.
2. A one-to-many relationship (Customer places Order) is realized by putting the "one" side's key as a foreign key on the "many" side: customer_id on orders.
3. A weak entity (OrderLine, which cannot exist or be identified without an Order) becomes a table whose primary key is the composite of the owning entity's key plus the weak entity's own partial key: (order_id, line_number), with order_id also carrying an ON DELETE CASCADE foreign key, since a line item has no meaning once its order is gone.
4. Many-to-many relationships (not shown above, but common, like Product-to-Category) become their own junction table with a composite key of the two participants' foreign keys.

Trade-offs and pitfalls

• A common mistake is treating a weak entity's partial key as if it were globally unique on its own (line_number alone) instead of scoping it to its owner (order_id, line_number); this silently allows line 1 of order A to collide with line 1 of order B if the composite key isn't enforced.
• Mandatory-vs-optional participation is easy to skip during modeling but directly decides whether a foreign-key column is nullable, which in turn affects every downstream query that joins on it.
• Over-eager n-ary relationships are rare in practice; most "three-way" associations decompose cleanly into two binary relationships once you look closely, and forcing a single n-ary relationship where two binary ones would do usually loses information about which pairing caused which fact.

The idea in plain words

A histogram is a row of bars of width 1 with given heights. A rectangle inside it must sit on the baseline and be as tall as its shortest bar, so a rectangle covering bars l..r has area min(heights[l..r]) * (r - l + 1). Instead of trying every l and r, ask the question per bar: if this bar is the shortest bar in the rectangle, how far can the rectangle stretch? It stretches left until the first bar that is shorter, and right until the first bar that is shorter. The answer is the best such area over all bars.

Finding "nearest shorter bar on each side" for every bar is what a monotonic stack (a stack that is kept in sorted order by popping anything that breaks the order) does in one pass.

The brute force and why it is not enough

Try every pair l, r, track the minimum as r grows, and keep the best area. That is O(n^2) for n bars. At n = 100,000 it is about 5 billion pairs, too slow, so the question asks for O(n). The program keeps this version as a reference to test against.

The invariant and the approach

Keep a stack of bar indices whose heights are strictly increasing from bottom to top. This is the invariant (a property that stays true after every step). The rising= column in the run below prints the stack after step 4 of each round, for example [(1, 1), (4, 2)] after bar 4: the heights 1 then 2 go up, never level or down. Scan left to right; for each new bar with height h:

1. While the top bar is at least as tall as h, pop it. The new bar is the first bar on the right that is not taller, so it bounds the popped bar's rectangle on the right at i - 1.
2. After the pop, the bar now on top of the stack is the nearest bar on the left that is strictly shorter, so it bounds the rectangle on the left. If the stack is empty, nothing to the left is shorter and the rectangle starts at index 0. The width is i - left_edge - 1, where left_edge is that bar's index, or -1 for an empty stack.
3. Area = popped height * width. Keep the maximum.
4. Push the new bar.

A sentinel (an extra dummy element that removes a special case) of height 0 is appended after the last bar. It is shorter than every real bar, so it pops everything still on the stack and no cleanup loop is needed.

Why the bar below is the left boundary

Step 2 is the part that needs a reason. Take a popped bar p and the bar t that is now on top of the stack. Two facts hold.

• t is strictly shorter than p. The stack heights strictly increase from bottom to top, and t sat directly under p.
• Every bar with an index between t and p is at least as tall as p. Each of those bars is no longer on the stack, so some later bar at most as tall as it removed it. If p itself removed it, it is at least as tall as p. If an earlier bar in the gap removed it, that bar is at most as tall as it, and the same argument applies to that bar in turn. The chain always ends at a bar that p removed, so every bar in the gap is at least as tall as p.

So a rectangle of height p can stretch left across the whole gap, and it must stop at t because t is shorter. In the run below the line pop bar 4 (height 2): spans 2..5, width 4 shows this: the new top is bar 1 (height 1), and the bars between, [(2, 5), (3, 6)], were both popped earlier by bar 4, so they are taller than 2 and the rectangle of height 2 covers them. That is why the width is i - left_edge - 1 = 6 - 1 - 1 = 4, not 1.

Equal heights. A bar equal to the new one is popped too. Its computed rectangle is narrower than the truth, but the new bar, which sits further right, gets its left edge from the same stack and computes the full-width rectangle. The second trace in the run shows it for [3, 3, 3]: bar 0 pops with width 1 (area 3), bar 1 pops with width 2 (area 6, bars between: bar 0), and bar 2 pops with width 3 (area 9, bars between: bars 0 and 1). The last bar's rectangle is the full one, so the answer is 9.

The code

import random


def largest_rectangle(heights, trace=False, stats=None):
    best = 0
    rising = []                                   # indices of bars, heights strictly increasing from bottom to top
    for i, h in enumerate(list(heights) + [0]):   # the extra 0 bar pops everything at the end
        while rising and heights[rising[-1]] >= h:
            if stats is not None:
                stats["pops"] += 1
            top = rising.pop()
            left_edge = rising[-1] if rising else -1      # nearest bar to the left that is shorter
            width = i - left_edge - 1
            area = heights[top] * width
            if trace:
                gap = [(k, heights[k]) for k in range(left_edge + 1, top)]
                print(f"    pop bar {top} (height {heights[top]}): spans {left_edge + 1}..{i - 1}, "
                      f"width {width}, area {area}; bars between the new top and it: {gap}")
            best = max(best, area)
        rising.append(i)
        if trace:
            label = "end" if i == len(heights) else f"h={h}"
            print(f"  i={i} {label}: rising={[(k, heights[k]) for k in rising if k < len(heights)]} best={best}")
    return best


def brute_force(heights):
    best = 0
    for left in range(len(heights)):
        low = heights[left]
        for right in range(left, len(heights)):
            low = min(low, heights[right])
            best = max(best, low * (right - left + 1))
    return best


def demo():
    heights = [2, 1, 5, 6, 2, 3]
    print("heights:", heights)
    stats = {"pops": 0}
    print("largest rectangle:", largest_rectangle(heights, trace=True, stats=stats),
          "| bars:", len(heights), "| pops:", stats["pops"])
    print("equal heights [3, 3, 3]:")
    print("largest rectangle:", largest_rectangle([3, 3, 3], trace=True))
    print("[]:", largest_rectangle([]), "| [7]:", largest_rectangle([7]),
          "| [3, 3, 3]:", largest_rectangle([3, 3, 3]), "| [0, 0]:", largest_rectangle([0, 0]),
          "| [5, 4, 3, 2, 1]:", largest_rectangle([5, 4, 3, 2, 1]))


def random_check():
    rng = random.Random(21)
    for _ in range(3000):
        heights = [rng.randint(0, 6) for _ in range(rng.randint(0, 10))]
        assert largest_rectangle(heights) == brute_force(heights), heights
    print("3000 random histograms (with zeros and equal heights) match the O(n^2) brute force")
    for n in (1000, 4000):
        heights = [rng.randint(0, 10**4) for _ in range(n)]
        stats = {"pops": 0}
        largest_rectangle(heights, stats=stats)
        assert stats["pops"] <= n
        print(f"n={n}: pops={stats['pops']} (at most n)")


if __name__ == "__main__":
    demo()
    random_check()

Run, it prints:

heights: [2, 1, 5, 6, 2, 3]
  i=0 h=2: rising=[(0, 2)] best=0
    pop bar 0 (height 2): spans 0..0, width 1, area 2; bars between the new top and it: []
  i=1 h=1: rising=[(1, 1)] best=2
  i=2 h=5: rising=[(1, 1), (2, 5)] best=2
  i=3 h=6: rising=[(1, 1), (2, 5), (3, 6)] best=2
    pop bar 3 (height 6): spans 3..3, width 1, area 6; bars between the new top and it: []
    pop bar 2 (height 5): spans 2..3, width 2, area 10; bars between the new top and it: []
  i=4 h=2: rising=[(1, 1), (4, 2)] best=10
  i=5 h=3: rising=[(1, 1), (4, 2), (5, 3)] best=10
    pop bar 5 (height 3): spans 5..5, width 1, area 3; bars between the new top and it: []
    pop bar 4 (height 2): spans 2..5, width 4, area 8; bars between the new top and it: [(2, 5), (3, 6)]
    pop bar 1 (height 1): spans 0..5, width 6, area 6; bars between the new top and it: [(0, 2)]
  i=6 end: rising=[] best=10
largest rectangle: 10 | bars: 6 | pops: 6
equal heights [3, 3, 3]:
  i=0 h=3: rising=[(0, 3)] best=0
    pop bar 0 (height 3): spans 0..0, width 1, area 3; bars between the new top and it: []
  i=1 h=3: rising=[(1, 3)] best=3
    pop bar 1 (height 3): spans 0..1, width 2, area 6; bars between the new top and it: [(0, 3)]
  i=2 h=3: rising=[(2, 3)] best=6
    pop bar 2 (height 3): spans 0..2, width 3, area 9; bars between the new top and it: [(0, 3), (1, 3)]
  i=3 end: rising=[] best=9
largest rectangle: 9
[]: 0 | [7]: 7 | [3, 3, 3]: 9 | [0, 0]: 0 | [5, 4, 3, 2, 1]: 9
3000 random histograms (with zeros and equal heights) match the O(n^2) brute force
n=1000: pops=1000 (at most n)
n=4000: pops=4000 (at most n)

Worked trace

On [2, 1, 5, 6, 2, 3]:

• Bar 0 (height 2) is pushed. Bar 1 (height 1) pops bar 0: it spans only index 0 (the stack is empty, so the left edge is -1), area 2. Bar 1 is pushed.
• Bars 2 and 3 (heights 5 and 6) are pushed: stack heights 1, 5, 6.
• Bar 4 (height 2) pops bar 3 (width 1, area 6), then bar 2 (height 5, spans indices 2 to 3, width 2, area 10). The best is now 10. It stops at bar 1 (height 1 is shorter than 2).
• Bar 5 (height 3) is pushed. The sentinel (height 0) then pops bar 5 (area 3), bar 4 (height 2, spans indices 2 to 5, width 4, area 8) and bar 1 (height 1, spans the whole row, width 6, area 6).
• The largest area is 10: the bars of height 5 and 6 give a rectangle of height 5 and width 2.
• On [3, 3, 3] the same code pops one bar per arrival and each pop is wider than the last (widths 1, 2, 3), as the second trace in the run shows.

Why each bar is processed a bounded number of times

Every bar is pushed exactly once and popped exactly once, because the sentinel forces every remaining bar off the stack. The while loop runs inside a for loop, but the total number of pops over the whole run equals the number of bars, so the loop body executes at most n times in total, not n times per bar. The program counts it: 6 pops for 6 bars in the trace, and 1000 pops for 1000 random bars and 4000 for 4000. Each pop does O(1) work (one multiplication, one comparison), so the total is O(n). This is an amortized argument: one bar can trigger many pops, but those pops were paid for by earlier pushes.

Complexity

Time O(n). Space O(n) for the stack, which holds every bar at once when the heights strictly increase ([1, 2, 3, 4]).

Edge cases and common mistakes

• Empty histogram: the loop sees only the sentinel, the stack is empty, and the answer is 0.
• One bar: area is its height. All-zero heights: 0.
• Forgetting the sentinel or the final flush, which loses rectangles that run to the right edge (such as [1, 2, 3], where the best is 4 from the bars 2 and 3).
• Computing the width as i - top instead of using the new top of the stack, which ignores the taller bars that were already popped to the left.
• Using the wrong width when the stack is empty (it must be i, which is i - (-1) - 1).
• Assuming the answer must use the tallest bar. In [2, 1, 5, 6, 2, 3] the best rectangle is built on the bar of height 5.

Running the code

python histogram.py

Python 3.12, standard library only.

Direct answer

With n elements, the best case is that the array holds exactly {1, 2, ..., n}, which makes the answer n + 1; otherwise the missing value lies somewhere in [1, n]. That collapses the search space enough to turn the array into its own presence table: place each value v (when 1 <= v <= n) at index v - 1 using swaps, then scan for the first index whose value doesn't match index + 1. That index (plus one) is the smallest missing positive integer, and the whole thing runs in O(n) time using O(1) extra space because no second array or hash set is ever allocated.

Structured elaboration

Why the search space collapses to [1, n+1]. Any value outside [1, n] (negative, zero, or greater than n) cannot possibly be the smallest missing positive integer for an n-element array, so it can be ignored or safely overwritten. This is what makes the array itself a viable substitute for a hash set: only n "slots" are needed to track presence of the n candidate values that matter.

The index-mapping (cyclic placement) pass. For each index i, while nums[i] is a valid candidate (1 <= nums[i] <= n) and it is not already sitting in its home slot (nums[nums[i] - 1] != nums[i]), swap nums[i] with nums[nums[i] - 1]. This pushes the value toward the index it "claims." A value equal to i + 1 is already home and the while loop stops immediately; a value outside [1, n] also stops the loop, since it can never claim a valid slot.

Why this stays O(n) despite the nested loop. Each swap places at least one element into its permanent correct home (once an element lands at its target index, the loop condition for that index becomes false and it never moves again). Since there are only n positions to permanently fill, the total number of swaps across the entire outer loop is bounded by n, so the nested while does not make this quadratic; it is a classic amortized-O(n) argument, the same one that justifies calling cyclic-sort-style placement linear.

The read-out pass. After placement, scan left to right for the first i where nums[i] != i + 1. That mismatch means value i + 1 never found a home, i.e. it was missing from the input, so the answer is i + 1. If no mismatch is found, every slot holds its expected value and the answer is n + 1.

Worked example

Trace on [3, 4, -1, 1] (n = 4), printing every swap exactly as executed:

start: [3, 4, -1, 1]
  swap nums[0] with nums[2] -> [-1, 4, 3, 1]
  swap nums[1] with nums[3] -> [-1, 1, 3, 4]
  swap nums[1] with nums[0] -> [1, -1, 3, 4]
after placement pass: [1, -1, 3, 4]
first mismatch at index 1: nums[1]=-1 != 2
answer = 2

Full runnable code (Python 3, no external dependencies) with pinned test cases:

def first_missing_positive(nums):
    """Return the smallest missing positive integer.
    O(n) time, O(1) extra space (beyond the input list, mutated in place).
    """
    n = len(nums)

    # Step 1: place each value v (1 <= v <= n) at index v-1 by swapping,
    # so that on a "perfect" array nums[i] == i+1 for all i.
    for i in range(n):
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            target = nums[i] - 1
            nums[i], nums[target] = nums[target], nums[i]

    # Step 2: the first index i where nums[i] != i+1 reveals the answer.
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    return n + 1


if __name__ == "__main__":
    tests = [
        ([3, 4, -1, 1], 2),
        ([1, 2, 0], 3),
        ([7, 8, 9, 11, 12], 1),
        ([1, 2, 3], 4),
        ([], 1),
        ([1], 2),
        ([2], 1),
    ]
    for arr, expected in tests:
        arr_copy = list(arr)
        result = first_missing_positive(arr_copy)
        print(f"input={arr!r:25} -> {result} (expected {expected})")

Output (actual run):

input=[3, 4, -1, 1]             -> 2 (expected 2)
input=[1, 2, 0]                 -> 3 (expected 3)
input=[7, 8, 9, 11, 12]         -> 1 (expected 1)
input=[1, 2, 3]                 -> 4 (expected 4)
input=[]                        -> 1 (expected 1)
input=[1]                       -> 2 (expected 2)
input=[2]                       -> 1 (expected 1)

Trade-offs and pitfalls

• The most common wrong turn is sorting first: it works, but costs O(n log n) time and fails the question's stated time bound. Naming it as a correct-but-non-optimal baseline before presenting the index-mapping trick shows the interviewer you understand why the O(n) approach is needed, not just that it exists.
• A hash set of seen values gets O(n) time but O(n) extra space, missing the O(1) space constraint. It is worth naming this trade-off explicitly rather than jumping straight to the in-place trick, since it demonstrates the same reasoning under a relaxed constraint.
• An easy implementation bug: omitting the "not already home" guard (nums[nums[i]-1] != nums[i]) causes an infinite loop whenever a value already equals its own target, which happens with duplicates like [1, 1], since the code would keep swapping a value with itself forever.
• The input array is mutated in place. If the array must be preserved, say so and either copy it first (paying O(n) space to keep O(n) time) or confirm in-place mutation is acceptable for the exercise.
• Duplicates and out-of-range values (negatives, zero, values greater than n) are both handled by the same guard condition, so no separate cleanup pass is required; stating this explicitly heads off the follow-up question before it's asked.

Direct answer

Layer the caches by how expensive a miss at that layer is and how often the content changes: content delivery network (CDN) edge for static/shared assets closest to the user, a regional shared cache (e.g., Redis) for personalized-but-cacheable data, and an application in-process cache for the hottest few keys where even a network hop to the regional cache is too slow, with each layer's time-to-live (TTL) and invalidation strategy sized to that layer's job.

Structured elaboration

• CDN/edge layer: caches fully static or long-TTL content (images, JS/CSS bundles, and cacheable HTML fragments for anonymous/public views) at points of presence near the user. This absorbs the largest fraction of read volume for almost no cost per request and should hold anything that does not vary per-user.
• Regional distributed cache (Redis/Memcached): serves personalized or frequently-changing data shared across all app instances in a region (product details, prices, computed recommendations). Requests per second (RPS) here are much lower than at the edge because the edge already absorbed the static traffic, but this layer must handle write-driven invalidation correctly since content changes.
• Application in-process (L1) cache: for the small set of extremely hot keys (a handful of top-selling products, a config flag read on every request), an in-process cache avoids even the network round-trip to the regional cache. It is the fastest layer and also the hardest to keep coherent, because every app instance has its own copy; use a short TTL or an event-driven invalidation signal (pub/sub) rather than relying on the regional cache alone.
• Database-side / materialized views: for expensive aggregate queries, a materialized view or a query-result cache sits closest to the database, reducing load on the primary store even when the higher layers miss.
• Invalidation strategy per layer: static assets at the edge use content-hashed URLs so "invalidation" is really just a new URL (no purge needed); the regional cache uses event-driven invalidation on write (an order/price update publishes an invalidation for that product's key); the in-process L1 layer uses a short TTL (seconds) plus a lightweight pub/sub signal, because coordinating a purge across every instance is expensive and slow.
• Sizing to a concrete target: pick numbers for the design (RPS, latency budget, SKU/product count) and work backward: at, say, 100,000 RPS globally with a 90 percent edge-cacheable static-asset ratio, only about 10,000 RPS reach the regional application tier, which then needs to comfortably serve that load with sub-50ms p95 latency from cache.

Worked example

For a product catalog with 1,000,000 stock-keeping units (SKUs) and 50,000 RPS globally: static images and category pages are edge-cached (roughly 35,000 RPS absorbed at essentially zero backend cost). The remaining ~15,000 RPS of personalized/price-sensitive reads hit the regional Redis cache; with a realistic 95 percent hit ratio there, the origin database sees roughly 750 RPS, which is a design a mid-sized read replica tier handles comfortably. Price changes (a write path) publish an invalidation event per SKU, propagated to the regional cache and any in-process L1 caches holding that SKU within roughly 100 to 500 ms, well inside a "price must update within seconds" product requirement.

Trade-offs and pitfalls

Adding more layers adds more places for staleness to hide; a change that only invalidates the regional cache and forgets the in-process L1 layer will show correct data to some app instances and stale data to others, which is a confusing bug class to debug. Do not put personalization-sensitive content at the CDN edge unless you are using edge compute (e.g., edge functions) that can vary the response per user; naively caching personalized HTML at a shared edge node leaks one user's data to another. Every additional layer is also an additional operational surface (its own metrics, its own failure mode, its own on-call runbook); do not add a layer unless the sizing math shows the layer above it cannot meet the latency or load target alone.

Direct answer

Pick a moment inside a genuine win where things nearly went the other way, then narrate the setback honestly before the recovery. The structure that works is: the moment you realized it was going wrong, the specific decision you made under that pressure, and only then the outcome, so the interviewer sees judgment under uncertainty rather than a highlight reel with a token complication bolted on.

How to select and structure the story

• Pick a real near-miss, not a manufactured one: a good test is whether you can honestly state what the downside outcome would have looked like if your intervention had failed or arrived later.
• Do not open with the win. Open with the moment the trajectory was bad, so the resolution actually lands as a turn instead of a footnote.
• Own your role in what nearly went wrong, if any. A setback story where you take zero responsibility and swoop in as the hero reads as self-serving; naming what you'd tighten next time is what makes it credible.
• The same shape (a relationship, deal, or project on a bad trajectory before you help point it back) applies just as well to a stalled stakeholder or account relationship as to a technical incident, the diagnostic beats are the same: notice, decide, recover.

Worked example (skeleton)

Situation: two weeks after a release, error rates spiked in a downstream service and a small but growing set of customer-facing requests started failing.
Task: I was responsible for diagnosing it fast and deciding whether to roll back or patch forward.
Action: within the first 30 minutes I found the error pattern pointed to a malformed payload from a new dependency, not the obvious suspect (a feature flag everyone assumed was the cause). I made the call to disable the flag as an immediate mitigation while I confirmed the real root cause, rather than waiting for full certainty, because the error rate was still climbing.
Result: the mitigation cut new errors within about 15 minutes of applying it, and the confirmed fix shipped the same day. Total customer-facing impact window was under 3 hours, measured from the first alert to the metrics returning to baseline on the same dashboard that raised it.

Trade-offs and pitfalls

• The most common failure mode is picking a "setback" that was never really in doubt, interviewers can tell when there's no real decision point in the story.
• Resist making the setback entirely someone else's fault; even in a shared-cause incident, name what you personally would do differently.
• Don't let the recovery narrative crowd out the setback. If the setback gets one sentence and the win gets ten, the interviewer will suspect you're avoiding the hard part.