Arrays, Strings, and Hashing Questions

Direct answer

Add the two digit strings exactly the way long addition is done by hand: walk both strings from the rightmost digit, add the corresponding digits plus any carry from the previous position, keep the ones digit as the result and carry the tens digit forward, and continue until both strings and the carry are exhausted. This never converts the whole number into a native integer type, runs in O(max(len(a), len(b))) time and space, and generalizes directly to any base by changing how individual digits are parsed and re-emitted.

Structured elaboration

Why this can't just use native integer addition. The entire point of the exercise is that the numbers may be arbitrarily large decimal strings, potentially larger than any fixed-width integer type can represent without an arbitrary-precision ("big-int") library; the question explicitly disallows using one, so digits are processed as characters, not as a machine integer.

The right-to-left digit-pair-plus-carry loop. Two index pointers start at the last character of each string and move left. At each step, the digit from a (or 0 if that pointer has run past the start of a) is added to the digit from b (or 0, similarly) plus the carry from the previous step. The result's ones digit (total % 10) is appended to the output, and the new carry is the tens digit (total // 10). The loop continues as long as either pointer still has digits left, or a carry is still pending, which correctly handles the case where the final addition produces an extra leading digit (e.g. 9 + 9 = 18, carrying a new leading 1).

Reversal at the end. Because digits are produced from least-significant to most-significant (processing right to left), the accumulated digit list is in reverse order relative to the final answer and must be reversed once before joining into the output string.

Generalizing to base 16 or other bases. The algorithm's structure doesn't change at all between bases; only two things change: how a single character is parsed into its numeric digit value, and how a numeric digit value is turned back into a character. In decimal, int(digit) and str(digit) handle this. For an arbitrary base b (2 through 36), Python's int(digit, b) parses a single base-b digit character (handling both decimal digits and letters a through z for bases above 10), and indexing into a fixed alphabet string (\"0123456789abcdefghijklmnopqrstuvwxyz\") re-emits a digit value as its base-b character. The carry logic is identical, just with % base and // base replacing % 10 and // 10.

Worked example

Full runnable code with pinned test cases, including the question's own large-number example, verified against Python's own native big-integer addition as ground truth (used here only to cross-check the from-scratch implementation, not as a substitute for it):

def add_strings(a, b):
    """Add two non-negative decimal-string integers without big-int libs.
    O(max(len(a), len(b))) time and space, single right-to-left pass with
    a carry, exactly like manual long addition."""
    i, j = len(a) - 1, len(b) - 1
    carry = 0
    digits = []
    while i >= 0 or j >= 0 or carry:
        da = int(a[i]) if i >= 0 else 0
        db = int(b[j]) if j >= 0 else 0
        total = da + db + carry
        digits.append(str(total % 10))
        carry = total // 10
        i -= 1
        j -= 1
    return ''.join(reversed(digits))


def add_strings_base(a, b, base):
    """Same algorithm generalized to an arbitrary base (2-36), using
    int(digit, base) to parse and a base-N string alphabet to re-emit."""
    digits_alphabet = "0123456789abcdefghijklmnopqrstuvwxyz"
    i, j = len(a) - 1, len(b) - 1
    carry = 0
    out = []
    while i >= 0 or j >= 0 or carry:
        da = int(a[i], base) if i >= 0 else 0
        db = int(b[j], base) if j >= 0 else 0
        total = da + db + carry
        out.append(digits_alphabet[total % base])
        carry = total // base
        i -= 1
        j -= 1
    return ''.join(reversed(out))


if __name__ == "__main__":
    a = "9876543210123456789"
    b = "1234567890987654321"
    result = add_strings(a, b)
    expected_via_python_int = str(int(a) + int(b))
    print(f"add_strings({a!r}, {b!r})")
    print(f"  result   = {result}")
    print(f"  expected = {expected_via_python_int} (cross-checked via Python's native int addition)")
    print(f"  match: {result == expected_via_python_int}")

    more_tests = [
        ("0", "0", "0"),
        ("1", "9", "10"),
        ("99", "1", "100"),
        ("123", "0", "123"),
    ]
    for x, y, exp in more_tests:
        r = add_strings(x, y)
        print(f"add_strings({x!r}, {y!r}) = {r} (expected {exp})")

    hex_result = add_strings_base("ff", "1", 16)
    print(f"add_strings_base('ff', '1', 16) = {hex_result} (expected 100)")

Output (actual run):

add_strings('9876543210123456789', '1234567890987654321')
  result   = 11111111101111111110
  expected = 11111111101111111110 (cross-checked via Python's native int addition)
  match: True
add_strings('0', '0') = 0 (expected 0)
add_strings('1', '9') = 10 (expected 10)
add_strings('99', '1') = 100 (expected 100)
add_strings('123', '0') = 123 (expected 123)
add_strings_base('ff', '1', 16) = 100 (expected 100)

This confirms the question's own stated example: '9876543210123456789' + '1234567890987654321' -> '11111111101111111110' is correct, verified both by the character-by-character implementation and by cross-checking against Python's native arbitrary-precision integer addition on the same inputs. The base-16 example ('ff' + '1' = '100' in hex, i.e. 255 + 1 = 256) confirms the generalization: the carry chain propagates through both hex digits exactly as it would for 99 + 1 = 100 in decimal.

Trade-offs and pitfalls

• Converting both strings to native integers, adding, and converting back (str(int(a) + int(b))) is the obvious shortcut and was used above only as a cross-check, not as the answer: for genuinely arbitrary-precision inputs in a language without native big-int support (or under an explicit "no big-int library" constraint, as this question states), this shortcut isn't available at all, which is the entire point of the exercise.
• A common bug is forgetting the final carry: if the loop condition doesn't check carry as an independent continuation condition (only checking i >= 0 or j >= 0), an addition like 9 + 9 (which produces 18, needing an extra leading digit) silently drops the final carry digit.
• Building the result with repeated string concatenation (result = digit + result instead of appending to a list and reversing once at the end) works but is less efficient in languages or situations where string concatenation is O(current length) per operation, making a naive left-prepend approach O(n^2) overall instead of O(n); appending to a list and reversing once avoids this.
• This implementation assumes both inputs are non-negative digit strings with no sign character or leading-zero ambiguity beyond a literal "0"; supporting signed values would require detecting and handling a leading - or + before the digit-processing loop, which is a real but separate extension.
• The base generalization above supports bases 2 through 36 only, since it relies on Python's int(digit, base) and a 36-character alphabet; supporting arbitrary bases beyond 36 would require a different, explicitly-provided digit alphabet rather than reusing 0-9a-z.

Direct answer

Model the parser as an explicit state machine with four states (start of field, inside an unquoted field, inside a quoted field, and "just saw a quote while inside a quoted field"), and drive it one character at a time so it can hold its place between calls. That is what makes it work on chunked input: the state and the current partial row live in an object between feed() calls, so a field, a quote, or even a line ending can be split arbitrarily across chunk boundaries without losing correctness.

Structured elaboration

The four states.

• FIELD_START: at the start of a field. A " opens a quoted field; anything else starts an unquoted one.
• UNQUOTED: scanning an unquoted field. , ends the field, \n ends the row, a bare \r is swallowed (so both \n and \r\n line endings work, even if the \r and \n land in different chunks).
• QUOTED: inside a quoted field. Only " is special; comma and newline are ordinary field content here, which is exactly why a naive line.split(',') cannot handle quoted CSV: a comma or newline inside quotes must not end the field or row.
• QUOTE_IN_QUOTED: just saw a " while inside a quoted field. The next character decides what that quote meant: another " is the RFC 4180 escaped-quote convention ("" inside quotes decodes to one literal "), while , or \n closes the field or row.

Escaped quotes. The QUOTE_IN_QUOTED state is precisely the escape mechanism: seeing " there means "was that a closing quote or an escaped one," and the answer is read off the very next character.

Streaming input. feed(chunk) iterates the chunk's characters through _feed_char, appends completed rows to an internal buffer, and returns (and clears) that buffer. A trailing finish() call flushes a final row that has no terminating newline. A generator, parse_csv_stream(chunks), wraps this so a caller can iterate rows directly over file.read(65536)-sized chunks without ever holding the whole file, or even a whole row beyond the one currently being assembled, in memory.

Worked example

class CSVStateMachine:
    FIELD_START, UNQUOTED, QUOTED, QUOTE_IN_QUOTED = range(4)

    def __init__(self):
        self.state = self.FIELD_START
        self.field_chars = []
        self.row = []
        self._rows_ready = []

    def feed(self, chunk: str):
        for ch in chunk:
            self._feed_char(ch)
        out, self._rows_ready = self._rows_ready, []
        return out

    def finish(self):
        if self.field_chars or self.row:
            self._end_row()
        out, self._rows_ready = self._rows_ready, []
        return out

    def _end_field(self):
        self.row.append(''.join(self.field_chars))
        self.field_chars = []

    def _end_row(self):
        self._end_field()
        self._rows_ready.append(self.row)
        self.row = []
        self.state = self.FIELD_START

    def _feed_char(self, ch):
        s = self.state
        if s == self.FIELD_START:
            if ch == '"':
                self.state = self.QUOTED
            elif ch == ',':
                self._end_field()
            elif ch == '\n':
                self._end_row()
            elif ch == '\r':
                pass
            else:
                self.field_chars.append(ch)
                self.state = self.UNQUOTED
        elif s == self.UNQUOTED:
            if ch == ',':
                self._end_field(); self.state = self.FIELD_START
            elif ch == '\n':
                self._end_row()
            elif ch == '\r':
                pass
            else:
                self.field_chars.append(ch)
        elif s == self.QUOTED:
            if ch == '"':
                self.state = self.QUOTE_IN_QUOTED
            else:
                self.field_chars.append(ch)
        elif s == self.QUOTE_IN_QUOTED:
            if ch == '"':
                self.field_chars.append('"'); self.state = self.QUOTED
            elif ch == ',':
                self._end_field(); self.state = self.FIELD_START
            elif ch == '\n':
                self._end_row()
            elif ch == '\r':
                pass
            else:
                self.field_chars.append(ch); self.state = self.UNQUOTED


def parse_csv_stream(chunk_iterable):
    machine = CSVStateMachine()
    for chunk in chunk_iterable:
        for row in machine.feed(chunk):
            yield row
    for row in machine.finish():
        yield row

test_input = (
    "id,name,note\r\n"
    "1,\"Smith, John\",\"Said \"\"hello\"\" today\"\r\n"
    "2,\"multi\nline note\",plain\r\n"
    "3,noquotes,last row no newline"
)

whole = list(parse_csv_stream([test_input]))
for row in whole:
    print(row)

lengths = [5, 1, 16, 1, 1, 16, 15, 15, 1, 40]
chunks, idx = [], 0
for L in lengths:
    chunks.append(test_input[idx:idx + L])
    idx += L

chunked = list(parse_csv_stream(chunks))
for row in chunked:
    print(row)

print("chunked parse matches whole-input parse:", chunked == whole)

Test input (CRLF endings, a quoted field with an embedded comma, a quoted field with an embedded escaped quote, a quoted field with an embedded newline, and a final row with no trailing newline):

id,name,note\r\n
1,"Smith, John","Said ""hello"" today"\r\n
2,"multi\nline note",plain\r\n
3,noquotes,last row no newline

Parsed whole, in one shot:

['id', 'name', 'note']
['1', 'Smith, John', 'Said "hello" today']
['2', 'multi\nline note', 'plain']
['3', 'noquotes', 'last row no newline']

Then the exact same text was cut into 10 deliberately awkward chunks (lengths [5, 1, 16, 1, 1, 16, 15, 15, 1, 40]), with boundaries landing mid-quoted-field, mid-escaped-quote, and mid-CRLF, and streamed through parse_csv_stream:

['id', 'name', 'note']
['1', 'Smith, John', 'Said "hello" today']
['2', 'multi\nline note', 'plain']
['3', 'noquotes', 'last row no newline']

chunked parse matches whole-input parse: True

The chunked result is character-for-character identical to the whole-input parse, which is the actual proof the state machine (not just the happy-path parse) is correct: if the state were not preserved correctly across feed() calls, at least one of those adversarial cut points would have corrupted a field.

Trade-offs and pitfalls

The single most common bug in a hand-rolled version of this: constructing a new parser instance per chunk instead of reusing one across feed() calls. That silently forgets which state (and which partial field) was in progress, and any chunk boundary landing inside a quoted field, an escaped quote, or a CRLF pair would be mis-parsed without raising any error, it would just produce wrong rows.

Memory footprint is bounded by the longest single field, not by file size, since only the current row's partial content is held between chunks, which is the entire point of doing this as a streaming state machine instead of reading the whole file into one big string first.

This hand-rolled parser is a demonstration of the state-machine technique, not a drop-in CSV library: it does not detect or strip a UTF-8 byte-order mark, does not validate that every row has the same column count as the header, and does not handle encodings other than already-decoded Unicode text. In real production code, reach for a maintained CSV library; this exercise is about the parsing technique the interviewer is actually checking.

Direct answer

Group strings that are anagrams of each other by mapping each string to a canonical key that is identical for all of its anagrams and different otherwise, then bucket strings by that key in a hash map. The two standard keys are the sorted-character string (simple, O(L log L) per string) and a fixed-length character-frequency vector (O(L) per string, faster for long strings, but only straightforward for a small, known, fixed alphabet).

Structured elaboration

Approach 1: sorted string as key

Sort each string's characters and join them back into a string; two strings are anagrams exactly when this sorted form is identical. Sorting a string of length L costs O(L log L), so grouping n strings this way costs O(n * L log L) in total, where L is the average or maximum string length.

Approach 2: frequency vector as key

Count the occurrences of each character into a fixed-size array (26 entries for lowercase English letters), then use that array, converted to an immutable tuple so it can be a hash-map key, as the grouping key. Building the count for one string costs O(L), so this approach costs O(n * (L + alphabet_size)) in total, asymptotically better than the sorted-key approach once L is large relative to log L, since counting avoids the sort entirely. The trade-off is that this fixed-size-array trick assumes a small, KNOWN alphabet; it does not generalize as cleanly the moment the alphabet is unbounded.

Unicode input

Both approaches need care once the input can contain arbitrary Unicode text rather than plain lowercase English letters. The frequency-vector approach's fixed 26-slot array breaks down immediately, since Unicode text can contain far more than 26 distinct characters; the practical fix is a hash map from character to count instead of a fixed array, which still works but loses the small constant-factor advantage of a fixed array. More subtly, even the sorted-key approach can give a WRONG answer on Unicode input if two visually and semantically identical strings are represented by different underlying code point sequences: an accented character can be represented either as a single precomposed code point, or as the base letter followed by a separate combining accent mark. These compare as different strings and produce different sorted keys even though they represent the same text. The fix is to first normalize every string using Unicode Normalization Form C (NFC), which canonicalizes precomposed and decomposed forms to the same representation, before computing either kind of key.

Performance for long strings and memory trade-offs

For long strings, the frequency-vector approach avoids the L log L sorting cost, which matters when strings are long, for example grouping DNA-like sequences or long tokenized identifiers rather than short English words. Memory-wise, the sorted-key approach's key is proportional to the string's own length, while the frequency-vector key has a FIXED size (26 entries, or however many distinct characters the chosen alphabet has) regardless of the string's length, which can be smaller for long strings but is pure overhead for very short ones.

Worked example

from collections import defaultdict
import unicodedata

def group_anagrams_sorted_key(strs):
    groups = defaultdict(list)
    for s in strs:
        key = ''.join(sorted(s))
        groups[key].append(s)
    return list(groups.values())

def group_anagrams_freq_key(strs, alphabet_size=26):
    groups = defaultdict(list)
    for s in strs:
        counts = [0] * alphabet_size
        for ch in s:
            counts[ord(ch) - ord('a')] += 1
        groups[tuple(counts)].append(s)
    return list(groups.values())

strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
print(group_anagrams_sorted_key(strs))
print(group_anagrams_freq_key(strs))

def normalize_for_unicode_anagram_key(s):
    return ''.join(sorted(unicodedata.normalize('NFC', s)))

precomposed = "café"          # single code point for e-acute
decomposed = "café"          # 'e' + combining acute accent
print(precomposed == decomposed)
print(''.join(sorted(precomposed)) == ''.join(sorted(decomposed)))
print(normalize_for_unicode_anagram_key(precomposed) == normalize_for_unicode_anagram_key(decomposed))

Output:

[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]
[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]
False
False
True

Both approaches group the same six words into the same three anagram groups. The Unicode section demonstrates the normalization issue directly: two strings that print identically and represent the same visible text, cafe with an accented e built from a single precomposed code point versus the same word built from a base letter plus a separate combining accent mark, compare as unequal Python strings, and their naive sorted-character keys also disagree, but normalizing both to NFC before computing the key makes them match, exactly the correctness gap this section describes.

Trade-offs and pitfalls

A common mistake is assuming string equality in Python already handles Unicode normalization: it does not, two strings built from a precomposed versus a decomposed representation of the same visible text can compare as unequal, which silently splits what should be one anagram group into two. A second is hardcoding a 26-entry frequency array without checking the actual input alphabet, which either crashes on characters outside a-z or silently produces wrong groupings once real-world text with punctuation, digits, or non-English characters shows up. For genuinely massive input, the scale this problem is asked at in a batch-processing context, well beyond what fits comfortably in memory as one hash map, the practical extension is external-memory or streaming grouping: sort the (key, original-string) pairs using an external merge sort so anagrams become adjacent on disk without needing every group held in memory at once, or shard by a prefix of the key across multiple workers so each worker only needs to hold its own shard's groups in memory. That is a genuine and reasonable extension of this same technique at scale, but it is a distinct system-design problem from choosing a grouping key, and is mentioned here only as the natural next question, not as something this answer needs to design in full. The same two key strategies carry over unchanged in Java (HashMap<String, List<String>> or HashMap<List<Integer>, List<String>>) and JavaScript (a Map keyed on the same sorted-string or frequency-array-as-string idea).

Direct answer

Treat each value in the array as a pointer: from index i, "follow" nums[i] to land on index nums[i]. Because there are n+1 values all in the range [1, n], at least two different indices must point to the same value (pigeonhole), which means this functional graph has a cycle, and the duplicate value is exactly the entry point of that cycle. Floyd's tortoise-and-hare cycle detection finds that entry point in O(n) time and O(1) extra space, without modifying the array at all, which is exactly what the question asks for.

Approach (Floyd's cycle detection)

1. Start both slow and fast at nums[0], i.e. one step into the implicit linked structure (index 0 always has an outgoing "pointer," but nothing points back to it, so it can't be part of the cycle itself, only the tail leading into it).
2. Advance slow one step (slow = nums[slow]) and fast two steps (fast = nums[nums[fast]]) each iteration until they meet; a meeting point is guaranteed to exist since the structure has a cycle (standard tortoise-and-hare argument).
3. Reset a second pointer to index 0, then advance it and slow one step at a time together; the index where they meet is the cycle's entry point, which is the duplicate value.

Complexity

Time: O(n) (each phase does at most O(n) steps). Space: O(1) extra; nums itself is never modified.

Edge cases

• Exactly one duplicate value, appearing exactly twice: this is the assumed input shape and the algorithm handles it directly.
• The duplicate value equal to n itself (the largest allowed value): handled the same way, since indexing is 0-based but values start at 1, so nums[i] is always a valid index regardless of which value 1..n is duplicated.

def find_duplicate_floyd(nums):
    slow = nums[0]
    fast = nums[nums[0]]
    while slow != fast:
        slow = nums[slow]
        fast = nums[nums[fast]]
    slow2 = 0
    while slow2 != slow:
        slow2 = nums[slow2]
        slow = nums[slow]
    return slow


data = [1, 3, 4, 2, 2]
original = list(data)
print(find_duplicate_floyd(data), data == original)

Output:

2 True

The duplicate is correctly identified as 2, and data == original confirms the array was never mutated during the search.

Alternative technique: index-marking

A second valid approach exploits the same "values are indices" fact differently: walk the array once, and for each value, negate the entry at the index that value points to (abs(value) - 1). If you ever land on an index whose entry is already negative, that index (converted back to 1-based) is the duplicate, because it means two different positions "pointed" to it. This is also O(n) time and O(1) additional space, but unlike Floyd's approach, it works by temporarily mutating nums in place (each visited value's target slot gets negated), so if the caller needs nums to remain externally unmodified while the function runs (not just restored by the time it returns), Floyd's version is the safer default.

def find_duplicate_marking(nums):
    duplicate = None
    for x in nums:
        idx = abs(x) - 1
        if nums[idx] < 0:
            duplicate = idx + 1
            break
        nums[idx] = -nums[idx]
    for i in range(len(nums)):
        nums[i] = abs(nums[i])
    return duplicate


data2 = [1, 3, 4, 2, 2]
print(find_duplicate_marking(data2), data2)

Output:

2 [1, 3, 4, 2, 2]

Both techniques agree on the duplicate (2), and the marking approach restores the array to its original values by the time it returns, even though it mutated it during the scan.

Trade-offs and pitfalls

• "Does not modify the array" has two readings, and the question's phrasing ("without modifying the array") most naturally means Floyd's guarantee: never mutated, at any point, including during execution. The marking approach only satisfies a weaker version ("unmodified once the function returns"), which is a meaningful difference if another thread could read nums concurrently while this function runs, or if the function could throw partway through and leave the array in its negated state.
• A frequent proof gap: candidates often reach for cycle detection without first establishing why a cycle must exist here. The argument is exactly pigeonhole: n+1 values drawn from a range of only n possible values guarantees at least one repeat, and because every value is a valid index (never 0, since the range is [1, n] not [0, n-1]), the "value points to index" structure is well-defined for every position, forcing at least one node in the sequence to be revisited, i.e. a cycle.
• A common bug in the marking approach: forgetting the final restoration pass, which silently corrupts the caller's array (still functionally finds the right duplicate, but violates the "don't modify the array" requirement in a way that's easy to overlook if you only test the return value).

Direct answer

Track two running arrays indexed by "how many transactions used so far": buy[j] (best running profit while holding a share, having started the j-th buy) and sell[j] (best running profit while not holding, having completed the j-th sell), and update both for every price in a single left-to-right pass. This is O(n * k) time and O(k) space. There is also a special case: once k is at least n // 2, there can never be more than n // 2 genuinely profitable non-overlapping transactions regardless of how large k is, so the problem collapses to unlimited transactions, solvable greedily in O(n) time by summing every positive day-to-day price increase.

Algorithm

For each day's price, and for each transaction count j from 1 to k:

• buy[j] = max(buy[j], sell[j-1] - price): either keep the best "holding" position already found for the j-th buy, or start a new j-th buy today, financed by whatever profit was banked after the (j-1)-th sell.
• sell[j] = max(sell[j], buy[j] + price): either keep the best "sold" position already found for the j-th sell, or sell today's holding for today's price.

Because buy[j] on the right-hand side is this day's just-updated value, sell[j] on the same day can reflect a buy-and-sell on the same day (a net-zero move, which never hurts an optimal solution since it's equivalent to not trading), while still processing the array in one pass with two length-(k+1) arrays rather than a full 2D table.

def max_profit_k_transactions(prices, k):
    n = len(prices)
    if n == 0 or k == 0:
        return 0

    if k >= n // 2:
        return sum(max(0, prices[i] - prices[i - 1]) for i in range(1, n))

    buy = [float("-inf")] * (k + 1)
    sell = [0] * (k + 1)
    for price in prices:
        for j in range(1, k + 1):
            buy[j] = max(buy[j], sell[j - 1] - price)
            sell[j] = max(sell[j], buy[j] + price)
    return sell[k]

Why k >= n // 2 collapses to unlimited transactions

Every transaction consumes at least 2 distinct days (one buy day, one sell day), and a set of non-overlapping transactions can't reuse a day. So no more than n // 2 transactions can ever be simultaneously "active" in an optimal non-overlapping schedule; once the allowed k reaches that ceiling, the constraint is no longer binding; you may as well capture every single profitable up-move independently, since doing so never uses more than n // 2 actual buy/sell pairs (adjacent up-runs merge into one transaction each) and no constrained schedule can beat the unconstrained greedy optimum.

Worked example

from functools import lru_cache

def max_profit_memoized(prices, k):
    n = len(prices)

    @lru_cache(maxsize=None)
    def rec(day, txns_used, holding):
        if day == n or txns_used == k:
            return 0
        best = rec(day + 1, txns_used, holding)
        if holding:
            best = max(best, prices[day] + rec(day + 1, txns_used + 1, False))
        else:
            best = max(best, -prices[day] + rec(day + 1, txns_used, True))
        return best

    result = rec(0, 0, False)
    rec.cache_clear()
    return result

cases = [
    ([2, 4, 1], 2),
    ([3, 2, 6, 5, 0, 3], 2),
    ([1, 2, 4, 2, 5, 7, 2, 4, 9, 0], 3),
]
for prices, k in cases:
    fast = max_profit_k_transactions(prices, k)
    memoized = max_profit_memoized(prices, k)
    print(f"max_profit_k_transactions({prices}, k={k}) = {fast}  (memoized cross-check: {memoized}, agree: {fast == memoized})")

Output (verified by execution, and cross-checked against an independently-implemented memoized recursion over (day, transactions_used, holding) for every case, a genuinely different formulation, not the same array-DP checked against itself):

max_profit_k_transactions([2, 4, 1], k=2) = 2  (memoized cross-check: 2, agree: True)
max_profit_k_transactions([3, 2, 6, 5, 0, 3], k=2) = 7  (memoized cross-check: 7, agree: True)
max_profit_k_transactions([1, 2, 4, 2, 5, 7, 2, 4, 9, 0], k=3) = 15  (memoized cross-check: 15, agree: True)

For [3, 2, 6, 5, 0, 3] with k=2: the optimal schedule is buy at 2 (index 1), sell at 6 (index 2), profit 4; buy at 0 (index 4), sell at 3 (index 5), profit 3; total 7, using exactly 2 of the allowed 2 transactions, matching the DP's answer. For [1, 2, 4, 2, 5, 7, 2, 4, 9, 0] with k=3: buy 1 sell 4 (profit 3), buy 2 sell 7 (profit 5), buy 2 sell 9 (profit 7), total 15, again using all 3 allowed transactions and matching the largest 3 disjoint up-runs in the sequence.

Trade-offs and pitfalls

• k small vs k large is a genuine complexity cliff, not a smooth trade-off: for small k (say, single or low double digits), O(n*k) is fast and the array-DP above is the right tool. For large k (specifically once k >= n // 2), the same DP still gives the correct answer but does unnecessary work; recognizing and special-casing the collapse to the O(n) greedy is the difference between an interviewer seeing a complete answer and a merely correct-but-naive one.
• Off-by-one in the collapse threshold is a common mistake: it's n // 2, not n / 2 rounded up or n - 1; a schedule needs 2 distinct days per transaction, so n days support at most n // 2 non-overlapping transactions (floor division).
• The buy[j] = sell[j-1] - price recurrence is the crux most people get wrong on their own the first time: it's tempting to write buy[j] - price (buying doesn't "cost" anything against your own already-open position; it should reset from the state before this transaction started, i.e., sell[j-1], the profit banked from the previous, already-closed transaction).
• This is a good example of the topic's own boundary: the natural solution technique here is DP-style state tracking over transaction count, but the practical implementation is two flat arrays updated in a single array pass, not a full 2D recursive table, the same reasoning that keeps Kadane's algorithm and expand-around-center palindrome checks classified as array-manipulation technique rather than routed to a dedicated dynamic-programming topic.