Apple Software Engineer (Entry Level) Interview Preparation Guide

isKnownUniquelyReferenced(_:) checks at runtime whether a given class instance is the sole strong reference to that instance. In Swift this is the canonical building block for safe copy‑on‑write (COW) of a reference‑type buffer that backs a value type (struct): before mutating the buffer, test uniqueness; if not unique, clone the buffer and mutate the new one so other owners see the original unchanged.

Example COW pattern:

final class Buffer {
  var storage: [Int]
  init(_ s: [Int]) { storage = s }
  func copy() -> Buffer { Buffer(storage) }
}

struct IntArray {
  private var box: Buffer
  init(_ s: [Int]) { box = Buffer(s) }

  mutating func append(_ x: Int) {
    if !isKnownUniquelyReferenced(&box) {
      box = box.copy() // ensure uniqueness before in-place mutation
    }
    box.storage.append(x)
  }
}

Race conditions: isKnownUniquelyReferenced reads the reference count and can report “unique” while another thread concurrently retains the same instance. If you rely on that result without synchronization, two threads might both observe uniqueness and both mutate the same underlying Buffer — breaking logical isolation and causing data races or memory-safety violations.

Mitigations:

• Locks: Surround the uniqueness check + possible copy + mutation with a mutex. Simple and safe; introduces blocking and potential contention.
  • Acquire lock
  • if not unique { copy }
  • perform mutation
  • release lock
• Actor isolation / serial queues: In Swift concurrency, confine the value or its mutating operations to a single actor or serial DispatchQueue. The actor ensures only one concurrent mutating task runs, eliminating race with no manual locks.
• Atomic reference management: Use atomic primitives for reference counting or an atomic “copy-on-write needed” flag (e.g., swift-atomics or UnsafeAtomic) to make the check-and-copy an atomic compare-and-swap sequence. Implementing correct lock‑free COW is hard and error-prone; it requires ensuring atomicity across the check-and-swap and careful memory ordering.
• Design alternatives: Prefer immutable shared instances (no mutation), or make copies eagerly when passing across threads.

Recommendation: For most code, prefer actor isolation or a lightweight lock around the COW path. Reserve atomic, lock‑free implementations for performance‑critical hotspots and validate thoroughly (stress tests, Thread Sanitizer).

I’d turn vague feedback like “this feels slow” into something measurable right away. First I’d ask whether the issue is perceived latency, actual render time, or too many interaction steps. Then I’d pick one quick metric and one testable change.

For example, if a dropdown feels sluggish, I might measure:

• Time to first visible response
• Number of clicks or keystrokes to complete the task
• Re-render count in the component

A quick change could be adding a loading skeleton, debouncing input, or reducing unnecessary re-renders with memoization. I’d say, “Let’s test whether the user feels progress within 100–200 ms and whether we can reduce the interaction from three steps to two.” That shows I can translate qualitative feedback into a concrete experiment.

Direct answer

Reach for depth-first search (DFS) when the answer is built from subtrees (heights, sums, validity, paths from the root, copies) or when the tree is shallow (DFS only remembers one root-to-node path, so a short tree needs little memory however wide it is); reach for level-order (breadth-first search, BFS) when the answer depends on distance from the root, such as the shallowest leaf or one result per level. The DFS order is chosen by when you need the parent relative to its children: preorder to use the parent first, inorder for sorted order in a binary search tree (BST), postorder to use the children first. On memory: DFS needs O(h) (h = height), BFS needs O(w) (w = widest level, the largest number of nodes on any single level). On a balanced tree that favours DFS strongly; on a skewed tree it depends on how the tree is skewed.

Height convention: number of nodes on the longest root-to-leaf path (empty tree = 0).

Choosing the DFS order

• Preorder (node, left, right): parent before children. Use it to copy or serialize a tree, to pass information down from the root (the current path, a running sum such as the total of values from the root to the current node, or the depth), and to print a directory-style outline.
• Inorder (left, node, right): on a BST this visits keys in ascending order. Use it for k-th smallest, validating a BST (each key must exceed the previous one), range queries and converting a BST to a sorted list.
• Postorder (left, right, node): children before the parent. Use it whenever a node's answer needs its children's answers: height, diameter (the longest path between any two nodes), subtree sum, balance check (does every node have left and right heights within 1 of each other), evaluating an expression tree (a tree whose leaves are numbers and whose inner nodes are operators, such as * with children + and 4 for (2 + 3) * 4: both sides must be computed before the operator), and freeing a tree safely (children are released before their parent).

When BFS is the better tool

• The question is about the shallowest or nearest thing: minimum depth, the nearest leaf, or the first node satisfying a condition. BFS stops as soon as it reaches that level; a plain DFS has to look at every branch before it can be sure (a DFS that abandons any branch already deeper than the best leaf found so far does less work, but only after it has found a shallow leaf).
• The output is organised by level: level-order rows, zigzag, right-side view, level averages.

The program below shows the shallowest-leaf case on a tree whose left side is a 500-node chain and whose right child is a leaf. BFS finds the nearest leaf at depth 2 after visiting 3 nodes. A plain DFS that has to rule out the other branch visits 502 nodes to report the same depth.

Memory on balanced versus skewed trees

BFS keeps a frontier: the nodes discovered but not yet processed, which is the unfinished part of the current level plus the children already discovered for the next one, so at most two neighbouring levels (still O(w), where w is the widest level). DFS keeps a path: either recursion frames (always about h) or an explicit stack (whose size depends on the order and the implementation). Measured peaks, counted from the code (an explicit stack counts entries, recursion frames equal the height):

from collections import deque

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

def complete_tree(levels):
    """Perfect tree with `levels` levels: 2**levels - 1 nodes (built level by level, no recursion)."""
    root = Node(0)
    level, count = [root], 1
    for _ in range(levels - 1):
        nxt = []
        for n in level:
            n.left, n.right = Node(count), Node(count + 1)
            count += 2
            nxt += [n.left, n.right]
        level = nxt
    return root

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

def bfs_peak(root):
    """Largest number of nodes waiting in the queue."""
    queue, peak = deque([root]), 1
    while queue:
        node = queue.popleft()
        for c in (node.left, node.right):
            if c:
                queue.append(c)
        peak = max(peak, len(queue))
    return peak

def dfs_peak(root):
    """Largest number of nodes waiting on an explicit preorder stack."""
    stack, peak = [root], 1
    while stack:
        node = stack.pop()
        for c in (node.right, node.left):
            if c:
                stack.append(c)
        peak = max(peak, len(stack))
    return peak

def inorder_peak(root):
    """Largest explicit-stack size during an iterative inorder walk."""
    stack, cur, peak = [], root, 0
    while cur or stack:
        while cur:
            stack.append(cur)
            cur = cur.left
        peak = max(peak, len(stack))
        cur = stack.pop().right
    return peak

def caterpillar_tree(spine):
    """A left spine of `spine` nodes where every spine node also has a leaf on its right."""
    root = cur = Node(0)
    for v in range(1, spine):
        cur.right = Node(-v)
        cur.left = Node(v)
        cur = cur.left
    return root

def height(root):                      # nodes on the longest path = recursion frames for DFS
    level, h = [root], 0
    while level:
        h += 1
        level = [c for n in level for c in (n.left, n.right) if c]
    return h

def count(root):
    stack, n = [root], 0
    while stack:
        node = stack.pop()
        n += 1
        stack += [c for c in (node.left, node.right) if c]
    return n

print(f"{'shape':20}{'nodes':>6}{'height':>7}{'BFS queue':>10}{'preorder stack':>15}{'inorder stack':>14}")
for name, t in [("perfect, 10 levels", complete_tree(10)),
                ("left chain", chain_tree(1023)),
                ("caterpillar", caterpillar_tree(512))]:
    print(f"{name:20}{count(t):>6}{height(t):>7}{bfs_peak(t):>10}{dfs_peak(t):>15}{inorder_peak(t):>14}")

# Nearest leaf: root with a 500-node left chain and a leaf on the right
lopsided = Node(0, chain_tree(500), Node(1))

def min_depth_bfs(root):
    visited, queue = 0, deque([(root, 1)])
    while queue:
        node, d = queue.popleft()
        visited += 1
        if not node.left and not node.right:
            return d, visited
        for c in (node.left, node.right):
            if c:
                queue.append((c, d + 1))

def min_depth_dfs(root):
    visited, best, stack = 0, None, [(root, 1)]
    while stack:
        node, d = stack.pop()
        visited += 1
        if not node.left and not node.right:
            best = d if best is None else min(best, d)
        for c in (node.right, node.left):
            if c:
                stack.append((c, d + 1))
    return best, visited

print("nearest leaf, BFS (depth, nodes visited):", min_depth_bfs(lopsided))
print("nearest leaf, DFS (depth, nodes visited):", min_depth_dfs(lopsided))

Output:

shape                nodes height BFS queue preorder stack inorder stack
perfect, 10 levels    1023     10       512             10            10
left chain            1023   1023         1              1          1023
caterpillar           1023    512         3            512           512
nearest leaf, BFS (depth, nodes visited): (2, 3)
nearest leaf, DFS (depth, nodes visited): (2, 502)

Reading the table, with n = 1023 for each shape:

• Perfect tree (balanced): DFS needs about h = 10 entries; BFS queues up to 512, the width of the last level (about n / 2). DFS uses roughly 50 times less. This is the usual reason to prefer DFS.
• Left chain (skewed, one child each): the tree is 1023 levels deep. Recursive DFS needs 1023 frames (and fails near 1000 in CPython). An iterative inorder walk holds the whole left spine: 1023. A preorder walk with an explicit stack holds 1 entry, because there is never a pending right sibling. BFS holds 1. So here BFS is the lean one.
• Caterpillar (a left spine of 512 nodes, each with a leaf on the right): height 512; preorder and inorder stacks peak at 512, BFS peaks at 3. Again BFS wins.

The same two shapes at 4 and 5 nodes

The two skewed shapes are small enough to follow by hand. The program prints the explicit stack after every visit of an iterative preorder and an iterative inorder walk on a left chain of 4 nodes (1 -> 2 -> 3 -> 4, each the left child of the one before) and on a caterpillar with a 3-node spine (a left spine, with a leaf hanging on the right of each spine node except the last).

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


def preorder_steps(root):
    """Iterative preorder; prints the explicit stack after each node is visited."""
    stack, peak = [root], 1
    while stack:
        node = stack.pop()
        for c in (node.right, node.left):
            if c:
                stack.append(c)
        peak = max(peak, len(stack))
        print(f"  visit {node.val:>2}   stack = {[n.val for n in stack]}")
    return peak


def inorder_steps(root):
    """Iterative inorder; prints the explicit stack after each pop."""
    stack, cur, peak = [], root, 0
    while cur or stack:
        while cur:
            stack.append(cur)
            cur = cur.left
        peak = max(peak, len(stack))
        cur = stack.pop()
        print(f"  visit {cur.val:>2}   stack = {[n.val for n in stack]}   (peak so far {peak})")
        cur = cur.right
    return peak


chain = Node(1, Node(2, Node(3, Node(4))))
caterpillar = Node(0, Node(1, Node(2), Node(-2)), Node(-1))
for name, tree in (("left chain of 4", chain), ("caterpillar with a 3-node spine", caterpillar)):
    print(name)
    print(" preorder")
    p = preorder_steps(tree)
    print(" inorder")
    i = inorder_steps(tree)
    print(f" largest stack: preorder {p}, inorder {i}")

It prints:

left chain of 4
 preorder
  visit  1   stack = [2]
  visit  2   stack = [3]
  visit  3   stack = [4]
  visit  4   stack = []
 inorder
  visit  4   stack = [1, 2, 3]   (peak so far 4)
  visit  3   stack = [1, 2]   (peak so far 4)
  visit  2   stack = [1]   (peak so far 4)
  visit  1   stack = []   (peak so far 4)
 largest stack: preorder 1, inorder 4
caterpillar with a 3-node spine
 preorder
  visit  0   stack = [-1, 1]
  visit  1   stack = [-1, -2, 2]
  visit  2   stack = [-1, -2]
  visit -2   stack = [-1]
  visit -1   stack = []
 inorder
  visit  2   stack = [0, 1]   (peak so far 3)
  visit  1   stack = [0]   (peak so far 3)
  visit -2   stack = [0]   (peak so far 3)
  visit  0   stack = []   (peak so far 3)
  visit -1   stack = []   (peak so far 3)
 largest stack: preorder 3, inorder 3

On the chain, preorder pops a node and pushes its only child, so the stack never holds more than 1 entry. Inorder must go all the way down the left side before it can visit anything: it pushes 1, 2, 3 and 4 and only then visits 4, so the stack reaches 4, the full height. On the caterpillar, preorder pushes the right leaf (-1, then -2) of each spine node before descending, and those leaves wait on the stack until the walk comes back; they pile up to the length of the spine, which at 512 spine nodes is the 512 in the table. BFS holds about one level at a time. The caterpillar has at most 2 nodes per level (a spine node and its leaf), and the queue peaks at 3 because it briefly holds the rest of one level plus the children already queued for the next. That is the 3 in the table.

So "DFS is O(h), BFS is O(w)" is the whole rule, and which one is smaller depends on shape. Deep and thin: BFS is smaller. Wide and shallow: DFS is smaller. A bushy tree of small height favours DFS when DFS keeps one position per level, as recursion does. With many children per node, an explicit stack that pushes all of a node's children at once can hold as many entries as BFS: on a root with 1000 leaf children both hold 1000, while a DFS that keeps one position per level holds 2. A long, narrow tree (list-like) favours BFS, as the chain and caterpillar rows show.

Complexity

All four traversals take O(n) time. Space: DFS O(h) for recursion frames or the explicit stack (worst case O(n) when h = n); BFS O(w) for the queue (worst case about n / 2 for a perfect tree). In Python, recursive DFS raises RecursionError beyond about 1000 levels, so for untrusted or possibly deep trees use an explicit stack.

Common mistakes

• Saying "BFS uses more memory than DFS" without conditions: the chain and caterpillar rows above show it is shape-dependent.
• Using a Python list with pop(0) as a BFS queue: O(n) per pop; use collections.deque.
• Picking inorder for a problem on a non-BST tree and expecting sorted output.
• Using a plain DFS for nearest-leaf and forgetting that, without a bound from the best leaf found so far, it must visit every branch to confirm minimality.

Running the code

Save the first listing (the measurements table and the nearest-leaf comparison) as dfs_bfs_demo.py and the second listing (the step-by-step stacks on the 4-node chain and the 3-node-spine caterpillar) as stack_trace_demo.py. Each is a complete program:

python3 dfs_bfs_demo.py
python3 stack_trace_demo.py

Standard library only (Python 3.12).

Direct answer
Read for the conclusion the source material is actually building toward, state that conclusion as the first sentence, then compress the two or three things a reader needs to trust it: the biggest risk or driver, and what you want them to do next.

Structured elaboration

1. Find the real headline first. Before writing a single summary sentence, identify what decision or fact the full document is ultimately arguing for. If you cannot state it in one sentence, you have not finished reading it.
2. Pick the two or three supporting points that matter most, not the ones that are easiest to quote. A common failure is summarizing the document's structure (section 1 covers X, section 2 covers Y) instead of its substance.
3. State the risk or the catch. A summary that hides the caveat the full report surfaces on page 8 is not a summary, it is spin. Include the single biggest risk or open question in the same paragraph as the good news.
4. End with the ask. What do you want the reader to approve, decide, or do. If there is no ask, say so explicitly ("for awareness only, no action needed") so the reader doesn't hunt for one.
5. Cut ruthlessly for length last. Once the four pieces above are on the page, tighten wording, not content: remove hedging phrases ("we believe that," "it seems"), redundant qualifiers, and any sentence that restates something already said.

Worked example
Source material (excerpt of a longer report): a 1,400-word analysis of a marketing campaign covering channel-by-channel spend, a methodology section, a table of conversion rates by week, a note that attribution data for the last two weeks is incomplete, and a recommendation to shift 20% of budget from display to search.

Executive summary (under 80 words): "Recommendation: shift 20% of display budget to search next quarter. Search converts at roughly double the rate of display in this campaign, and the gap has held for six of the eight weeks measured. Caveat: the final two weeks of data are incomplete due to a tracking gap, so we're treating the 2x figure as directional rather than final. Full channel breakdown and methodology in the appendix."

This keeps the conclusion, the one supporting number, the caveat, and the ask, and drops the methodology walkthrough and the week-by-week table, which belong in an appendix a reader can choose to open.

Trade-offs and pitfalls

• The most common failure mode is summarizing evenly across sections instead of unevenly toward the conclusion; a good summary is lopsided on purpose.
• Compressing away a real caveat to make the summary look cleaner is a trust problem, not an editing win. It's the fastest way to have your future summaries doubted.
• For a highly technical audience, "top risk" might be a methodology limitation; for an executive audience it might be a cost or timeline risk. The compression target changes with audience even when the underlying facts don't.

Direct answer

In short: instead of comparing keys, sort the numbers one byte at a time, lowest byte first, using a cheap counting step each time. LSD (least significant digit first) radix sort sorts integers by splitting each key into fixed-size digits, here 8-bit bytes, and doing one stable counting sort per byte, starting from the lowest byte and ending at the highest. A 32-bit key has four bytes, so four passes. Each pass touches every element a constant number of times, so the total is about 4 * (n + 256) steps, which is O(n) because the word size is fixed. Each pass must be stable (equal digits keep their previous order) because the order produced by the lower bytes is the tie-break for the higher byte. Signed keys need the sign bit handled (add 2^31, which flips the top bit), and 64-bit keys need eight passes instead of four.

The idea in plain words

Think of sorting a pile of numbered cards by the last digit, then by the tens digit, then by the hundreds digit, each time dealing the cards into ten piles and picking them back up in order. After the last deal the pile is fully sorted. This works only if, within one pile of the tens-digit deal, the cards stay in the order the previous deal left them. That "equal keys stay in their incoming order" property is called stability.

Here a "digit" is a byte (256 possible values), so the piles are 256 buckets. Terms: counting sort is a sort for small integer keys that counts how many items fall in each bucket, turns the counts into starting positions, and drops each item into its slot. Fixed word size means every key has the same number of bits (32 or 64), so the number of passes does not grow with n.

Pulling one byte out of a number

A byte is 8 bits, so it holds one of 256 values (0 to 255). Writing a key in hexadecimal (base 16) makes bytes visible: one hex character stands for 4 bits, so two hex characters are exactly one byte. That is why the trace below prints keys as 8 hex characters: 70000 is 00011170, whose four bytes are 00, 01, 11, 70 from highest to lowest.

The expression (key >> shift) & MASK extracts one of those bytes in two steps. key >> shift is a right shift: it slides every bit shift places to the right and drops the bits that fall off the end, which is the same as integer division by 2^shift. & MASK is a bitwise AND with MASK = 255 (binary 11111111): it keeps the low 8 bits and zeroes everything above them. Together they read the byte that starts shift bits up. In the code, 1 << RADIX_BITS is a left shift that computes 2^8 = 256, the number of buckets, and MASK = BUCKETS - 1 is 255. This small program prints the steps for 70000 and shows the signed fix on three keys:

key = 70000
print("70000 in binary:", format(key, "032b"))
print("70000 in hex   :", format(key, "08x"), "(two hex characters = one byte = 8 bits)")
for shift in (0, 8, 16, 24):
    byte = (key >> shift) & 255
    print(f"shift {shift:2d}: key >> {shift:2d} = {key >> shift:5d}; & 255 keeps the low 8 bits = {byte:3d} (hex {byte:02x})")

BIAS = 2**31
for x in (-3, 0, 2**31 - 1):
    raw = x & 0xFFFFFFFF            # the 32-bit two's complement pattern of x
    print(f"x = {x:11d}: raw bits {raw:032b}; after adding 2**31: {x + BIAS:10d} = {x + BIAS:032b}")

Output (python:3.12):

70000 in binary: 00000000000000010001000101110000
70000 in hex   : 00011170 (two hex characters = one byte = 8 bits)
shift  0: key >>  0 = 70000; & 255 keeps the low 8 bits = 112 (hex 70)
shift  8: key >>  8 =   273; & 255 keeps the low 8 bits =  17 (hex 11)
shift 16: key >> 16 =     1; & 255 keeps the low 8 bits =   1 (hex 01)
shift 24: key >> 24 =     0; & 255 keeps the low 8 bits =   0 (hex 00)
x =          -3: raw bits 11111111111111111111111111111101; after adding 2**31: 2147483645 = 01111111111111111111111111111101
x =           0: raw bits 00000000000000000000000000000000; after adding 2**31: 2147483648 = 10000000000000000000000000000000
x =  2147483647: raw bits 01111111111111111111111111111111; after adding 2**31: 4294967295 = 11111111111111111111111111111111

Reading it: shift 0 gives the low byte 112 (hex 70), shift 8 gives 17 (hex 11), shift 16 gives 1 and shift 24 gives 0, which are the four bytes of 00011170 from lowest to highest. For signed keys, -3 in 32-bit two's complement (the usual machine form of negative numbers) is 111...101, a pattern with the top bit set, so as raw unsigned bits it would sort after every non-negative number. Adding 2^31 turns the top bit off for negatives and on for non-negatives: -3 becomes 2147483645 and 0 becomes 2147483648, so -3 sorts before 0, and 2^31 - 1 becomes 4294967295, the largest 32-bit value. x ^ 0x80000000 (bitwise exclusive-or with the top bit) gives the same result as adding 2^31 when it is applied to the 32-bit pattern, for example (x & 0xFFFFFFFF) ^ 0x80000000. Applied to a negative Python integer itself it stays negative (-3 ^ 0x80000000 is -2147483651), which is why the code adds 2**31 instead.

Brute force and why it is not enough

A comparison sort (merge sort, sorted) needs on the order of n log2 n comparisons, because it learns about the order only by comparing pairs of keys. Radix sort reads the key's bits directly and never compares two keys, so that bound does not apply to it. The price is that it works only for keys that can be viewed as fixed-width digit strings (integers, fixed-length strings, floats after a bit transformation).

Approach

1. Convert each key to an unsigned integer (for signed keys, add 2^(bits-1)).
2. For shift = 0, 8, 16, 24 (low byte first): count how many keys have each byte value, turn the counts into start positions with a running sum (each digit's start is the total of all smaller digits' counts, so it is the first output slot reserved for that digit), then scan the input from front to back and place each item at start[digit], incrementing that start position.
3. Scanning front to back is what makes the pass stable: two items with the same byte land in their slots in the order they were read.
4. After the top byte the list is sorted.

Code

radix_sort carries items (so records can be sorted by a key function) and raises an error for a key that does not fit the stated width. The driver prints the array after every pass (the trace), checks stability with tagged equal keys, shows what a back-to-front scan does, and compares against sorted() on random cases.

import random

RADIX_BITS = 8
BUCKETS = 1 << RADIX_BITS          # 256 possible digit values
MASK = BUCKETS - 1


def counting_pass(pairs, shift, backwards=False):
    """One stable counting-sort pass on the byte at `shift`. pairs = [(key, item)]."""
    count = [0] * BUCKETS
    for key, _ in pairs:
        count[(key >> shift) & MASK] += 1
    start, running = [0] * BUCKETS, 0
    for digit in range(BUCKETS):          # start[d] = first output slot for digit d
        start[digit] = running
        running += count[digit]
    out = [None] * len(pairs)
    # Scanning front to back keeps equal digits in their input order (stable).
    for key, item in (reversed(pairs) if backwards else pairs):
        digit = (key >> shift) & MASK
        out[start[digit]] = (key, item)
        start[digit] += 1
    return out


def radix_sort(items, key=lambda x: x, bits=32, signed=False, trace=False):
    """Stable LSD radix sort of `items` by an integer key that fits in `bits` bits."""
    bias = 1 << (bits - 1) if signed else 0       # shifts signed keys into the unsigned range, negatives first
    low, high = -bias, (1 << bits) - bias
    pairs = []
    for item in items:
        k = key(item)
        if not low <= k < high:
            raise ValueError(f"key {k} does not fit in {bits} bits (signed={signed})")
        pairs.append((k + bias, item))
    for shift in range(0, bits, RADIX_BITS):      # least significant byte first
        pairs = counting_pass(pairs, shift)
        if trace:
            print(f"after byte {shift // RADIX_BITS}:", [f"{k:08x}" for k, _ in pairs])
    return [item for _, item in pairs]


if __name__ == "__main__":
    data = [170, 45, 75, 90, 802, 24, 2, 66, 70000, 65536, 300]
    print("input      :", [f"{k:08x}" for k in data])
    result = radix_sort(data, trace=True)
    print("sorted     :", result)

    # Stability: records with equal keys must keep their input order.
    records = [(5, "a"), (3, "b"), (5, "c"), (3, "d"), (5, "e")]
    print("stable     :", radix_sort(records, key=lambda r: r[0], bits=8))
    for shift_backwards in (False, True):          # two passes on 16-bit keys 0x0102, 0x0101
        p = counting_pass([(0x0102, "x"), (0x0101, "y")], 0)
        p = counting_pass(p, 8, backwards=shift_backwards)
        print("high pass scans", "back to front" if shift_backwards else "front to back", "->", [f"{k:04x}" for k, _ in p])

    # Signed 32-bit and 64-bit keys.
    print("signed     :", radix_sort([5, -3, 0, -2147483648, 2147483647, -1], signed=True))
    big = [2**64 - 1, 0, 2**40, 2**63, 7]
    print("64-bit     :", radix_sort(big, bits=64))
    try:
        radix_sort([2**32], bits=32)
    except ValueError as err:
        print("rejected   :", err)

    # Check against sorted() on random inputs, including duplicates and tagged equal keys.
    rng = random.Random(41)
    for _ in range(300):
        n = rng.randint(0, 40)
        recs = [(rng.randint(-50, 50), i) for i in range(n)]
        assert radix_sort(recs, key=lambda r: r[0], bits=32, signed=True) == sorted(recs, key=lambda r: r[0])
        recs64 = [(rng.getrandbits(64), i) for i in range(n)]
        assert radix_sort(recs64, key=lambda r: r[0], bits=64) == sorted(recs64, key=lambda r: r[0])
    print("300 random cases match sorted() including tie order")

    # Cost model: passes d = ceil(bits / r), work per pass about n + 2^r.
    for n in (1_000, 1_000_000):
        for r in (4, 8, 16):
            passes = -(-32 // r)
            print(f"n={n:>9,} r={r:2d}: passes={passes}, total work ~ passes * (n + 2^r) = {passes * (n + 2**r):,}")

Output (python:3.12):

input      : ['000000aa', '0000002d', '0000004b', '0000005a', '00000322', '00000018', '00000002', '00000042', '00011170', '00010000', '0000012c']
after byte 0: ['00010000', '00000002', '00000018', '00000322', '0000012c', '0000002d', '00000042', '0000004b', '0000005a', '00011170', '000000aa']
after byte 1: ['00010000', '00000002', '00000018', '0000002d', '00000042', '0000004b', '0000005a', '000000aa', '0000012c', '00000322', '00011170']
after byte 2: ['00000002', '00000018', '0000002d', '00000042', '0000004b', '0000005a', '000000aa', '0000012c', '00000322', '00010000', '00011170']
after byte 3: ['00000002', '00000018', '0000002d', '00000042', '0000004b', '0000005a', '000000aa', '0000012c', '00000322', '00010000', '00011170']
sorted     : [2, 24, 45, 66, 75, 90, 170, 300, 802, 65536, 70000]
stable     : [(3, 'b'), (3, 'd'), (5, 'a'), (5, 'c'), (5, 'e')]
high pass scans front to back -> ['0101', '0102']
high pass scans back to front -> ['0102', '0101']
signed     : [-2147483648, -3, -1, 0, 5, 2147483647]
64-bit     : [0, 7, 1099511627776, 9223372036854775808, 18446744073709551615]
rejected   : key 4294967296 does not fit in 32 bits (signed=False)
300 random cases match sorted() including tie order
n=    1,000 r= 4: passes=8, total work ~ passes * (n + 2^r) = 8,128
n=    1,000 r= 8: passes=4, total work ~ passes * (n + 2^r) = 5,024
n=    1,000 r=16: passes=2, total work ~ passes * (n + 2^r) = 133,072
n=1,000,000 r= 4: passes=8, total work ~ passes * (n + 2^r) = 8,000,128
n=1,000,000 r= 8: passes=4, total work ~ passes * (n + 2^r) = 4,001,024
n=1,000,000 r=16: passes=2, total work ~ passes * (n + 2^r) = 2,131,072

Worked trace

The printed passes read as follows.

• After byte 0 the list is ordered by the lowest byte only: 00010000 (low byte 00), 00000002 (02), 00000018 (18), 00000322 (22), and so on up to 000000aa (aa).
• After byte 1 the list is ordered by the lowest two bytes. Ties on byte 1 keep the byte-0 order, which is where stability does its work: 00010000 stays ahead of 00000002 because both have byte 1 equal to 00 and the previous pass had already put it first.
• After byte 2, 00010000 and 00011170 (byte 2 equal to 01) move behind every key below 65536.
• Byte 3 is 00 for every key, so that pass changes nothing, and the final list is [2, 24, 45, 66, 75, 90, 170, 300, 802, 65536, 70000].

Why each pass must be stable

Pass j orders the keys by byte j alone. Two keys with the same byte j look equal to pass j. If the pass shuffled them, the work of passes 0 to j-1, which ordered those two keys by their lower bytes, would be lost. The driver shows it on two 16-bit keys, 0x0102 and 0x0101, which share the high byte 01: after the low-byte pass they are in the right order. A high-byte pass that scans front to back keeps that order (['0101', '0102']), while one that scans back to front prints ['0102', '0101'], which is wrong.

Why the total is O(n) for a fixed word size, and choosing the digit size

One pass costs n steps to count, 2^r steps for the prefix sum, and n steps to place: about n + 2^r up to a constant factor. With b-bit keys and r-bit digits there are d = ceil(b / r) passes, so the total is d * (n + 2^r). For b = 32 and r = 8, d = 4 and the total is 4n + 1,024, which is O(n) because d and 2^r are constants. The factor d is hidden inside that O(n), and the digit size trades passes against table size:

The last six printed lines evaluate the model. At n = 1,000 the 16-bit choice costs 133,072 modelled steps against 5,024 for 8 bits, because the 65,536-entry table is rebuilt every pass. At n = 1,000,000 it halves the passes and costs 2,131,072 against 4,001,024. The rule from d * (n + 2^r): pick r near log2 of n, capped by what fits comfortably in fast memory. These are modelled step counts from the formula, not measurements.

Signed integers, 64-bit keys, and limited memory

• Signed 32-bit. In two's complement (the standard way machines store negative integers, shown on -3 above), a negative number has its top bit set, so as raw unsigned patterns every negative key sorts after every non-negative one. Adding 2^31 to each key (identical to flipping the top bit, x ^ 0x80000000 in C on a uint32_t, an unsigned 32-bit integer type) maps -2^31 to 0 and 2^31 - 1 to 2^32 - 1, in numeric order. The code does this with signed=True, and the output shows -2147483648 first. It needs no extra memory and still takes four passes. A second option is to sort as unsigned and then rotate the output so the block of negatives goes first.
• 64-bit. The same algorithm with bits=64: eight passes with 8-bit digits, or four with 16-bit digits. The output shows 18446744073709551615 last. In C use uint64_t and keep every shift below 64, because shifting by the type's width or more is undefined behaviour (the C standard places no requirement on what the program then does).
• Limited memory. LSD needs a second buffer of n items (two arrays swapped after each pass). If even that is too much, an in-place MSD (most significant digit first, so the top byte is sorted first and each bucket is then sorted by the next byte) variant such as American flag sort permutes items into their buckets directly and recurses per bucket. It is not stable, which matters only when records with equal keys carry other data. A pass can also be skipped when one bucket holds all n keys, for example the top byte in the trace.

Interviews typically stop at the stable four-pass version and the sign-bit fix; lower-memory MSD variants and 64-bit details in C are deeper material that rarely comes up.

Complexity

Time O(d * (n + 2^r)), here O(n) for 32-bit keys. Extra space O(n + 2^r): the shipped code holds the old and new pair lists during a pass plus a 256-entry count table. It is not in place.

Edge cases and common mistakes

• Empty and one-element lists pass through every loop with nothing to do (the random check includes n = 0).
• Duplicates are fine and keep their input order, checked with tagged keys against sorted().
• A key outside the width is rejected (2**32 with bits=32 raised the error shown).
• Mistake: scanning the input backwards while using start positions, which reverses ties.
• Mistake: running the passes from the most significant byte first with a stable pass; the low byte then decides last and the order is wrong.
• Mistake: forgetting the sign bit, which puts negatives after positives.
• Mistake: a digit size whose count table is bigger than n, so the table costs more than the data.

Running the code

python:3.12, standard library only
save the code above as radix_sort.py
python radix_sort.py

The idea

Every one of the four operations is a one-bit mask plus one operator. Build the mask with 1u << k, which is a word that has a 1 only at position k (counted from the least significant bit, bit 0). Then:

A small worked example makes the four rows concrete. Take an 8-bit value v = 00101100 (0x2C, decimal 44) and work on bit 4, then bit 3, then bit 5:

Each row changes only the bit named by the mask; every other bit passes through unchanged. The 32-bit versions below do exactly the same thing with a wider word.

For several bits at once, use a multi-bit mask: v ^ 0xF flips four bits in one operation, and (v & ~mask) | (value & mask) replaces a whole field.

Out-of-range k

For a 32-bit word the valid values of k are 0 to 31. 1u << 32 is undefined behaviour in C (the standard places no requirement on what the program then does, so the compiler may produce any result, and -fsanitize=undefined reports it), so the check must happen before the shift, not after. The choice to make is what the function does when k is bad. The options are to silently mask k (k & 31, which quietly operates on the wrong bit), to assert (good while developing, absent in release builds), or to report an error. For a library function the safe choice is to report it: mutators return false and leave the value unchanged, and the test returns false. Declaring k unsigned also makes a negative argument wrap to a huge value that the same check rejects. If k is a compile-time constant, a static assertion (_Static_assert, a check the compiler performs while compiling) is better than a runtime check because the mistake cannot ship.

Code

#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>

#define WORD_BITS 32u

/* k is unsigned, so a negative argument becomes a huge value and is rejected too. */
static bool bit_test(uint32_t v, unsigned k) {
    return k < WORD_BITS && ((v >> k) & 1u) != 0;
}
static bool bit_set(uint32_t *v, unsigned k) {
    if (k >= WORD_BITS) return false;
    *v |= 1u << k;
    return true;
}
static bool bit_clear(uint32_t *v, unsigned k) {
    if (k >= WORD_BITS) return false;
    *v &= ~(1u << k);
    return true;
}
static bool bit_toggle(uint32_t *v, unsigned k) {
    if (k >= WORD_BITS) return false;
    *v ^= 1u << k;
    return true;
}
/* Several bits at once: flip every bit that is 1 in mask. */
static void bits_toggle_mask(uint32_t *v, uint32_t mask) { *v ^= mask; }

/* Replace a multi-bit field: clear it with the mask, then OR in the new value. */
static void field_write(uint32_t *v, uint32_t mask, uint32_t value) {
    *v = (*v & ~mask) | (value & mask);
}

/* Memory-mapped register where writing 1 to a bit clears it (write-one-to-clear),
   simulated here by a plain variable. */
static uint32_t sim_status = 0;
static void sim_write_w1c(uint32_t written) { sim_status &= ~written; }

int main(void) {
    uint32_t v = 0;
    bit_set(&v, 0);  bit_set(&v, 31);
    printf("set 0 and 31 : 0x%08x\n", v);
    printf("test 31, 30  : %d %d\n", bit_test(v, 31), bit_test(v, 30));
    bit_toggle(&v, 5);
    printf("toggle 5     : 0x%08x\n", v);
    bit_clear(&v, 31);
    printf("clear 31     : 0x%08x\n", v);
    bits_toggle_mask(&v, 0x0000000Fu);
    printf("toggle 0xF   : 0x%08x\n", v);
    uint32_t f = 0xFFFFFFFFu;
    field_write(&f, 0x00F0u, 0x5u << 4);
    printf("field 7:4 = 5: 0x%08x\n", f);
    bool ok = bit_set(&v, 32);
    printf("k=32 set ok? : %d, value still 0x%08x\n", ok, v);
    printf("k=-1 test    : %d\n", bit_test(v, (unsigned)-1));

    /* Write-one-to-clear: acknowledge bit 1 while bit 2 is also pending. */
    sim_status = 0x6u;                       /* bits 1 and 2 pending */
    uint32_t tmp = sim_status;               /* read-modify-write (wrong here) */
    tmp &= ~(1u << 1);
    sim_write_w1c(tmp);                      /* writes 1 to bit 2, clearing it */
    printf("RMW ack bit 1  -> status 0x%x (bit 1 not acknowledged, bit 2 cleared unseen)\n", sim_status);

    sim_status = 0x6u;
    sim_write_w1c(1u << 1);                  /* write only the bit to acknowledge */
    printf("direct ack bit 1 -> status 0x%x (bit 2 kept)\n", sim_status);
    return 0;
}

Output:

set 0 and 31 : 0x80000001
test 31, 30  : 1 0
toggle 5     : 0x80000021
clear 31     : 0x00000021
toggle 0xF   : 0x0000002e
field 7:4 = 5: 0xffffff5f
k=32 set ok? : 0, value still 0x0000002e
k=-1 test    : 0
RMW ack bit 1  -> status 0x2 (bit 1 not acknowledged, bit 2 cleared unseen)
direct ack bit 1 -> status 0x4 (bit 2 kept)

Reading the output

• Setting bits 0 and 31 gives 0x80000001. Test 31 is true and test 30 is false.
• Toggling bit 5 adds 0x20, giving 0x80000021. Clearing 31 leaves 0x00000021. Toggling mask 0xF flips four bits: bits 0 (was 1, now 0) and 1, 2, 3 (were 0, now 1), giving 0x2e.
• field_write with mask 0x00F0 and value 5 shifted into place turns 0xffffffff into 0xffffff5f: the four bits 7 to 4 become 0101, nothing else moves.
• k = 32 returns false and the value is unchanged. k = -1 converts to 4294967295 and is rejected.

If the value lives in a shared hardware status register

A hardware register is a location in memory-mapped I/O (MMIO): the address is wired to a peripheral, not to RAM. The same masks apply, but one fact drives everything that changes: the hardware, an interrupt handler or another processor can read and write that location at the same moment your code does. A read-modify-write is the sequence read the whole word, change one bit in a copy, write the whole word back. Every "set bit k", "clear bit k" and "toggle bit k" above is one of those, and that is what becomes unsafe. Three things follow.

1. volatile. Declare the pointer volatile uint32_t *. Without it the compiler may cache the value in a CPU register, merge two accesses into one or drop a read whose result is unused, all of which are wrong when reading the location itself has an effect.
2. Read-modify-write is not atomic. *reg |= mask is three steps: read, OR, write. If an interrupt service routine (ISR, a function the hardware runs when an event fires) or another bus master (any other device that can write the same register, such as a second CPU core or a DMA controller that copies data without the CPU) changes a different bit between the read and the write, the write puts back a stale value and that change is lost. For example, your code reads 0x1, an ISR sets bit 3 so the register holds 0x9, and your write of 0x1 | 0x2 = 0x3 silently turns bit 3 back off. Fixes, in order of preference: use the peripheral's separate set and clear registers if it offers them (one write touches only the bits you name); otherwise disable interrupts around the read-modify-write; for shared plain memory (not MMIO) use an atomic operation (one that completes as a single indivisible step, so no other observer can see it half done) such as atomic_fetch_or from <stdatomic.h>, which ORs a mask into a variable atomically.
3. Write-one-to-clear (W1C) status bits. Many status registers clear a flag when you write a 1 to it, and writing 0 changes nothing. Then the read-modify-write "clear" is dangerous: the demo above has bits 1 and 2 pending, so the register reads 0x6 (binary 110). Clearing bit 1 in a temporary gives 0x4 (binary 100), and writing that back writes a 1 to bit 2, which clears bit 2. So 0x6 minus the bits named by the write 0x4 leaves 0x2. The output shows that result: status 0x2, so bit 2 was cleared without anyone handling it and bit 1 was never acknowledged. Writing only the mask (1u << 1) leaves status 0x4, bit 2 intact. For a W1C register the correct "clear bit k" is a single plain write of the mask, and "set" and "toggle" usually do not exist.

Check the peripheral's datasheet for each register's access type (read/write, read-only, W1C, write-only) before choosing the operation.

Complexity and mistakes

Each function is O(1) time and O(1) space: one shift, one mask, one store. Common mistakes: 1 << k with a signed 1 (undefined for k = 31), forgetting the parentheses in (v >> k) & 1u, writing v & mask to "clear" (that keeps the bit), and using || instead of |.

Running the code

gcc -std=c11 -Wall -Wextra -fsanitize=undefined bits.c -o bits && ./bits

Direct answer
For a 'Quantity' field valid on integers 1 to 1000, there are three equivalence classes: below-range (invalid), in-range (valid), and above-range (invalid). One representative test value per class is sufficient because equivalence partitioning assumes the system treats every value inside a class identically, so testing one member of a class exercises the same code path as testing all of them.

Structured elaboration

• Valid partition: integers 1 through 1000 inclusive. Representative value: 500 (a value comfortably inside the range, not near either edge, so it is not accidentally doubling as a boundary test).
• Invalid partition (below): any value less than 1, including 0 and negative integers. Representative value: -5.
• Invalid partition (above): any value greater than 1000. Representative value: 5000.

Why 500 rather than, say, 1 or 1000: picking a mid-range value keeps EP's purpose distinct from BVA's. If you pick 1 or 1000 as your EP representative you are silently doing boundary testing and calling it equivalence partitioning, which hides the fact that BVA (min-1, min, min+1, max-1, max, max+1) is a separate, necessary pass.

Worked example: negative and unexpected-input tests

• Negative test: submit Quantity = 0. Expected result: the system rejects the value with a validation message (e.g. "Quantity must be at least 1"), not a silent clamp to 1 or a crash. This is a negative test because it is a value inside the representable input space (an integer) but outside the valid business range.
• Unexpected-input test: submit Quantity = "abc" (non-numeric) or Quantity = 3.5 (a decimal where an integer is required). Expected result: the field rejects non-integer input before it ever reaches the range check, distinct from the range-validation error message above. This matters because a form that only guards the numeric range but not the type can crash downstream (e.g. a database insert expecting an INT) when handed a string or float.

Trade-offs & pitfalls
The most common mistake with EP is treating the invalid-below and invalid-above partitions as one "invalid" bucket and testing only one of them; they are separate classes because the failure code path (or business meaning, e.g. "quantity too small to fulfill" vs. "exceeds available stock") can legitimately differ. A second pitfall is stopping at EP and assuming the three representative values are a complete test set: EP tells you which classes exist, not where the class boundaries actually break, which is exactly the gap BVA fills.

The idea

A subsequence of s keeps some of its characters, in their original order, and deletes the rest. Two selections count as different if they use different positions, even when the letters they spell are the same. In rabbbit the target rabbit can be spelled by three different position sets, because any two of the three bs can serve as the two bs of the target.

Look at the last character of the part of s you are considering. Either it is not used, and then the count equals the count for the shorter s; or it is used as the last character of the target part, which is only possible when the two characters match, and then the rest of the target is matched inside the shorter s. Add the two cases.

The five things to state

1. State. (i, j): the first i characters of s and the first j characters of t.
2. What one cell means. ways[i][j] is the number of different index sets in s[:i] whose characters, read in order, spell exactly t[:j].
3. Recurrence. ways[i][j] = ways[i-1][j], plus ways[i-1][j-1] when s[i-1] == t[j-1]. Reduce modulo 10^9+7 after each addition.
4. Base cases. ways[i][0] = 1 for every i (spell the empty string by picking nothing) and ways[0][j] = 0 for j > 0 (no characters left to spell something non-empty).
5. Fill order. i ascending, and j ascending within the row in the full table, since cell (i, j) reads row i - 1 only. The answer is ways[m][n].

Brute force first

Trying every index set of size n in s means C(m, n) candidates. The plain recursion go(i, j) branches twice whenever the characters match, and the program counts its calls, root included: 1 call for two empty strings, 1 for ("a", ""), 1 for ("", "a"), 6 for ("ab", "ab"), 52 for rabbbit and rabbit, 1,275 for ten as against five and 78,405 for sixteen as against eight. The table has only (m+1)(n+1) cells (56, 66 and 153 for the last three), because the recursion keeps revisiting the same (i, j).

The code

import random
from itertools import combinations
from math import comb

MOD = 10**9 + 7


def count_table(s, t, mod=None):
    """ways[i][j] = number of index sets in s[:i] whose characters spell t[:j]."""
    m, n = len(s), len(t)
    ways = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        ways[i][0] = 1                              # the empty target: pick nothing
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            ways[i][j] = ways[i - 1][j]             # leave s[i-1] unused
            if s[i - 1] == t[j - 1]:
                ways[i][j] += ways[i - 1][j - 1]    # or use s[i-1] as t[j-1]
            if mod:
                ways[i][j] %= mod
    return ways


def count_rolling(s, t, mod=None, ascending=False, show=False):
    """One row: ways[j] for the prefix of s seen so far. j must go DOWNWARDS."""
    n = len(t)
    ways = [1] + [0] * n
    if show:
        print("start        ", ways)
    for ch in s:
        js = range(1, n + 1) if ascending else range(n, 0, -1)
        for j in js:
            if ch == t[j - 1]:
                ways[j] += ways[j - 1]
                if mod:
                    ways[j] %= mod
        if show:
            print(f"after {ch!r:5}   ", ways)
    return ways[n]


def count_recursive(s, t):
    """Plain recursion on suffixes; returns (count, calls with the root counted)."""
    calls = 0

    def go(i, j):
        nonlocal calls
        calls += 1
        if j == len(t):
            return 1
        if i == len(s):
            return 0
        total = go(i + 1, j)
        if s[i] == t[j]:
            total += go(i + 1, j + 1)
        return total

    return go(0, 0), calls


def count_brute(s, t):
    return sum("".join(s[i] for i in idx) == t
               for r in range(len(t), len(t) + 1) for idx in combinations(range(len(s)), r))


s, t = "rabbbit", "rabbit"
table = count_table(s, t)
print("table for s = rabbbit, t = rabbit (rows: prefixes of s, columns: prefixes of t)")
print("      " + "".join(f"{c:>3}" for c in " " + t))
for i, row in enumerate(table):
    print(f"{('' if i == 0 else s[i - 1]):>2} {i}: " + "".join(f"{v:>3}" for v in row))
print("answer:", table[-1][-1])
print("rolling row:")
print("answer:", count_rolling(s, t, show=True))
print("same input with j ascending (wrong):", count_rolling(s, t, ascending=True))

print("s          t        count  recursion_calls  (m+1)*(n+1)")
for s2, t2 in (("", ""), ("a", ""), ("", "a"), ("ab", "ab"), ("rabbbit", "rabbit"),
               ("aaaaaaaaaa", "aaaaa"), ("a" * 16, "a" * 8)):
    value, calls = count_recursive(s2, t2)
    print(f"{s2:10s} {t2:8s} {value:5d}  {calls:15d}  {(len(s2) + 1) * (len(t2) + 1)}")

big_s, big_t = "a" * 60, "a" * 30
exact = count_rolling(big_s, big_t)
print("60 a's, target 30 a's: exact", exact, "= C(60, 30):", exact == comb(60, 30),
      "| mod 1e9+7:", count_rolling(big_s, big_t, MOD), "|", exact % MOD)

random.seed(64)
for _ in range(300):
    m, n = random.randint(0, 11), random.randint(0, 5)
    s2 = "".join(random.choice("ab") for _ in range(m))
    t2 = "".join(random.choice("ab") for _ in range(n))
    expected = count_brute(s2, t2)
    assert count_table(s2, t2)[m][n] == count_rolling(s2, t2) == count_recursive(s2, t2)[0] == expected, (s2, t2)
    assert count_rolling(s2, t2, MOD) == expected % MOD
print("300 seeded pairs (s of length 0..11, t of length 0..5, alphabet a/b): table, rolling row and recursion equal brute force")

Output:

table for s = rabbbit, t = rabbit (rows: prefixes of s, columns: prefixes of t)
           r  a  b  b  i  t
   0:   1  0  0  0  0  0  0
 r 1:   1  1  0  0  0  0  0
 a 2:   1  1  1  0  0  0  0
 b 3:   1  1  1  1  0  0  0
 b 4:   1  1  1  2  1  0  0
 b 5:   1  1  1  3  3  0  0
 i 6:   1  1  1  3  3  3  0
 t 7:   1  1  1  3  3  3  3
answer: 3
rolling row:
start         [1, 0, 0, 0, 0, 0, 0]
after 'r'      [1, 1, 0, 0, 0, 0, 0]
after 'a'      [1, 1, 1, 0, 0, 0, 0]
after 'b'      [1, 1, 1, 1, 0, 0, 0]
after 'b'      [1, 1, 1, 2, 1, 0, 0]
after 'b'      [1, 1, 1, 3, 3, 0, 0]
after 'i'      [1, 1, 1, 3, 3, 3, 0]
after 't'      [1, 1, 1, 3, 3, 3, 3]
answer: 3
same input with j ascending (wrong): 6
s          t        count  recursion_calls  (m+1)*(n+1)
                        1                1  1
a                       1                1  2
           a            0                1  2
ab         ab           1                6  9
rabbbit    rabbit       3               52  56
aaaaaaaaaa aaaaa      252             1275  66
aaaaaaaaaaaaaaaa aaaaaaaa 12870            78405  153
60 a's, target 30 a's: exact 118264581564861424 = C(60, 30): True | mod 1e9+7: 737009364 | 737009364
300 seeded pairs (s of length 0..11, t of length 0..5, alphabet a/b): table, rolling row and recursion equal brute force

Reading the output

• The first table is the real ways table for rabbbit and rabbit. Row b 3 ends in 1 at the column for rab, row b 4 has 2 there, and row b 5 has 3: rabbb contains rab in three ways (the three bs). The last row, last column is the answer 3.
• Column rabb (j = 4) climbs 0, 1, 3 over the three bs, then stays at 3 through the i and the t: 1 way after the second b, 3 after the third. These are the 3 pairs of bs that can form the bb of the target.
• The rolling run prints the single row after every character of s, and ends at the same 3. In that version row i overwrites row i - 1 in place. The inner loop must go from j = n down to 1, so that ways[j-1] still holds the value from before this character. With the loop ascending, the same input prints 6 instead of 3, because each b first updates ways[3] and then ways[4] reads that fresh value, so a single character is used for two positions of the target.
• Sixty as against thirty as: the exact count is 118264581564861424, equal to comb(60, 30), and reduced modulo 10^9+7 it is 737009364, the value the modular run also returns. This is why the modulus is needed: counts grow like binomial coefficients.
• The seeded test draws 300 pairs with s of length 0 to 11 and t of length 0 to 5 over the letters a and b (so empty s, empty t, and t longer than s all occur) and checks the table, the rolling row and the recursion against a brute force over index sets, and the modular run against the exact value reduced.

Complexity

• Time. O(m * n): (m + 1)(n + 1) cells in the table, one addition each.
• Space. O(m * n) for the full table, O(n) for the rolling row (a list of n + 1 numbers). The recursion uses O(m) stack but takes exponential time, so it is not used.
• If n is greater than m, the answer is 0, which the loops give without special handling (covered in the random test).

Edge cases and common mistakes

• Empty t returns 1 for any s (including empty s), and empty s with non-empty t returns 0; both appear in the output.
• Looping j upward in the one-row version, shown above (6 instead of 3).
• Forgetting the modulus when counts get large; the exact value for 60 and 30 is 18 digits long. In a fixed-width language the unreduced value would overflow a 64-bit integer once it exceeds 9.22 * 10^18, so reduce at every addition.

Running the code

python3.12 distinct_subsequences.py

Standard library only. Save the listing as distinct_subsequences.py and run the command above; it prints exactly the output shown.

Direct answer. Order by (created_at, id) and filter for rows strictly greater than the cursor's (created_at, id) pair, using a compound comparison so ties on created_at are broken by id rather than skipping or duplicating rows.

The query, against posts(id BIGINT PRIMARY KEY, created_at TIMESTAMP, title TEXT):

SELECT id, created_at, title
FROM posts
WHERE (created_at, id) > (:last_created_at, :last_id)
ORDER BY created_at ASC, id ASC
LIMIT 50;

The index. A composite index on (created_at, id) is what turns this into a single ordered index range scan instead of a sort-then-filter: CREATE INDEX idx_posts_created_at_id ON posts (created_at, id);. Without it, the database can still produce correct results, just by sorting the whole table first, which is exactly the cost keyset pagination exists to avoid.

Handling ties. Two posts inserted in the same second will have identical created_at values. The compound comparison (created_at, id) > (:last_created_at, :last_id) is what makes this safe: a row with the SAME created_at as the cursor but a LARGER id is still correctly included on the next page, and a row with the same created_at and a smaller-or-equal id is correctly excluded, so no row is skipped or returned twice even when many rows share one timestamp. Ordering by created_at alone, without id as a tiebreaker, would make the result of paging through tied rows depend on the database's arbitrary internal ordering, which can differ between two runs of the exact same query.

Verified with a small SQLite database (the query shape and the index it relies on are identical for Postgres): 120 rows seeded, three of them (ids 50, 51, 52) sharing one timestamp on purpose to exercise the tie-break.

import sqlite3
from datetime import datetime, timedelta

conn = sqlite3.connect(":memory:")
conn.execute("CREATE TABLE posts (id INTEGER PRIMARY KEY, created_at TEXT NOT NULL, title TEXT NOT NULL)")
conn.execute("CREATE INDEX idx_posts_created_at_id ON posts (created_at, id)")

base_time = datetime(2026, 1, 1, 0, 0, 0)
rows = []
for i in range(1, 121):
    ts = base_time + timedelta(minutes=50) if i in (50, 51, 52) else base_time + timedelta(minutes=i)
    rows.append((i, ts.isoformat(), f"Post {i}"))
conn.executemany("INSERT INTO posts (id, created_at, title) VALUES (?, ?, ?)", rows)
conn.commit()

def next_page(conn, last_created_at, last_id, page_size=50):
    cur = conn.execute(
        "SELECT id, created_at, title FROM posts WHERE (created_at, id) > (?, ?) "
        "ORDER BY created_at ASC, id ASC LIMIT ?",
        (last_created_at, last_id, page_size),
    )
    return cur.fetchall()

page1 = next_page(conn, "", 0, page_size=50)
last_id, last_created_at, _ = page1[-1]
page2 = next_page(conn, last_created_at, last_id, page_size=50)
last_id, last_created_at, _ = page2[-1]
page3 = next_page(conn, last_created_at, last_id, page_size=50)

all_ids = [r[0] for r in page1] + [r[0] for r in page2] + [r[0] for r in page3]
print(f"page 1: {len(page1)} rows, ids {page1[0][0]}..{page1[-1][0]}")
print(f"page 2: {len(page2)} rows, ids {page2[0][0]}..{page2[-1][0]}")
print(f"page 3: {len(page3)} rows, ids {page3[0][0]}..{page3[-1][0]}")
print("total rows returned:", len(all_ids))
print("no duplicates:", len(all_ids) == len(set(all_ids)))
print("every id 1..120 returned exactly once:", sorted(all_ids) == list(range(1, 121)))

Output (actually run):

page 1: 50 rows, ids 1..50
page 2: 50 rows, ids 51..100
page 3: 20 rows, ids 101..120
total rows returned: 120
no duplicates: True
every id 1..120 returned exactly once: True

Complexity. With the composite index, each page fetch is an index range scan of roughly O(page_size + log n) rather than an O(n) or O(offset) scan, and that cost does not grow with how many pages the client has already fetched.

Edge cases. A row inserted with a timestamp that ties the CURRENT cursor value but a lower id than the cursor's last_id is correctly excluded (it would have already been included on the current page if it existed at fetch time); a row deleted after being handed to the client simply does not reappear, since nothing about the query depends on that row still existing.

Direct answer. DRY is right for logic that represents ONE decision that should always change together; it's wrong when the forced abstraction merges things that only look similar today but represent DIFFERENT decisions that happen to coincide -- the 'wrong abstraction' costs more than the duplication it replaced, because a bad shared abstraction is often harder to safely split apart than duplication is to later consolidate.

When abstraction beats duplication

Three services independently implementing the SAME tax-rounding rule: this is one business decision (how does the company round tax) expressed three times. A rule change means finding and fixing three places, with real risk of missing one -- extracting a shared round_tax() function is the right call here because all three copies are genuinely the same concept and should change in lockstep.

When the 'wrong abstraction' is worse

Two onboarding flows for different customer segments both validate a phone number with the SAME regex today. It's tempting to extract validate_phone() and use it in both. Six months later, one segment needs to support international formats and the other doesn't -- now the shared function needs a parameter (allow_international: bool), then another distinction, then another, until the 'shared' function is a tangle of flags serving two purposes that were never actually the same thing. At that point you're paying MORE cognitive cost reading the merged function's branches than you would have paid maintaining two small, independent, honestly-different validators.

How to tell the difference in the moment

• Ask: 'if this changes, is there a REASON both callers would need the same change?' If the reason is coincidental (they both happen to use a US-only regex today, for unrelated reasons), that's a signal to keep them separate.
• Watch for a shared function accumulating boolean flags or optional parameters that only ONE caller ever sets -- that's the tell-tale sign an abstraction is being stretched to cover cases it wasn't designed for.
• If you're not sure yet (early in a project, requirements still unclear), tolerating duplication for a while costs little and preserves the option to extract correctly later, once real usage reveals which parts genuinely need to move together.

Recovering from a bad abstraction

When you notice a shared function has accumulated flags for divergent needs, the fix is usually to SPLIT it back into purpose-specific functions (possibly still sharing a smaller, GENUINELY common piece), not to add a third flag on top of the first two.

Trade-offs and pitfalls

• DRY applied to superficial text similarity rather than conceptual identity (two unrelated pieces of code that happen to both loop over a list and sum a field) is a common over-application -- the sameness has to be about MEANING, not appearance.
• Recognize that 'we already extracted this, so let's keep using it even though it doesn't quite fit' is a sunk-cost trap; a growing flag list on a shared function is a stronger signal to split than to add one more flag.