Arrays, Strings, and Hashing Questions

Direct answer

Use a read/write two-pointer: walk the array once with a read index, and every time you see a value that isn't val, copy it into the next open slot tracked by a write index. The write index at the end is the new length. Whether order must be preserved decides which of two variants you use: the read/write copy above preserves the original relative order in O(n) writes; if order doesn't matter, you can instead swap a matching element with the current last element and shrink the array, which does fewer writes when val is rare.

Approach

1. Order-preserving (read/write two-pointer): write starts at 0. For each read index in order, if nums[read] != val, copy it to nums[write] and advance write. Every kept element lands in its original relative order, one slot earlier than or at its original position.
2. Order-not-preserved (swap-with-last): keep a shrinking logical length n. When nums[i] == val, overwrite it with nums[n-1] (the current last element) and shrink n by one, without advancing i (the swapped-in element still needs to be checked). When nums[i] != val, advance i. This does one write per removal instead of potentially shifting every later element, which is cheaper when matches are rare and scattered.
3. Both mutate nums in place and return the new length; elements at or past the returned length are not meaningfully defined afterward.

Complexity

Both variants: O(n) time (single pass), O(1) extra space. The order-preserving version always does one write per surviving element; the swap variant does one write per removed element, which is fewer when val is rare.

Edge cases

• val not present at all: every element is kept, new length equals original length, zero writes beyond the initial pass.
• All elements equal val: new length is 0.
• Empty input: returns 0 immediately.

def remove_element(nums, val):
    write = 0
    for read in range(len(nums)):
        if nums[read] != val:
            nums[write] = nums[read]
            write += 1
    del nums[write:]
    return write


def remove_element_unordered(nums, val):
    i = 0
    n = len(nums)
    while i < n:
        if nums[i] == val:
            n -= 1
            nums[i] = nums[n]
        else:
            i += 1
    del nums[n:]
    return n


payload = [4, 2, 5, 2, 7, 2, 9]
k = remove_element(payload, 2)
print(k, payload)

payload2 = [4, 2, 5, 2, 7, 2, 9]
k2 = remove_element_unordered(payload2, 2)
print(k2, payload2)

Output:

4 [4, 5, 7, 9]
4 [4, 9, 5, 7]

Both agree on the count (4 surviving elements), but the surviving values land in different positions: [4, 5, 7, 9] keeps the original left-to-right order, while [4, 9, 5, 7] does not (9 moved from the end into an earlier slot during a swap), which is exactly the trade-off the question is asking about.

Trade-offs and pitfalls

• A common bug: using list.remove(val) or deleting elements from the middle of the array inside a loop, which is O(n) per removal (everything after the deletion point shifts down), making the whole operation O(n^2) in the worst case, and it also skips the next element if you don't adjust the loop index after a deletion. The two-pointer approaches here avoid both problems.
• The same read/write two-pointer technique applies directly to low-level, fixed-size buffers, not just Python lists. In C, given a null-terminated char *s, removing all space characters in place is the identical idea: a write index and a read index both walk the buffer, the write index only advances when the current character should be kept, and a null terminator is placed at the final write position. There's no list-resize step (del nums[write:]) because a C string doesn't carry a separate length field the way a Python list does; the null terminator is the length.
• Backend-cleanup framing from the question: "compacting payload arrays before storage" is exactly the order-preserving case if the array represents an ordered sequence (e.g. a time-ordered log) where reordering would corrupt meaning, or the order-not-preserved case if it's an unordered set of records where minimizing writes matters more than position.

Direct answer

A straightforward recursive flatten walks the nested structure, recursing into every sub-list and appending every non-list element directly to the result. It is correct and easy to read, but its recursion depth equals the input's NESTING depth, not its total element count, so an extremely deeply nested input (thousands of levels of [[[...]]]) can exceed the language's recursion limit and crash with a stack overflow, even though the total amount of data is tiny. An iterative version using an explicit stack does the identical traversal without ever growing the call stack, and handles arbitrary nesting depth safely.

Structured elaboration

The recursive approach

For each item in the input list: if it is itself a list, recursively flatten it and extend the result with what comes back; otherwise, append it directly. This mirrors the problem's own recursive structure (a nested list is either an element or a list of nested lists) almost exactly, which is why it reads so naturally, but that same one-to-one mirroring is exactly what ties its stack depth to the input's nesting depth.

Why recursion depth is the real concern here

Python's default recursion limit, retrievable via sys.getrecursionlimit(), is 1000. This limit exists to protect the underlying interpreter stack from being exhausted, which would crash the process outright rather than raising a catchable Python exception; the recursion limit is what turns that hard crash into a catchable RecursionError instead. A list nested 1500 levels deep, [[[...[1]...]]], has only a single element, but flattening it recursively requires 1500 nested calls, comfortably past the default limit, so the recursive version raises RecursionError on an input that is trivially small in terms of total data.

The iterative alternative with an explicit stack

Replace the call stack with an explicit Python list acting as a stack, where each stack entry is an ITERATOR over one level of nesting rather than a raw list. Repeatedly pull the next item from the iterator at the top of the stack: if it is a list, push an iterator over IT onto the stack and continue; if it is a plain element, append it to the result; if the top iterator is exhausted, pop it off and continue with whatever is now on top. This performs the exact same traversal as the recursive version, but the "depth" it tracks lives on the heap (as entries in the stack list), bounded only by available memory, not by the interpreter's fixed recursion limit.

Worked example

import sys

def flatten(nested):
    result = []
    for item in nested:
        if isinstance(item, list):
            result.extend(flatten(item))
        else:
            result.append(item)
    return result

def flatten_iterative(nested):
    result = []
    stack = [iter(nested)]
    while stack:
        top = stack[-1]
        try:
            item = next(top)
        except StopIteration:
            stack.pop()
            continue
        if isinstance(item, list):
            stack.append(iter(item))
        else:
            result.append(item)
    return result

example = [1, [2, [3, 4], 5], 6]
print(flatten(example))
print(flatten_iterative(example))

depth = sys.getrecursionlimit() + 500
deeply_nested = 1
for _ in range(depth):
    deeply_nested = [deeply_nested]

try:
    flatten(deeply_nested)
    print("recursive: no error")
except RecursionError:
    print("recursive: RecursionError")

print("iterative:", flatten_iterative(deeply_nested))

Output:

[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
recursive: RecursionError
iterative: [1]

Both implementations agree exactly on the question's own example, [1, [2, [3, 4], 5], 6] -> [1, 2, 3, 4, 5, 6]. The recursion-depth concern is demonstrated directly, not just asserted: building a list nested 500 levels past the default recursion limit and flattening it recursively does raise RecursionError (confirmed against Python's default limit of 1000), while the iterative version flattens the exact same deeply nested input to [1] without any error.

Trade-offs and pitfalls

Raising sys.setrecursionlimit() to a larger number is a tempting quick fix, but it does not remove the underlying risk, it only moves the crash point further out, and pushing it too far can crash the whole PROCESS with a C-level stack overflow instead of a catchable Python exception, since the interpreter's own limit exists specifically to stay within the real stack memory available. The iterative version is the more ROBUST general answer for this reason: it trades a small amount of code complexity, managing an explicit stack of iterators rather than relying on the language's call stack, for a traversal that cannot fail on input shape alone, only on genuinely running out of memory. Also worth naming: neither version currently guards against a value that is directly self-referential (a list containing itself), which would recurse or loop forever regardless of which approach is used; that is a distinct edge case from nesting depth and would need explicit cycle detection if the input could ever be adversarial or attacker-controlled rather than merely deeply nested.

Direct answer

Read the input in fixed-size chunks (not the whole stream at once), strip any whitespace or newlines from each chunk, and only decode the largest prefix of accumulated characters that is a multiple of 4 (one base64 "quantum"). Carry the leftover 0-3 characters forward to be combined with the next chunk. This bounds memory use to the chunk size regardless of how large the input stream is, and correctly reproduces the standard library's own base64.b64decode output on the full data.

Structured elaboration

Why a naive whole-input decode does not work here: base64.b64decode (and equivalents in other languages) requires the entire encoded string in memory first. The question explicitly asks for constant extra memory proportional to block size, so the decode has to happen incrementally as bytes arrive.

The three things that make streaming base64 harder than streaming raw bytes:

1. Base64 decodes in fixed-size groups of 4 encoded characters to 3 raw bytes. You cannot decode a partial group, so any chunk boundary that splits a group of 4 has to be handled by holding the incomplete tail back and prepending it to the next chunk.
2. Whitespace and newlines are not part of the base64 alphabet but commonly appear in real-world encoded data (classic MIME-style line wrapping at 76 characters, for example). These must be filtered out per chunk, not just once at the start, since they can appear anywhere.
3. Padding (=) only ever appears at the very end of the full encoded string, so it naturally falls out of the last "leftover" group processed, no special-casing is needed beyond decoding whatever is left when the stream ends.

Algorithm:

• Maintain a small leftover byte buffer (0 to 3 bytes) carried between reads.
• On each read of block_size bytes: strip whitespace, prepend leftover, decode the largest prefix that is a multiple of 4, write the decoded bytes to the output stream, and save the remainder as the new leftover.
• After the input is exhausted, decode any final leftover (a well-formed base64 stream always leaves a multiple-of-4 remainder including padding at the true end).

Worked example

import base64

def streaming_b64_decode(in_stream, out_stream, block_size=4096):
    assert block_size % 4 == 0, "block_size must be a multiple of 4"
    leftover = b""
    while True:
        raw = in_stream.read(block_size)
        if not raw:
            break
        if isinstance(raw, str):
            raw = raw.encode("ascii")
        cleaned = bytes(c for c in raw if c not in b" \t\r\n")
        chunk = leftover + cleaned
        usable_len = (len(chunk) // 4) * 4
        usable, leftover = chunk[:usable_len], chunk[usable_len:]
        if usable:
            out_stream.write(base64.b64decode(usable))
    if leftover:
        out_stream.write(base64.b64decode(leftover))

# Pinned verification: random payloads of varying sizes, MIME-style 76-char line
# wrapping injected to exercise whitespace handling, decoded with an artificially
# small block_size=8 to force many chunk boundaries, compared byte-for-byte
# against base64.b64decode() run on the whole un-streamed input.
import io, random
random.seed(1234)

def make_test_payload(n_bytes):
    return bytes(random.randrange(0, 256) for _ in range(n_bytes))

for n in [0, 1, 2, 3, 4, 100, 1000, 12345]:
    payload = make_test_payload(n)
    encoded = base64.b64encode(payload)
    wrapped = b"\n".join(encoded[i:i+76] for i in range(0, len(encoded), 76))
    in_buf, out_buf = io.BytesIO(wrapped), io.BytesIO()
    streaming_b64_decode(in_buf, out_buf, block_size=8)
    decoded = out_buf.getvalue()
    reference = base64.b64decode(encoded)
    print(f"n_bytes={n:6d} encoded_len={len(wrapped):6d} matches_reference={decoded == reference == payload}")

Output:

n_bytes=     0 encoded_len=     0 matches_reference=True
n_bytes=     1 encoded_len=     4 matches_reference=True
n_bytes=     2 encoded_len=     4 matches_reference=True
n_bytes=     3 encoded_len=     4 matches_reference=True
n_bytes=     4 encoded_len=     8 matches_reference=True
n_bytes=   100 encoded_len=   137 matches_reference=True
n_bytes=  1000 encoded_len=  1353 matches_reference=True
n_bytes= 12345 encoded_len= 16676 matches_reference=True

Every case, including the empty input and inputs whose length is not a multiple of 3 (which is exactly what produces = padding), matched the standard library's non-streaming decoder exactly.

Trade-offs & pitfalls

• block_size must be a multiple of 4. If it is not, the "largest usable multiple of 4" logic still works correctly (it is computed dynamically from the accumulated chunk, not assumed from block_size directly), but choosing a multiple of 4 up front avoids an unnecessary one-off adjustment and keeps the memory bound exactly predictable.
• The leftover buffer is the entire reason this works, and it is easy to get wrong by resetting it every read instead of carrying it forward. That specific bug silently corrupts output only when a chunk boundary happens to fall mid-group, which makes it easy to miss with small test inputs that fit in a single chunk.
• Memory is bounded by chunk size, not stream size, which is the whole point for very large files, but this means you cannot validate the base64 alphabet or overall structure ahead of time the way an in-memory decode implicitly does; invalid characters are only caught when base64.b64decode raises on the chunk containing them, so error messages will reference a chunk-relative position, not a position in the original stream, unless you track a running byte offset yourself.
• This does not parallelize trivially. Because state (the leftover bytes) carries across chunks, you cannot decode arbitrary byte ranges independently the way you could with a format that has self-describing block boundaries; splitting work across threads requires aligning split points to 4-character boundaries first.

Direct answer

If every element is guaranteed non-negative, a sliding window works: grow the window's sum, and shrink from the left whenever the sum overshoots the target, because adding a non-negative element can only increase or hold the sum, so shrinking is guaranteed to monotonically decrease it. Once negative numbers are allowed, that monotonicity breaks, so the general solution instead tracks prefix sums in a hash map: if prefix[i] - prefix[j] == target, the subarray from j+1 to i sums to target, so scanning once while checking whether running_sum - target has been seen before as an earlier prefix sum finds the answer in O(n) time and O(n) space.

Positive-only case: sliding window

def subarray_indices_positive_only(nums, target):
    left = 0
    running = 0
    for right, val in enumerate(nums):
        running += val
        while running > target and left <= right:
            running -= nums[left]
            left += 1
        if running == target:
            return (left, right)
    return None

This relies entirely on non-negativity: shrinking the window (removing nums[left]) can only decrease running, so the while running > target loop is guaranteed to terminate at a sum that is <= target, and if it lands exactly on target, that's a valid answer. With negative numbers present, removing an element from the left could just as easily increase the running sum as decrease it, so there is no longer a reliable direction to shrink in.

General case (including negatives): prefix sum plus hash map

def subarray_indices_prefix_hashmap(nums, target):
    prefix_to_index = {0: -1}   # empty prefix (before index 0) sums to 0
    running = 0
    for i, val in enumerate(nums):
        running += val
        needed = running - target
        if needed in prefix_to_index:
            return (prefix_to_index[needed] + 1, i)
        if running not in prefix_to_index:
            prefix_to_index[running] = i
    return None

The {0: -1} seed entry is what lets a subarray starting at index 0 be found correctly: it represents "the prefix sum before any elements have been added is 0," so if running itself ever equals target, needed = running - target = 0 is already in the map, pointing to index -1, giving a correct start index of 0. The if running not in prefix_to_index guard only stores the first occurrence of each prefix sum, which is what guarantees the returned subarray is as long as possible from that starting point rather than an arbitrarily chosen one (though any correct pair satisfies "sums to target"; the problem only asks for existence, not the shortest or longest one).

Worked example

def brute_force_subarray_indices(nums, target):
    n = len(nums)
    for i in range(n):
        s = 0
        for j in range(i, n):
            s += nums[j]
            if s == target:
                return (i, j)
    return None

r1 = subarray_indices_positive_only([1, 2, 3, 4, 5], 9)
r2 = subarray_indices_prefix_hashmap([1, -1, 5, -2, 3], 3)
print(r1, " (brute-force cross-check:", brute_force_subarray_indices([1, 2, 3, 4, 5], 9), ")")
print(r2, " (brute-force cross-check:", brute_force_subarray_indices([1, -1, 5, -2, 3], 3), ")")

Output (verified by execution, both cross-checked against an O(n^2) brute-force reference that tries every contiguous subarray directly):

(1, 3)  (brute-force cross-check: (1, 3) )
(0, 3)  (brute-force cross-check: (0, 3) )

For [1, 2, 3, 4, 5], target 9: the window grows through [1], [1,2], [1,2,3] to [1,2,3,4] (sum 10), which overshoots; one shrink step drops the leading 1, bringing the sum to exactly 9 with the window now [2,3,4] (indices 1-3), which matches immediately, returning (1, 3). For [1, -1, 5, -2, 3], target 3: the running prefix sums as the scan proceeds are 1, 0, 5, 3 (indices 0-3), with needed = running - target at each step -2, -3, 2, 0. At i=3, needed = 0, which IS in the map, but crucially it maps to index -1 (the seed entry), not index 1 (where prefix sum 0 also occurs, at i=1, from 1 + -1 = 0): the if running not in prefix_to_index guard means that once index -1 claims prefix-sum 0, the later occurrence at index 1 is never allowed to overwrite it. So the match resolves to (-1 + 1, 3) = (0, 3), i.e., the subarray [1, -1, 5, -2], which does sum to 1 + -1 + 5 + -2 = 3.

Trade-offs and pitfalls

• The sliding window is NOT a valid fallback once any negative number can appear, even a single one. A frequent mistake is applying the two-pointer shrink logic to "mostly positive" data and only breaking on adversarial inputs; the moment even one negative value is possible, the general prefix-sum-plus-hashmap approach is required for correctness, not just performance.
• The {0: -1} seed entry is the single most commonly dropped detail. Without it, any subarray that must start at index 0 is silently missed, because there is no recorded "prefix sum before the array starts" to subtract against.
• Storing only the first occurrence of each prefix sum (via the if running not in prefix_to_index guard) is a deliberate choice, not an accident: if the problem instead asked for the shortest subarray summing to target, this is exactly right; if it asked for the count of subarrays summing to target (a related but different problem), the correct approach is to track counts, not indices, and accumulate every match rather than returning early on the first one.
• Return-value ambiguity: this implementation returns any one valid subarray's indices (existence), which matches what the question asks; a caller wanting all valid subarrays, or the shortest, or the count, needs a variant of this same prefix-sum idea, not a fundamentally different algorithm.

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.