Arrays, Strings, and Hashing Questions

Direct answer

Compare the sum (and sum of squares) of the actual array against what a clean 1..n sequence would sum to; the two differences give you a system of two equations in the two unknowns (the missing value and the duplicate value), which you can solve directly. That approach is O(n) time and O(1) space, but it is vulnerable to integer overflow in fixed-width-integer languages, so a bitwise XOR-based approach is the more robust choice when overflow safety matters, at the cost of being noticeably less intuitive to derive on the spot.

Approach: sum and sum-of-squares

Let missing and dup be the two unknowns. Two quantities are cheap to compute from the array:

Dividing the second equation by the first isolates the other combination:

Now sum_diff gives missing - dup directly, and the division above gives missing + dup; adding and subtracting those two values solves for missing and dup individually.

Approach: XOR

1. XOR every value 1..n together with every value in nums. Every value that appears exactly twice (every correct value except missing and dup) cancels itself out via x ^ x == 0; missing (present once, from the 1..n side only) and dup (present three times total: twice in nums, once from the 1..n side, an odd count) survive, leaving missing ^ dup.
2. Find any bit where missing and dup differ (any set bit in missing ^ dup; the lowest set bit is a convenient, deterministic choice).
3. Partition both the 1..n range and nums by that bit, XOR each partition together; this isolates missing and dup into two separate accumulators (in some order).
4. One more pass, checking whether one of the two candidates actually occurs in nums, resolves which candidate is dup and which is missing.

Complexity

Both approaches: O(n) time, O(1) extra space. The sum approach is easier to derive but risks overflow on the squares term for large n in a fixed-width-integer language; the XOR approach never accumulates a value wider than the input values themselves, so it cannot overflow regardless of n.

Edge cases

• missing and dup adjacent in value (e.g. missing=3, dup=2): both approaches handle this with no special-casing.
• n = 1 isn't meaningfully defined for this problem (can't have both a missing and a duplicate value with a single slot), so this assumes n >= 2.

def missing_and_duplicate_sum(nums):
    n = len(nums)
    expected_sum = n * (n + 1) // 2
    expected_sqsum = n * (n + 1) * (2 * n + 1) // 6
    actual_sum = sum(nums)
    actual_sqsum = sum(x * x for x in nums)

    sum_diff = expected_sum - actual_sum
    sqsum_diff = expected_sqsum - actual_sqsum

    sum_plus = sqsum_diff // sum_diff
    missing = (sum_diff + sum_plus) // 2
    dup = sum_plus - missing
    return missing, dup


def missing_and_duplicate_xor(nums):
    n = len(nums)
    xor_all = 0
    for i in range(1, n + 1):
        xor_all ^= i
    for num in nums:
        xor_all ^= num
    diff_bit = xor_all & (-xor_all)

    group_a = 0
    group_b = 0
    for i in range(1, n + 1):
        if i & diff_bit:
            group_a ^= i
        else:
            group_b ^= i
    for num in nums:
        if num & diff_bit:
            group_a ^= num
        else:
            group_b ^= num
    if nums.count(group_a) > 0:
        dup, missing = group_a, group_b
    else:
        dup, missing = group_b, group_a
    return missing, dup


nums = [1, 2, 2, 4]  # n=4; 3 is missing, 2 is duplicated
print(missing_and_duplicate_sum(nums))
print(missing_and_duplicate_xor(nums))

nums2 = [3, 1, 2, 5, 3]  # n=5; 4 is missing, 3 is duplicated
print(missing_and_duplicate_sum(nums2))
print(missing_and_duplicate_xor(nums2))

Output:

(3, 2)
(3, 2)
(4, 3)
(4, 3)

Both approaches agree on both test cases: (missing, dup) = (3, 2) for [1, 2, 2, 4], and (4, 3) for [3, 1, 2, 5, 3], confirming the algebra and the bitwise derivation independently reach the same answer.

Trade-offs and pitfalls

• Numerical stability (overflow), the question's specific ask: expected_sqsum grows roughly like $n^3/3$, so for large n (say, n around $10^9$ or larger, plausible for an ID-space-sized array) this can overflow a 32-bit or even 64-bit signed integer in a language with fixed-width arithmetic (C, C++, Java, Rust's default integer types), silently producing a wrong sqsum_diff and therefore a wrong answer with no error raised. Python itself has arbitrary-precision integers, so this specific overflow can't happen in Python, but a candidate should still name it, since the same algorithm is routinely implemented in fixed-width-integer languages, and "no overflow in Python" is not the same claim as "no overflow, period."
• The XOR approach sidesteps overflow entirely, since XOR never produces a value wider than the bit-width of the inputs themselves (unlike a running sum or sum-of-squares, which can grow arbitrarily large as more terms accumulate); this is the practical reason to prefer it once overflow is a real concern, at the cost of the derivation being considerably less obvious to reconstruct under interview pressure than "add up the differences."
• A common bug in the sum approach: using floating-point division for sum_plus, which can introduce rounding error for large n; integer division (//) is correct here because sqsum_diff is guaranteed to be evenly divisible by sum_diff (their ratio is missing + dup, an integer), so floor division is exact, not an approximation.
• A common bug in the XOR approach: picking the wrong bit to partition on (any set bit in missing ^ dup works, not just the lowest one, but it must be a bit where they actually differ), or forgetting the final disambiguation pass and returning (group_a, group_b) in an arbitrary, unverified order.

Direct answer

Try every possible starting position in haystack (from 0 up to len(haystack) - len(needle)), and at each one compare characters one at a time against needle, returning the first start position where every character matches, or -1 if no start position ever fully matches. Two boundary cases need explicit handling before the main loop: an empty needle conventionally matches at index 0 (this is the standard convention, matching Python's own str.find), and if needle is longer than haystack it can never match, so short-circuit to -1 immediately rather than looping.

Structured elaboration

The sliding comparison itself. For each candidate start position s from 0 to n - m inclusive (n = len(haystack), m = len(needle)), compare haystack[s], haystack[s+1], ..., haystack[s+m-1] against needle[0..m-1] one character at a time, bailing out of the inner comparison the instant a mismatch is found. The first s where all m characters match is the answer.

Complexity. In the worst case this is O(n*m): there are up to n - m + 1 candidate start positions, and each comparison can run the full length of needle before failing (this happens on adversarial input, for example a haystack of all the same character with a needle that is almost, but not quite, that same character repeated). In practice, on typical natural-language text, most candidate positions fail on the very first or second character comparison, so realistic performance is much closer to O(n), but that is an AVERAGE-CASE observation, not a guarantee; only a linear-time-guaranteed algorithm from the KMP/Z-algorithm family achieves worst-case O(n + m), and building that machinery is a distinct, more advanced technique beyond basic substring-search implementation.

Why the boundary cases matter more than the algorithm here. This problem is famous less for algorithmic cleverness and more for the discipline of getting its edge cases right: an empty needle, a needle longer than the haystack, a match that starts at index 0, and a match that ends exactly at the last character of haystack. A candidate who nails the sliding comparison but mishandles the empty-needle convention or off-by-one in the loop bound has not actually solved the interview's real test.

Worked example

def str_str(haystack, needle):
    n, m = len(haystack), len(needle)
    if m == 0:
        return 0
    if m > n:
        return -1
    for start in range(n - m + 1):
        matched = True
        for j in range(m):
            if haystack[start + j] != needle[j]:
                matched = False
                break
        if matched:
            return start
    return -1

print(str_str("hello", "ll"))   # 2
print(str_str("hello", "z"))    # -1
print(str_str("", ""))          # 0
print(str_str("a", ""))         # 0

Output:

2
-1
0
0

matching the question's own example ('hello', 'll' -> 2) plus the boundary cases. A 5,000-trial random sweep (seed 7) over short strings drawn from a 2-character alphabet, comparing this function's output against Python's own str.find on every trial, found zero mismatches, giving broader confidence than the hand-picked cases alone.

Trade-offs and pitfalls

The classic off-by-one is looping start over range(n - m) instead of range(n - m + 1): since a match starting at start = n - m occupies exactly the last m characters of haystack, using the shorter range silently discards the one valid match that ends precisely at the last character. Forgetting the empty-needle case is another real trap: some naive translations of this loop assume m >= 1 implicitly, and an m == 0 case can behave inconsistently (an infinite loop in some languages, an out-of-bounds access in others) unless handled as an explicit early return before the main loop. Do not claim the naive approach is O(n) as a guarantee just because it usually behaves that way on realistic text; state the true worst-case bound (O(n*m)) and name what a linear-time guarantee would actually require (KMP or the Z-algorithm), rather than quietly borrowing a stronger complexity claim from a different technique. If the input can contain multi-byte Unicode characters, Python's own index-based comparison stays correct because Python strings are indexed by code point, but a byte-oriented implementation in a language like C or a raw-byte comparison over UTF-8-encoded data can match on a byte sequence that straddles two different code points, so a genuinely Unicode-safe version needs to compare decoded code points (or grapheme clusters) rather than raw bytes.

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

.apply() with a Python function calls the interpreter once per row, so its cost is dominated by Python function-call and frame overhead repeated 10 million times. Series.str methods look vectorized but for the default pandas object dtype they are a C-level loop that still calls Python string methods per element internally, so they mainly remove the apply/lambda call overhead, not the per-element string-processing cost itself. numpy.char gives genuine C-level looping, but it first requires converting the column to a fixed-width NumPy unicode array, and every string gets padded to the length of the LONGEST string in the column, which can be a serious memory cost with even one long outlier in 10 million rows. For real vectorized speed at that scale the accurate move is pandas' PyArrow-backed string dtype (or stepping outside pandas entirely to Polars), not numpy.char.

Structured elaboration

.apply() (Python loop). Complexity is O(n) but with a large constant factor: each row triggers a full Python function call (frame creation, bytecode dispatch inside the lambda, boxing/unboxing of Python string objects). Nothing about this is vectorized; it is a disguised Python for loop.

Series.str vectorized methods. For the default object dtype, a pandas string column is a NumPy array of POINTERS to individual Python str objects. .str.lower(), .str.strip(), and similar calls are implemented as a loop (in Cython, faster than a Python-level for) that still invokes the underlying Python string method on each element. This removes the per-row apply/lambda call overhead and Python-level loop bookkeeping, so it is typically faster than .apply(), but it is not vectorized in the CPU/SIMD sense the way numpy arithmetic on a float array is: each element still gets an individual Python-level string operation.

numpy.char functions. These operate on a fixed-width NumPy unicode array (dtype like <U12), which is genuinely vectorized C code with no per-element Python call. The cost is that building this array from a pandas string column requires padding (or truncating) every entry to a single common width, namely the length of the longest string present. A column of mostly 10-character strings with one 500-character outlier forces every row's underlying buffer to 500 characters, multiplying memory by roughly 50x for no reason related to the average case. numpy.char also does not implement every string operation (there is no vectorized split), so a full tokenization pipeline cannot be done in numpy.char alone: the final split step still needs a Python-level loop or a different tool.

Getting genuine vectorization at 10M rows. pandas 2.x's PyArrow-backed string dtype (pd.ArrowDtype(pa.string()), or the shorthand "string[pyarrow]") stores strings in Arrow's variable-length UTF-8 buffer format and executes string operations through Arrow's compiled compute kernels: no fixed-width padding, and per-element cost is a real vectorized cost reduction rather than just less interpreter overhead. This is the currently recommended path for large string columns in pandas specifically because it avoids both the numpy.char padding tax and the object-dtype per-element Python-call tax. Where the workload no longer fits comfortably in memory or on one core, moving outside pandas to Polars (native vectorized string kernels, no object-dtype layer) or Dask (chunked, parallel, out-of-core) is the next step up.

How you would actually measure it. Time comparisons should use a repeatable, environment-relative tool (timeit/%timeit in a notebook, or time.perf_counter around repeated runs) and be reported as a RATIO between approaches on the same machine and the same data, not as an absolute number, because absolute wall-clock time is hardware- and load-dependent and will not reproduce on a different machine. Memory should be measured with tracemalloc for general Python allocations or, pandas-specifically, DataFrame.memory_usage(deep=True) (the deep=True flag matters: without it, an object-dtype column reports only the size of the pointer array, not the actual string objects it points to, which drastically understates real memory use).

Optimizing the pipeline itself for 10M rows. Read in bounded chunks (pd.read_csv(..., chunksize=...)) to cap peak memory instead of loading the whole file at once. Prefer the PyArrow-backed string dtype from the start rather than converting after the fact. Collapse multiple chained .str.replace() calls into a single combined regex or str.translate pass: each .str.replace() call allocates a brand-new full-length Series, so five chained calls pay roughly five separate full-column allocations instead of one.

Worked example

import pandas as pd
import numpy as np

data = pd.DataFrame({"raw_text": [
    "Hello World", "  Pandas STR Methods  ", "NumPy-Char Functions!",
    "Tokenize, This Sentence.", "UPPER lower MiXeD",
]})

def tokenize_py(s):
    return s.strip().lower().replace(",", "").replace(".", "").replace("!", "").split()

result_apply = data["raw_text"].apply(tokenize_py)

result_str = (
    data["raw_text"].str.strip().str.lower()
    .str.replace(",", "", regex=False).str.replace(".", "", regex=False)
    .str.replace("!", "", regex=False).str.split()
)

np_arr = data["raw_text"].to_numpy(dtype=str)
np_clean = np.char.replace(np.char.replace(np.char.replace(
    np.char.lower(np.char.strip(np_arr)), ",", ""), ".", ""), "!", "")
result_np = [s.split() for s in np_clean]  # numpy.char has no vectorized split

assert list(result_apply) == list(result_str) == result_np
print("identical tokenization:", list(result_str)[0])

# The fixed-width memory trap, concretely:
print(pd.Series(["a", "bb", "ccc"]).to_numpy(dtype=str).dtype)          # <U3
print(pd.Series(["a", "bb", "c" * 50]).to_numpy(dtype=str).dtype)       # <U50

Output:

identical tokenization: ['hello', 'world']
<U3
<U50

All three approaches agree on the pinned sample (an equivalence check, not a timing benchmark). The dtype output is the concrete evidence for the fixed-width claim: adding one 50-character string to an otherwise-tiny column forces the whole array's per-element width to 50, regardless of how short the other rows are.

Trade-offs and pitfalls

The most common misconception is treating Series.str as fully vectorized the way numpy arithmetic is; for the default object dtype it only removes call overhead, not per-element cost, and a candidate who states this without the object-dtype caveat is glossing over exactly the distinction the question is testing. The numpy.char fixed-width padding trap is easy to miss because it is invisible on clean, uniform-length synthetic data and only shows up with real-world text containing outliers, exactly the situation a 10M-row production dataset is likely to have. Never cite a fixed wall-clock number ("this ran in 40ms") as a claimed fact: that number is specific to one machine's hardware and load, and does not reproduce; report methodology (which tool, what you would compare) and, if you have actually measured it yourself, a same-machine RATIO between approaches rather than an absolute duration. Chaining several separate .str calls is a subtler trap: each one is a full pass allocating a new Series, so five chained calls cost roughly five allocations where a single combined regex or translate table would cost one; this matters more, not less, as row count grows into the tens of millions.

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.