Arrays, Strings, and Hashing Questions

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

Normalize both strings the same way (lowercase, drop non-alphanumeric characters), then compare their character frequency counts. Building a frequency map is a single O(n) pass per string; sorting both normalized strings and comparing them is O(n log n). For long strings that gap is the entire reason to prefer the frequency map.

Structured elaboration

Normalizing. Filter each string down to lowercase alphanumeric characters only (c.isalnum()), dropping spaces and punctuation. This is a modeling decision worth stating out loud: taken completely literally, "Dormitory" and "dirty room" are not the same sequence of characters at all (different case, an extra space), the question's own instruction to ignore case and non-alphanumeric characters is what licenses treating them as equivalent.

Frequency map. Count occurrences of each normalized character in both strings (collections.Counter does this in one pass) and compare the two counts for equality. Two strings are anagrams exactly when every distinct character occurs the same number of times in both, which a Counter equality check verifies directly, in O(k) time to compare, where k is the number of distinct normalized characters, bounded by the alphabet rather than by n.

Sorting alternative. Sort both normalized character sequences and check they are identical; two strings are anagrams if and only if their sorted forms match. Correct, but O(n log n) because of the sort, versus O(n) for building and comparing frequency maps. For long strings, that difference in growth rate is exactly what "preferred... for long strings" is asking you to justify.

Cheap short-circuit. Compare lengths of the two normalized sequences first; a mismatch there proves non-anagram in O(1) (after the O(n) normalization pass), without needing to build either a sorted copy or a frequency map.

Worked example

from collections import Counter

def is_anagram(s: str, t: str) -> bool:
    def normalize(x: str):
        return [c.lower() for c in x if c.isalnum()]
    ns, nt = normalize(s), normalize(t)
    if len(ns) != len(nt):
        return False
    return Counter(ns) == Counter(nt)

from collections import Counter as _Counter

def _is_anagram_sorted_check(s, t):
    def normalize(x):
        return sorted(c.lower() for c in x if c.isalnum())
    return normalize(s) == normalize(t)

cases = [
    ("Dormitory", "Dirty Room", True),
    ("William Shakespeare", "I am a weakish speller", True),
    ("listen", "silent", True),
    ("hello", "world", False),
    ("A gentleman", "Elegant man", True),
    ("", "", True),
    ("a", "ab", False),
]
all_agree = True
for a, b, expected in cases:
    r = is_anagram(a, b)
    print(f"is_anagram({a!r}, {b!r}) = {r} (expected {expected})")
    if r != _is_anagram_sorted_check(a, b):
        all_agree = False
print()
print("all cases agree between frequency-map and sorting approaches, as expected."
      if all_agree else "MISMATCH between frequency-map and sorting approaches!")

Output:

is_anagram('Dormitory', 'Dirty Room') = True (expected True)
is_anagram('William Shakespeare', 'I am a weakish speller') = True (expected True)
is_anagram('listen', 'silent') = True (expected True)
is_anagram('hello', 'world') = False (expected False)
is_anagram('A gentleman', 'Elegant man') = True (expected True)
is_anagram('', '') = True (expected True)
is_anagram('a', 'ab') = False (expected False)

all cases agree between frequency-map and sorting approaches, as expected.

Every case, including the classic "William Shakespeare" / "I am a weakish speller" anagram and the empty-string edge case, matches expectation, and a parallel sorting-based implementation was run against the identical inputs and agreed with the frequency-map result on every one, confirming the two approaches are equivalent in correctness, differing only in complexity.

Trade-offs and pitfalls

Check the length mismatch before doing anything else; it is the cheapest possible rejection and avoids building a data structure you already know cannot match.

Sorting is still a reasonable, sometimes preferable, choice for very short strings, or when you need the sorted form anyway for something else (grouping many words by their sorted key, for instance): at small n, the constant-factor difference between O(n) and O(n log n) barely matters in practice, and the sorted form doubles as a canonical grouping key.

Stating your normalization rules explicitly is part of a senior answer here: "ignore case and non-alphanumeric characters" is a specific, narrower definition of anagram than the literal character-for-character one, and silently assuming it without saying so is a common way this question goes subtly wrong in an interview, even when the code itself is correct.

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

Boyer-Moore majority vote keeps a single candidate and a counter. Walking the array once, a match with the candidate increments the counter, a mismatch decrements it, and whenever the counter hits zero the candidate is replaced by the current element. If a true majority element exists (one appearing more than n/2 times), this candidate is guaranteed to be it, and a second pass over the array verifies the count exceeds n/2 before returning it, since the vote alone does not check that a majority actually exists. Both passes are single linear scans and the only extra memory is the candidate and the counter, so the whole algorithm runs in O(n) time and O(1) extra space, exactly the bound the question asks for.

Structured elaboration

Why the vote finds the right candidate

Think of each occurrence of the eventual majority element as a "+1 vote" and every other element as a "-1 vote" against whatever the current candidate happens to be. Because the majority element appears more than n/2 times, its total positive contribution outweighs everything else combined, no matter how the non-majority elements are arranged. The counter resetting to zero and swapping candidates effectively cancels out one occurrence of the current candidate against one occurrence of something else, a kind of pairing-off. Since the true majority element has more occurrences than everything else put together, it can never be fully cancelled out: it always survives as the final candidate once all the cancellation has happened.

Why a verification pass is required

The vote procedure always produces SOME candidate, even when no true majority element exists at all. Consider an array with no repeated majority: the same cancel-and-replace dynamic still runs and still ends with some element left standing as "candidate," but that element might appear far less than n/2 times. The algorithm's guarantee is one-directional: IF a majority exists, the vote finds it; it says nothing about whether a majority exists in the first place. The second, verification pass counts the actual occurrences of the candidate and checks that count against n/2, which turns "a plausible candidate" into "a proven majority element" (or correctly reports that none exists).

Worked example

def majority_element(nums):
    candidate = None
    count = 0
    for x in nums:
        if count == 0:
            candidate = x
        count += 1 if x == candidate else -1
    verify_count = sum(1 for x in nums if x == candidate)
    if verify_count > len(nums) // 2:
        return candidate
    return None

nums1 = [2, 2, 1, 1, 1, 2, 2]
print(majority_element(nums1))

nums2 = [1, 2, 3, 4]
print(majority_element(nums2))

Output:

2
None

For [2, 2, 1, 1, 1, 2, 2] (length 7, so a majority needs more than 3 occurrences), 2 appears 4 times and the vote correctly settles on it. For [1, 2, 3, 4], every value appears exactly once, so no majority exists at all: the vote still produces SOME candidate internally as it runs, but the verification pass catches that its true count (1) does not exceed 4 // 2 = 2, and the function correctly returns None rather than a wrong answer.

Trade-offs and pitfalls

The most common mistake is skipping the verification pass entirely and trusting the vote's output unconditionally, which silently returns a wrong "majority" on any input where no true majority exists, exactly the [1, 2, 3, 4] case above. A second is resetting the counter to zero but forgetting to also update the candidate to the current element at that moment, which breaks the cancellation logic the whole proof depends on. This algorithm specifically finds an element appearing more than n/2 times; a different and looser problem, find any element appearing at least n/k times for some k > 2, needs the generalized Boyer-Moore voting scheme with k-1 candidate slots instead of one, not this exact two-variable version. The same vote-and-verify logic is unchanged in Java or JavaScript, since it only relies on equality comparison and increment/decrement.

Direct answer

Add the two digit strings exactly the way long addition is done by hand: walk both strings from the rightmost digit, add the corresponding digits plus any carry from the previous position, keep the ones digit as the result and carry the tens digit forward, and continue until both strings and the carry are exhausted. This never converts the whole number into a native integer type, runs in O(max(len(a), len(b))) time and space, and generalizes directly to any base by changing how individual digits are parsed and re-emitted.

Structured elaboration

Why this can't just use native integer addition. The entire point of the exercise is that the numbers may be arbitrarily large decimal strings, potentially larger than any fixed-width integer type can represent without an arbitrary-precision ("big-int") library; the question explicitly disallows using one, so digits are processed as characters, not as a machine integer.

The right-to-left digit-pair-plus-carry loop. Two index pointers start at the last character of each string and move left. At each step, the digit from a (or 0 if that pointer has run past the start of a) is added to the digit from b (or 0, similarly) plus the carry from the previous step. The result's ones digit (total % 10) is appended to the output, and the new carry is the tens digit (total // 10). The loop continues as long as either pointer still has digits left, or a carry is still pending, which correctly handles the case where the final addition produces an extra leading digit (e.g. 9 + 9 = 18, carrying a new leading 1).

Reversal at the end. Because digits are produced from least-significant to most-significant (processing right to left), the accumulated digit list is in reverse order relative to the final answer and must be reversed once before joining into the output string.

Generalizing to base 16 or other bases. The algorithm's structure doesn't change at all between bases; only two things change: how a single character is parsed into its numeric digit value, and how a numeric digit value is turned back into a character. In decimal, int(digit) and str(digit) handle this. For an arbitrary base b (2 through 36), Python's int(digit, b) parses a single base-b digit character (handling both decimal digits and letters a through z for bases above 10), and indexing into a fixed alphabet string (\"0123456789abcdefghijklmnopqrstuvwxyz\") re-emits a digit value as its base-b character. The carry logic is identical, just with % base and // base replacing % 10 and // 10.

Worked example

Full runnable code with pinned test cases, including the question's own large-number example, verified against Python's own native big-integer addition as ground truth (used here only to cross-check the from-scratch implementation, not as a substitute for it):

def add_strings(a, b):
    """Add two non-negative decimal-string integers without big-int libs.
    O(max(len(a), len(b))) time and space, single right-to-left pass with
    a carry, exactly like manual long addition."""
    i, j = len(a) - 1, len(b) - 1
    carry = 0
    digits = []
    while i >= 0 or j >= 0 or carry:
        da = int(a[i]) if i >= 0 else 0
        db = int(b[j]) if j >= 0 else 0
        total = da + db + carry
        digits.append(str(total % 10))
        carry = total // 10
        i -= 1
        j -= 1
    return ''.join(reversed(digits))


def add_strings_base(a, b, base):
    """Same algorithm generalized to an arbitrary base (2-36), using
    int(digit, base) to parse and a base-N string alphabet to re-emit."""
    digits_alphabet = "0123456789abcdefghijklmnopqrstuvwxyz"
    i, j = len(a) - 1, len(b) - 1
    carry = 0
    out = []
    while i >= 0 or j >= 0 or carry:
        da = int(a[i], base) if i >= 0 else 0
        db = int(b[j], base) if j >= 0 else 0
        total = da + db + carry
        out.append(digits_alphabet[total % base])
        carry = total // base
        i -= 1
        j -= 1
    return ''.join(reversed(out))


if __name__ == "__main__":
    a = "9876543210123456789"
    b = "1234567890987654321"
    result = add_strings(a, b)
    expected_via_python_int = str(int(a) + int(b))
    print(f"add_strings({a!r}, {b!r})")
    print(f"  result   = {result}")
    print(f"  expected = {expected_via_python_int} (cross-checked via Python's native int addition)")
    print(f"  match: {result == expected_via_python_int}")

    more_tests = [
        ("0", "0", "0"),
        ("1", "9", "10"),
        ("99", "1", "100"),
        ("123", "0", "123"),
    ]
    for x, y, exp in more_tests:
        r = add_strings(x, y)
        print(f"add_strings({x!r}, {y!r}) = {r} (expected {exp})")

    hex_result = add_strings_base("ff", "1", 16)
    print(f"add_strings_base('ff', '1', 16) = {hex_result} (expected 100)")

Output (actual run):

add_strings('9876543210123456789', '1234567890987654321')
  result   = 11111111101111111110
  expected = 11111111101111111110 (cross-checked via Python's native int addition)
  match: True
add_strings('0', '0') = 0 (expected 0)
add_strings('1', '9') = 10 (expected 10)
add_strings('99', '1') = 100 (expected 100)
add_strings('123', '0') = 123 (expected 123)
add_strings_base('ff', '1', 16) = 100 (expected 100)

This confirms the question's own stated example: '9876543210123456789' + '1234567890987654321' -> '11111111101111111110' is correct, verified both by the character-by-character implementation and by cross-checking against Python's native arbitrary-precision integer addition on the same inputs. The base-16 example ('ff' + '1' = '100' in hex, i.e. 255 + 1 = 256) confirms the generalization: the carry chain propagates through both hex digits exactly as it would for 99 + 1 = 100 in decimal.

Trade-offs and pitfalls

• Converting both strings to native integers, adding, and converting back (str(int(a) + int(b))) is the obvious shortcut and was used above only as a cross-check, not as the answer: for genuinely arbitrary-precision inputs in a language without native big-int support (or under an explicit "no big-int library" constraint, as this question states), this shortcut isn't available at all, which is the entire point of the exercise.
• A common bug is forgetting the final carry: if the loop condition doesn't check carry as an independent continuation condition (only checking i >= 0 or j >= 0), an addition like 9 + 9 (which produces 18, needing an extra leading digit) silently drops the final carry digit.
• Building the result with repeated string concatenation (result = digit + result instead of appending to a list and reversing once at the end) works but is less efficient in languages or situations where string concatenation is O(current length) per operation, making a naive left-prepend approach O(n^2) overall instead of O(n); appending to a list and reversing once avoids this.
• This implementation assumes both inputs are non-negative digit strings with no sign character or leading-zero ambiguity beyond a literal "0"; supporting signed values would require detecting and handling a leading - or + before the digit-processing loop, which is a real but separate extension.
• The base generalization above supports bases 2 through 36 only, since it relies on Python's int(digit, base) and a 36-character alphabet; supporting arbitrary bases beyond 36 would require a different, explicitly-provided digit alphabet rather than reusing 0-9a-z.