Netflix Software Engineer Interview Preparation Guide - Entry Level

Direct answer

lower_bound(arr, x) returns the first index whose value is greater than or equal to x; upper_bound(arr, x) returns the first index whose value is strictly greater than x. Both return len(arr) when no such index exists. They are the same loop with one character of difference (< becomes <=): the lower bound moves right while arr[mid] < x, the upper bound while arr[mid] <= x. The number of occurrences of x is upper_bound - lower_bound, in O(log n) time.

The idea in plain words

In a sorted array, think of the values as three runs for a given x: first the values smaller than x, then the values equal to x, then the values bigger than x. lower_bound finds where the equal run begins, upper_bound finds where it ends (one past its last element). The distance between them is the run's length, which is the count. If x is absent, both functions return the same index (the position where x would be inserted to keep the array sorted), and the count is 0.

Brute force

arr.count(x) or a loop scans the whole array: O(n). Binary search finds the two boundaries with about log2(n) steps each: for 1,000,000 items that is at most 20 halvings, against up to 1,000,000 reads for the scan.

Approach and invariant

Use a half-open window [lo, hi): the square bracket means lo is inside the window and the round bracket means hi is outside it, so [0, 6) over six items covers indices 0, 1, 2, 3, 4, 5. Start with lo = 0 and hi = len(arr) (one past the end, so the answer len(arr) is reachable). Invariant, in words: every index left of lo holds a value on the "go right" side (smaller than x for the lower bound, smaller or equal for the upper bound), and every index from hi on holds a value on the other side. The undecided positions are the ones between lo and hi.

• If arr[mid] is on the left side, then mid and everything before it are decided: lo = mid + 1.
• Otherwise mid may be the boundary itself, so it stays in the window: hi = mid.

The loop ends when lo == hi, and that index is the boundary.

Code

Each function has its own loop so each invariant stays visible. The driver prints lo, hi and mid for target 2 in [1, 2, 2, 2, 5, 7], then edge cases (target below, between, at the ends and above everything; an empty array; an all-equal array), a buggy version to show an off-by-one pitfall, and a check of 5000 random cases (seed 3) against the standard library's bisect_left, bisect_right and list.count.

import random
from bisect import bisect_left, bisect_right
from typing import List


def lower_bound(arr: List[int], target: int, trace: bool = False) -> int:
    """First index i with arr[i] >= target (len(arr) if there is none).

    Invariant: arr[j] < target for every j < lo, and arr[j] >= target for every j >= hi.
    """
    lo, hi = 0, len(arr)                 # hi is one past the last candidate
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if trace:
            print(f"  lower: lo={lo} hi={hi} mid={mid} arr[mid]={arr[mid]}")
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo


def upper_bound(arr: List[int], target: int, trace: bool = False) -> int:
    """First index i with arr[i] > target (len(arr) if there is none).

    Invariant: arr[j] <= target for every j < lo, and arr[j] > target for every j >= hi.
    """
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if trace:
            print(f"  upper: lo={lo} hi={hi} mid={mid} arr[mid]={arr[mid]}")
        if arr[mid] <= target:           # the only change from lower_bound: < becomes <=
            lo = mid + 1
        else:
            hi = mid
    return lo


def count_occurrences(arr: List[int], target: int) -> int:
    return upper_bound(arr, target) - lower_bound(arr, target)


def buggy_lower_bound(arr: List[int], target: int) -> int:
    """Pitfall: hi = len(arr) - 1 can never return len(arr)."""
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo


if __name__ == "__main__":
    arr = [1, 2, 2, 2, 5, 7]
    print("arr =", arr)
    print("target 2")
    print("  lower_bound ->", lower_bound(arr, 2, trace=True))
    print("  upper_bound ->", upper_bound(arr, 2, trace=True))
    print("  count       ->", count_occurrences(arr, 2))

    for t in (0, 1, 3, 7, 8):
        print(f"target {t}: lower={lower_bound(arr, t)} upper={upper_bound(arr, t)} count={count_occurrences(arr, t)}")
    print("empty array:", lower_bound([], 4), upper_bound([], 4), count_occurrences([], 4))
    print("all equal [6,6,6] target 6:", lower_bound([6, 6, 6], 6), upper_bound([6, 6, 6], 6))

    print("\npitfall: hi = len(arr) - 1")
    print("  buggy_lower_bound(arr, 8) =", buggy_lower_bound(arr, 8), " correct:", lower_bound(arr, 8))

    rng = random.Random(3)
    for _ in range(5000):
        a = sorted(rng.randint(0, 6) for _ in range(rng.randint(0, 10)))
        t = rng.randint(-1, 7)
        assert lower_bound(a, t) == bisect_left(a, t)
        assert upper_bound(a, t) == bisect_right(a, t)
        assert count_occurrences(a, t) == a.count(t)
    print("5000 random checks against bisect and list.count passed")

Run in a python:3.12 container, it prints:

arr = [1, 2, 2, 2, 5, 7]
target 2
  lower: lo=0 hi=6 mid=3 arr[mid]=2
  lower: lo=0 hi=3 mid=1 arr[mid]=2
  lower: lo=0 hi=1 mid=0 arr[mid]=1
  lower_bound -> 1
  upper: lo=0 hi=6 mid=3 arr[mid]=2
  upper: lo=4 hi=6 mid=5 arr[mid]=7
  upper: lo=4 hi=5 mid=4 arr[mid]=5
  upper_bound -> 4
  count       -> 3
target 0: lower=0 upper=0 count=0
target 1: lower=0 upper=1 count=1
target 3: lower=4 upper=4 count=0
target 7: lower=5 upper=6 count=1
target 8: lower=6 upper=6 count=0
empty array: 0 0 0
all equal [6,6,6] target 6: 0 3

pitfall: hi = len(arr) - 1
  buggy_lower_bound(arr, 8) = 5  correct: 6
5000 random checks against bisect and list.count passed

Worked trace

For target 2 in [1, 2, 2, 2, 5, 7] (equal run at indices 1 to 3):

• Lower bound: window [0, 6), mid 3 holds 2 (not smaller), hi becomes 3. Window [0, 3), mid 1 holds 2, hi becomes 1. Window [0, 1), mid 0 holds 1 (smaller), lo becomes 1. Result 1.
• Upper bound: window [0, 6), mid 3 holds 2 (not greater), lo becomes 4. Window [4, 6), mid 5 holds 7 (greater), hi becomes 5. Window [4, 5), mid 4 holds 5, hi becomes 4. Result 4.
• Count: 4 - 1 = 3, matching the three 2s.

Complexity

Each function halves a window of size n, so O(log n) time (at most floor(log2 n) + 1 iterations) and O(1) space. Counting occurrences calls both, so it is O(log n) as well, compared with O(n) for a scan. These two functions are the building blocks for "first and last position", "insert position" and "how many values fall in [a, b]", which is upper_bound(b) - lower_bound(a).

Off-by-one pitfalls checked

1. Window end. Starting with hi = len(arr) - 1 and while lo < hi can never return len(arr). The run shows the failure: for target 8 in [1, 2, 2, 2, 5, 7] the buggy version returns 5, while the correct answer is 6.
2. Wrong comparison. Using < in the upper bound (or <= in the lower bound) swaps the two functions; for target 2 the upper bound would return 1 instead of 4.
3. Shrinking the window incorrectly. hi = mid - 1 throws away a possible boundary; lo = mid instead of mid + 1 can loop forever once the window is down to one element, where mid equals lo (shown in the run after this list).
4. Out-of-range reads. The functions never read arr[len(arr)], because mid < hi <= len(arr). Code that reads arr[lo] after the loop must first test lo < len(arr).
5. Midpoint overflow. lo + (hi - lo) // 2 instead of (lo + hi) // 2 for fixed-width integers (a 32-bit signed int overflows when lo + hi exceeds 2,147,483,647).
6. Empty array. hi = 0 so the loop never runs; both functions return 0 and the count is 0.
7. All-equal array. [6, 6, 6] with target 6 gives lower 0 and upper 3, count 3, with no special case.

Two claims above are easy to check with a short program: the stuck loop of pitfall 3 and the step count. It uses the same half-open window, and the last line shows what [0, 6) covers.

import math


def stuck_lower_bound(arr, target, max_rounds=4):
    """Pitfall: lo = mid instead of lo = mid + 1."""
    lo, hi = 0, len(arr)
    for _ in range(max_rounds):
        if lo >= hi:
            print("  finished")
            return lo
        mid = lo + (hi - lo) // 2
        print(f"  lo={lo} hi={hi} mid={mid} arr[mid]={arr[mid]}")
        if arr[mid] < target:
            lo = mid                 # bug: should be mid + 1
        else:
            hi = mid
    print(f"  still undecided after {max_rounds} rounds: lo={lo} hi={hi}")
    return None


def lower_bound_steps(n, target):
    arr = list(range(n))
    lo, hi, steps = 0, n, 0
    while lo < hi:
        mid = lo + (hi - lo) // 2
        steps += 1
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return steps


print("target 2 in [1, 3], with lo = mid:")
stuck_lower_bound([1, 3], 2)
n = 1_000_000
print("n =", n, "steps:", lower_bound_steps(n, n), "bound floor(log2 n) + 1 =", math.floor(math.log2(n)) + 1)
print("window [0, 6) covers indices:", list(range(0, 6)))

Run in a python:3.12 container, it prints:

target 2 in [1, 3], with lo = mid:
  lo=0 hi=2 mid=1 arr[mid]=3
  lo=0 hi=1 mid=0 arr[mid]=1
  lo=0 hi=1 mid=0 arr[mid]=1
  lo=0 hi=1 mid=0 arr[mid]=1
  still undecided after 4 rounds: lo=0 hi=1
n = 1000000 steps: 19 bound floor(log2 n) + 1 = 20
window [0, 6) covers indices: [0, 1, 2, 3, 4, 5]

Read it like this: with lo = mid, the window [0, 1) has mid = lo = 0, arr[0] is smaller than the target, and lo = mid leaves the window unchanged, so every later round is identical. A window of one element is where mid equals lo, which is why the fix is mid + 1. For one million items the loop ran 19 times, and the bound floor(log2 n) + 1 allows 20.

Node.js version

The same logic with JavaScript signatures lowerBound(arr, target), upperBound(arr, target) and countOccurrences(arr, target). The midpoint uses >> 1, a right shift by one bit, which halves a non-negative whole number and drops the remainder (7 >> 1 is 3). It is safe here for arrays shorter than 2^31 elements because JavaScript's bit shifts operate on 32-bit integers. The test calls print the lower bound, upper bound and count for the same data.

function lowerBound(arr, target) {
  let lo = 0, hi = arr.length;
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (arr[mid] < target) lo = mid + 1; else hi = mid;
  }
  return lo;
}

function upperBound(arr, target) {
  let lo = 0, hi = arr.length;
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (arr[mid] <= target) lo = mid + 1; else hi = mid;
  }
  return lo;
}

const countOccurrences = (arr, target) => upperBound(arr, target) - lowerBound(arr, target);

const arr = [1, 2, 2, 2, 5, 7];
console.log(lowerBound(arr, 2), upperBound(arr, 2), countOccurrences(arr, 2));
console.log(lowerBound(arr, 8), upperBound(arr, 0), countOccurrences([], 4));
console.log(lowerBound([6, 6, 6], 6), upperBound([6, 6, 6], 6));

Run in a node:22 container, it prints:

1 4 3
6 0 0
0 3

The three lines are: lower 1, upper 4 and count 3 for target 2; lower 6 for target 8, upper 0 for target 0 and count 0 on an empty array; and lower 0, upper 3 on [6, 6, 6].

Running the code

Python 3.12 (standard library only): python lower_upper_bound.py
Node.js 22: node lower_upper_bound.js
Pitfall check: python window_pitfalls.py
Save the listings as lower_upper_bound.py, lower_upper_bound.js and window_pitfalls.py.

Direct answer

Kadane's algorithm tracks the best sum ending exactly at the current index, resetting it whenever it goes negative, which gives O(n) time and O(1) extra space. Extend it with a couple of extra index variables to also recover the winning subarray's start and end, and treat an empty input as an explicit error rather than guessing a placeholder value.

Structured elaboration

• State. current_sum: best sum of a subarray ending at the current index. best_sum: best seen anywhere so far.
• Reset rule. If current_sum goes negative, it can never help a future subarray (adding a negative running total only hurts the next element), so restart at the current element. This is what makes the algorithm handle an all-negative array correctly, PROVIDED you initialize best_sum and current_sum with nums[0], not 0.
• The classic initialization bug. Initializing best_sum = 0 silently treats the empty subarray as a legal candidate. For an all-negative array like [-3, -1, -4, -1, -5], the true best NON-EMPTY subarray sum is -1 (the single element -1), but a 0-initialized version would wrongly report 0, implying an empty subarray beats every real one. Most interview phrasings (this one included) require a non-empty subarray, so seed with the first element.
• Recovering indices. Track current_start (where the current running sum began) alongside current_sum; whenever current_sum resets, current_start moves to the current index. Whenever current_sum beats best_sum, copy current_start and the current index into best_start/best_end.
• Empty array. There is no subarray to return, so raise explicitly rather than returning 0 or None, which would look like a valid (and wrong) answer to a caller who doesn't check.

Worked example

def max_subarray(nums):
    if not nums:
        raise ValueError("max_subarray: input array must be non-empty")

    best_sum = current_sum = nums[0]
    best_start = best_end = 0
    current_start = 0

    for i in range(1, len(nums)):
        if current_sum < 0:
            current_sum = nums[i]
            current_start = i
        else:
            current_sum += nums[i]

        if current_sum > best_sum:
            best_sum = current_sum
            best_start = current_start
            best_end = i

    return best_sum, best_start, best_end


def max_subarray_brute_force(nums):
    n = len(nums)
    best = nums[0]
    for i in range(n):
        s = 0
        for j in range(i, n):
            s += nums[j]
            if s > best:
                best = s
    return best


cases = [
    [-2, 1, -3, 4, -1, 2, 1, -5, 4],
    [-3, -1, -4, -1, -5],
    [5],
    [2, 2, 2],
]
for nums in cases:
    best_sum, start, end = max_subarray(nums)
    brute = max_subarray_brute_force(nums)
    print(f"nums={nums} -> best_sum={best_sum}, subarray={nums[start:end+1]}, indices=({start},{end}), brute_force={brute}")
    assert best_sum == brute

try:
    max_subarray([])
except ValueError as e:
    print(f"empty input raised ValueError as expected: {e}")
print("brute-force cross-check passed for all cases")

Output (executed, python3 s62_kadane.py, also cross-checked against an O(n^2) brute force for every case):

nums=[-2, 1, -3, 4, -1, 2, 1, -5, 4] -> best_sum=6, subarray=[4, -1, 2, 1], indices=(3,6), brute_force=6
nums=[-3, -1, -4, -1, -5] -> best_sum=-1, subarray=[-1], indices=(1,1), brute_force=-1
nums=[5] -> best_sum=5, subarray=[5], indices=(0,0), brute_force=5
nums=[2, 2, 2] -> best_sum=6, subarray=[2, 2, 2], indices=(0,2), brute_force=6
empty input raised ValueError as expected: max_subarray: input array must be non-empty
brute-force cross-check passed for all cases

Trade-offs & pitfalls

• Seeding best_sum = 0 is the single most common bug on this problem; always test against an all-negative array to catch it (as above).
• Deciding whether the empty subarray is a legal answer is a real design decision, not a formality; state the assumption up front rather than let the code's default silently pick one.
• The state above is O(1) beyond the input, so it also works directly on a stream you can only scan once, but you cannot recover the ORIGINAL array's earlier indices after the fact unless you kept them as you went, which is exactly what current_start/best_start already do here at no extra asymptotic cost.
• A Java port of this same logic is a straightforward, mechanical translation (three int locals instead of Python variables, an explicit IllegalArgumentException in place of the ValueError); nothing about the algorithm changes across the two languages.

A CPU flame graph turns "the service is slow" into "this specific function, at this depth in the call stack, is where the CPU time actually goes."

Generating one (Node.js example)

node --prof app.js
# ... reproduce the load ...
node --prof-process isolate-*.log > processed.txt
# or, using the community 0x tool for an interactive SVG:
npx 0x -- node app.js

The tool samples the call stack at a fixed interval (e.g. every few milliseconds) while the service handles real or synthetic load, then aggregates samples into a flame graph: each box is a function, its width represents the proportion of samples where that function was on the stack, and stacking upward shows the call hierarchy.

Interpreting it

Wide boxes are where time concentrates; a wide box near the top of a stack (a leaf function) means that function itself is expensive, while a wide box lower down that's wide mostly because of what's stacked above it points at a caller invoking something expensive repeatedly. Given a hot function path, the concrete next step is either optimizing that function directly, reducing how often it's called (caching, batching), or moving it off the hot path (async, a background job).

Validating the fix

Regenerate the flame graph after the change under the same load profile and confirm the previously-wide box narrows, while also checking tail latency and throughput didn't regress elsewhere as a side effect (an optimization that shifts work rather than removing it is easy to mistake for a fix).

Trade-offs and pitfalls

A textual, stack-only flame graph excerpt can mislead if you don't also check what's not code: JIT compilation, garbage collection pauses, and syscalls can all show up as wide "hot" regions that no application-level optimization will fix, and reading them as ordinary application hotspots wastes effort on the wrong target.

Direct answer

Plain Kahn's algorithm with a FIFO queue produces a valid topological order, but which one depends on insertion order among tied, simultaneously-available vertices. To force the lexicographically smallest valid order (smallest by node id, compared position by position), replace the queue with a min-heap: at every step, among all vertices currently free of unmet dependencies, always emit the smallest id. This is a small structural change with a real complexity cost: $O((V+E)\log V)$ instead of $O(V+E)$, because every insertion and extraction on the heap costs $O(\log V)$.

Structured elaboration

The algorithm is Kahn's algorithm verbatim except for one substitution: swap deque for heapq. Correctness for cycle detection is unchanged (a cycle still means some vertices never reach in-degree 0, so the output stays short); the only new property is that whenever more than one vertex is simultaneously eligible, the heap always yields the smallest one first, which is exactly the greedy rule that produces the lexicographically smallest sequence: committing to the smallest available choice at every position, given that any later choice is still available to be picked in a later position if it becomes newly eligible.

Why greedy-smallest-first is provably correct here (not just plausible). Suppose the true lexicographically smallest valid order picks vertex $x$ at some position, but $x$ is not the smallest currently-eligible vertex; call the smallest eligible one $y < x$. Since $y$ has no unmet dependency, nothing prevents placing $y$ at that position instead, and $y$'s own dependents only become eligible later regardless of whether $y$ is placed now or later, so swapping $y$ into that earlier position can only make the sequence lexicographically smaller or equal, never invalid. This is the standard exchange argument for greedy algorithms; it is why the heap substitution alone (no other logic change) is sufficient.

Worked example

import heapq
from typing import Dict, List, Optional

def topo_lex(graph: Dict[int, List[int]]) -> Optional[List[int]]:
    # Kahn's algorithm with a min-heap instead of a FIFO queue: among all
    # nodes currently available (indegree 0), always pop the smallest id.
    # Returns the lexicographically smallest valid topological order, or
    # None if the graph has a cycle.
    indegree = {u: 0 for u in graph}
    for u in graph:
        for v in graph[u]:
            indegree[v] += 1

    heap = [u for u in graph if indegree[u] == 0]
    heapq.heapify(heap)
    order = []
    while heap:
        u = heapq.heappop(heap)
        order.append(u)
        for v in graph[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                heapq.heappush(heap, v)

    if len(order) != len(graph):
        return None
    return order

if __name__ == "__main__":
    dag = {5: [2, 0], 4: [0, 1], 2: [3], 3: [1], 0: [], 1: []}
    result = topo_lex(dict(dag))
    print("Lexicographically smallest order:", result)

    def is_valid_topo(order, graph):
        pos = {n: i for i, n in enumerate(order)}
        return all(pos[u] < pos[v] for u in graph for v in graph[u])
    print("Valid topological order:", is_valid_topo(result, dag))

    from itertools import permutations
    nodes = list(dag.keys())
    valid_orders = [list(p) for p in permutations(nodes) if is_valid_topo(list(p), dag)]
    brute_min = min(valid_orders)
    print("Brute-force minimum over all valid orders:", brute_min)
    print("Matches heap-based result:", brute_min == result)

    cyclic = {0: [1], 1: [2], 2: [0]}
    print("Cyclic graph result:", topo_lex(dict(cyclic)))

Output (actually executed with python3):

Lexicographically smallest order: [4, 5, 0, 2, 3, 1]
Valid topological order: True
Brute-force minimum over all valid orders: [4, 5, 0, 2, 3, 1]
Matches heap-based result: True
Cyclic graph result: None

The brute-force check enumerates every permutation of the six vertices, keeps only the ones that respect every edge, and takes the minimum by standard list (lexicographic) comparison. This is only feasible for the toy example ($6! = 720$ permutations) and exists purely to independently confirm the heap-based algorithm's exchange argument holds on a real case, not as a scalable approach in itself.

Complexity

Time $O((V+E)\log V)$: every vertex is pushed and popped from the heap once ($O(V \log V)$ total), and every edge triggers at most one additional push when its target's in-degree reaches zero ($O(E \log V)$ total). Space $O(V)$ for the heap and in-degree map, plus $O(V+E)$ for the adjacency list.

Edge cases

• All vertices tied at in-degree 0 (a totally disconnected graph): the heap degenerates to simply popping vertices in ascending id order, which is correct and matches the lexicographically-smallest definition trivially.
• A long single chain ($0\to1\to2\to\dots$): only one vertex is ever eligible at a time, so the heap never actually has a choice to make; the result is forced and identical to what plain Kahn's algorithm would produce.
• Cycle: identical detection to plain Kahn's algorithm, None when the output falls short of len(graph).
• Negative or non-integer ids: the heap comparison works for any totally ordered, hashable type, so this generalizes to string ids (alphabetical order) without changing the algorithm, only the type annotation.

Trade-offs and pitfalls

• Common mistake: assuming a plain, unmodified Kahn's algorithm with a FIFO queue already gives the lexicographically smallest order "because it processes in the order things become available." That is false in general: two vertices can become eligible in the same round, and FIFO preserves insertion order (which reflects the order their prerequisites happened to be processed in), not numeric order. Only replacing the queue's tie-breaking mechanism with an explicit min-heap (or a per-round sort) fixes this.
• Common mistake: sorting the entire vertex list once at the start and iterating in that fixed order while checking in-degree, instead of using a heap. This looks similar but is wrong: a vertex with a smaller id can become eligible several rounds after a vertex with a larger id, and a single static sort pass cannot re-examine a vertex once skipped in an earlier scan, or would need to re-scan the whole list every round, which is $O(V)$ per round instead of $O(\log V)$ per operation.
• This exact technique (a min-heap-based topological sort relying on the same exchange-argument correctness) shows up repeatedly in practice, confirming it is a stable, recognized approach rather than an unusual one-off construction; the min-heap substitution is the standard way this requirement is solved, not a workaround.
• The $O(\log V)$ factor genuinely matters at scale: for a graph with $V=10^6$ vertices, plain Kahn's algorithm and the lexicographic variant differ by roughly a factor of 20, which is worth naming explicitly if a system does not actually need reproducible ordering and is paying this cost for no functional benefit.

The idea

You may complete at most k buy-then-sell trades, holding one share at a time, so trades cannot overlap. The profit of a plan is the sum of (sell price - buy price) over its trades. The DP asks, for each number of trades allowed and each day, what the best profit is, and builds up from fewer trades and earlier days. Because a trade needs a buy day strictly before its sell day, a plan in which no day is used twice needs at least 2 days per trade, so at most n // 2 trades fit in n days. That fact gives the k > n/2 edge case.

Define the state first

1. Meaning of one cell: dp[t][i] is the most profit using at most t trades with all trades inside days 0..i.
2. Transition: dp[t][i] = max(dp[t][i-1], max over j < i of (prices[i] - prices[j] + dp[t-1][j])). Either day i is not a sale day (so the best is the same as the previous day), or the last trade buys on some day j and sells on day i, and before day j at most t-1 trades happened. The inner maximum is the best value of "profit already banked before buying, minus the buy price" over every earlier day j. It is kept as a running value best = max over j of (dp[t-1][j] - prices[j]): moving from day i to day i+1 adds exactly one new candidate (day i), so best = max(best, dp[t-1][i] - prices[i]) updates it in O(1) and each cell costs O(1). That is where the O(n k) time comes from.
3. Base cases: dp[0][i] = 0 (no trades, no profit) and dp[t][0] = 0 (one day cannot hold a complete trade).
4. Fill order: for each t from 1 to k, days left to right, so row t-1 is complete before row t starts.
5. Where the answer is read: dp[k][n-1].

The table lets a sale and a new purchase fall on the same day (best may use dp[t-1][i], which already includes a sale on day i). That does not change the answer: selling on day j and buying again on day j gives the same profit as holding through day j, which uses one trade fewer. So same-day sale and rebuy is allowed but never helps, and the "at most n // 2 trades" count below refers to plans that do not reuse a day.

An O(k)-memory formulation

The table can be replaced by two arrays of size k + 1 that are updated on each day. buy[j] is the best cash while holding the share bought in trade j, and sell[j] is the best cash with j trades finished and nothing held. On each price p: buy[j] = max(buy[j], sell[j-1] - p) and sell[j] = max(sell[j], buy[j] + p). The start is buy[j] = -infinity ("holding a share" is impossible before any price has been seen, and minus infinity can never win a max against a real value) and sell[j] = 0 (zero trades finished means zero profit, and sell[0] stays 0 forever). Each price is processed in two steps for every j: first the best cash while holding is updated (keep the old one, or spend p out of the cash from j-1 finished trades), then the best cash while flat is updated (keep the old one, or sell the share at p). The trace printed below walks the prices [3, 2, 6, 5, 0, 3] with k = 2. This is what the profit_buy_sell function does; it takes O(n k) time and O(k) extra memory beyond the input.

The case where k is larger than n/2

At most n // 2 trades can fit in n days, because each needs a buy day and a later sell day, and the next trade starts after the sale. If k >= n // 2, the limit never binds, and the answer is the unlimited-trades answer: add every day-to-day rise, sum(max(0, p[i+1] - p[i])). It is optimal because the unlimited problem can collect each rise separately. Group the rises into maximal runs of consecutive rising days; one trade per run (buy at the start of the run, sell at its end) earns exactly the sum. Two runs are separated by at least one day on which the price does not rise (it falls or stays level), so they share no day, and each run covers at least two days (a buy day and a later sell day). Hence there are at most n // 2 runs, and n // 2 trades are enough to earn the unlimited total. On [1, 5, 2, 8, 3, 9] the runs are 1 to 5, 2 to 8 and 3 to 9: three runs on six days, which the rise runs line of the output lists. The check also protects memory and time: with k = 10^9, the arrays of length k + 1 would be unaffordable, but the shortcut returns in O(n). The output shows k = 10^9 answering immediately.

Brute force first

The recursion go(i, left, holding) has three state values: the day, trades left and whether a share is held. It tries doing nothing, selling if holding, buying otherwise. Without memoization the call count depends on how large k is. The first table prints it from the real function, with the root call counted, for 0 to 6 days at k = 2; the second table compares k fixed at 2 with k as large as the number of days n. With k fixed, the count grows like a power of n (113, 1587 and 8095 calls for 6, 12 and 18 days). With k = n it roughly doubles with every added day (127, 8191 and 524287 calls). With memoization the states are n x (k + 1) x 2, which is the same work as the DP.

Code

import random


def profit_brute(prices, k):
    """Recursion on (day, transactions left, holding). Returns (profit, calls); root counted."""
    n = len(prices)
    calls = 0

    def go(i, left, holding):
        nonlocal calls
        calls += 1
        if i == n or (left == 0 and not holding):
            return 0
        best = go(i + 1, left, holding)                               # do nothing today
        if holding:
            best = max(best, prices[i] + go(i + 1, left, False))      # sell today
        elif left > 0:
            best = max(best, -prices[i] + go(i + 1, left - 1, True))  # buy today, uses one transaction
        return best

    return go(0, k, False), calls


def profit_unlimited(prices):
    """Every rise between consecutive days can be collected."""
    return sum(max(0, b - a) for a, b in zip(prices, prices[1:]))


def profit_table(prices, k):
    """dp[t][i] = best profit using at most t transactions within days 0..i."""
    n = len(prices)
    dp = [[0] * n for _ in range(k + 1)]
    for t in range(1, k + 1):
        # best = max over j <= i of (dp[t-1][j] - prices[j]): the cheapest 'net cost' of a buy
        best = dp[t - 1][0] - prices[0] if n else 0
        for i in range(1, n):
            dp[t][i] = max(dp[t][i - 1], prices[i] + best)           # no sale today, or sell today
            best = max(best, dp[t - 1][i] - prices[i])
    return dp


def profit_buy_sell(prices, k):
    """O(k) memory. buy[j] = best cash while holding a share bought in transaction j.
    sell[j] = best cash with j transactions completed and no share held."""
    n = len(prices)
    if k >= n // 2:                                                  # transactions can never run out
        return profit_unlimited(prices)
    buy = [float("-inf")] * (k + 1)
    sell = [0] * (k + 1)
    for p in prices:
        for j in range(1, k + 1):
            buy[j] = max(buy[j], sell[j - 1] - p)
            sell[j] = max(sell[j], buy[j] + p)
    return sell[k]


def profit_buy_sell_descending(prices, k):
    n = len(prices)
    if k >= n // 2:
        return profit_unlimited(prices)
    buy = [float("-inf")] * (k + 1)
    sell = [0] * (k + 1)
    for p in prices:
        for j in range(k, 0, -1):
            buy[j] = max(buy[j], sell[j - 1] - p)
            sell[j] = max(sell[j], buy[j] + p)
    return sell[k]


def profit_buy_sell_zero_init(prices, k):
    """Bug: buy[] starts at 0 instead of minus infinity, as if shares could be had for free."""
    buy = [0] * (k + 1)
    sell = [0] * (k + 1)
    for p in prices:
        for j in range(1, k + 1):
            buy[j] = max(buy[j], sell[j - 1] - p)
            sell[j] = max(sell[j], buy[j] + p)
    return sell[k]


def profit_one_row(prices, k, reverse=False):
    """The table above collapsed to one row over days. Day order matters."""
    n = len(prices)
    if n == 0:
        return 0
    dp = [0] * n
    order = list(range(1, n))
    if reverse:
        order.reverse()
    for _ in range(k):
        best = dp[0] - prices[0]
        for i in order:
            old = dp[i]                    # dp[t-1][i], needed for the next 'best'
            dp[i] = max(dp[i - 1], prices[i] + best)    # dp[i-1] must already be row t
            best = max(best, old - prices[i])
    return dp[-1]


def profit_buy_sell_trace(prices, k):
    """Same updates as profit_buy_sell without the shortcut, printing both arrays after each price."""
    buy = [float("-inf")] * (k + 1)
    sell = [0] * (k + 1)
    print("start         buy", buy[1:], "sell", sell)
    for p in prices:
        for j in range(1, k + 1):
            buy[j] = max(buy[j], sell[j - 1] - p)
            sell[j] = max(sell[j], buy[j] + p)
        print("price", p, "  buy", buy[1:], "sell", sell)
    return sell[k]


def rise_runs(prices):
    """Maximal runs of consecutive rising days, as (start price, end price)."""
    runs, i = [], 0
    while i < len(prices) - 1:
        if prices[i + 1] > prices[i]:
            j = i
            while j + 1 < len(prices) and prices[j + 1] > prices[j]:
                j += 1
            runs.append((prices[i], prices[j]))
            i = j
        else:
            i += 1
    return runs


def profit_enumerate(prices, k):
    """Reference: try every choice of up to k non-overlapping (buy day, sell day) pairs."""
    n = len(prices)
    best = 0

    def pick(start, left, total):
        nonlocal best
        best = max(best, total)
        if left == 0:
            return
        for b in range(start, n):
            for s in range(b + 1, n):
                pick(s + 1, left - 1, total + prices[s] - prices[b])

    pick(0, k, 0)
    return best


# 1. Brute-force calls at tiny sizes (root counted), k = 2
print("days  brute_calls")
for n in range(0, 7):
    print(n, profit_brute([1] * n, 2)[1])

# 1b. Brute-force growth: k fixed at 2 versus k = n (root counted)
print("n   calls(k=2)   calls(k=n)")
for n in (6, 12, 18):
    print("%2d %11d %12d" % (n, profit_brute([1] * n, 2)[1], profit_brute([1] * n, n)[1]))

# 2. Filled table
prices, k = [3, 2, 6, 5, 0, 3], 2
dp = profit_table(prices, k)
print("prices:", prices, " k =", k)
print("day i   ", list(range(len(prices))))
for t, row in enumerate(dp):
    print("dp[%d][i]" % t, row)
print("table:", dp[k][-1], " O(k) memory:", profit_buy_sell(prices, k), " brute:", profit_brute(prices, k)[0], " enumerate:", profit_enumerate(prices, k))

# 3. k larger than n // 2
prices = [1, 5, 2, 8, 3, 9]
print("n =", len(prices), " n // 2 =", len(prices) // 2)
for k in (1, 2, 3, 4, 10, 10**9):
    print("k =", k, "->", profit_buy_sell(prices, k))
print("unlimited:", profit_unlimited(prices))
runs = rise_runs(prices)
print("rise runs:", runs, "->", len(runs), "runs, profit", sum(b - a for a, b in runs))

# 3b. The O(k)-memory arrays, state after every price (k = 2)
print("O(k) trace, final:", profit_buy_sell_trace([3, 2, 6, 5, 0, 3], 2))

# 4. Edge cases
for p, k in (([], 3), ([7], 3), ([7, 3], 1), ([3, 7], 1), ([5, 4, 3, 2], 2), ([1, 2, 3, 4], 0)):
    print(p, "k =", k, "->", profit_buy_sell(p, k))

# 5. Pitfalls that change the result
print("free-buy init:", profit_buy_sell_zero_init([5, 4, 3, 2], 2), "(correct: 0)")
p = [3, 2, 6, 5, 0, 3]
print("one row, days ascending:", profit_one_row(p, 2), " days descending:", profit_one_row(p, 2, reverse=True))

# 6. Random checks against the enumeration of transaction pairs
random.seed(21)
seen, limited, with_empty = set(), 0, 0
for _ in range(400):
    p = [random.randint(0, 12) for _ in range(random.randint(0, 10))]
    k = random.randint(0, 4)
    want = profit_enumerate(p, k)
    assert profit_buy_sell(p, k) == profit_buy_sell_descending(p, k) == profit_one_row(p, k) == want
    assert profit_brute(p, k)[0] == want
    if p:
        assert profit_table(p, k)[k][-1] == want
    else:
        with_empty += 1
    limited += k < len(p) // 2
    seen.add((tuple(p), k))
print("random cases checked:", len(seen), " with k < n // 2:", limited, " empty price lists:", with_empty)

Output:

days  brute_calls
0 1
1 3
2 7
3 15
4 31
5 61
6 113
n   calls(k=2)   calls(k=n)
 6         113          127
12        1587         8191
18        8095       524287
prices: [3, 2, 6, 5, 0, 3]  k = 2
day i    [0, 1, 2, 3, 4, 5]
dp[0][i] [0, 0, 0, 0, 0, 0]
dp[1][i] [0, 0, 4, 4, 4, 4]
dp[2][i] [0, 0, 4, 4, 4, 7]
table: 7  O(k) memory: 7  brute: 7  enumerate: 7
n = 6  n // 2 = 3
k = 1 -> 8
k = 2 -> 13
k = 3 -> 16
k = 4 -> 16
k = 10 -> 16
k = 1000000000 -> 16
unlimited: 16
rise runs: [(1, 5), (2, 8), (3, 9)] -> 3 runs, profit 16
start         buy [-inf, -inf] sell [0, 0, 0]
price 3   buy [-3, -3] sell [0, 0, 0]
price 2   buy [-2, -2] sell [0, 0, 0]
price 6   buy [-2, -2] sell [0, 4, 4]
price 5   buy [-2, -1] sell [0, 4, 4]
price 0   buy [0, 4] sell [0, 4, 4]
price 3   buy [0, 4] sell [0, 4, 7]
O(k) trace, final: 7
[] k = 3 -> 0
[7] k = 3 -> 0
[7, 3] k = 1 -> 0
[3, 7] k = 1 -> 4
[5, 4, 3, 2] k = 2 -> 0
[1, 2, 3, 4] k = 0 -> 0
free-buy init: 5 (correct: 0)
one row, days ascending: 7  days descending: 0
random cases checked: 364  with k < n // 2: 194  empty price lists: 35

Reading the output

The trace lists buy[1], buy[2] and then sell[0], sell[1], sell[2] after each price of [3, 2, 6, 5, 0, 3] (k = 2). Price 3: buy[1] = max(-inf, sell[0] - 3) = -3, and buy[2] is also -3 because sell[1] is still 0. Price 2: both buys improve to -2, a cheaper purchase. Price 6: sell[1] = -2 + 6 = 4; then buy[2] = max(-2, sell[1] - 6) = -2 and sell[2] = -2 + 6 = 4, so two trades allowed gives no more than one yet. Price 5: buy[2] = max(-2, 4 - 5) = -1, which means 4 banked and a share bought at 5. Price 0: buy[1] = 0 (a share bought at 0 with nothing banked) and buy[2] = 4 - 0 = 4. Price 3: sell[2] = 4 + 3 = 7, the answer.

On [3, 2, 6, 5, 0, 3] with k = 2, row 1 shows the best single trade: buy at 2, sell at 6 for 4 (from day 2 on). Row 2 adds the second trade: buy at 0 on day 4, sell at 3 on day 5, for 3 more, so 7. The table, the O(k) version, the brute force and an enumeration of all trade pairs all print 7.

On [1, 5, 2, 8, 3, 9] (n = 6, so n // 2 = 3), k = 1 gives 8, k = 2 gives 13, and k = 3 already reaches 16, the unlimited answer. Larger k, including 10^9, gives 16 too. A price list that only falls, such as [5, 4, 3, 2], gives 0 for any k.

Pitfalls shown by runs

1. Starting buy[j] at 0 instead of negative infinity lets the code "hold a share" for free: on the falling prices [5, 4, 3, 2] it reports a profit of 5 where the correct answer is 0.
2. If the table is collapsed into one row over the days, the day loop must run left to right. The new dp[i] reads dp[i-1] from the row being built, and it reads the old dp[i] into best before overwriting it. Run right to left, the same code prints 0 on [3, 2, 6, 5, 0, 3] instead of 7.
3. In the O(k) version the order of the trade loop (j ascending or descending) does not change the result here. The ascending order lets a sale and the next purchase happen on the same day, which, as noted earlier, adds nothing. The random check compares both directions and they agree.

Complexity

Time: n x k states with constant work each, so O(n k); with the shortcut, a call with k >= n // 2 is O(n). Space: O(k) for the buy and sell arrays (the input is O(n)); the full table is O(n k). The brute force is a polynomial in n for a fixed k (the second table) and exponential in n when k grows with n.

Running the code

docker run --rm -v "$PWD":/w -w /w python:3.12 python stock_k.py

Direct answer

A project-based, hands-on course on SQL and practical data analysis did more for me than anything else recently, precisely because it graded real deliverables instead of playing videos at me; a couple of earlier attempts at pure lecture-style courses on other topics hadn't stuck the same way, which is part of why I chose the format deliberately this time.

Structured elaboration

Why that resource over the alternatives: I picked it because it forced me to produce something checkable at each stage, rather than trusting that watching explanations would translate into ability later. Not every part of it earned its time: the introductory theory modules were mostly filler I already knew, and the value was concentrated in the applied exercises with real, graded feedback.

The gap between finishing a resource and actually applying it is where most answers like this fall down, and it's worth naming directly: finishing the course did not mean I was done. The real test was the first time I used it on live work with something real depending on it, several weeks later, where I still hit gaps the course hadn't covered because the real system was messier than the course's clean examples.

There's also a time-pressured version of this same decision: on a separate occasion I picked a much narrower, faster resource specifically because I needed to solve a live problem within about two weeks, not to build general capability, and I judged it purely on whether it would get me to that specific outcome fast enough, not on how comprehensive it was.

Worked example

The concrete artifact that came out of the course was a small internal tool: a live, query-backed dashboard that replaced a set of spreadsheets three different people were manually updating each week to track our numbers. I built it directly from what the course taught and put it in front of my team within about a month of finishing. The honest measure of impact is qualitative, not a number I can defend precisely: the specific task the course targeted, pulling and reconciling that weekly data, went from something I'd avoid or hand off to something I'd take on directly, and I could point to that shift happening within a couple of months, not immediately.

Trade-offs and pitfalls

A weak version of this answer just praises the resource; a stronger one names what didn't transfer and why, since that's the part that shows genuine reflection rather than an advertisement. It's also worth being honest, if true, that a more hands-on route (shadowing someone, or just building the thing you need and looking things up as you go) might have gotten you to competence faster than a structured course did; the structured option is not automatically the right call.

Direct answer

A retro after a release with repeated design-engineering friction should produce two things: an honest, specific account of where the handoff actually broke down, not a vague 'communication issues,' and a small number of concrete process changes, each with an owner and a way to tell in a quarter whether it worked. Running it well means separating fact-finding from diagnosis, and diagnosis from blame.

Structured elaboration

Design principles for the session

• Facts before diagnosis: start from a timeline of what actually happened (spec dates, handoff dates, bug counts, points where implementation and design diverged), not from opinions about who was at fault.
• Root cause, not the nearest symptom: 'engineering didn't follow the spec' is a symptom; the root cause might be that the spec didn't capture edge-case states, or that both sides were working from different versions of a shared design system mid-migration.
• Few, high-leverage commitments: two or three process changes people will actually do beat ten action items that quietly get dropped.
• Everyone leaves with the same understanding of what changed, not just what went wrong.

A workable structure

One illustrative shape, adaptable to a team's own rhythm:

What 'actually changes how the two teams work' looks like

The output isn't a list of intentions, it's a specific artifact or habit that exists after the meeting and didn't before: a shared checklist embedded in the handoff process, an automated check that catches a class of mismatch before it ships, or a standing short sync during implementation windows. Whatever it is, it needs a way to tell if it worked, not just that it happened.

Worked example

One team's root cause turned out to be that design tokens (colors, spacing values) were maintained in the design tool but hand-copied into code, so drift was inevitable and nobody could tell which side was 'correct' when they disagreed. The concrete fix was an automated export from the design tool into the codebase, checked by both a design reviewer and a frontend reviewer before merge, plus a short recurring sync during active implementation. A quarter later, the team had a real signal that it worked: noticeably fewer visual-mismatch comments on pull requests and less late-stage rework than the release that triggered the retro. The same root-cause pattern shows up in other domains as a hand-copied data contract or config value instead of a design token, so the same fix shape (automate the handoff, add a lightweight check, add a short sync during the risky window) generalizes well beyond design and engineering specifically.

Trade-offs and pitfalls

• A retro that produces ten action items usually produces zero completed ones; prioritizing ruthlessly matters more than being thorough.
• If the room jumps straight to solutions or blame instead of facts first, the real root cause, often structural or tooling-related rather than a person's failure, never surfaces.
• A retro that isn't revisited becomes theater. Put the check-in on the calendar before the room disperses, not as a vague intention afterward.
• Watch for a fix that only addresses this specific release's symptom (a one-off manual double-check) rather than the structural cause; it holds for one cycle and then quietly stops happening.

Direct answer

Model the problem as a 4-state dynamic program tracking the best cash position after each of four events: first buy, first sell, second buy, second sell. Scan the prices once, updating all four states in the order buy1 -> sell1 -> buy2 -> sell2 so each state only ever builds on a value that is legally available before it, and the final "sold twice" state is the answer. This runs in O(n) time and O(1) space, instead of the O(n) states x O(k) transactions table a general k-transaction version would need.

Structured elaboration

The four states (all measured as net cash, i.e. profit so far minus money currently tied up in a held share):

• buy1: best position after buying the first share
• sell1: best position after selling the first share (a completed transaction)
• buy2: best position after buying a second share, funded out of sell1's profit
• sell2: best position after selling the second share (the final answer)

Recurrence, applied once per day p:

buy1  = max(buy1,  -p)
sell1 = max(sell1,  buy1 + p)
buy2  = max(buy2,   sell1 - p)
sell2 = max(sell2,  buy2 + p)

The update order matters: sell1 on day p must see buy1 as of the SAME day (not yesterday's), otherwise you could accidentally model buying and selling on two different days as if they were legal same-day actions in the wrong sequence. Because "sell before buying again" is enforced implicitly by each state only reading the state to its left within the same pass, there is no way to double-count a share.

def max_profit_two_transactions(prices):
    """
    Max profit with at most two non-overlapping buy/sell transactions.
    O(n) time, O(1) space state machine.
    """
    if not prices:
        return 0

    buy1 = -prices[0]   # best cash after 1st buy (spent money, so negative)
    sell1 = 0            # best profit after 1st sell
    buy2 = -prices[0]    # best cash after 2nd buy (funded by sell1's profit)
    sell2 = 0            # best profit after 2nd sell

    for p in prices[1:]:
        buy1 = max(buy1, -p)
        sell1 = max(sell1, buy1 + p)
        buy2 = max(buy2, sell1 - p)
        sell2 = max(sell2, buy2 + p)

    return sell2

prices = [3, 3, 5, 0, 0, 3, 1, 4]
print(max_profit_two_transactions(prices))
print(max_profit_two_transactions([]))
print(max_profit_two_transactions([7, 6, 4, 3, 1]))

Output:

6
0
0

Key points

• Each variable only ever holds the BEST value seen for that state so far; nothing is ever overwritten with a worse option.
• Initializing buy1/buy2 to -prices[0] (instead of negative infinity) is safe because day 0 cannot possibly contribute a completed transaction yet.

Worked example

Trace prices = [3, 3, 5, 0, 0, 3, 1, 4] day by day:

The final answer, 6, comes from buying at 3 (day 0 or 1) and selling at 5 (day 2) for a profit of 2, then buying again at 0 (day 3 or 4) and selling at 4 (day 7) for a profit of 4: $2 + 4 = 6$.

Complexity

$T(n) = O(n), \quad S(n) = O(1)$: a single pass over the $n$ prices, four $O(1)$ updates
(buy1, sell1, buy2, sell2) per day, and only four scalar variables carried between days.

Edge cases

• Empty or single-price input returns 0.
• A monotonically decreasing price series also returns 0 (no profitable trade exists).
• If the best strategy only uses one transaction, sell2 naturally converges to the same value
  as the best single-transaction profit, since buy2/sell2 are free to "waste" a transaction
  at zero net effect.

Trade-offs & pitfalls

• Generalizing to k transactions: extend to 2k states (buy1..buyk, sell1..sellk), giving O(nk) time and O(k) space; once k is large enough that 2k >= n, the problem degenerates to the unlimited-transactions case (simply sum every positive day-over-day price increase).
• Transaction fees: subtract the fee at each sell step (sell1 = max(sell1, buy1 + p - fee)), which changes which trades are worth taking but not the shape of the recurrence.
• Cooldown period: if you must wait a day after selling before buying again, buy states need to read from sell two steps back rather than the immediately preceding state, which requires carrying an extra lagging variable.
• Pitfall: getting the update order wrong (e.g. computing all four states from the PREVIOUS day's values instead of chaining within the same day) silently allows an extra profit unit per day, most easily caught by tracing a short example like the one above by hand.

Direct answer

Track promotion redemptions with three tables: promotions (the rule definition), promotion_assignments (which users are eligible for which promotion), and promotion_redemptions (which assignments were actually used), so that redemption rate is a simple ratio between the last two tables.

Structured elaboration

• promotions(promotion_id PK, code, discount_type, discount_value, is_one_time_use, valid_from, valid_to).
• promotion_assignments(assignment_id PK, promotion_id FK, user_id FK, assigned_at): one row per user made eligible for a promotion, whether by targeting, opt-in, or automatic enrollment.
• promotion_redemptions(redemption_id PK, assignment_id FK, order_id FK, redeemed_at, is_one_time_use): one row per actual use. The is_one_time_use column is a copy of the flag from promotions, captured at redemption time so the one-time-use rule can be enforced with a partial unique index scoped to this table alone (a unique index cannot reference columns on another table, so the flag has to be denormalized onto the redemptions row itself to be enforceable this way).

Metrics fall out directly: redemption_rate = COUNT(DISTINCT promotion_redemptions.assignment_id) / COUNT(DISTINCT promotion_assignments.assignment_id) per promotion, and time_to_redemption = redeemed_at - assigned_at, averaged per promotion.

Worked example

CREATE TABLE promotions (
  promotion_id   BIGINT PRIMARY KEY,
  code           TEXT NOT NULL UNIQUE,
  discount_value NUMERIC(10,2) NOT NULL,
  is_one_time_use BOOLEAN NOT NULL DEFAULT TRUE
);

CREATE TABLE promotion_assignments (
  assignment_id  BIGINT PRIMARY KEY,
  promotion_id   BIGINT NOT NULL REFERENCES promotions(promotion_id),
  user_id        BIGINT NOT NULL,
  assigned_at    TIMESTAMP NOT NULL,
  UNIQUE (promotion_id, user_id)
);

CREATE TABLE promotion_redemptions (
  redemption_id  BIGINT PRIMARY KEY,
  assignment_id  BIGINT NOT NULL REFERENCES promotion_assignments(assignment_id),
  order_id       BIGINT NOT NULL,
  redeemed_at    TIMESTAMP NOT NULL,
  is_one_time_use BOOLEAN NOT NULL   -- copied from promotions.is_one_time_use when the redemption is written
);

-- Enforces "at most one redemption per assignment" only for assignments flagged
-- one-time-use; multi-use promotions are free to redeem the same assignment
-- more than once.
CREATE UNIQUE INDEX one_time_redemption_uq
  ON promotion_redemptions (assignment_id)
  WHERE is_one_time_use;

This was verified in sqlite3 (which supports partial indexes): for a one-time-use promotion, a second INSERT referencing the same assignment_id is correctly rejected by the partial unique index; for a non-one-time-use promotion (is_one_time_use = false), a second redemption against the same assignment_id correctly succeeds, since that row falls outside the partial index's WHERE clause. A plain, unconditional UNIQUE constraint on assignment_id (with no WHERE clause) would have blocked legitimate repeat redemptions for multi-use promotions too, which is why the constraint has to be partial rather than blanket.

Trade-offs and pitfalls

• Concurrency is the real risk with one-time-use promotions: two simultaneous checkout requests for the same user and promotion could both pass an application-level "already redeemed?" check before either commits; the partial UNIQUE index is what actually prevents the double-redemption race, by making the database itself reject the second insert rather than relying on a check-then-act race in application code.
• The is_one_time_use value on promotion_redemptions is a denormalized copy of the flag on promotions, captured at write time; if the promotion's flag ever changes after assignments already exist, already-written redemption rows keep whatever flag they were written with, so a promotion-level flag change does not retroactively tighten or loosen enforcement on rows written before the change.
• For promotions with stacking rules, conditional eligibility (new customer only, minimum basket size), expiration, and partial refunds, this schema is a floor, not a ceiling: those rules typically live in a separate eligibility-evaluation layer that reads promotions and the customer/order context at checkout time, rather than being encoded as extra columns on these three tables, because the rules themselves change far more often than the redemption-tracking shape does.
• Redemption rate as defined here silently excludes users who were never assigned in the first place; if the real question is "what fraction of ALL customers used this promotion," you need to join against the full customer base, not just promotion_assignments, which measures conversion only among those who were targeted.

Direct answer
Before writing safeParseInt, the edge cases to list are: null, empty, and whitespace-only input; a lone sign with no digits; leading/trailing whitespace around valid digits; leading zeros; the exact Integer.MIN_VALUE/Integer.MAX_VALUE boundaries; one past each boundary (overflow and underflow); embedded non-digit characters; and malformed sign sequences. The implementation returns Optional<Integer> rather than throwing, so a caller who does not want exception-based control flow for routine "bad input" cases gets a value it can check instead.

Structured elaboration
Parsing digit-by-digit while checking for overflow before each multiply/add avoids needing BigInteger or a long accumulator: for each incoming digit, compare the current partial result against (Integer.MAX_VALUE - digit) / 10 (positive branch) or (Integer.MIN_VALUE + digit) / 10 (negative branch) before combining it in. Accumulating as a negative number when the sign is negative (rather than accumulating positive and negating at the end) is what lets the parser correctly represent Integer.MIN_VALUE, since -Integer.MIN_VALUE overflows int on its own (the positive magnitude 2147483648 doesn't fit in a 32-bit signed int).

Return-value design: Optional.empty() for anything invalid keeps the API total (it always returns something of the declared type, never throws for "just bad input") and forces the caller to handle absence at the type level. The commented-out parseIntOrThrow variant shows the alternative for call sites that prefer exception-based flow, typically throwing NumberFormatException (matching the exception Java's own Integer.parseInt throws, so the custom parser stays consistent with the standard library's convention) instead of returning Optional.empty(); both are valid, the API just needs to pick one and be consistent about it.

Worked example (executed)

public static Optional<Integer> safeParseInt(String s) {
 if (s == null) return Optional.empty();
 s = s.trim();
 if (s.isEmpty()) return Optional.empty();

 int i = 0, n = s.length();
 int sign = 1;
 char c = s.charAt(0);
 if (c == '+' || c == '-') {
 sign = (c == '-') ? -1 : 1;
 i++;
 if (i == n) return Optional.empty(); // only a sign, no digits
 }

 int result = 0;
 final int INT_MAX = Integer.MAX_VALUE;
 final int INT_MIN = Integer.MIN_VALUE;
 while (i < n) {
 c = s.charAt(i++);
 if (c < '0' || c > '9') return Optional.empty();
 int digit = c - '0';
 if (sign == 1) {
 if (result > (INT_MAX - digit) / 10) return Optional.empty();
 result = result * 10 + digit;
 } else {
 if (result < (INT_MIN + digit) / 10) return Optional.empty();
 result = result * 10 - digit;
 }
 }
 return Optional.of(result);
}

The plain driver below calls this exact method against 17 pinned inputs (a JUnit runner was not available in this sandbox, so this is the reproducible equivalent):

public class Driver {
 static void check(String label, String input, String expected) {
 java.util.Optional<Integer> r = safeParseInt(input);
 String actual = r.isPresent() ? "Optional[" + r.get() + "]" : "Optional.empty";
 System.out.println((actual.equals(expected) ? "PASS " : "FAIL ") + label + ": safeParseInt(" + (input == null ? "null" : "\\"" + input + "\\"") + ") = " + actual);
 }
 public static void main(String[] args) {
 check("null input", null, "Optional.empty");
 check("empty string", "", "Optional.empty");
 check("whitespace only", " ", "Optional.empty");
 check("lone plus", "+", "Optional.empty");
 check("lone minus", "-", "Optional.empty");
 check("plain digits", "123", "Optional[123]");
 check("leading plus", "+123", "Optional[123]");
 check("leading minus", "-123", "Optional[-123]");
 check("leading zeros", "0000123", "Optional[123]");
 check("INT_MAX exact", "2147483647", "Optional[2147483647]");
 check("INT_MIN exact", "-2147483648", "Optional[-2147483648]");
 check("INT_MAX + 1 overflow", "2147483648", "Optional.empty");
 check("INT_MIN - 1 underflow", "-2147483649", "Optional.empty");
 check("embedded non-digit", "12a34", "Optional.empty");
 check("surrounding whitespace", " -42 ", "Optional[-42]");
 check("malformed sign", "+-2", "Optional.empty");
 check("space between sign and digits", " + 1", "Optional.empty");
 }
}

Running this driver against the exact safeParseInt implementation above:

PASS null input: safeParseInt(null) = Optional.empty
PASS empty string: safeParseInt("") = Optional.empty
PASS whitespace only: safeParseInt(" ") = Optional.empty
PASS lone plus: safeParseInt("+") = Optional.empty
PASS lone minus: safeParseInt("-") = Optional.empty
PASS plain digits: safeParseInt("123") = Optional[123]
PASS leading plus: safeParseInt("+123") = Optional[123]
PASS leading minus: safeParseInt("-123") = Optional[-123]
PASS leading zeros: safeParseInt("0000123") = Optional[123]
PASS INT_MAX exact: safeParseInt("2147483647") = Optional[2147483647]
PASS INT_MIN exact: safeParseInt("-2147483648") = Optional[-2147483648]
PASS INT_MAX + 1 overflow: safeParseInt("2147483648") = Optional.empty
PASS INT_MIN - 1 underflow: safeParseInt("-2147483649") = Optional.empty
PASS embedded non-digit: safeParseInt("12a34") = Optional.empty
PASS surrounding whitespace: safeParseInt(" -42 ") = Optional[-42]
PASS malformed sign: safeParseInt("+-2") = Optional.empty
PASS space between sign and digits: safeParseInt(" + 1") = Optional.empty
ALL 17 CASES PASSED

The INT_MIN case is the one worth double-checking by hand: -2147483648 parses to sign=-1, accumulates negatively digit by digit, and lands exactly on Integer.MIN_VALUE without ever needing to negate a too-large positive magnitude.

Complexity and edge cases
safeParseInt is O(n) time and O(1) extra space in the length of the input string, it makes one left-to-right pass with no auxiliary structures. The edge cases are exactly the 17 pinned inputs verified above: null, empty, whitespace-only, a lone sign with no digits, leading zeros, both exact 32-bit boundaries, both one-past-boundary overflow/underflow cases, an embedded non-digit character, surrounding whitespace around otherwise-valid digits, and a malformed sign sequence.

Trade-offs & pitfalls
The most common bug in this exact problem is accumulating positively and negating only at the end, which silently breaks on Integer.MIN_VALUE (the negation itself overflows). A second common bug is checking overflow after the multiply/add instead of before, by which point the overflow has already happened and the check is comparing corrupted data. Using a long accumulator instead of digit-by-digit bound checks is a legitimate simpler alternative when the language guarantees a wider integer type is available and performance isn't a hard constraint, the question's "without BigInteger" constraint specifically rules out the arbitrary-precision route, not necessarily a long-based one, so it's worth naming both.