Arrays, Strings, and Hashing Questions

Direct answer

Make a single pass over the list and accumulate counts in a hash map (Python's collections.Counter, which is a dict subclass purpose-built for this): for each string, increment its entry by one. This is O(n) time, where n is the total number of strings processed, and O(u) extra space, where u is the number of unique strings, which for typical real-world data (repeated categorical values, tokens, log lines) is far smaller than n itself, keeping the approach both time- and memory-efficient at the "millions of items" scale the question asks about.

Structured elaboration

Why a hash map is the right tool here. Counting occurrences requires answering "have I seen this exact value before, and how many times" for each item, which is precisely the operation a hash map is built to do in O(1) average time per lookup/update. Building the count dict is therefore a single O(n) pass: for each string, look up its current count (defaulting to 0 if new) and increment it. Counter does exactly this internally and additionally provides convenience methods (most_common(), direct construction from an iterable) on top of a plain dict.

Time and space, stated precisely. Time is O(n) because every one of the n input strings is visited exactly once, and each hash map update is O(1) amortized. Space is O(u), the number of distinct strings, not O(n): a list with heavy repetition (say, a categorical column with only a handful of distinct values repeated millions of times) uses memory proportional to that handful of distinct values, not to the list's full length. This distinction between n (total items) and u (unique items) is the detail that actually matters for the "millions of items" framing in the question, since it is u, not n, that determines the dict's memory footprint.

Applying the same technique at a narrower grain: counting vowels in a string. The identical hash-based counting technique applies just as well one level down, to counting occurrences of specific characters within a single string rather than counting occurrences of whole strings within a list. A case-insensitive vowel count is the same idea: fold case first (so 'A' and 'a' count as the same vowel), then check each character against a fixed small set of vowels, incrementing a running total. Because the set of vowels is fixed and tiny (5 characters), this doesn't even need a full frequency dict. A simple counter check against a frozenset suffices, which is O(n) time (n = length of the single string) and O(1) extra space, since the vowel set's size never grows with input size.

Worked example

Full runnable code with pinned test cases, including the question's own example and the vowel-counting variant:

from collections import Counter


def string_frequencies(strings):
    """O(n) time (n = total strings), O(u) extra space (u = unique strings)."""
    return dict(Counter(strings))


def count_vowels(s, vowels=frozenset("aeiou")):
    """Same hash-based technique applied to characters of one string instead
    of elements of a list: case-insensitive vowel count, O(n) time, O(1)
    extra space (the vowel set has fixed size 5, independent of len(s))."""
    return sum(1 for ch in s.casefold() if ch in vowels)


if __name__ == "__main__":
    data = ['a', 'b', 'a', 'c', 'b', 'a']
    result = string_frequencies(data)
    print(f"string_frequencies({data!r}) = {result!r}")

    vowel_tests = [
        ("Hello World", 3),
        ("AEIOUaeiou", 10),
        ("xyz", 0),
        ("", 0),
        ("Interview", 4),
    ]
    for s, expected in vowel_tests:
        r = count_vowels(s)
        print(f"count_vowels({s!r}) = {r} (expected {expected})")

Output (actual run):

string_frequencies(['a', 'b', 'a', 'c', 'b', 'a']) = {'a': 3, 'b': 2, 'c': 1}
count_vowels('Hello World') = 3 (expected 3)
count_vowels('AEIOUaeiou') = 10 (expected 10)
count_vowels('xyz') = 0 (expected 0)
count_vowels('') = 0 (expected 0)
count_vowels('Interview') = 4 (expected 4)

The first line matches the question's own example exactly: ['a','b','a','c','b','a'] -> {'a': 3, 'b': 2, 'c': 1}. The count_vowels('Interview') case is worth naming explicitly: the capital I counts alongside the lowercase e, i, e, since .casefold() runs before the membership check, giving 4 total (I, e, i, e), matching a case-insensitive count rather than an ASCII-literal one.

Trade-offs and pitfalls

• Sorting the list first and counting runs of equal adjacent elements is a valid alternative, but costs O(n log n) time versus the hash map's O(n), and it also destroys the original ordering unless a copy is sorted separately; for "moderate lists (millions of items)" as the question specifies, the linear hash-map approach is the better default.
• Counter(strings) alone already returns a fully-functional mapping; wrapping it in dict(...) here is purely to return a plain, predictable type to a caller who may not want Counter-specific behavior (like its most_common() method or its handling of missing keys returning 0 instead of raising KeyError); either is a reasonable answer, and it's worth naming the trade-off rather than silently picking one.
• For truly massive inputs that don't fit in memory as a single Python list (as opposed to "millions of items," which a modern machine handles comfortably in RAM), the same technique still applies conceptually: replace strings with a generator/iterator and update a single running Counter one item (or one fixed-size chunk) at a time via .update(), instead of ever materializing the whole input as a list. Peak memory then holds only the current item or chunk plus the running counts, not the full input; the counting operation itself does not change, only how the input is fed into it.
• A frequency count over Unicode strings needs the same normalization awareness as any other string-identity comparison: two strings that look identical but differ in Unicode representation (composed versus decomposed accented characters) will be counted as different keys unless normalized first, which matters if the input list can contain non-ASCII text.
• For the vowel-counting variant specifically, .casefold() is the correct choice over .lower() for the same reason it matters in general caseless comparison: locale-independent, more aggressive folding handles edge cases like the German sharp s correctly, though for a fixed 5-character ASCII vowel set this distinction rarely changes the result in practice; naming .casefold() anyway signals the same caseless-comparison discipline that matters whenever a comparison needs to be genuinely Unicode-safe.

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

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

Precompute a running-total array prefix where prefix[i] is the sum of the first i counts, built once in O(n). Any inclusive range sum [left, right] is then prefix[right + 1] - prefix[left], O(1). When a new minute of events arrives, append one new prefix entry (last + new_count) in O(1) rather than recomputing anything. A "last W minutes" query is just a range-sum query where the range is derived from the current length, so it reuses the same O(1) machinery.

Approach

1. Build: prefix = [0]; for each count in order, append prefix[-1] + count. prefix has n+1 entries so that prefix[0] = 0 represents "the sum of zero elements," letting the range-sum formula work uniformly even for a range starting at index 0.
2. Range query [left, right] inclusive: prefix[right + 1] - prefix[left]. This is O(1) regardless of range width, because the two boundary lookups already encode the running total up to each endpoint.
3. Streaming update: appending a new minute's count is prefix.append(prefix[-1] + new_count), O(1) amortized (Python list append), since it only ever adds one new entry using the existing last total; nothing earlier in prefix needs to change. This is what makes the update efficiently incremental: each new event only costs one addition, never a recomputation of the whole array.
4. Windowed query ("last W minutes"): since the array is indexed one entry per minute in arrival order, the last W minutes are just the range [n - W, n - 1] (clamped to 0 if W exceeds the history length), so this reuses the same O(1) range-sum formula directly.

Complexity

Build: O(n) time, O(n) space for the prefix array. Range query: O(1). Streaming append: O(1) amortized. Windowed query: O(1), same as any other range query, because the window boundary is derivable directly from the current array length.

Edge cases

• Windowed query wider than the history so far (e.g. asking for the last 60 minutes when only 5 minutes of data exist): clamp the left boundary to 0 rather than going negative, returning the sum of everything available.
• Zero-length range (left == right + 1, i.e. querying an empty window): returns 0 correctly, since prefix[right+1] - prefix[left] collapses to prefix[left] - prefix[left].

class MinuteEventCounter:
    def __init__(self, counts):
        self.prefix = [0]
        for c in counts:
            self.prefix.append(self.prefix[-1] + c)

    def range_sum(self, left, right):
        return self.prefix[right + 1] - self.prefix[left]

    def append(self, count):
        self.prefix.append(self.prefix[-1] + count)

    def last_window_sum(self, window_minutes):
        n = len(self.prefix) - 1
        left = max(0, n - window_minutes)
        return self.range_sum(left, n - 1)


counts = [10, 0, 5, 20, 3]
counter = MinuteEventCounter(counts)

print(counter.range_sum(0, 4))
print(counter.range_sum(2, 3))

counter.append(7)
print(counter.range_sum(0, 5))

print(counter.last_window_sum(3))
print(counter.last_window_sum(60))

Output:

38
25
45
30
45

Five minutes of counts [10, 0, 5, 20, 3] sum to 38 overall, and minutes 2-3 (5 + 20) sum to 25, both matching the range-sum formula directly. After a sixth minute (7 events) streams in, the full six-minute sum is 45. The last-3-minutes window covers minutes 3, 4, 5 (20 + 3 + 7 = 30); asking for a 60-minute window when only 6 minutes of history exist correctly clamps to the whole history's sum, 45.

Trade-offs and pitfalls

• This O(1)-per-minute update relies on the array being indexed one entry per minute, in order, with no gaps (exactly the shape given in the question). If events instead arrived with irregular or sparse timestamps (not one guaranteed entry per minute) and a windowed query meant "events from timestamp T-60min to now" rather than "the last 60 array slots," you would need to look up the index corresponding to a given timestamp first, which is a binary search over a parallel timestamps array (O(log n)), not O(1); the O(1) windowed-query property here is a direct consequence of the question's stated per-minute indexing, not something that survives arbitrary timestamp irregularity for free.
• Prefix sums do not support efficient updates to a value that has already been counted (e.g. correcting minute 2's count after the fact): that would require rebuilding every later prefix entry (O(n)) with this simple array, whereas a Fenwick tree (binary indexed tree) supports both point updates and prefix queries in O(log n) each, at the cost of noticeably more implementation complexity than this straight prefix array. For a purely append-only stream (as asked here), the simple array is the right level of machinery; reach for a Fenwick tree only once in-place corrections to historical counts become a real requirement.
• Memory grows without bound on an infinite append-only stream: since every new minute keeps a running prefix entry forever, a long-lived service would eventually want to either cap the retained history (e.g. only keep the last 24 hours of prefix entries, discarding older ones once no query can reference them) or periodically "re-base" by dropping fully-expired history and adjusting subsequent range-sum math accordingly.