Lyft Full-Stack Developer Interview Preparation Guide - Mid Level

Direct answer

For data with a small hot subset that is written frequently (comments, upvotes), the right strategy depends on how immediately correct a read needs to be: invalidate-on-write for moderate freshness needs, write-through only where every read must reflect every write instantly, and accepting brief staleness (via a time-to-live, TTL, or lazy invalidation) wherever that is tolerable, since write-through on every single upvote would add real latency for a benefit most reads do not need.

Structured elaboration

• Invalidate-on-write: on each write, remove (or update) the cached entry; the next read repopulates it from the datastore. This keeps writes fast (no synchronous cache update required beyond the invalidation itself) while keeping reads correct after a very short window.
• Versioned keys: instead of invalidating, bump a version so the old cached entry simply becomes unreachable; useful when you want to avoid a race between a slow read repopulating the cache with a stale value right after an invalidation.
• Write-through and write-behind for hot writes: write-through keeps the cache always current but adds write latency to every single write, which is expensive when writes are frequent (like upvotes ticking constantly); write-behind trades durability for throughput, generally the wrong choice for anything users would notice being lost.
• Hybrid systems: a common pattern for a frequently-updated counter (like upvote count) is to accept brief staleness (a few seconds) via a short TTL or periodic flush of an in-memory increment buffer, rather than treating every single increment as needing to be immediately, individually visible; this dramatically reduces write amplification for high-frequency, low-individual-significance updates.
• Choosing per requirement: an "immediate consistency" requirement (the user must see their OWN comment appear instantly) can be satisfied narrowly (read-your-own-write for that specific user/action) without requiring every OTHER reader to see it with zero delay; distinguishing "the writer needs to see it now" from "everyone needs to see it now" often reveals a much cheaper design.

Worked example

An upvote counter incremented thousands of times per minute on a popular post: rather than invalidating the cached count on every single increment (which would defeat the cache's purpose under this write rate), buffer increments in a fast in-memory or Redis atomic counter and periodically (e.g., every 1 to 2 seconds) reconcile that buffered delta with the durable count, giving readers a count that is at most 1 to 2 seconds behind reality, an acceptable trade for a number nobody expects to be exactly, instantaneously precise.

Trade-offs and pitfalls

Applying write-through uniformly to a hot-write field "to be safe" can quietly become the write path's latency bottleneck as write frequency grows; revisit the choice as traffic patterns change, not just at initial design time. Buffering writes for periodic reconciliation must have a bounded, monitored flush interval; an unbounded or silently-stalled buffer turns "briefly stale" into "indefinitely wrong.

Direct answer
Turn a vague request into something actionable by asking about the underlying problem, the scope, the success criteria, the constraints, and the audience, before committing to any plan.

Structured elaboration

• Underlying problem: "What made you raise this now? What's the actual pain point behind 'make this better'?" A vague request almost always has a specific trigger; find it.
• Scope: "Better for whom, and for which part of the system or process? Everyone, or a specific segment?"
• Success criteria: "How will we know this worked? Is there a metric, or is it a qualitative judgment?"
• Constraints: "What's the timeline, budget, or team capacity for this? Is there a deadline driving the request?"
• Priority relative to other work: "Where does this rank against what's already committed?"
• Audience/stakeholders: "Who else cares about the outcome, and does anyone need to sign off?"

Ask these as a short, prioritized set, not all twelve possible questions at once; pick the three or four that would most change your plan if the answer were different.

Worked example
Request: "We need improved reporting."

Clarifying questions actually asked, in order: "What decision is the current reporting failing to support, what's an example of a time it fell short?" "Is this for internal use, or does it go to customers or leadership?" "Is there a specific number or turnaround time we're trying to hit, or is this more about it being easier to use?" "Is there a deadline tied to this, like a board meeting or a renewal?"

The answers turn "improved reporting" into something like "leadership wants same-day revenue numbers instead of the current 3-day lag, ahead of next month's board meeting," which is now a scoped, testable requirement instead of a vague preference.

Trade-offs and pitfalls

• Asking too many questions at once, or overly generic ones ("can you tell me more?"), reads as not having engaged with the request; targeted questions that show you've already thought about what would change your plan land better.
• Sometimes the requester genuinely doesn't know the answer either (they're relaying a vague ask from someone else); in that case, propose a specific, falsifiable interpretation ("I'll assume you mean X unless you tell me otherwise") rather than blocking on an answer that may never come.
• There's a real cost to over-clarifying trivial requests; match the depth of questioning to the size of the commitment you're about to make.

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

At-most-once, at-least-once, and exactly-once describe how many times a message's effect is applied to a consumer's state when failures happen, and they trade off data loss against duplication: at-most-once can lose messages but never duplicates them, at-least-once never loses messages but can duplicate them, and exactly-once achieves neither loss nor duplication, at the cost of real coordination complexity between the broker and the application. The broker only ever guarantees delivery attempts and retries; whether duplicates or gaps actually matter is always decided by what the application does with what it receives.

Structured elaboration

At-most-once in practice

• The broker or transport makes a single delivery attempt and does not retry on failure; if the consumer or the network drops the message, it is gone.
• Appropriate when losing an occasional message is cheaper than the cost of retry infrastructure and the risk of duplicates, for example high-volume sensor telemetry feeding a dashboard where one missing data point among thousands is invisible.

At-least-once in practice

• The broker persists the message and retries delivery until it receives an acknowledgment, which means a consumer crash between processing a message and acknowledging it results in redelivery of a message that was already (partially or fully) processed.
• The broker's job stops at "you will eventually get this message, possibly more than once." The application's job is to make processing that message twice harmless: a unique message identifier plus a dedup store, or a write that is naturally idempotent (an upsert keyed by a stable identifier, rather than an increment).
• Appropriate for analytics ingestion or audit logging, where losing a record is unacceptable but a duplicate can be cleaned up downstream (deduplicated at query time, or filtered by the same identifier used for idempotency).

Exactly-once in practice

• True end-to-end exactly-once requires coordination beyond a single retry-and-acknowledge loop: either the broker offers transactional semantics that atomically tie together "I read this" and "I wrote that" (so a crash mid-processing rolls back cleanly rather than leaving a partial, retryable state), or the application achieves the same outcome by combining at-least-once delivery with strict idempotent processing, which is functionally exactly-once from the business's point of view even though the transport itself only promised at-least-once.
• Appropriate for financial transfers or order processing, where a duplicate effect (charging a customer twice, decrementing inventory twice for one order) or a lost effect (an order accepted but never charged) both cause real monetary or legal problems, not just a dirty analytics row.

Worked example

A payments system processes a $250 transfer as a single message.

• Under at-most-once: if the consumer crashes after receiving the message but before applying the transfer, the $250 transfer is simply lost, no automatic retry recovers it, and the sender's balance is silently wrong by $250 unless a separate reconciliation process catches it.
• Under at-least-once with no application-side idempotency: the same crash-after-receive scenario causes the broker to redeliver the message; if the consumer blindly reapplies "subtract $250" a second time, the sender's balance is now wrong by $250 in the opposite direction (over-debited), a duplicate-effect bug, not a loss bug.
• Under at-least-once with application-side idempotency (a unique transfer identifier and an idempotent upsert: "set this transfer's status to applied if it is not already applied," not "subtract $250 unconditionally"): the redelivery is a no-op the second time, and the sender's balance is debited exactly once, $250, regardless of how many times the message is redelivered. This is the practical way most systems get exactly-once business outcomes without needing the broker to provide literal exactly-once transport.

Trade-offs and pitfalls

• Common wrong turn: choosing at-most-once for anything with real business consequence (payments, inventory decrements, order state) purely because it is the simplest and fastest option; the missing-message failure mode is invisible until an audit or a customer complaint surfaces it.
• Common wrong turn: assuming "the broker supports exactly-once" is a complete answer without checking what scope that guarantee actually covers (often just broker-internal processing, not the full path out to an external side effect like a payment gateway call, which the broker cannot make transactional on your behalf).
• Common wrong turn: implementing at-least-once with no deduplication strategy at all, treating "the broker retries" as sufficient without doing the application-side half of the job.
• Senior signal: naming which side, broker or application, is responsible for which half of the guarantee, and picking the example that matches the actual business cost of loss versus duplication rather than defaulting to whichever semantic sounds strongest.

Direct answer: Dijkstra's complexity depends entirely on the priority-queue implementation: $O(V^2)$ with a plain array, $O((V+E)\log V)$ with a binary heap, and $O(E + V \log V)$ with a Fibonacci heap (the theoretically best, rarely used in practice due to large constants). A* uses the same underlying machinery as Dijkstra but adds a heuristic $h(n)$ estimating remaining distance to the goal, which - if admissible (never overestimates) and consistent (satisfies a triangle-inequality-like property) - guarantees the optimal path is still found while typically exploring far fewer nodes than Dijkstra by prioritizing promising directions.

Structured elaboration

• Array-based Dijkstra: finding the minimum-distance unvisited vertex is an $O(V)$ scan, done $V$ times, giving $O(V^2)$ - reasonable for dense graphs where $E \approx V^2$ anyway.
• Binary-heap Dijkstra: each extract-min is $O(\log V)$, and each edge relaxation may trigger a decrease-key (also $O(\log V)$, or handled via re-insertion with lazy deletion in many implementations), giving $O((V+E)\log V)$ - the standard choice for sparse graphs.
• Fibonacci-heap Dijkstra: decrease-key is $O(1)$ amortized, so the bound improves to $O(E + V \log V)$ - asymptotically best, but the large constant factors and implementation complexity of Fibonacci heaps mean binary heaps usually win in practice except at very large scale.
• A*: identical algorithmic skeleton to Dijkstra, but the priority queue orders by $f(n) = g(n) + h(n)$ (cost-so-far plus heuristic estimate to goal) instead of just $g(n)$. An ADMISSIBLE heuristic (never overestimates true remaining cost) guarantees A* still finds the optimal path; a CONSISTENT heuristic (satisfies $h(n) \le \text{cost}(n, n') + h(n')$ for every edge) additionally guarantees no node needs to be re-expanded once popped, matching Dijkstra's efficiency guarantees while exploring fewer nodes in the common case, because the heuristic actively steers the search toward the goal instead of expanding uniformly outward in all directions.

Worked example

Consider road-network routing where straight-line (Euclidean) distance to the destination is used as $h(n)$: it's admissible (straight-line distance never overestimates actual road distance, which must be $\ge$ straight-line) and consistent (the triangle inequality holds for Euclidean distance). On a grid or road network, this heuristic causes A* to expand nodes roughly in an ellipse oriented toward the goal, rather than Dijkstra's expanding circle in all directions - for a goal far from the source, this concretely means A* explores a small fraction of the nodes Dijkstra would, even though both are guaranteed to find the same optimal-cost path.

Trade-offs & pitfalls

• A* is only as good as its heuristic - a poorly-chosen or non-admissible heuristic can make it explore MORE nodes than Dijkstra (if it misleads the search) or, worse, return a suboptimal path (if it's not admissible).
• When there's no useful domain-specific heuristic available (e.g. an abstract graph with no geometric embedding), A* degenerates to Dijkstra (using $h(n) = 0$ everywhere is trivially admissible and consistent).
• Fibonacci heaps are a common "textbook-optimal, practically-never-used" answer - know the asymptotic bound but be ready to say WHY binary heaps usually win in real systems (much smaller constant factors, simpler implementation, better cache behavior).

Direct answer

Keep an inclusive window lo..hi over the array, look at the middle element, and move lo or hi past the middle depending on whether it is too small or too big. Return the index when the middle equals the target, and -1 once the window is empty. An empty array needs no special case: hi starts at -1, so lo <= hi is false immediately. Compute the middle as lo + (hi - lo) // 2, which cannot overflow in fixed-width integer languages, unlike (lo + hi) // 2.

The idea in plain words

A sorted array lets one comparison eliminate half of the candidates: if the middle value is smaller than the target, the middle and everything to its left are too small. The loop invariant (a fact that is true before every iteration and so proves the loop correct) is: if the target is in the array, its index is inside lo..hi. The initial window is the whole array, so it holds at the start; each step removes only positions proven too small or too big, and mid itself, which was just checked; when lo > hi the window is empty, so the target is not there.

Brute force and why not

target in arr or a loop with arr.index scans every element: O(n). On a sorted array that wastes the ordering. Binary search needs O(log n) comparisons (about 20 for a million elements).

Code

For clarity the driver traces lo, hi and mid on a distinct-element array (a hit and a miss), shows the empty array and a duplicate case, emulates 32-bit signed arithmetic to show the overflow, and checks 2000 random small arrays (fixed seed) against Python's in operator.

import random
from typing import List


def binary_search(arr: List[int], target: int, trace: bool = False) -> int:
    """Index of target in ascending arr, or -1.

    Invariant: if target is in arr, its index lies in lo..hi (inclusive).
    """
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if trace:
            print(f"lo={lo} hi={hi} mid={mid} arr[mid]={arr[mid]}")
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1


def to_int32(x: int) -> int:
    """What a signed 32-bit integer would hold after wrapping around."""
    x &= 0xFFFFFFFF
    return x - (1 << 32) if x >= (1 << 31) else x


if __name__ == "__main__":
    nums = [1, 3, 5, 7, 9, 11, 13]
    print("distinct elements", nums)
    for t in (9, 4):
        print(f"target {t}")
        print("result:", binary_search(nums, t, trace=True))

    print("\nempty array:", binary_search([], 3))

    dups = [1, 2, 2, 2, 2, 3]
    print("duplicates", dups, "-> target 2 found at index", binary_search(dups, 2),
          f"(the first 2 is at index {dups.index(2)})")

    lo, hi = 1_500_000_000, 2_000_000_000
    print("\n32-bit emulation with lo=%d hi=%d" % (lo, hi))
    print("  (lo + hi) // 2 in int32  :", to_int32(lo + hi) // 2)
    print("  lo + (hi - lo) // 2 int32:", to_int32(lo + (hi - lo) // 2))

    rng = random.Random(42)
    for _ in range(2000):
        arr = sorted(rng.randint(-8, 8) for _ in range(rng.randint(0, 10)))
        t = rng.randint(-10, 10)
        got = binary_search(arr, t)
        if t in arr:
            assert got != -1 and arr[got] == t
        else:
            assert got == -1
    print("\nrandom checks against `in` passed")

Run in a python:3.12 container, it prints:

distinct elements [1, 3, 5, 7, 9, 11, 13]
target 9
lo=0 hi=6 mid=3 arr[mid]=7
lo=4 hi=6 mid=5 arr[mid]=11
lo=4 hi=4 mid=4 arr[mid]=9
result: 4
target 4
lo=0 hi=6 mid=3 arr[mid]=7
lo=0 hi=2 mid=1 arr[mid]=3
lo=2 hi=2 mid=2 arr[mid]=5
result: -1

empty array: -1
duplicates [1, 2, 2, 2, 2, 3] -> target 2 found at index 2 (the first 2 is at index 1)

32-bit emulation with lo=1500000000 hi=2000000000
  (lo + hi) // 2 in int32  : -397483648
  lo + (hi - lo) // 2 int32: 1750000000

random checks against `in` passed

Worked trace (distinct elements)

For target 9 in [1, 3, 5, 7, 9, 11, 13]: the window 0..6 has mid 3 holding 7, smaller than 9, so lo becomes 4. The window 4..6 has mid 5 holding 11, larger, so hi becomes 4. The window 4..4 has mid 4 holding 9: found at index 4. For target 4, mid 3 (7) is too big so hi becomes 2; mid 1 (3) is too small so lo becomes 2; mid 2 (5) is too big so hi becomes 1; now lo (2) is greater than hi (1), the loop stops and the function returns -1.

The mid calculation and overflow

In a language with 32-bit signed integers (Java int, C int), the largest value is 2,147,483,647. For lo = 1,500,000,000 and hi = 2,000,000,000 the sum lo + hi is 3,500,000,000, which does not fit: in Java it wraps to a negative number (in C, signed overflow is undefined behaviour), so the "middle" is negative and indexing crashes or returns garbage. The run emulates the wrap: (lo + hi) // 2 gives -397483648 while lo + (hi - lo) // 2 gives 1750000000. The safe form works because hi - lo is never larger than the array length, so it cannot overflow, and lo plus half of that is at most hi, so the result cannot overflow either (worked with numbers below). Another safe form is the unsigned shift (lo + hi) >>> 1 in Java. Python integers are arbitrary precision, so this cannot fail in the Python code; the habit still matters when you port it.

How to_int32 works. A signed 32-bit integer has 32 bits, and when the leftmost (top) bit is 1 the machine reads the number as negative. x &= 0xFFFFFFFF keeps only the low 32 bits (the bit-by-bit AND with 32 ones discards everything above them, as the hardware does when a result is too wide). If that 32-bit value is at least 231, the top bit is set, and subtracting 232 gives the negative number the machine reads. For the sum above:

x = 3_500_000_000                      # the true value of lo + hi
bits = x & 0xFFFFFFFF                  # keep only the low 32 bits, as a 32-bit register would
print("true sum", x, "-> low 32 bits", bits, "=", format(bits, "032b"))
print("top bit set?", bits >= 1 << 31, "-> a signed 32-bit int reads it as", bits - (1 << 32), "(subtract 2**32)")

Output (python:3.12):

true sum 3500000000 -> low 32 bits 3500000000 = 11010000100111011100001100000000
top bit set? True -> a signed 32-bit int reads it as -794967296 (subtract 2**32)

The same arithmetic run in real Java 21 (int is 32-bit signed there; / on integers truncates toward zero, and >>> is the unsigned right shift, which shifts the bits right and fills the top with 0 instead of copying the sign, so a wrapped sum is still treated as a large positive 32-bit pattern before halving):

public class Mid {
    public static void main(String[] args) {
        int lo = 1_500_000_000, hi = 2_000_000_000;
        System.out.println("lo + hi              = " + (lo + hi));
        System.out.println("(lo + hi) / 2        = " + ((lo + hi) / 2));
        System.out.println("lo + (hi - lo) / 2   = " + (lo + (hi - lo) / 2));
        System.out.println("(lo + hi) >>> 1      = " + ((lo + hi) >>> 1));
    }
}

Output (Java 21, javac Mid.java && java Mid):

lo + hi              = -794967296
(lo + hi) / 2        = -397483648
lo + (hi - lo) / 2   = 1750000000
(lo + hi) >>> 1      = 1750000000

The sum wraps to -794,967,296, so the plain midpoint is -397,483,648, matching the Python emulation. lo + (hi - lo) / 2 is safe: hi - lo is 500,000,000, never more than the array length allows, and half of it added to lo stays at most hi. With lo = 1,500,000,000 and hi = 2,000,000,000 that is 1,500,000,000 + 250,000,000 = 1,750,000,000. The unsigned shift gives the same 1,750,000,000 because the wrapped 32-bit pattern still holds the correct sum when read as unsigned (3,500,000,000 fits in 32 unsigned bits), and halving it is correct. Undefined behaviour in C means the language standard places no requirement on what the program does after signed overflow, so a compiler may produce anything, not only a wrapped number. Arbitrary precision (Python integers) means integers grow as large as needed, so no wrap happens.

Duplicates

The function returns some index holding the target, not a particular one. In [1, 2, 2, 2, 2, 3] it returns index 2 although the first 2 is at index 1, because it stops as soon as arr[mid] == target. If the question needs the first or last match, keep searching left or right after a hit (a lower-bound search: it returns the first position whose value is at least the target) instead of returning immediately; the plain version still gives a correct yes/no and a valid index.

Complexity

Time O(log n): the window halves each iteration, so at most floor(log2 n) + 1 iterations. Space O(1) (three integers; no recursion, no slicing, so no copies of the array).

The two loop mistakes listed below can be tried directly. This is the same search with one mistake switched on at a time; it gives up after 50 rounds so that a stuck loop shows up as loops, and it runs on every array of 1, 2 and 3 elements (values 0 to n - 1) with every target from -1 to n.

def variant(arr, target, mistake=None, limit=50):
    lo, hi = 0, len(arr) - 1
    for _ in range(limit):
        if (lo >= hi) if mistake == "lo < hi" else (lo > hi):
            return -1
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            lo = mid if mistake == "lo = mid" else mid + 1
        else:
            hi = mid if mistake == "hi = mid" else mid - 1
    return "loops"


for mistake in (None, "lo < hi", "lo = mid", "hi = mid"):
    bad = []
    for n in (1, 2, 3):
        data = list(range(n))
        for target in range(-1, n + 1):
            expected = target if 0 <= target < n else -1
            got = variant(data, target, mistake)
            if got != expected:
                bad.append(f"n={n} target={target} -> {got}")
    print(f"{str(mistake):9s}", bad if bad else "all correct")

Output (python:3.12):

None      all correct
lo < hi   ['n=1 target=0 -> -1', 'n=2 target=1 -> -1', 'n=3 target=0 -> -1', 'n=3 target=2 -> -1']
lo = mid  ['n=1 target=1 -> loops', 'n=2 target=1 -> loops', 'n=2 target=2 -> loops', 'n=3 target=2 -> loops', 'n=3 target=3 -> loops']
hi = mid  ['n=1 target=-1 -> loops', 'n=2 target=-1 -> loops', 'n=3 target=-1 -> loops']

Edge cases and common mistakes

• Empty array: returns -1 with zero iterations (shown in the run).
• One element: the window 0..0 is checked once; a miss shrinks it to empty.
• Target below the smallest or above the largest: hi falls below 0 or lo rises past the last index, and the loop ends with -1.
• while lo < hi misses the final single-element window (the lo < hi row of the mistakes run: the sole element of a one-element array is reported absent).
• lo = mid or hi = mid can loop forever. A window of one element already sticks, because mid equals lo and the update leaves the window unchanged; with lo = mid a window of two elements sticks as well (the lo = mid and hi = mid rows of the mistakes run).
• Slicing the list in a recursive version (arr[mid+1:]) copies elements and turns O(log n) into O(n), and the returned index then refers to the slice, not the original array.
• Sorted input is a precondition: nothing detects an unsorted array.

Running the code

python:3.12, standard library only.
Save the listing as binary_search_function.py and run: python binary_search_function.py

Building a coalition before a decision point starts before you ever present: identify whose support or veto will actually matter, engage them privately in an order that makes each later yes easier to get, and bring each person something concrete they need rather than a generic ask for support.

Mapping and sequencing

• Map influence and interest. List everyone who could formally veto or bless the proposal, plus anyone with no formal say who still has real influence over those decision-makers.
• Sequence deliberately. Engage the lowest-friction likely allies first, before the proposal is public, so you arrive at the wider decision point with visible support already lined up rather than asking a group to be first movers together.
• Offer something specific per stakeholder, tied to what they're actually measured on: reduced risk to their own metric, a pilot scoped to their team, early visibility into results, or public credit. A generic ask for support is much weaker than something concrete.

Two named shapes of this pattern

Resolving separate vetoes before convening a group. A tech lead wants to relax a security control temporarily to hit a launch date, with a compensating control added afterward, a security versus time-to-market tradeoff. Brought cold to a mixed room, the most risk-averse voice usually wins by default. Instead, the lead meets security first, alone, asking what compensating control would make a temporary exception acceptable, not asking them to simply waive the check. Only once security has a specific answer does the lead bring legal, showing the agreed compensating control and asking what documentation legal needs to be comfortable with the interim exposure window. Product only joins once security and legal's actual sign-off is already attached, so the wider room is there to confirm, not to negotiate the tradeoff from scratch.

Multiple buy-in strategies aimed at different needs. For a cross-functional analytics initiative that hasn't launched yet, product and marketing may need to be brought along with three genuinely different offers: a scoped pilot for the team most worried about disruption, early access to the resulting data for the team that wants visibility, and public co-ownership credit for whichever team's cooperation is hardest to secure. Using the same single pitch on both functions usually undersells what each one actually needs to say yes.

Scaling it into standing influence

• From one-off coalition to a repeatable habit. Winning support once, on one proposal, with one team, is different from scaling personal influence beyond your immediate team into middle management across the organization. That scaling requires codifying the tactic into something repeatable (pilot, then data, then public credit) rather than reinventing the ask each time, and building relationships with peer leads before you actually need something from them.
• Trusted contributor to go-to partner. The credibility this builds over time moves through a specific progression: from being a trusted contributor, someone whose individual work is reliable, to being a go-to partner, someone stakeholders proactively loop in before a decision is even finalized, because your input has consistently made past decisions better. Track this by whether you're being consulted earlier in the process over time, not just by whether individual asks succeed.
• Owning the plan without owning the decision. When you don't own the decision outright, such as cross-functional analytics choices that belong to other teams, a personal influence plan means investing in relationships and data credibility with the actual owners on an ongoing cadence, not waiting until you need a specific yes.

Worked example

A tech lead wants to ship an integration faster by relaxing a specific security control temporarily, with a compensating control added within a defined follow-up window, instead of the default full security review blocking the launch date, a security versus time-to-market compromise. Approached cold, in a mixed room, security could veto outright, legal could block over compliance exposure, and product needs the date to hold for a partner commitment.

The lead meets security separately first: "what compensating control would make a temporary exception acceptable to you?" Security proposes a monitoring and alerting control plus a hard remediation date. The lead brings that specific agreement to legal next, asking what documentation legal needs to be comfortable with the interim exposure window; legal signs off given a written record and the fixed remediation date. Only then does the lead convene product, security, and legal together, now presenting a plan that already carries security and legal's specific sign-off, so product's core need (the date holds) is satisfied without the lead having to relitigate the tradeoff with all three functions at once.

The wider meeting is short, because every veto-holder's actual concern was resolved one-on-one beforehand, tailored to that function's own criteria, not a single generic pitch delivered to all three simultaneously.

What a senior person does differently here: never brings unresolved cross-functional tension into a group room, resolves each function's specific veto criteria privately in an order that makes later conversations easier, and only convenes the group to confirm what's already agreed.

Trade-offs and pitfalls

• Sequencing takes real calendar time. Under a hard deadline, skipping the one-on-one alignment to save time usually costs more time recovering from a group veto than the sequencing would have taken.
• What you offer each stakeholder has to be genuinely deliverable; an empty promise to secure a yes burns exactly the go-to-partner reputation the moment it isn't honored.
• Scaling this into a repeatable, org-wide habit without a track record of delivered promises just looks like politicking. The trusted-contributor credibility has to come first, before the scaled version works.

Direct answer

Keep a resizable array of the stored values plus a hash map from value to that value's index in the array. Insert appends to the array in O(1); getRandom picks a uniformly random array index in O(1); the trick is delete, which must not leave a gap: swap the removed value with the array's last element, update that moved element's index in the hash map, then pop the last slot off in O(1).

Structured elaboration

• values: an array of the currently stored values, with no gaps.
• index_of: hash map from value to its current position in values.

insert(val): if val is already in index_of, return false. Otherwise append it to values and record its index.

remove(val): if val is absent, return false. Otherwise look up its index, overwrite that slot with the array's last element (updating that moved element's entry in index_of to the vacated index), then pop the array's last slot and delete val from index_of. Because the moved element simply changes which index it lives at, and every array slot is always occupied by exactly one live value, no gap is ever created and no shifting of the remaining elements is needed.

getRandom(): choose a uniformly random integer index in [0, len(values)) and return values[that index]. Since each stored value occupies exactly one slot and slots are chosen uniformly, every value has equal probability of being returned.

The reason a plain hash set cannot support getRandom in O(1) is that hash tables give you no way to address "the k-th element" directly: you would need to walk buckets, which is not O(1) and not uniform once buckets have different chain lengths. The array gives you that direct O(1) addressing that a hash table structurally lacks.

Worked example

import random


class RandomizedSet:
    def __init__(self):
        self.index_of: dict[int, int] = {}
        self.values: list[int] = []

    def insert(self, val: int) -> bool:
        if val in self.index_of:
            return False
        self.index_of[val] = len(self.values)
        self.values.append(val)
        return True

    def remove(self, val: int) -> bool:
        if val not in self.index_of:
            return False
        idx = self.index_of[val]
        last_val = self.values[-1]
        self.values[idx] = last_val
        self.index_of[last_val] = idx
        self.values.pop()
        del self.index_of[val]
        return True

    def get_random(self) -> int:
        return random.choice(self.values)


random.seed(42)
rs = RandomizedSet()
print(rs.insert(1))
print(rs.insert(2))
print(rs.insert(3))
print(rs.remove(2))     # swaps 3 into index 1
print(rs.values)
print(rs.get_random())
print(rs.get_random())

Running this (CPython's random module, seeded) prints:

True
True
True
True
[1, 3]
1
1

Key points

• The swap-with-last trick is what keeps delete O(1): it avoids shifting every element after the removed one.
• Uniformity comes from the array having no gaps: random.choice over indices is exactly a uniform choice over the stored values.

Complexity

for insert, remove, and getRandom; $O(n)$ space for the array and hash map together.

Edge cases

• Removing the last element in the array: the "swap with last" step is swapping an element with itself, which is harmless.
• getRandom on an empty structure has no valid answer; guard it explicitly (raise, or document as undefined behavior) rather than letting random.choice throw an unhandled exception on an empty list.

Trade-offs & pitfalls

The most common mistake is deleting by shifting all elements after the removed index, which is correct but O(n), defeating the point. A second common mistake is deleting by using values.remove(val) in Python, which internally does that same O(n) scan-and-shift. The design absorbs a lighter-weight sibling problem well: an insertion-order-preserving set (for example, deduplicating items in a shopping cart while keeping display order) uses the same "array plus hash map of positions" composition, but it cannot use the swap-with-last trick, because swapping would destroy the insertion order it is trying to preserve. That variant instead needs either a tombstone marker left in place (with periodic compaction) or a doubly linked list plus hash map (the same structure used for an LRU cache), trading away the O(1) swap-delete for order preservation.

Direct answer

Put a GraphQL layer in front of the existing REST services as a facade (a thin new front door that translates the new query language into calls to the old system) and migrate the product screen by screen. Existing clients keep calling REST untouched, the facade reuses the same services and business rules, and each screen switches behind a feature flag (a configuration switch, read at run time, that turns the new code path on or off for chosen users without a deploy) once its GraphQL version is proven equivalent. Retire a REST endpoint only when measured traffic to it has been zero for longer than your slowest client can take to upgrade.

Phase 1: facade over the existing services

• Stand up one GraphQL server (the facade) whose resolvers (the functions that fetch each field) call the existing REST endpoints or the service layer behind them. No data model rewrite and no REST change, so there is nothing for old clients to notice.
• Model the schema around what screens need, not a 1:1 mirror of the REST resources. This is where the over-fetching (receiving fields the screen ignores) and under-fetching (needing extra calls for missing fields) problems are actually fixed.
• Pass the caller's credentials through and keep authorisation in the services, so the facade cannot become a bypass.
• Guard against the classic resolver cost: a list of 50 orders whose resolver calls the customer service once per order issues 50 calls (the "N+1" problem). Batch lookups per request with a batching helper such as DataLoader, and set query depth and complexity limits, or allow only pre-registered ("persisted") queries from your own apps.

Phase 2: move screens one at a time

1. Pick a low-risk, high-pain first screen (one with many REST calls, so the win is visible).
2. Build it against GraphQL behind a feature flag, and run a parity check in staging: load the same data through the REST path and the GraphQL path and diff what the screen renders. For example, for order 1042 the REST path renders the total $84.50 and the GraphQL path renders $84.5; the diff flags that one field, and the fix is a formatting rule or a missing field in the schema, not a change to the check.
3. Roll out by canary (named after the canary in the coal mine: a small slice of users gets the change first, so a problem shows up on few people): for example 1 percent, 10 percent, 50 percent, 100 percent, holding at each step long enough to see error and latency data. Rollback is the flag, not a deploy.
4. Compare the same signals for both paths: error rate, 95th percentile latency (the time that 95 percent of requests beat; only the slowest 1 in 20 take longer), payload bytes, and backend calls per page. Stop the rollout if any regresses.
5. Repeat for the next screen. New screens are GraphQL from the start, which stops the legacy surface from growing.

Mark REST-shaped parts of the schema that you want people to leave with GraphQL's built-in @deprecated(reason: "...") directive, which the GraphQL documentation describes as the way to annotate deprecated fields; tooling then warns developers.

Gateway, stitching, or one facade

• Single facade owned by one team is the recommendation to start: one schema, one deploy, simple debugging.
• Schema stitching or federation (two ways of combining several teams' separate GraphQL schemas into one graph that clients query as a single API; a gateway routes each field to the team that owns it) pays off when multiple teams own different parts and cannot share one repository. It adds a gateway layer to operate, so adopt it when team boundaries demand it, not on day one.
• A BFF per client type (a backend-for-frontend, a server tailored to one client such as web or mobile) is an alternative when clients differ sharply; GraphQL lets one server serve both because each client chooses its fields.

Keeping existing clients working

REST contracts are frozen: no breaking changes while GraphQL adoption proceeds. Old mobile app versions stay in the wild for months, so the legacy API must outlive the web migration. Add a client-version tag to requests now (a header such as an app version) if one does not exist, since the retirement decision depends on it.

Deciding when to retire an endpoint

Retire per endpoint, never as one big switch. Evidence to require:

1. Traffic: request count per endpoint, broken down by client and app version, shows zero from supported versions for a full window. Choose the window to cover your slowest release cadence plus your forced-upgrade policy (for example the longest period a mobile version stays supported); that number is a business decision, not a technical constant. Illustrative policy: each app version stays supported for 12 months after the release that replaced it, so an endpoint last used by version 7 can be retired only once version 7's support has ended (12 months after version 8 shipped), plus a 30-day margin, with zero supported-version traffic in the final 30 days.
2. Remaining callers identified: any non-zero traffic maps to a named owner (internal job, partner, old app version), each with a migration path or an agreed end date.
3. Replacement proven: the GraphQL path has run at full traffic through at least one complete business cycle (month end, sale peaks) with no regression.
4. Staged shutdown: announce, then log warnings and email owners of the remaining callers, then run short scheduled outages of the endpoint to flush out hidden dependants, then remove. The scheduled outages convert silent dependencies into visible, reversible failures.

Communicate throughout: a published timeline, a migration guide per endpoint, a single dashboard showing traffic left, and a named contact for partners. Incentives matter for internal teams: new features ship only on GraphQL, and their performance wins are reported back to them.

Worked example

A mobile "order details" screen currently makes 4 REST calls: /orders/{id}, /customers/{id}, /orders/{id}/items, /shipments?order={id}. The facade exposes one order(id) query asking for 9 of the roughly 40 fields across those responses. In staging, a parity test fetches the screen's data both ways for 200 sampled order ids and fails if any rendered field differs. The screen then ships at 1 percent of users behind a flag; the team watches error rate and latency against the REST cohort for a week before raising it. Illustrative figures, assuming a 150 ms round trip from the phone, 30 ms of server time per call, a 5 ms internal link from the facade to the services, and about 300 bytes per field: the REST screen needs two sequential waves (the order first, then customer, items and shipments in parallel), about 2 x (150 + 30) = 360 ms and 40 x 300 = 12,000 bytes; the GraphQL screen needs one round trip plus the facade's own two waves, about 150 + 2 x (5 + 30) = 220 ms and 9 x 300 = 2,700 bytes. The four REST routes stay alive for the previous app versions; their per-version traffic chart is what later justifies removal.

Trade-offs and pitfalls

• Facade becomes the bottleneck: every GraphQL request now depends on it, so give it its own scaling, timeouts and per-resolver circuit breaking (when one downstream service keeps failing, the resolver stops calling it for a short time and returns an error or a fallback at once, instead of letting every request wait on a service that is down).
• HTTP caching is harder: GraphQL queries are typically POST, so URL-based caches and CDNs (content delivery networks) do less; plan persisted queries or response-level caching.
• Two systems to run during migration: budget for the overlap period and set the end date up front, or the legacy layer lives forever.
• Mirroring REST 1:1 in the schema keeps the old problems with a new syntax.
• What flips the recommendation: if the problem is only one or two chatty screens, a purpose-built BFF endpoint is cheaper than adopting GraphQL across the product.

Direct answer

Normalize the transactional core (orders, order items, payments) for correctness, so a checkout can never drift into a partially-updated state, and add a deliberately denormalized, separately-maintained analytic layer, rollup tables or a columnar replica, for the live dashboard, rather than denormalizing the transactional schema itself to serve both. Protect transactional latency by structurally separating where the analytic query executes: a replica, a columnar engine, or an isolated resource pool inside an HTAP database, never the same buffer pool and lock manager checkout writes to.

Structured elaboration

Normalized vs denormalized

Order placement needs a normalized schema (orders one-to-many order_items, a foreign key to payments) so a single update can't leave line items and totals inconsistent. The live dashboard wants pre-aggregated, denormalized rollups (orders per minute by region, say) because recomputing that aggregation from the normalized tables on every refresh means repeatedly scanning the same tables checkout is writing to.

Indexing

The transactional side wants few, narrow, high-selectivity indexes (indexes on columns with enough distinct values that a lookup quickly narrows to a small number of rows, instead of scanning a large chunk of the table) tuned for point lookups and inserts, because every extra index is write amplification (each index has to be updated too, so one logical write turns into several physical writes) on every insert and update. Analytic queries want either a columnar representation, compressed and scanned by column, or purpose-built aggregate tables. That is a fundamentally different access pattern than a small set of B-tree indexes (a sorted tree structure most relational databases use by default, good at point lookups and range scans over rows) can serve well at both ends.

Protecting transactional latency

Resource isolation is the core requirement: (a) a physically separate replica so analytic scans never share a buffer pool (the in-memory cache of recently used data pages) or lock manager (the component that tracks which rows are locked by in-progress transactions) with checkout writes, (b) if using a genuinely HTAP engine, isolate at the engine level (TiDB pairs a transactional row store, TiKV, with a separate columnar replica, TiFlash, and routes analytic queries to TiFlash's nodes so they don't consume TiKV's transactional resources; SingleStore's unified storage still benefits from routing heavy scans to dedicated compute), and (c) query timeouts and resource governors so a runaway dashboard query gets killed rather than starving checkout.

Consistency models

Dashboard reads are usually fine as read-committed (each query only sees data that has already been committed, though two steps of the same query can still see slightly different snapshots, unlike a stricter isolation level), or even bounded-staleness against a replica (orders 5 to 30 seconds old is normal for a live dashboard). Order placement needs full ACID within the checkout transaction: an order and its payment record commit together or not at all. Naming this distinction explicitly in the design, which paths get which guarantee, prevents someone downstream from assuming the whole system is uniformly strongly consistent.

HTAP database vs separate systems with CDC

Choose a purpose-built HTAP database when the dashboard needs to reflect committed writes within single-digit seconds and you want to operate one system instead of two. Choose CDC (change data capture: streaming each committed row change out of the database as an event) into a separate analytic system when the team already runs a mature analytics stack, when tens of seconds to a couple of minutes of dashboard staleness is acceptable, or when the transactional engine is fixed by other constraints (an existing investment, a compliance requirement) and swapping it isn't realistic.

Worked example

-- Transactional core (normalized)
CREATE TABLE orders (
  order_id    BIGSERIAL PRIMARY KEY,
  customer_id BIGINT NOT NULL,
  region      TEXT NOT NULL,
  status      TEXT NOT NULL,
  placed_at   TIMESTAMPTZ NOT NULL DEFAULT now()
);
CREATE TABLE order_items (
  order_item_id    BIGSERIAL PRIMARY KEY,
  order_id         BIGINT NOT NULL REFERENCES orders(order_id),
  sku              TEXT NOT NULL,
  qty              INT NOT NULL,
  unit_price_cents BIGINT NOT NULL
);
CREATE INDEX idx_orders_customer ON orders(customer_id);

-- Analytic rollup, maintained out of band (CDC or a scheduled job), never read by checkout
CREATE TABLE orders_per_minute_by_region (
  minute_bucket TIMESTAMPTZ NOT NULL,
  region        TEXT NOT NULL,
  order_count   BIGINT NOT NULL,
  revenue_cents BIGINT NOT NULL,
  PRIMARY KEY (minute_bucket, region)
);

The dashboard queries orders_per_minute_by_region, a handful of rows per screen refresh, instead of aggregating the full orders table, so its query cost stays roughly constant as orders grows, and checkout writes only ever touch orders and order_items, never contending with the dashboard's aggregation.

Trade-offs & pitfalls

Over-denormalizing the transactional side itself, embedding computed aggregates directly into orders, trades write-path correctness for read convenience and reintroduces the anomalies normalization exists to prevent. Under-isolating, letting the dashboard query the live orders table "just for now", is the single most common way this design degrades in production: a query that was fine at low volume becomes a lock-contention or cache-eviction problem once order volume climbs. On the HTAP side, only the specific tables the dashboard reads need dual row and columnar treatment; forcing every table in the schema onto the HTAP engine's more constrained feature set buys nothing.