Arrays, Strings, and Hashing Questions

Direct answer

In Python and Java, strings are immutable: every operation that looks like a modification, concatenation, replacing a character, actually allocates a new string object, leaving the original untouched. In C++, std::string is mutable by design: it supports true in-place modification of its own buffer. That single difference changes how you write efficient string-processing code: Python and Java favor building output through a mutable intermediate (a list of pieces, or Java's StringBuilder) and converting to a string once at the end, while C++ can often modify a std::string directly without ever needing that intermediate.

Structured elaboration

What mutable and immutable mean here

An immutable string type guarantees that once created, the sequence of characters it represents never changes. Any apparent edit, s = s + "x" in Python, s = s.concat("x") in Java, produces a brand new string object; the variable name is simply reassigned to point at it. A mutable string type, std::string in C++, or Java's StringBuilder/StringBuffer (which exist specifically because String itself is immutable), allows the underlying character buffer to be changed directly, without creating a new object each time.

How this affects algorithm design

For a problem like "reverse this string in place," C++ can genuinely reverse the existing std::string buffer with a two-pointer swap and zero extra allocation. The identical-looking task in Python or Java cannot touch the original string object at all, since it is immutable; the practical in-place technique is to convert to a mutable structure first, a list of characters in Python, a char[] or StringBuilder in Java, perform the two-pointer swap on THAT structure, and only build a new string from it at the very end. This is why coding-interview answers to "reverse a string in place" in Python conventionally operate on list(s): that satisfies the spirit of in-place swapping even though the original str object could never have been mutated directly.

Time complexity and memory usage

Because every "modification" of an immutable string allocates a new object sized to the result, repeated modification in a loop, appending a small piece to a string n times, costs O(n) time for a single append but can cost O(n^2) time in total across n iterations if done naively, since each append copies everything accumulated so far into the new object. A std::string or a StringBuilder/list-based accumulator instead grows its internal buffer with amortized doubling, giving O(n) total time cost for n appends, since only the buffer's OWN internal reallocation is doubling-based, not a full-string copy on every single append. The memory usage story mirrors the time complexity one: the immutable-string approach transiently holds BOTH the old and new copies at every step (peak memory proportional to the final size, plus churn from every discarded intermediate copy needing garbage collection), while the mutable-accumulator approach holds only the one growing buffer, at some points with a bit of unused reserved capacity from the last doubling.

Worked example

s = "hello"
before_id = id(s)
s = s + " world"
after_id = id(s)
print(before_id != after_id)   # True: concatenation created a new object

lst = [1, 2, 3]
lst_id_before = id(lst)
lst.append(4)
lst_id_after = id(lst)
print(lst_id_before == lst_id_after)   # True: append mutated the SAME object

Output:

True
True

The first check confirms that s + " world" really did allocate a new string object (the identity changes), demonstrating immutability directly rather than just asserting it. The second confirms the contrasting case: a Python list, which is mutable, keeps the same object identity across an in-place append. The equivalent contrast in C++ would show std::string::operator+= modifying the SAME underlying buffer (when capacity allows) rather than always allocating a new one, which is the concrete behavioral difference this question is asking about.

Trade-offs and pitfalls

A frequent mistake in interviews is claiming a Python or Java "in-place" string function actually mutates the original string object, when what really happened is the function returned a new string; the answer needs to be explicit about that distinction. Another is assuming C++'s mutability makes it strictly faster for all string work: C takes mutability further still, since a char*/array-backed string is always mutable at the byte level with no separate immutable type at all, but that control comes with none of the safety immutability provides elsewhere, buffer overruns and missing null terminators are a classic consequence. Go's string mirrors Python's model closely (immutable, with strings.Builder playing the accumulator role list+join plays in Python), and Kotlin's String is immutable for the same reason Java's is, since both compile to the same JVM string representation, so the same StringBuilder-based advice carries over unchanged. The practical lesson that generalizes across every one of these languages: whenever you need to build a string piece by piece in a loop, reach for the language's designated mutable-accumulator type rather than the plain immutable string type.

Direct answer

Maintain a window [left, right] and a hash map of character frequencies inside it. Expand right one character at a time, always incrementing that character's count; whenever the map holds more than k distinct keys, shrink from left (decrementing and removing counts that hit zero) until it's back to at most k. Track the best window length seen after each expansion. Because left only ever moves forward and never resets, the whole scan is O(n), not O(n * k) from re-scanning.

Approach

1. Two pointers, left and right, both starting at 0, plus a dict mapping character to its count within the current window.
2. For each right, add s[right] to the frequency map.
3. While the map has more than k distinct keys, remove s[left] from the count (deleting the key entirely once its count hits 0, so "distinct key count" stays accurate) and advance left.
4. After the shrink step, the window [left, right] is valid (at most k distinct); update best = max(best, right - left + 1).
5. k == 0 is a special case: no window can ever be valid except length 0, so short-circuit and return 0.

Complexity

Time: O(n), since left and right each advance at most n times total across the whole scan (amortized O(1) per character, not per window). Space: O(k) for the frequency map (at most k+1 distinct keys are ever held at once, momentarily, before a shrink).

Edge cases

• Empty string or k == 0: return 0.
• k greater than or equal to the number of distinct characters in s: the whole string is the answer.
• All characters identical: the whole string is always a valid window regardless of k (as long as k >= 1).

def longest_substring_k_distinct(s, k):
    if k == 0 or not s:
        return 0
    freq = {}
    left = 0
    best = 0
    for right, ch in enumerate(s):
        freq[ch] = freq.get(ch, 0) + 1
        while len(freq) > k:
            left_ch = s[left]
            freq[left_ch] -= 1
            if freq[left_ch] == 0:
                del freq[left_ch]
            left += 1
        best = max(best, right - left + 1)
    return best


print(longest_substring_k_distinct("eeeeeaaabbbccd", 3))
print(longest_substring_k_distinct("araaci", 2))
print(longest_substring_k_distinct("", 2))
print(longest_substring_k_distinct("abc", 0))

Output:

11
4
0
0

For "eeeeeaaabbbccd" with k=3: the run "eeeeeaaabbb" (the first 11 characters) uses exactly the 3 distinct characters e, a, b; including either c afterward would push distinct-character count to 4, so 11 is correct and matches the printed value. For "araaci" with k=2, the window "araa" (characters a, r) is the longest 2-distinct window, matching the classic reference answer of 4.

If this were being used to gauge "language diversity" in a stream of characters (say, distinct scripts or token categories represented as characters), this same window answers "what's the longest run of content that only mixes at most k categories," which is a reasonable proxy for local diversity, though a real diversity metric would probably want a normalized measure (e.g. distinct-count / window-length) rather than raw longest-run.

Trade-offs and pitfalls

• Deleting keys once their count hits zero is required, not cosmetic: if you just decrement without deleting, len(freq) will overcount distinct characters that are no longer actually in the window, and the shrink loop will keep running (or stop too early) based on stale keys.
• Off-by-one in the length calculation: right - left + 1, not right - left, since both left and right are inclusive window bounds.
• The same one-pass, maintained-invariant window family applies to time-ordered event streams, not just character strings. Given an unordered stream of (user_id, timestamp) events, you can reconstruct per-user sessions (a session ends when the gap to the next event from that user exceeds a threshold) with an analogous single sweep once the events are sorted: instead of a frequency-count invariant, the invariant is "gap since the last event for this key is within the threshold."

def build_sessions(events, gap_seconds):
    sessions_by_user = {}
    for user_id, ts in sorted(events):
        user_sessions = sessions_by_user.setdefault(user_id, [])
        if user_sessions and ts - user_sessions[-1][-1] <= gap_seconds:
            user_sessions[-1].append(ts)
        else:
            user_sessions.append([ts])
    return sessions_by_user


events = [
    ("u1", 100), ("u1", 130), ("u1", 500),
    ("u2", 90), ("u2", 640),
    ("u1", 505),
]
print(build_sessions(events, gap_seconds=60))

Output:

{'u1': [[100, 130], [500, 505]], 'u2': [[90], [640]]}

u1's events at 100 and 130 are 30 seconds apart (within the 60-second gap, same session), 500 is 370 seconds after 130 (new session), and 505 is 5 seconds after 500 (same session as 500). u2's events are 550 seconds apart, so each is its own session. Sorting first costs O(n log n); the sweep itself is O(n), so the whole thing is O(n log n), dominated by the sort rather than the windowing logic.

Direct answer

Compare characters column by column across all the strings at once (vertical scanning): at each position i, check that every string shares the same character at that position. The first mismatch, or the first string that runs out of characters, marks the end of the common prefix. This is simple, correct, and exits as soon as a genuine mismatch is found, rather than fully comparing whole strings pairwise the way a naive approach might.

Structured elaboration

Vertical scanning approach

def longest_common_prefix_vertical(strs):
    if not strs:
        return ""
    for i, ch in enumerate(strs[0]):
        for other in strs[1:]:
            if i >= len(other) or other[i] != ch:
                return strs[0][:i]
    return strs[0]

O(n*m) naive complexity (the question's explicit ask)

With n strings and m the length of the shortest string, ANY correct approach touches at most n * m character comparisons in the worst case, imagine every string identical except for a mismatch right at the very last position checked. Vertical scanning does not beat this worst-case bound; what it buys you is exiting early on realistic negative cases, where a mismatch is usually found within the first handful of characters and strings, not at the theoretical worst-case position.

Binary-search-on-prefix-length approach (the question's explicit ask)

Binary search over candidate prefix lengths from 0 to the shortest string's length, using an O(n*m) helper ("is this length a common prefix of every string") as the check at each step:

def _is_common_prefix(strs, length):
    prefix = strs[0][:length]
    return all(s[:length] == prefix for s in strs)


def longest_common_prefix_binary_search(strs):
    if not strs:
        return ""
    min_len = min(len(s) for s in strs)
    lo, hi = 0, min_len
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if _is_common_prefix(strs, mid):
            lo = mid
        else:
            hi = mid - 1
    return strs[0][:lo]

Being honest about what this buys you: the per-step check itself costs O(nm) in the worst case, and binary search runs that check O(log m) times, so the WORST-CASE complexity of this version is actually O(n * m * log m), asymptotically worse than vertical scanning's O(nm), not better. Binary-search-over-the-answer is a genuinely useful general problem-solving pattern, and it can pay off here if the per-length check can be made cheap (for example, comparing precomputed rolling hashes of each candidate-length prefix instead of a fresh character-by-character comparison every time), but for the plain character-comparison check shown above, it is not a real optimization over vertical scanning. If a true asymptotic improvement is the goal, the standard technique is building a trie once over all the strings and walking it, which finds the common prefix in a single O(S) pass, where S is the total character count across all strings.

Worked example

Executed with python3 s78.py, both approaches run on the same inputs and confirmed to agree:

['flower', 'flow', 'flight']                  vertical='fl'       binary_search='fl'       agree=True
['dog', 'racecar', 'car']                     vertical=''         binary_search=''         agree=True
['interview', 'internal', 'interstate']       vertical='inter'    binary_search='inter'    agree=True
['single']                                    vertical='single'   binary_search='single'   agree=True

['flower', 'flow', 'flight'] maps to 'fl', matching the question's own stated example exactly.

Trade-offs and pitfalls

• Do not claim the binary-search version is asymptotically faster than vertical scanning for the plain per-length character check shown here; it is not, and overclaiming this specific trade-off is a common mistake that a careful interviewer will probe.
• Vertical scanning's early exit is a genuine, practical win on typical negative inputs (most real-world string sets diverge within the first few characters), even though its worst-case bound matches the fully naive pairwise approach.
• Edge cases worth naming explicitly: an empty list of strings (handled here by convention, returning ""), a single string (the whole string is trivially its own prefix), and one empty string anywhere in the list (the prefix is immediately "", which the vertical-scan loop handles correctly since strs[0] may be empty and its enumerate simply never executes).

Direct answer

Make two passes over the array without ever dividing. In the first pass, fill the output with the running PREFIX product (the product of everything to the left of each index). In the second pass, walk from the right and multiply each entry by a running SUFFIX product (the product of everything to the right of each index). After both passes, output[i] holds the product of every element except nums[i].

Structured elaboration

Approach

def product_except_self(nums):
    n = len(nums)
    output = [1] * n

    prefix = 1
    for i in range(n):
        output[i] = prefix
        prefix *= nums[i]

    suffix = 1
    for i in range(n - 1, -1, -1):
        output[i] *= suffix
        suffix *= nums[i]

    return output


def naive_division(nums):
    """The disallowed shortcut, shown only to make its zero-element failure
    concrete rather than asserted: multiply everything once, then divide by
    each element in turn."""
    total = 1
    for x in nums:
        total *= x
    out = []
    for x in nums:
        if x == 0:
            out.append(None)  # division by the zero element is undefined
        else:
            out.append(total // x)
    return out

This is O(n) time (two linear passes) and O(1) extra space, not counting the output array itself, exactly as the question specifies, since only two running scalar accumulators (prefix and suffix) are kept alongside the output.

Why prefix and suffix products work, and why no division is needed

Every position i's answer is exactly (product of nums[0..i-1]) * (product of nums[i+1..n-1]), the product of everything strictly to the left, times the product of everything strictly to the right. The first pass computes and stores the left-hand factor for every index in one sweep (writing it into output[i] before nums[i] itself is folded into the running prefix). The second pass computes the right-hand factor the same way while sweeping backward, multiplying it directly into the value already stored. Because the two factors are built and combined without ever needing nums[i] itself in the final expression, this naturally avoids the "divide the total product by nums[i]" approach, which is both explicitly disallowed here and would break outright on any zero in the input (division by zero, or worse, silently wrong results if a naive implementation tries to special-case just one zero).

Leave-one-out features (the question's explicit ask)

The prefix/suffix accumulation pattern used here is the general technique behind computing a "leave-one-out" aggregate for every position without recomputing the whole aggregate from scratch each time. The most common leave-one-out feature in practice is a SUM (for example, "total spend across a group, excluding this member"), computed the same way with running prefix and suffix sums instead of products; the product version shown here applies the identical idea whenever the aggregate you need excluded is a product rather than a sum, for example computing a joint likelihood or a normalization factor across a set of independent factors while excluding one factor at a time.

Worked example

Executed with python3 s84.py (both functions defined above):

product_except_self([1, 2, 3, 4]) = [24, 12, 8, 6]
manual check: [24, 12, 8, 6]

Manually: excluding index 0 leaves 2*3*4=24; excluding index 1 leaves 1*3*4=12; excluding index 2 leaves 1*2*4=8; excluding index 3 leaves 1*2*3=6. All four match the function's output exactly.

product_except_self([1, 2, 0, 4]) = [0, 0, 8, 0]
naive division-based version on the same input = [0, 0, None, 0]  <- breaks on the zero element

With a zero present, every output except the one at the zero's own index is 0 (since every other output's product still includes the zero), while the output AT the zero's index is the product of everything else (1*2*4=8). A division-based approach (compute the total product, then divide by nums[i]) fails outright here: dividing by the zero element itself is undefined, shown above returning None rather than the correct value 8.

Trade-offs and pitfalls

• The division-based shortcut (multiply everything, then divide by nums[i] for each output) is both explicitly disallowed by the question and fundamentally broken the moment any element is zero; the executed comparison above makes this concrete rather than asserted.
• The two-pass prefix/suffix technique generalizes directly to any associative combining operation (sum, product, min, max, and so on) wherever a "leave-one-out" aggregate is needed without an inverse operation (subtraction for sum, division for product) available or safe to use.
• If the array can be very large and the values themselves can be large integers, the running prefix and suffix products can grow to very large magnitudes; in a fixed-width integer language (unlike Python's arbitrary-precision integers), this needs an explicit overflow check or a different numeric representation, which is worth naming even though Python itself does not hit this limit.

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.