Arrays, Strings, and Hashing Questions

Direct answer

Profile with tracemalloc (or a sampling profiler like py-spy for a live production process you cannot restart) to find which lines are allocating the most, then reduce churn by building strings incrementally into a preallocated buffer (io.StringIO, a list plus "".join(), or a bytearray/memoryview for byte-oriented data) instead of repeated concatenation, and only reach for rewriting the hot path in a compiled language like Go once profiling shows the Python-level allocation itself, not something else, is the bottleneck. To demonstrate improvement, compare allocation counts and bytes allocated before and after, not wall-clock time, since wall-clock measurements are too environment-dependent to be a reliable before/after signal on their own.

Structured elaboration

Profiling and identifying hotspots:

• tracemalloc (standard library): take a snapshot, run the workload, take a second snapshot, and compare them grouped by traceback (Snapshot.compare_to(..., "lineno")). This ranks allocation sites by net bytes and net object count, which is exactly "identify hotspots" turned into a concrete procedure.
• py-spy: a sampling profiler that attaches to an already-running process by PID, with no code changes and low enough overhead to run against production. This matters specifically in a Site Reliability Engineering (SRE) context, where the process causing the pressure may not be restartable or instrumentable on demand.
• objgraph: useful when the concern is object retention (things not being freed) rather than pure allocation churn, by showing what is holding references to a suspect object type.

A precision point that changes how you frame the problem to a team: plain Python str objects are refcounted, not tracked by the cyclic garbage collector (garbage collection, GC) at all, since they cannot hold references to other objects. Confirmed directly: gc.is_tracked("hello") returns False. This means transient string churn in CPython does not, by itself, increase cyclic-GC pause frequency the way churn of container objects (lists, dicts, custom class instances) can; it shows up instead as allocator (pymalloc) traffic, more time spent in malloc/free-equivalent bookkeeping, and heap fragmentation. Calling this "GC pressure" is common shorthand but is worth correcting precisely when advising a team, since it points them at the right tool (tracemalloc, allocator-level metrics) instead of the wrong one (gc.get_stats(), which reports on the cyclic collector).

Reducing allocations, in the order the question names them:

• bytearray/memoryview: bytearray is mutable, so appending to it does not create a new object each time the way immutable str concatenation can; memoryview lets you take zero-copy slices of existing buffer objects instead of allocating a new copy for every substring.
• io.StringIO: acts as a growable in-memory buffer with .write(), giving the same "accumulate then finalize" benefit as building a list and joining it, useful when the code is structured as many small writes rather than a clean list comprehension.
• Preallocated buffers / pooling: if the maximum size is known or bounded, allocate the buffer once outside the hot loop and reuse it, rather than allocating fresh per iteration or per request; this is the standard fix once profiling shows the same code path allocating repeatedly at high frequency.
• "".join(list_of_parts): append parts to a list (which CPython over-allocates geometrically, so appending is amortized $O(1)$) and join once at the end, rather than repeated += concatenation.
• Moving the hot path to a language with different allocation and escape-analysis behavior: Go's escape analysis can keep many short-lived values on the stack instead of the heap, avoiding per-object allocator overhead entirely for values that never need to outlive the function call; a hand-written C extension goes further still, giving full manual control over a single reused buffer with zero object-header overhead per string. Both are justified only once profiling has shown the allocation itself, not I/O or something else entirely, is the actual bottleneck.

Metrics to collect to demonstrate improvement:

• Net bytes allocated and net object count from tracemalloc snapshot comparisons, run against the same fixed workload before and after the change (a controlled, repeatable comparison, not a wall-clock timing claim).
• gc.get_stats() collection counts per generation, mainly as a sanity check that the change has not shifted pressure onto container types the cyclic collector does track, rather than as the primary signal for string-specific churn (per the precision point above).
• Process-level memory metrics already collected by most SRE tooling: resident set size (RSS) over time and page-fault counts, which reflect real allocator and operating-system-level cost.
• Downstream 95th/99th-percentile (P95/P99) request latency in production dashboards, correlated with the change's rollout, as the ultimate business-relevant signal, understanding that latency is influenced by many factors and is a correlation check, not a controlled experiment by itself.

Worked example

A controlled comparison of three approaches to building an 80,000-character string from 2,000 fixed 40-character pieces, counting reallocations directly via consecutive-identity comparison rather than timing anything:

import gc

N_ITEMS = 2000
ITEM = "x" * 40

print(f"gc.is_tracked('hello') = {gc.is_tracked('hello')}")

def count_reallocations_plus_equals(alias=False):
    s = ""
    history = [] if alias else None
    realloc_count = 0
    bytes_copied = 0
    prev_id = None
    for _ in range(N_ITEMS):
        if alias:
            history.append(s)  # keeps refcount(s) >= 2, defeating CPython's in-place resize fast path
        s += ITEM
        if id(s) != prev_id:
            realloc_count += 1
            bytes_copied += len(s)
        prev_id = id(s)
    return realloc_count, bytes_copied

def count_reallocations_join():
    parts = [ITEM for _ in range(N_ITEMS)]
    result = "".join(parts)
    return 1, len(result)

n_no_alias, bytes_no_alias = count_reallocations_plus_equals(alias=False)
n_alias, bytes_alias = count_reallocations_plus_equals(alias=True)
n_join, bytes_join = count_reallocations_join()

quadratic_upper_bound = sum(i * len(ITEM) for i in range(1, N_ITEMS + 1))
print(f"'+=' no alias  : reallocations = {n_no_alias:6d}, bytes copied = {bytes_no_alias:9d}")
print(f"'+=' aliased   : reallocations = {n_alias:6d}, bytes copied = {bytes_alias:9d}")
print(f"''.join(list)  : reallocations = {n_join:6d}, bytes copied = {bytes_join:9d}")
print(f"O(n^2) upper bound if every '+=' fully reallocated = {quadratic_upper_bound}")
print(f"aliased bytes-copied / no-alias bytes-copied = {bytes_alias / bytes_no_alias:.1f}x")
print(f"aliased bytes-copied / quadratic upper bound  = {bytes_alias / quadratic_upper_bound:.3f}")

Output (one representative run; counting via id(s) != prev_id rather than accumulating ids in a set matters here, because CPython can reuse a freed string's memory address for a later object, which silently under-counts reallocations if you count distinct id() values seen across the whole run instead of consecutive-call transitions):

gc.is_tracked('hello') = False
'+=' no alias  : reallocations =     36, bytes copied =    212200
'+=' aliased   : reallocations =   2000, bytes copied =  80040000
''.join(list)  : reallocations =      1, bytes copied =     80000
O(n^2) upper bound if every '+=' fully reallocated = 80040000
aliased bytes-copied / no-alias bytes-copied = 377.2x
aliased bytes-copied / quadratic upper bound  = 1.000

This is a genuinely interesting result, not the textbook story most candidates repeat: when nothing else holds a reference to the accumulating string, CPython's own refcount-1 fast path resizes the string in place for most iterations, so only a few dozen reallocations (36 in this run; repeated local runs varied between 36 and 37, with bytes copied varying correspondingly between roughly 212,200 and 277,720, since the fast path's exact behavior depends on the allocator's in-memory layout at the time) were actually needed for 2,000 concatenations, and total bytes copied is nowhere near the naive $O(n^2)$ bound in any of those runs. The moment something else holds a reference to the intermediate value on each iteration (history.append(s), simulating an innocuous-looking debug log or snapshot list elsewhere in the code), that fast path is completely defeated: exactly 2,000 reallocations occur every time (one per iteration, matching $N$ exactly) and the bytes-copied total lands at a ratio of 1.000 against the textbook quadratic bound, with no run-to-run variation

exactly matching the printed value, in every run. "".join() allocates exactly one object regardless. The practical lesson for an SRE debugging this in a real service: the dangerous pattern is not += concatenation itself, it is += concatenation where something else (a logger, a cache, a list of "recent values" for a debug endpoint) is quietly holding a reference to each intermediate string.

Trade-offs & pitfalls

• "Always use join, never +=" is oversimplified advice given what this measurement shows: in CPython specifically, single-owner += is often not the quadratic disaster it is in languages without that optimization. "".join() remains the right default because it is portable (not every Python implementation, such as PyPy in some configurations, guarantees the same optimization) and immune to accidental aliasing, but do not present the complexity claim as universally true across implementations without qualifying it.
• Reporting "reduced GC pressure" without the gc.is_tracked distinction can send a team optimizing the wrong layer. If the actual problem is generational-collector pause time, the fix is about reducing tracked-container churn (dicts, lists, custom objects), not string handling at all; conflating the two wastes an investigation cycle.
• Rewriting a hot path in Go or C is the highest-effort, highest-risk option on this list (new language, new deployment surface, a cross-language call boundary to maintain) and should be the last resort, justified by profiler evidence that the allocation itself, not serialization overhead, I/O wait, or something else in the same code path, is what dominates.
• A common measurement mistake: comparing wall-clock time for a "before" and "after" version on a shared, noisy production host and presenting the difference as the improvement. Machine load, CPU frequency scaling, and other tenants make single wall-clock comparisons unreliable; use allocation counts and bytes (as measured above) or repeated, controlled benchmarking on an isolated host as the primary evidence instead.

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

Walk the string once: skip leading whitespace, consume an optional sign, then consume digits until a non-digit character, converting as you go and clamping to the 32-bit signed integer range the moment the running value would exceed it. Overflow is detected before it happens, by comparing against a threshold, rather than by letting the value overflow and checking after the fact.

Structured elaboration

The parsing steps in order

1. Skip any leading space characters.
2. Read an optional + or -; anything else in that position (or nothing at all) means the sign defaults to positive.
3. Read consecutive digit characters, stopping at the first non-digit (including the end of the string). Everything after this point, including any trailing whitespace or trailing garbage characters, is ignored: there is no separate "trim the trailing spaces" step, because stopping the digit scan at the first non-digit already has the same effect as trimming, whatever comes after the last digit was never going to be parsed anyway.
4. If no digits were consumed at all, whether because the string was empty, all whitespace, or a sign with nothing after it, the result is invalid input and the function returns 0.
5. Apply the sign to the accumulated digits, then clamp to the 32-bit signed range: [-2147483648, 2147483647].

Detecting overflow without a big-integer library

The naive approach, accumulate the number as a normal machine integer and check afterward whether it exceeds the 32-bit range, does not work in a genuinely fixed-width language, because the multiplication and addition that build up the number can themselves overflow before you ever get to check. The safe pattern is to check BEFORE combining: given the current accumulated value num, the next digit d, and INT_MAX = 2147483647, the update num * 10 + d will exceed INT_MAX exactly when:

Since this comparison only involves num (kept within a checked range by this same rule applied to the previous digit) and small fixed constants, it never itself overflows, so you can safely bail out to the clamped INT_MAX (or INT_MIN for the negative sign) the moment the check trips, without ever needing arbitrary-precision arithmetic. In Python this exact discipline is not strictly required for correctness, since Python integers do not overflow, but it is exactly what a Java implementation of the same function needs: Java's int genuinely wraps around on overflow rather than raising an error, and Java's own Integer.parseInt throws a NumberFormatException on overflow rather than clamping, so a hand-rolled atoi in Java has to implement this check explicitly to match the clamp-on-overflow contract this problem asks for.

Treating invalid input

"Invalid" here specifically means: no digits were ever consumed. That covers an empty string, a string of only whitespace, a lone sign character with nothing after it, and a string that starts with a non-digit, non-sign, non-whitespace character. All of these return 0, matching the classic atoi contract; there is no exception path in this version of the problem.

Worked example

INT_MAX = 2**31 - 1
INT_MIN = -2**31

def string_to_int(s: str) -> int:
    i, n = 0, len(s)
    while i < n and s[i] == ' ':
        i += 1
    sign = 1
    if i < n and s[i] in '+-':
        if s[i] == '-':
            sign = -1
        i += 1
    digits_start = i
    num = 0
    while i < n and s[i].isdigit():
        digit = ord(s[i]) - ord('0')
        if num > (INT_MAX - digit) // 10:
            return INT_MAX if sign == 1 else INT_MIN
        num = num * 10 + digit
        i += 1
    if i == digits_start:
        return 0
    return sign * num

for t in ["42", "   -42", "4193 with words", "words and 987", "-91283472332", "91283472332"]:
    print(repr(t), "->", string_to_int(t))

Output:

'42' -> 42
'   -42' -> -42
'4193 with words' -> 4193
'words and 987' -> 0
'-91283472332' -> -2147483648
'91283472332' -> 2147483647

The last two lines show the overflow clamp firing correctly in both directions: 91283472332 is far larger than INT_MAX, and the function returns exactly 2147483647, not a wrapped or garbage value.

Trade-offs and pitfalls

The most common bug is checking for overflow AFTER the multiply-and-add, which is unsafe once you are in a language with real fixed-width integers, since the overflow has already corrupted the value by the time you inspect it. A second common mistake is forgetting that a sign character with no digits after it (just "-", or a sign followed only by more whitespace) must return 0, not treat the sign alone as meaningful. A third is stopping only at whitespace instead of at any non-digit, which mishandles inputs like "12a34" (should return 12, not attempt to parse further digits after the letter). Finally, remember this problem's clamp-and-return-0 behavior is a deliberate simplification for interview purposes: production-grade parsers, and most standard library functions, instead raise an exception on malformed or out-of-range input, so this should not be presented as how you would design a real parsing API, only as the exact contract this problem specifies.

Direct answer

Slide a fixed-size window of length len(p) across s, tracking the window's contents with two fixed-size frequency arrays (as the question specifies), one for p's required counts and one for the current window, indexed directly by character rather than through hashing. Updating the window incrementally (increment the entering character's slot, decrement the exiting character's slot) rather than rebuilding and comparing a fresh count every position is what makes this O(n) instead of O(n * |p|). Space is O(alphabet size): for lowercase English letters, that is a fixed 26 integers regardless of how long s or p are.

Algorithm

1. Build need, a length-26 array of p's character counts (need[ord(ch) - ord('a')] += 1 for each character in p).
2. Initialize window as the length-26 count array of s's first len(p) characters.
3. If window == need (array-to-array comparison), index 0 is a match.
4. Slide the window one character at a time: increment the slot of the character entering on the right, decrement the slot of the character leaving on the left, and compare window == need again after each slide.

def find_anagrams(s: str, p: str) -> list:
    len_s, len_p = len(s), len(p)
    if len_p > len_s:
        return []

    def index_of(ch):
        return ord(ch) - ord("a")

    need = [0] * 26
    window = [0] * 26
    for ch in p:
        need[index_of(ch)] += 1
    for ch in s[:len_p]:
        window[index_of(ch)] += 1

    result = []
    if window == need:
        result.append(0)

    for i in range(len_p, len_s):
        incoming, outgoing = s[i], s[i - len_p]
        window[index_of(incoming)] += 1
        window[index_of(outgoing)] -= 1
        if window == need:
            result.append(i - len_p + 1)
    return result

Using a fixed-size array indexed directly by ord(ch) - ord('a'), rather than a hash map keyed by the character, is exactly what "frequency array" means here: no hashing, no key deletion bookkeeping (a count naturally sits at 0 in an untouched slot, so there is nothing to clean up the way there would be with a dict-based count map), and the window == need comparison is a fixed-length list comparison, always exactly 26 elements, regardless of the alphabet actually observed in a given window. This assumes a known, bounded alphabet (lowercase English letters, size 26 here); for Unicode or an unbounded alphabet, a hash map keyed by character is the structure that scales with distinct characters actually seen instead of the size of the declared alphabet, at the cost of per-key hashing overhead.

Applications for substring pattern detection in tokenized text

The same fixed-size-window-plus-count-comparison technique applies directly to detecting "this window of tokens is a rearrangement of a target token multiset," which comes up in tasks like flagging text spans that contain exactly the same word multiset as a suspicious phrase (word-order-scrambled plagiarism or obfuscation detection) or matching a fixed-size set of required tags in a tokenized log line regardless of their order. The technique is identical, only the "character" unit changes to "token."

Worked example

def brute_force_find_anagrams(s, p):
    len_p = len(p)
    target = sorted(p)
    result = []
    for i in range(len(s) - len_p + 1):
        if sorted(s[i:i+len_p]) == target:
            result.append(i)
    return result

tests = ["cbaebabacd", "abab", "aaaaaaaaaa"]
patterns = ["abc", "ab", "aaa"]
for s, p in zip(tests, patterns):
    fast = find_anagrams(s, p)
    brute = brute_force_find_anagrams(s, p)
    print(f"find_anagrams({s!r}, {p!r}) = {fast}  (brute-force agrees: {fast == brute})")

Output (verified by execution, and cross-checked against an O(n * k log k) brute-force reference that sorts every window directly, so the fast result's correctness is independently confirmed rather than assumed):

find_anagrams('cbaebabacd', 'abc') = [0, 6]  (brute-force agrees: True)
find_anagrams('abab', 'ab') = [0, 1, 2]  (brute-force agrees: True)
find_anagrams('aaaaaaaaaa', 'aaa') = [0, 1, 2, 3, 4, 5, 6, 7]  (brute-force agrees: True)

Tracing s='cbaebabacd', p='abc' (need = {a:1, b:1, c:1}): the window at index 0 is "cba", whose counts exactly match need, so index 0 is recorded. Sliding to index 1 gives "bae", which introduces 'e' (not in need at all) so it fails to match. The window keeps sliding until index 6, "bac" (b,a,c), which again matches need exactly, giving the second recorded index. No other window in between matches because each contains either a repeated letter with the wrong count or a letter ('e', 'd') that need doesn't have at all.

Trade-offs and pitfalls

• Comparing two full 26-length arrays on every slide is itself O(alphabet size) per comparison, not O(1), so even though the alphabet here is small and fixed, this is not free; a common refinement is to track a single integer "how many of the 26 positions currently match between the two arrays" (the same trick used in minimum-window-substring problems), updated incrementally as each slide changes at most two positions, which turns the check into O(1) instead of O(26) per step.
• The frequency-array approach assumes a known, bounded alphabet. It is the right choice here (lowercase English letters) precisely because the question specifies it; for Unicode text or an unbounded token vocabulary, a hash map keyed by the actual character or token is what scales with distinct values seen, and switching to one is a straightforward substitution of the counting structure without changing the sliding-window logic itself.
• This is a fixed-size window, unlike minimum-window-substring's variable-size window: the window length here is always exactly len(p), which is simpler (no shrink/grow decision needed) but means the technique doesn't generalize to "smallest window containing X" problems without the additional grow/shrink logic those require.
• Edge cases: p longer than s (no window can exist, return empty immediately), p empty (depends on the problem's intended contract, typically treated as matching every position or explicitly disallowed), and heavily repeated characters in s (as in the 'aaaaaaaaaaaa'/'aaa' case above), which stress-test that the sliding update (not a full rebuild) is genuinely being used, since a naive re-slice-and-recount implementation would still pass correctness tests here but silently lose its performance advantage.

Direct answer

An array gives O(1) random access because an index maps directly to a memory address via arithmetic, but inserting or deleting anywhere except the very end requires shifting every following element, an O(n) operation. A singly linked list gives O(1) insert or delete once you already hold a reference to the relevant node, but finding that node in the first place (including "the middle") costs O(n), since there is no arithmetic shortcut, only following pointers one at a time.

Structured elaboration

• The "O(1) insert" caveat, worth stating explicitly. A linked-list insert or delete is only O(1) when you ALREADY have a reference to the right node, typically because you're iterating and acting as you go. If you're only given a numeric position (say, "insert at index 500,000"), you still have to walk there first, which costs O(n); claiming a flat "O(1) insert" without that condition is the single most common oversimplification of this comparison.
• Concrete scenario favoring the array. A lookup table mapping millions of user IDs to profile records, queried by index or key extremely frequently: O(1) random access is the whole point, and the data is rarely inserted into at arbitrary positions.
• Concrete scenario favoring the linked list. An eviction-order list for a cache, where an arbitrary, already-known node is frequently removed from the middle and a new node re-inserted at the front; both operations are O(1) once you hold the node reference, with no shifting cost regardless of list size.

Worked example

Consider inserting one new element at the FRONT of a collection holding 1,000,000 items. On an array, every one of the 1,000,000 existing elements must shift one position to make room, an O(n) cost that scales with however large the array has grown. On a singly linked list, the operation is exactly two pointer writes (the new node's next pointer, and the head pointer), regardless of whether the list holds 10 elements or 10,000,000: the cost does not grow with list size at all. This is the concrete shape of the O(n)-versus-O(1) difference in the table above, not just an abstract notation.

Trade-offs & pitfalls

• Memory overhead and cache locality. Each linked-list node carries at least one extra pointer (8 bytes on a 64-bit system) beyond its payload, and nodes are not stored contiguously in memory. For an iteration-heavy workload, an array is often noticeably faster IN PRACTICE despite both being asymptotically O(n), because sequential array access is cache-friendly while pointer-chasing a linked list typically is not; this is a constant-factor, hardware-driven effect, not a difference in asymptotic complexity.
• The most common oversimplification is stating "linked-list insert/delete is O(1)" without the caveat that this assumes the relevant node reference is already in hand; always confirm whether the scenario gives you the node or just a position.
• Singly linked lists only walk forward. Anything that needs "delete the node before this one" or other backward movement needs either a doubly linked list, or tracking a trailing pointer while iterating forward.
• Don't confuse this with dynamic-array append. A dynamic array (Python's list, Java's ArrayList) amortizes appending at the END to O(1) via geometric growth, which is a different operation from inserting at an ARBITRARY position; conflating the two is a common mistake when reasoning about array costs.