Arrays, Strings, and Hashing Questions

Direct answer

When the items themselves (like token dictionaries) aren't hashable, derive a hashable canonical key from each item's content, use that key in a seen-set for O(1) membership checks, and keep appending original items to the output in scan order exactly as with the hashable case. For datasets too large to hold in memory at once, the only state that needs to persist across chunks is that seen-set of keys, which lets the same logic run incrementally over a stream without ever materializing the whole dataset.

Building a canonical key for an unhashable item

A dict is unhashable because it's mutable, but its content can be turned into something hashable: json.dumps(obj, sort_keys=True) serializes a dict to a string with keys in a fixed order, so two dicts with identical content but different insertion order ({"text": "the", "pos": "DET"} vs {"pos": "DET", "text": "the"}) produce the identical key string and are correctly treated as duplicates. This assumes the values are themselves JSON-serializable (nested dicts/lists work, since sort_keys recurses; a value like a raw NumPy array or a custom object would need its own serialization rule first).

import json

def canonical_key(obj):
    return json.dumps(obj, sort_keys=True)

def dedupe_preserve_order(items):
    seen = set()
    result = []
    for item in items:
        key = canonical_key(item)
        if key not in seen:
            seen.add(key)
            result.append(item)
    return result

Adapting for extremely large datasets processed in chunks or streaming

The dedup logic doesn't change; what changes is that the input arrives as an iterable of chunks rather than one in-memory list, and the function becomes a generator so it never needs to hold more than the current chunk plus the running seen set in memory at once:

def dedupe_preserve_order_streaming(chunks):
    seen = set()
    for chunk in chunks:
        for item in chunk:
            key = canonical_key(item)
            if key not in seen:
                seen.add(key)
                yield item

Worked example

tokens = [
    {"text": "the", "pos": "DET"},
    {"pos": "DET", "text": "the"},   # same content, different key order -> duplicate
    {"text": "cat", "pos": "NOUN"},
    {"text": "the", "pos": "DET"},   # exact duplicate
    {"text": "sat", "pos": "VERB"},
]
print(dedupe_preserve_order(tokens))

chunk_a = [{"text": "the", "pos": "DET"}, {"text": "cat", "pos": "NOUN"}]
chunk_b = [{"pos": "DET", "text": "the"}, {"text": "sat", "pos": "VERB"}]
chunk_c = [{"text": "sat", "pos": "VERB"}, {"text": "mat", "pos": "NOUN"}]
print(list(dedupe_preserve_order_streaming([chunk_a, chunk_b, chunk_c])))

Output (verified by execution):

[{'text': 'the', 'pos': 'DET'}, {'text': 'cat', 'pos': 'NOUN'}, {'text': 'sat', 'pos': 'VERB'}]
[{'text': 'the', 'pos': 'DET'}, {'text': 'cat', 'pos': 'NOUN'}, {'text': 'sat', 'pos': 'VERB'}, {'text': 'mat', 'pos': 'NOUN'}]

The key-order-independence is confirmed directly: {"text": "the", "pos": "DET"} and {"pos": "DET", "text": "the"} are the same content in different insertion order, and both are correctly collapsed into a single kept occurrence, the first one, with the original dict shape preserved in the output (not the canonical JSON string). The streaming version, run across three separate chunks, produces exactly the same sequence as running the whole-input version on the concatenation of all three chunks, confirming that splitting the input into chunks doesn't change the result as long as the seen set is the one piece of state carried across chunk boundaries.

Trade-offs and pitfalls

• The seen set itself still grows with the number of distinct items, which is the real scaling limit. Chunking solves "the raw dataset doesn't fit in memory," but if the number of distinct keys is itself enormous (billions of unique tokens), the seen-set can become the new bottleneck. At that point the standard move is to accept approximate membership testing (a probabilistic structure that trades a small, bounded false-positive rate for sublinear memory), which is a different data structure than the exact-membership techniques covered here and belongs to the hash-table-internals side of the boundary between basic hashing techniques and hash-table design; naming it here as the next escalation point rather than implementing it is the honest answer once genuinely billions-scale.
• json.dumps(sort_keys=True) is not free: it's O(size of the item) per item, and for very large or deeply nested items this serialization cost can dominate; a cheaper but riskier alternative is hashing a canonical tuple representation directly (e.g., tuple(sorted(obj.items())) recursively) to avoid string formatting overhead, at the cost of more code to handle nested structures correctly.
• Streaming changes what "preserve order" can mean: within a single chunk, order is preserved as before; across chunks, the output order is chunk-arrival order, which is the only sensible definition once the whole dataset is never resident in memory simultaneously to be reordered globally.
• Common wrong turn: converting each dict to a frozenset(obj.items()) for hashing. This looks reasonable but silently breaks on nested unhashable values (a dict value inside the item) and, more subtly, changes semantics for numeric-vs-string key confusion in a way that a sorted JSON string does not, since JSON serialization is explicit about type.

Direct answer

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

Approach (Floyd's cycle detection)

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

Complexity

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

Edge cases

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

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


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

Output:

2 True

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

Alternative technique: index-marking

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

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


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

Output:

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

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

Trade-offs and pitfalls

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

Direct answer

Normalize both strings to a canonical Unicode form (NFC: compose combining marks into precomposed characters wherever a composed form exists), then casefold them (a Unicode-aware, more aggressive relative of .lower()), and finally compare character frequency counts using a hash map. Two strings are anagrams exactly when their normalized, casefolded character-count maps are equal. This is O(n) time and O(k) extra space, where k is the number of distinct characters actually present, not the size of the whole alphabet.

Structured elaboration

Why raw codepoint comparison fails on Unicode text. The same visible character can be represented by different codepoint sequences: an accented letter like an e with an acute accent can be one precomposed codepoint, or two codepoints (the base letter plus a separate combining acute-accent mark). Two strings that look identical to a human, and that a user would absolutely expect to be treated as anagrams of each other, can fail a naive character-by-character or Counter-based comparison if one uses the composed form and the other the decomposed form, because they are literally different sequences of codepoints.

Normalization (NFC) before comparison. Running both strings through Unicode Normalization Form C (NFC) converts any decomposed base-plus-combining-mark sequence into its precomposed equivalent wherever one exists, so that two visually-identical strings become byte-for-byte identical at the codepoint level before any counting happens. Normalization must happen before counting, not after, since counting decomposed and precomposed forms separately would treat them as different characters.

Casefolding, not just lowercasing. Python's .casefold() is used instead of .lower() because casefolding is defined specifically for caseless string matching and handles cases .lower() doesn't, most famously the German sharp s (ß), which casefolds to the two-character sequence ss (matching how ß and ss are treated as equivalent in caseless comparisons) while .lower() leaves it unchanged. This means casefolding can change a string's length, which matters for the next step.

Order of operations for the length check. The length check (len(s) != len(t) as a fast rejection before doing full character counting) must be performed on the normalized-and-casefolded strings, never on the raw input, precisely because casefolding can change length. Checking the raw lengths first, as a shortcut before normalization, is a subtle but real bug: it would incorrectly reject valid Unicode-aware anagram pairs whose raw lengths differ only because casefolding expands one of them.

Sorting-based versus counting-based comparison, and the large-alphabet trade-off. A sorting-based approach (sort both normalized/casefolded strings, compare for equality) costs O(n log n) time but only O(1) extra space if sorting can be done on a mutable copy in place (or O(n) if the language's sort isn't in-place), and it never needs a hash map at all, which matters when the character alphabet is enormous, since a sort never allocates space proportional to the alphabet size, only to the string length. A counting-based approach (build a frequency map, compare maps) is O(n) time but pays O(k) space for the map, where k is the number of distinct characters seen; for a small, fixed alphabet like lowercase ASCII, that map is trivially small and counting wins outright on speed, but for full Unicode text (over a million possible codepoints, even though any single string only uses a tiny fraction of them), a hash-map-based counter is still the right call because k is bounded by the input length itself, not by the alphabet size, since a Python dict/Counter only allocates entries for characters that actually appear.

Worked example

Full runnable code with pinned test cases, including the composed-versus-decomposed accented-character case and the German sharp-s casefold case (a genuine subtlety, not a contrived one):

import unicodedata
from collections import Counter


def normalize_for_compare(s):
    """NFC-normalize then casefold. Length check must happen AFTER this,
    never on the raw string (see the STRASSE case below)."""
    return unicodedata.normalize("NFC", s).casefold()


def is_anagram(s, t):
    """O(n) time, O(k) extra space where k is the distinct-character count,
    counting-based rather than sorting-based."""
    s_norm = normalize_for_compare(s)
    t_norm = normalize_for_compare(t)
    if len(s_norm) != len(t_norm):
        return False
    return Counter(s_norm) == Counter(t_norm)


if __name__ == "__main__":
    # Built from explicit codepoint escapes so the composed/decomposed
    # distinction is unambiguous regardless of source-file encoding.
    precomposed = "caf" + "\u00e9"          # c a f e-acute (1 codepoint, U+00E9)
    decomposed = "caf" + "e" + "\u0301"     # c a f e + combining acute (U+0301)

    print("raw codepoint lengths (decomposed vs precomposed):", len(decomposed), len(precomposed))
    print("raw equal (no normalization)?", decomposed == precomposed)
    print("NFC-normalized equal?", unicodedata.normalize("NFC", decomposed) == unicodedata.normalize("NFC", precomposed))

    reordered_precomposed = "\u00e9" + "fac"          # e-acute f a c (reordered anagram)
    strasse_lower = "stra" + "\u00df" + "e"           # stra-sharp_s-e

    tests = [
        ("listen", "silent", True),
        ("Listen", "Silent", True),
        (precomposed, decomposed + "x", False),
        (precomposed, reordered_precomposed, True),
        (decomposed, reordered_precomposed, True),
        ("STRASSE", strasse_lower, True),   # casefold('ss') == casefold('\u00df')
        ("ab", "abc", False),
    ]
    for a, b, expected in tests:
        result = is_anagram(a, b)
        print(f"is_anagram({a!r}, {b!r}) = {result} (expected {expected})")

    print("raw len(strasse_lower) =", len(strasse_lower), " raw len('STRASSE') =", len("STRASSE"))
    print("casefold(strasse_lower) =", strasse_lower.casefold())
    print("casefold('STRASSE') =", "STRASSE".casefold())

Output (actual run):

raw codepoint lengths (decomposed vs precomposed): 5 4
raw equal (no normalization)? False
NFC-normalized equal? True
is_anagram('listen', 'silent') = True (expected True)
is_anagram('Listen', 'Silent') = True (expected True)
is_anagram('café', 'caféx') = False (expected False)
is_anagram('café', 'éfac') = True (expected True)
is_anagram('café', 'éfac') = True (expected True)
is_anagram('STRASSE', 'straße') = True (expected True)
is_anagram('ab', 'abc') = False (expected False)
raw len(strasse_lower) = 6  raw len('STRASSE') = 7
casefold(strasse_lower) = strasse
casefold('STRASSE') = strasse

The STRASSE / straße case is the one to walk through out loud in an interview: the raw strings have different lengths (7 versus 6 codepoints), so a fast-reject on raw length would wrongly report "not an anagram." But ß casefolds to the two characters ss, so both strings casefold to the same 7-character string strasse, and they are correctly identified as an anagram pair. This is exactly why the length check must run on the normalized-and-casefolded strings.

Trade-offs and pitfalls

• Comparing raw strings, or even lowercasing with .lower() instead of .casefold(), silently fails on real internationalized input like the ß/ss case above; .lower() alone leaves ß unchanged and would report STRASSE and straße as not anagrams, which is wrong under Unicode caseless matching rules.
• Checking length before normalizing (a tempting micro-optimization to avoid normalizing strings that "obviously" can't match) is a genuine bug source, not a harmless shortcut, precisely because casefolding and normalization can both change apparent length.
• Sorting-based comparison is the right call when the alphabet is small and fixed (interview-classic lowercase-English anagram checks) since it avoids hash-map overhead entirely; counting-based comparison is the right call once the input might be full Unicode text, since a hash map's cost scales with how many distinct characters actually appear in this particular input, not with the size of the Unicode codepoint space.
• Grapheme-cluster-level correctness (treating an emoji-with-modifier sequence, or a base character plus multiple combining marks, as a single user-perceived "character") is a further layer beyond codepoint-level NFC normalization; this answer normalizes and compares at the codepoint level, which is sufficient for the vast majority of real anagram-style interview questions, but a fully grapheme-aware comparison would need a dedicated segmentation library, which is depth beyond what this question is testing.
• NFC (compose) rather than NFD (decompose) is used here because it produces the more compact, more widely-used-as-a-default form; either would work correctly as long as it's applied consistently to both strings before comparison, since the point is only that both strings land on the same normalized form, not which specific form is chosen.

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

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.