Arrays, Strings & Hashing

01Arrays: the physics of contiguous memory

An array is a promise: n elements, side by side, in one contiguous block of memory. Everything good and bad about arrays follows from that single fact.

address:   1000   1008   1016   1024   1032
          ┌──────┬──────┬──────┬──────┬──────┐
          │ a[0] │ a[1] │ a[2] │ a[3] │ a[4] │   (8 bytes each)
          └──────┴──────┴──────┴──────┴──────┘

a[i] lives at:  base_address + i × element_size   ← one multiply + one add = O(1)

Dynamic arrays (Python list)

A Python list is a dynamic array of pointers to objects. It keeps spare capacity: append fills a slot in O(1), and when full it reallocates bigger and copies — amortized O(1) (the full doubling argument lives in file 01 §5). Consequences you should recite on demand:

02Strings: immutable arrays of characters

A Python string behaves like a read-only array. Immutability is the interview-relevant property: every "modification" builds a brand-new string. That's how you fall into the classic accidental quadratic:

s = ""
for ch in chunks:
    s += ch   # each += copies the WHOLE
              # accumulated string → O(n²)

parts = []
for ch in chunks:
    parts.append(ch)  # O(1) amortized
s = "".join(parts)    # one O(n) pass

Other string moves that come up constantly:

s[::-1]                    # reverse (O(n), makes a copy)
s.split(), s.strip()       # tokenize / trim
ord('a'), chr(97)          # char ↔ codepoint, for count arrays
sorted(s)                  # list of chars, O(n log n) — canonical form for anagrams

For "compare letter counts" problems, a 26-slot count array is the zero-overhead hashmap:

counts = [0] * 26
for ch in s:
    counts[ord(ch) - ord('a')] += 1

03Hashmaps: how the magic actually works

This is the data structure interviewers most love to ask you to explain, because it separates "I use dicts" from "I know what a dict is."

The problem it solves

Arrays give O(1) access by integer index. But we want O(1) access by arbitrary key — a user ID string, a tuple, an email. The trick: convert the key into an index.

The mechanism, step by step

1. Hash the key → a deterministic, well-scattered integer. Same key ⇒ same hash, always.
2. Modulo by capacity → a bucket index.
3. Store (key, value) in that bucket. We keep the key too — because of the next point.

Collisions: the inevitable complication

Different keys can land in the same bucket (pigeonhole: infinite keys, finite buckets). Two classic strategies:

• Chaining: each bucket holds a small list; on collision, append. Lookup = hash, then scan that short list, comparing stored keys — that's why we keep them.
• Open addressing (what CPython uses): on collision, probe other slots in a deterministic sequence until a free one is found. Lookup follows the same probe sequence.

Chaining:                          Open addressing:
bucket[3] ──► (k1,v1) ─► (k9,v9)   bucket[3] full? try 4… full? try 6… (probe sequence)

Load factor: when to grow

load factor = entries / buckets. As it rises, buckets get crowded, chains/probes lengthen, and O(1) decays toward O(n). So hashmaps resize when the load factor crosses a threshold (CPython: 2/3): allocate a bigger table and re-insert everything — hashes must be re-moduloed by the new capacity. That resize is O(n), but rare, so inserts are amortized O(1). Same doubling logic as dynamic arrays.

The contract that makes it all work

Sets

A set is a hashmap that stores only keys. Same costs, same mechanics. Use it whenever the question is "have I seen this before?"

04Pattern: Two Pointers

When: the array is sorted (or can be), or you're working from both ends, or comparing/merging two sequences.

Why it works: sortedness gives you monotonicity — moving a pointer changes the quantity you're tracking in a predictable direction, so you can discard candidates without checking them. That's how you delete an O(n) inner loop.

Two Sum on a sorted array — the canonical demo:

def two_sum_sorted(a, target):
    lo, hi = 0, len(a) - 1
    while lo < hi:
        s = a[lo] + a[hi]
        if s == target: return [lo, hi]
        if s < target:  lo += 1     # sum too small → only a bigger left element can fix it
        else:           hi -= 1     # sum too big → only a smaller right element can fix it
    return []

[1, 3, 4, 6, 8, 11]   target 10
 lo↑            ↑hi   1+11 = 12 too big   → hi--
 lo↑         ↑hi      1+8  = 9  too small → lo++
    lo↑      ↑hi      3+8  = 11 too big   → hi--
    lo↑   ↑hi         3+6  = 9  too small → lo++
       lo↑↑hi         4+6  = 10 ✓

Same-direction variant (reader / writer)

In-place dedup, remove-element, move-zeroes — a slow pointer marks where the next kept element goes, a fast pointer scans:

def move_zeroes(a):
    write = 0
    for read in range(len(a)):
        if a[read] != 0:
            a[write], a[read] = a[read], a[write]
            write += 1

Other members of the family: valid palindrome (ends inward), container with most water, 3Sum (sort + fix one + two-pointer the rest), merging two sorted lists.

05Pattern: Sliding Window

When: "longest / shortest / count of contiguous subarray or substring satisfying a condition."

Why it works: instead of re-examining every one of the O(n²) windows from scratch, you maintain one window and update its state incrementally as the edges move. The right edge grows the window; the left edge shrinks it when the constraint breaks. Each element enters once and leaves once ⇒ O(n) — amortized: the inner while is paid for by prior expansions (file 01 §5 energy).

Longest substring without repeating characters — the archetype:

def longest_unique(s):
    last = {}                       # char → most recent index
    left = best = 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1     # jump past the previous occurrence
        last[ch] = right
        best = max(best, right - left + 1)
    return best

The general template — worth memorizing as a shape, not code:

left = 0
for right in range(n):
    # 1. absorb a[right] into window state
    while window_is_invalid:
        # 2. evict a[left] from window state
        left += 1
    # 3. window [left..right] is valid → update answer

• Longest valid window → update the answer after the while (as above).
• Shortest valid window (min-window-substring, min-size subarray sum ≥ target) → shrink while valid, updating the answer inside the shrink loop.
• Fixed-size window → no while; slide both edges together (max-average subarray).

06Pattern: Prefix Sums

When: many range-sum queries, or "count subarrays with sum/property X" — especially when negatives make sliding windows invalid.

The idea: precompute running totals once, then any range sum is a subtraction.

a        =  [ 2,  4,  1,  3,  5]
prefix   =  [0,  2,  6,  7, 10, 15]      (prefix[i] = sum of first i elements)

sum(a[i..j]) = prefix[j+1] - prefix[i]   ← O(1) per query after O(n) prep
e.g. sum(a[1..3]) = prefix[4] - prefix[1] = 10 - 2 = 8   (4+1+3 ✓)

The power move — prefix sums + hashmap (Subarray Sum Equals K)

A subarray (i..j] sums to k ⟺ prefix[j] − prefix[i] = k ⟺ prefix[i] = prefix[j] − k. So walk left to right, and at each point ask: how many earlier prefixes equal (current prefix − k)? A hashmap counts them:

def subarray_sum(a, k):
    from collections import defaultdict
    seen = defaultdict(int)
    seen[0] = 1                     # empty prefix — subarrays starting at index 0
    total = ans = 0
    for x in a:
        total += x
        ans += seen[total - k]      # each match = one subarray ending here
        seen[total] += 1
    return ans

O(n), handles negatives, and the seen[0] = 1 line is the detail interviewers probe ("why?" — because a prefix that itself equals k forms a valid subarray from the start).

07Classic problems, worked briskly

Try to state the approach and complexity before revealing each answer.

def two_sum(nums, target):
    seen = {}
    for i, x in enumerate(nums):
        if target - x in seen:
            return [seen[target - x], i]
        seen[x] = i

from collections import Counter
def is_anagram(s, t):
    return Counter(s) == Counter(t)

def group_anagrams(strs):
    from collections import defaultdict
    groups = defaultdict(list)
    for s in strs:
        groups[tuple(sorted(s))].append(s)   # or a 26-count tuple for O(n·k)
    return list(groups.values())

Honorable mentions to have in your pocket

08Choosing the pattern — a mini decision tree

Contiguous subarray/substring, longest/shortest/count?
 ├─ all values non-negative / constraint monotone → SLIDING WINDOW
 └─ negatives involved, sum-based                → PREFIX SUM (+ hashmap)

Pairs/triples with a target relation?
 ├─ sorted (or sorting is free)  → TWO POINTERS
 └─ unsorted, need indices       → HASHMAP complement lookup

"Seen before?" / dedupe / grouping → SET / HASHMAP with canonical key

Many range-sum queries → PREFIX SUM
In-place compaction / partition → READER-WRITER POINTERS

09Common interview questions

10Self-test

Answer from memory, then open the spot-checks.

1. Walk through what d["user:42"] = v does, mechanically, in ≤ 4 steps (hash → ? → ? → ?).
2. What is load factor, and what does the map do when it gets too high? What's the cost and why is it acceptable?
3. Chaining vs open addressing — one sentence each.
4. Write two-pointer Two Sum (sorted) from memory. Then explain why discarding a[lo] when the sum is too small is safe.
5. Write the general sliding-window template (3 comment lines are enough). How does it change for "shortest valid window"?
6. sum(a[i..j]) via prefix array — the exact formula, with the off-by-one right.
7. In Subarray Sum Equals K, why initialize seen[0] = 1?
8. Design a canonical key for grouping anagrams. Give two options and their costs.
9. s += ch in a loop over n chars — total complexity and the fix?
10. Longest Consecutive Sequence in O(n): what's the trick that avoids sorting?