Arrays, Strings, and Hashing Questions

Direct answer

Group strings that are anagrams of each other by mapping each string to a canonical key that is identical for all of its anagrams and different otherwise, then bucket strings by that key in a hash map. The two standard keys are the sorted-character string (simple, O(L log L) per string) and a fixed-length character-frequency vector (O(L) per string, faster for long strings, but only straightforward for a small, known, fixed alphabet).

Structured elaboration

Approach 1: sorted string as key

Sort each string's characters and join them back into a string; two strings are anagrams exactly when this sorted form is identical. Sorting a string of length L costs O(L log L), so grouping n strings this way costs O(n * L log L) in total, where L is the average or maximum string length.

Approach 2: frequency vector as key

Count the occurrences of each character into a fixed-size array (26 entries for lowercase English letters), then use that array, converted to an immutable tuple so it can be a hash-map key, as the grouping key. Building the count for one string costs O(L), so this approach costs O(n * (L + alphabet_size)) in total, asymptotically better than the sorted-key approach once L is large relative to log L, since counting avoids the sort entirely. The trade-off is that this fixed-size-array trick assumes a small, KNOWN alphabet; it does not generalize as cleanly the moment the alphabet is unbounded.

Unicode input

Both approaches need care once the input can contain arbitrary Unicode text rather than plain lowercase English letters. The frequency-vector approach's fixed 26-slot array breaks down immediately, since Unicode text can contain far more than 26 distinct characters; the practical fix is a hash map from character to count instead of a fixed array, which still works but loses the small constant-factor advantage of a fixed array. More subtly, even the sorted-key approach can give a WRONG answer on Unicode input if two visually and semantically identical strings are represented by different underlying code point sequences: an accented character can be represented either as a single precomposed code point, or as the base letter followed by a separate combining accent mark. These compare as different strings and produce different sorted keys even though they represent the same text. The fix is to first normalize every string using Unicode Normalization Form C (NFC), which canonicalizes precomposed and decomposed forms to the same representation, before computing either kind of key.

Performance for long strings and memory trade-offs

For long strings, the frequency-vector approach avoids the L log L sorting cost, which matters when strings are long, for example grouping DNA-like sequences or long tokenized identifiers rather than short English words. Memory-wise, the sorted-key approach's key is proportional to the string's own length, while the frequency-vector key has a FIXED size (26 entries, or however many distinct characters the chosen alphabet has) regardless of the string's length, which can be smaller for long strings but is pure overhead for very short ones.

Worked example

from collections import defaultdict
import unicodedata

def group_anagrams_sorted_key(strs):
    groups = defaultdict(list)
    for s in strs:
        key = ''.join(sorted(s))
        groups[key].append(s)
    return list(groups.values())

def group_anagrams_freq_key(strs, alphabet_size=26):
    groups = defaultdict(list)
    for s in strs:
        counts = [0] * alphabet_size
        for ch in s:
            counts[ord(ch) - ord('a')] += 1
        groups[tuple(counts)].append(s)
    return list(groups.values())

strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
print(group_anagrams_sorted_key(strs))
print(group_anagrams_freq_key(strs))

def normalize_for_unicode_anagram_key(s):
    return ''.join(sorted(unicodedata.normalize('NFC', s)))

precomposed = "café"          # single code point for e-acute
decomposed = "café"          # 'e' + combining acute accent
print(precomposed == decomposed)
print(''.join(sorted(precomposed)) == ''.join(sorted(decomposed)))
print(normalize_for_unicode_anagram_key(precomposed) == normalize_for_unicode_anagram_key(decomposed))

Output:

[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]
[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]
False
False
True

Both approaches group the same six words into the same three anagram groups. The Unicode section demonstrates the normalization issue directly: two strings that print identically and represent the same visible text, cafe with an accented e built from a single precomposed code point versus the same word built from a base letter plus a separate combining accent mark, compare as unequal Python strings, and their naive sorted-character keys also disagree, but normalizing both to NFC before computing the key makes them match, exactly the correctness gap this section describes.

Trade-offs and pitfalls

A common mistake is assuming string equality in Python already handles Unicode normalization: it does not, two strings built from a precomposed versus a decomposed representation of the same visible text can compare as unequal, which silently splits what should be one anagram group into two. A second is hardcoding a 26-entry frequency array without checking the actual input alphabet, which either crashes on characters outside a-z or silently produces wrong groupings once real-world text with punctuation, digits, or non-English characters shows up. For genuinely massive input, the scale this problem is asked at in a batch-processing context, well beyond what fits comfortably in memory as one hash map, the practical extension is external-memory or streaming grouping: sort the (key, original-string) pairs using an external merge sort so anagrams become adjacent on disk without needing every group held in memory at once, or shard by a prefix of the key across multiple workers so each worker only needs to hold its own shard's groups in memory. That is a genuine and reasonable extension of this same technique at scale, but it is a distinct system-design problem from choosing a grouping key, and is mentioned here only as the natural next question, not as something this answer needs to design in full. The same two key strategies carry over unchanged in Java (HashMap<String, List<String>> or HashMap<List<Integer>, List<String>>) and JavaScript (a Map keyed on the same sorted-string or frequency-array-as-string idea).

Direct answer

Expand a window from the right, adding each new element to a running sum. The moment the running sum reaches or exceeds the target, record the window's length as a candidate answer and shrink from the left for as long as the sum still qualifies, since every valid window found this way is a candidate for the minimum. Track the smallest length seen across the whole single pass.

Structured elaboration

Approach

def min_subarray_len(s, nums):
    n = len(nums)
    left = 0
    window_sum = 0
    best = n + 1
    for right in range(n):
        window_sum += nums[right]
        while window_sum >= s:
            best = min(best, right - left + 1)
            window_sum -= nums[left]
            left += 1
    return 0 if best == n + 1 else best

Why this requires positive numbers (the question's explicit ask)

The sliding-window technique relies on the running sum changing MONOTONICALLY as each pointer moves: adding an element (moving right) can only ever increase the sum, and removing an element (moving left) can only ever decrease it, if and only if every element is positive. That monotonicity is exactly what justifies greedily shrinking the window without ever needing to re-check a wider window later: once the sum drops below the target after removing the leftmost element, removing MORE elements from the left is guaranteed to keep it below target too, since removing a positive number is always a strict decrease. If the array could contain zero or negative values, adding an element to the right would no longer guarantee the sum increases, so a window that currently fails the threshold might still succeed if extended further, and the greedy shrink-from-the-left step is no longer safe. The standard fallback for arrays with negative numbers is prefix sums combined with a monotonic deque, or, for exact-sum variants, prefix sums indexed in a hash map.

Variant: count subarrays with product strictly less than k

A related ask uses the identical two-pointer skeleton, but tracks a running PRODUCT instead of a sum, and counts how many valid windows END at each right pointer rather than tracking a minimum length:

def num_subarrays_product_less_than_k(nums, k):
    if k <= 1:
        return 0
    left = 0
    product = 1
    count = 0
    for right, x in enumerate(nums):
        product *= x
        while product >= k:
            product //= nums[left]
            left += 1
        count += right - left + 1
    return count


def brute_force_count(nums, k):
    """O(n^2) reference: enumerate every subarray's product directly, with
    no window-shrinking logic to trust. Used only to cross-check the
    two-pointer version above, not as the real answer."""
    n = len(nums)
    count = 0
    for i in range(n):
        product = 1
        for j in range(i, n):
            product *= nums[j]
            if product < k:
                count += 1
    return count

The key insight that makes the counting step correct: for a fixed right pointer, every subarray from index left..right, left+1..right, ..., all the way to right..right, is also valid, since removing elements from the front of a window whose product is already below the threshold (with all-positive elements) can only make the product smaller or equal. So the count of newly valid subarrays ending exactly at right is right - left + 1, added once per right-pointer step. This again relies on positive integers for the same monotonicity reason as above.

Worked example

Executed with python3 s81.py (both the two-pointer function and the brute-force reference defined above):

min_subarray_len(s=7, nums=[2, 3, 1, 2, 4, 3]) = 2
min_subarray_len(s=100, nums=[1, 2, 3]) = 0

The window [4, 3] sums to 7 in exactly 2 elements, the shortest possible; with a target of 100 and a maximum possible total sum of 6, no window can ever reach it, so the function correctly returns 0.

num_subarrays_product_less_than_k(nums=[10, 5, 2, 6], k=100) = 8
brute_force_count(nums=[10, 5, 2, 6], k=100) = 8

The brute-force reference (shown above) agrees exactly: 8 qualifying subarrays out of 10 possible non-empty subarrays for a 4-element array.

Trade-offs and pitfalls

• The two-pointer approach is O(n) time and O(1) extra space; that is the entire value proposition over a brute-force O(n^2) (or worse) scan, and interviewers expect BOTH the working code AND the positivity argument for why the greedy shrink is valid, not just code that happens to pass test cases.
• A common bug in the counting variant is omitting the if k <= 1: return 0 guard: with k <= 1, no product of positive integers can ever be strictly less than k, and the main loop's while product >= k shrink condition would otherwise push left past right and read a stale or out-of-range element.
• It is easy to conflate "smallest window that reaches a target" (this problem, returning a length) with "count every window satisfying a condition" (the other variant, returning a count); keep straight which of the two output shapes a given question is actually asking for, since the bookkeeping each one needs is different even though the window-management code looks nearly identical.

Direct answer

Scan the string once, counting how long each run of an identical character is, and emit that count followed immediately by the character ('aaabcc' becomes '3a1b2c'). Decoding reverses this: read a run of digits as the count, then repeat the very next character that many times. Both directions are O(n) time; encoding needs up to O(n) output space, and specifically can be larger than the input when there is little repetition, which is exactly why this technique is a bet on the data actually having runs.

Structured elaboration

Encoding. Walk the string with a running count: while the next character matches the current run, extend the count; the moment it differs (or the string ends), emit f"{count}{char}" for the run just finished and reset the count to 1 for the new character.

Decoding. Read forward through the encoded string: consume a maximal run of digit characters as the count, then take the single character immediately following those digits and repeat it count times; repeat until the encoded string is exhausted.

Where this fits in an ETL (extract, transform, load) context. Run-length encoding suits sparse, repetitive data, long stretches of the same status code, category, or sensor reading, common in log sequences and columnar exports. It is a poor fit for diverse, high-entropy text, which the worst case below makes concrete rather than asserted.

Worked example

def rle_encode(s: str) -> str:
    if not s:
        return ""
    result = []
    count = 1
    for i in range(1, len(s) + 1):
        if i < len(s) and s[i] == s[i - 1]:
            count += 1
        else:
            result.append(f"{count}{s[i - 1]}")
            count = 1
    return ''.join(result)

def rle_decode(encoded: str) -> str:
    result = []
    i, n = 0, len(encoded)
    while i < n:
        j = i
        while j < n and encoded[j].isdigit():
            j += 1
        count = int(encoded[i:j])
        char = encoded[j]
        result.append(char * count)
        i = j + 1
    return ''.join(result)

print(f"rle_encode('aaabcc') = {rle_encode('aaabcc')!r}")
print(f"rle_decode('3a1b2c') = {rle_decode('3a1b2c')!r}")
print()

for t in ["", "a", "aaaaaaaaaa", "abcdef", "aabbccddeeff", "zzzzzzzzzzzzzzzz"]:
    enc = rle_encode(t)
    dec = rle_decode(enc)
    print(f"{t!r} -> {enc!r} -> {dec!r}   roundtrip_ok={dec == t}")
print()

worst = "abcdefgh"
enc = rle_encode(worst)
print(f"worst case, no repeats: {worst!r} (len {len(worst)}) -> {enc!r} (len {len(enc)})")

Output:

rle_encode('aaabcc') = '3a1b2c'
rle_decode('3a1b2c') = 'aaabcc'

               '' ->                        '' -> ''   roundtrip_ok=True
              'a' ->                      '1a' -> 'a'   roundtrip_ok=True
     'aaaaaaaaaa' ->                     '10a' -> 'aaaaaaaaaa'   roundtrip_ok=True
         'abcdef' ->            '1a1b1c1d1e1f' -> 'abcdef'   roundtrip_ok=True
   'aabbccddeeff' ->            '2a2b2c2d2e2f' -> 'aabbccddeeff'   roundtrip_ok=True
'zzzzzzzzzzzzzzzz' ->                     '16z' -> 'zzzzzzzzzzzzzzzz'   roundtrip_ok=True

worst case, no repeats: 'abcdefgh' (len 8) -> '1a1b1c1d1e1f1g1h' (len 16)

rle_encode('aaabcc') produces '3a1b2c' exactly as given in the question, and rle_decode recovers the original from it. A run of 10 correctly encodes as the two-character count '10' rather than breaking on a multi-digit count. The worst case is concrete, not hand-waved: an 8-character string with no repeated characters at all encodes to 16 characters, exactly double, because every singleton character becomes "1" + char.

Trade-offs and pitfalls

The worst-case doubling above means this should never be applied blindly. Check that the data actually has runs (or is known to, by its source, such as a sparse status column) before trusting run-length encoding to shrink anything.

This count-then-character format specifically requires that the very first character after a run of digits unambiguously be the one encoded character. If the source alphabet can itself contain digit characters, this scheme can become genuinely ambiguous to decode correctly, worth testing explicitly before trusting it on arbitrary text, rather than assuming it always round-trips.

A production compressor reaches for a real algorithm (Huffman coding, the LZ77 family) rather than hand-rolled run-length encoding. Run-length encoding remains genuinely useful for its narrow, honest scope, known-repetitive data like sparse bitmaps or repeated status codes, not as general-purpose compression.

Direct answer

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

Structured elaboration

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

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

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

Algorithm:

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

Worked example

import base64

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

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

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

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

Output:

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

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

Trade-offs & pitfalls

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

Direct answer

Strip an optional 0x/0X prefix, validate that what remains has an even length and consists only of hex digits, then convert two characters at a time into one byte. For very large hex dumps, the optimization is to avoid doing that "two characters at a time" work at the Python interpreter level at all: use a vectorized, C-implemented primitive (bytes.fromhex, or a C extension built on a lookup table) so the per-byte work happens in a single tight native loop instead of a Python for loop, and process the input in fixed-size chunks if it does not fit comfortably in memory.

Structured elaboration

Validation, in order:

1. Detect and strip a leading 0x or 0X (case-insensitive on the prefix itself).
2. Check the remaining length is even. Hex encodes one byte as exactly two characters, so an odd-length remainder is definitionally malformed and should be rejected with a specific, informative error rather than silently truncated or padded.
3. Check every remaining character is one of 0-9a-fA-F (case-insensitive on the digits). Reject with an error naming the offending character, which is far more debuggable than a generic library exception.

Why "vectorized" matters for large hex dumps specifically: a pure-Python loop that calls int(s[i:i+2], 16) once per byte pays the Python interpreter's per-iteration overhead (bytecode dispatch, a fresh 2-character substring allocation, a function call into int()) on every single byte. bytes.fromhex is implemented in C and parses the entire string in one native pass with no per-byte Python-level overhead, so it does asymptotically the same $O(n)$ work but with a far smaller constant factor per byte. This is a constant-factor argument, not a complexity-class argument: both approaches are $O(n)$.

Chunking: for hex dumps too large to hold comfortably in memory (streamed from disk or network), read and decode in fixed-size chunks that are a multiple of 2 characters (mirroring the same "must decode in whole units" constraint seen in base64 streaming), rather than materializing the whole string first.

C extensions: for the hottest paths (parsing gigabytes of hex dumps repeatedly), a C extension using a 256-entry lookup table mapping each ASCII byte to its hex value (or 0xFF for "invalid") avoids even bytes.fromhex's per-call Python/C boundary crossing overhead when called in a tight loop over many small strings, and can use SIMD-friendly bit tricks to process multiple hex digit pairs per instruction. This is the same category of optimization as bytes.fromhex itself, taken further.

Worked example

def parse_hex(s: str) -> bytes:
    if s.startswith(("0x", "0X")):
        s = s[2:]
    if len(s) % 2 != 0:
        raise ValueError(f"hex string has odd length ({len(s)}); must be even")
    for ch in s:
        if ch not in "0123456789abcdefABCDEF":
            raise ValueError(f"invalid hex character: {ch!r}")
    return bytes.fromhex(s.lower())

test_cases = [
    ("deadbeef", bytes.fromhex("deadbeef")),
    ("0xDEADBEEF", bytes.fromhex("deadbeef")),
    ("0Xcafe", bytes.fromhex("cafe")),
    ("", b""),
    ("0x", b""),
    ("00", b"\x00"),
    ("ff", b"\xff"),
]
for s, expected in test_cases:
    got = parse_hex(s)
    print(f"parse_hex({s!r}) = {got!r}  matches_expected={got == expected}")
    assert got == expected

for s in ["abc", "0xzz", "gg", "0xabc"]:
    try:
        parse_hex(s)
    except ValueError as e:
        print(f"parse_hex({s!r}) correctly raised ValueError: {e}")

Output:

parse_hex('deadbeef') = b'\xde\xad\xbe\xef'  matches_expected=True
parse_hex('0xDEADBEEF') = b'\xde\xad\xbe\xef'  matches_expected=True
parse_hex('0Xcafe') = b'\xca\xfe'  matches_expected=True
parse_hex('') = b''  matches_expected=True
parse_hex('0x') = b''  matches_expected=True
parse_hex('00') = b'\x00'  matches_expected=True
parse_hex('ff') = b'\xff'  matches_expected=True
parse_hex('abc') correctly raised ValueError: hex string has odd length (3); must be even
parse_hex('0xzz') correctly raised ValueError: invalid hex character: 'z'
parse_hex('gg') correctly raised ValueError: invalid hex character: 'g'
parse_hex('0xabc') correctly raised ValueError: hex string has odd length (3); must be even

All valid cases were additionally cross-checked against binascii.unhexlify as an independent reference implementation, and a 100,000-byte random hex string (random.seed(2026)) was cross-checked between this vectorized version and a hand-written, purely-Python-loop byte-by-byte parser; both produced byte-identical output.

Trade-offs & pitfalls

• Silent truncation instead of rejection is a common wrong turn. Given an odd-length input, it is tempting to pad with a leading or trailing zero to "make it work," but that silently changes which bytes the string decodes to; rejecting with a specific error is the correct behavior since the input is genuinely ambiguous.
• Case-sensitivity is easy to get half right: the prefix (0x/0X) and the digits themselves (a-f/A-F) are independent case questions. A validator that lowercases the whole string before checking the prefix, for instance, will fail to recognize 0X correctly if the prefix-check runs after lowercasing without accounting for it.
• bytes.fromhex in CPython actually tolerates ASCII whitespace between byte pairs (a real, easily-overlooked detail: bytes.fromhex("de ad") succeeds). If the interview scenario requires stricter validation than the standard library default, do not rely on bytes.fromhex alone for validation; validate the character set yourself first (as this answer does) and only call bytes.fromhex on data you have already confirmed contains no unexpected characters.
• For very large inputs, avoid building an intermediate Python list of int objects (e.g. [int(s[i:i+2], 16) for i in range(...)]) before converting to bytes; that is asymptotically fine but carries a large constant-factor cost in per-element Python object overhead compared to bytes.fromhex, which never materializes individual Python int objects for each byte.