Microsoft interview guide

Problem

You are given a list of account records. Each record is a list of strings whose first entry is a person's display name and whose remaining entries are email addresses that belong to that account.

Two records belong to the same person if they share at least one email address, and this relation is transitive: if A shares an email with B and B shares one with C, then A, B, and C are all the same person. Two people can have the same display name; that alone does not merge them.

Merge the records and return one list per person, formatted as the name followed by that person's distinct emails in sorted (ASCII) order. The order of the people in the output does not matter.

• Up to a few thousand records; each holds a name plus between one and a dozen emails.
• Names and emails are short ASCII strings (a few dozen characters at most).
• Every record has at least one email, and all records that end up merged carry the same name.

Examples

• [["Priya","[email protected]","[email protected]"],["Priya","[email protected]","[email protected]"],["Tom","[email protected]"],["Priya","[email protected]"]] → [["Priya","[email protected]","[email protected]","[email protected]"],["Priya","[email protected]"],["Tom","[email protected]"]]. The first two Priya records share [email protected]; the third Priya shares nothing and stays a separate person.
• [["Lee","[email protected]","[email protected]"],["Lee","[email protected]"],["Lee","[email protected]","[email protected]"]] → [["Lee","[email protected]","[email protected]","[email protected]"]]. The last record bridges the first two, so all three collapse into one person.
• [["Sam","[email protected]"],["Sam","[email protected]"],["Sam","[email protected]"]] → three unchanged records. Same name, no shared email, no merge.

Hints

1. Think of each email as a node. What connects two nodes?
2. The answer is one group per connected component. Which structure finds components incrementally as you read records?
3. Union-find keyed by email (or by account index); then group emails by their root and sort each group.

Approach

Treat every email as a graph node and connect all emails that appear in the same record. A person is a connected component of that graph. The brute force compares every pair of records for a shared email and merges repeatedly until nothing changes, which can cost O(n²) comparisons per pass and needs multiple passes before it stabilizes.

Two clean linear-ish solutions exist. The DFS version builds an adjacency list (each record's first email connected to every other email in that record is enough, because they only need to be in the same component) and runs a DFS from every unvisited email, collecting the component. The union-find version avoids building adjacency lists: keep a map from email to the index of the first account that mentioned it. When a record contains an email you have seen before, union the current account index with that earlier one. After one pass, every email maps to an account and every account has a root; group emails by root, sort, and prepend the name.

Why union by account index rather than by email? Fewer nodes (n accounts instead of up to 10n emails), and the name comes for free from the root account. Both approaches are acceptable; union-find has the edge that the merge relation is naturally incremental, which is exactly what the "records arrive over time" follow-up needs.

The sort at the end dominates: each group's emails are sorted, and across all groups that is O(E log E) string comparisons on emails of length up to 30.

Solution (Python)

class Solution:
    def accountsMerge(self, accounts: list[list[str]]) -> list[list[str]]:
        n = len(accounts)
        parent = list(range(n))

        def find(x: int) -> int:
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        size = [1] * n

        def union(a: int, b: int) -> None:
            ra, rb = find(a), find(b)
            if ra == rb:
                return
            if size[ra] < size[rb]:          # union by size: attach the smaller tree
                ra, rb = rb, ra
            parent[rb] = ra
            size[ra] += size[rb]

        # Map each email to the first account index that mentioned it; union on repeats.
        owner: dict[str, int] = {}
        for i, record in enumerate(accounts):
            for email in record[1:]:
                if email in owner:
                    union(i, owner[email])
                else:
                    owner[email] = i

        # Group emails by the root account of their owner.
        groups: dict[int, list[str]] = {}
        for email, i in owner.items():
            groups.setdefault(find(i), []).append(email)

        return [[accounts[root][0]] + sorted(emails) for root, emails in groups.items()]

Complexity

Time: O(E log E), where E is the total number of emails: the union-find pass is O(E α(E)) thanks to path halving plus union by size (with path halving alone it would be O(E log n) amortised) and the final sort of each group costs O(E log E) overall (each comparison is O(L) for email length L, usually stated as a constant). Space: O(E) for the owner map and groups, plus O(n) for the parent and size arrays.

Follow-ups

• Records arrive over time; support addAccount(record) and getPerson(email) queries. Union-find is the natural fit: each new record unions its emails' owners as above, so an add is O(k α) for a k-email record and a lookup is a single find. The DFS approach would need to re-run per query. Mention that deletions (an email is removed from a person) break union-find, which cannot un-merge; you would need to rebuild or use a different structure.
• The name can differ across merged records. Which name do you output? Clarify before coding. Options: the name from the earliest record (what the root index gives you), the most frequent name, or all names; noticing the assumption matters more than which rule you pick.
• Why does it suffice to link only the first email of each record to the others rather than all pairs? Because connectivity is transitive: a star from the first email reaches every email in the record with k-1 edges instead of k(k-1)/2. In the union-find version the same effect comes from unioning to the first owner.
• Emails are case-insensitive or have +tags. Now what? Normalize before hashing (lowercase, strip the +tag for providers that ignore it). Whether two normalized strings count as "the same person" is a product decision, not an algorithmic one, and saying so is the expected answer.

Company variations

• Google. Commonly reported as an identity-resolution framing (merging user records across products); expect follow-ups on records arriving over time and on billion-scale distributed connected components, and be ready to name which identifier types are trustworthy enough to merge on.
• Meta. The coding bar rewards finishing the union-find pass correctly and quickly; get the base solution working and tested inside 20-25 minutes before volunteering the multi-identifier or streaming extensions.
• Amazon. Often framed as consolidating customer profiles rather than plain emails; narrate the union-by-first-owner trick as your "dive deep" moment and have a metric-backed story ready for the inevitable Leadership Principle question mid-round.
• Apple. Teams owning account or device identity are commonly reported to push straight into the multi-identifier-type variant (email, phone, device ID) as the main event, and to ask which identifier kinds are strong enough to merge on versus which need a manual review step.
• Microsoft. Interviewers commonly reported to hint toward union-find if you open with an O(n²) pairwise-comparison brute force; naming the structure and the first-owner trick up front heads that off, and the domain framing often skews toward directory/tenant identity given Microsoft's enterprise products.
• Netflix. Given the loop's senior skew, expect the billion-records distributed variant (hash-partition, per-partition union-find, iterate cross-partition links) to be asked without prompting, with real weight on why component diameters shrink each round.

Tests

def test():
    s = Solution()
    def norm(out):
        return sorted(out)
    r = s.accountsMerge([["Priya","[email protected]","[email protected]"],["Priya","[email protected]","[email protected]"],["Tom","[email protected]"],["Priya","[email protected]"]])
    assert norm(r) == [["Priya","[email protected]","[email protected]","[email protected]"],["Priya","[email protected]"],["Tom","[email protected]"]]
    r = s.accountsMerge([["Lee","[email protected]","[email protected]"],["Lee","[email protected]"],["Lee","[email protected]","[email protected]"]])
    assert norm(r) == [["Lee","[email protected]","[email protected]","[email protected]"]]
    r = s.accountsMerge([["Sam","[email protected]"],["Sam","[email protected]"],["Sam","[email protected]"]])
    assert norm(r) == [["Sam","[email protected]"],["Sam","[email protected]"],["Sam","[email protected]"]]
    # Single record with a repeated email
    r = s.accountsMerge([["Uma","[email protected]","[email protected]","[email protected]"]])
    assert norm(r) == [["Uma","[email protected]","[email protected]"]]
    # Chain joined only by the final record
    r = s.accountsMerge([["K","k1@z","k2@z"],["K","k3@z","k4@z"],["K","k5@z"],["K","k4@z","k5@z","k1@z"]])
    assert norm(r) == [["K","k1@z","k2@z","k3@z","k4@z","k5@z"]]
    # ASCII order puts digits and capitals before lowercase
    r = s.accountsMerge([["N","z@n","9@n","Q@n","a@n"]])
    assert norm(r) == [["N","9@n","Q@n","a@n","z@n"]]
    # Many records, all disjoint, output count must match input count
    many = [[f"P{i}", f"p{i}@m"] for i in range(500)]
    assert len(s.accountsMerge(many)) == 500
    # Many records that all share one hub email collapse to one person
    hub = [["H", "hub@m", f"h{i}@m"] for i in range(300)]
    r = s.accountsMerge(hub)
    assert len(r) == 1 and len(r[0]) == 302 and r[0][0] == "H"
    print("ok")
test()

Prompt

"Advertisers pay per click. Design the system that ingests click events and answers 'how many clicks did ad X get in the last M minutes' and 'top 100 ads by clicks in the last hour'. Billing depends on these numbers."

Clarifying questions

• What is a click event and who produces it? Ad-serving frontends emit one event per user click: ad_id, click_id, user_id, timestamp, country, ip, plus a few attributes.
• How fresh must the counts be? Dashboards want under one minute of lag. Billing runs on end-of-day numbers and must be exact.
• Are duplicates possible? Yes. Clients retry, and frontends may re-emit on timeout. Each click carries a globally unique click_id.
• What about late events? Events can arrive minutes late due to buffering; a small fraction hours late. We need a policy, not a promise that it never happens.
• Filters on the queries? Yes: by country and by ad campaign. Assume at most a handful of low-cardinality dimensions.
• Is fraud detection in scope? Out of scope, but the pipeline must be able to attach a "suspect" flag later, so raw events must be retained.
• How long is history kept? Raw events for 90 days; minute-level aggregates for 2 years.

Requirements

Functional

• Ingest click events at scale without loss.
• Query 1: click count for one ad_id in a time window, at one-minute granularity.
• Query 2: top-K ads by clicks over a window, optionally filtered by country.
• Exact, deduplicated counts for billing; near-real-time approximate counts for dashboards.

Non-functional

• End-to-end freshness under 60 seconds for the streaming path.
• No double counting for billing; no lost events even during failover.
• Correctness must be provable: the batch path must be able to recompute any window from raw data.

Back-of-envelope

• Assume 1 billion ad impressions per day is too low for a Google-scale system, so take 10 billion impressions/day with a 1% click-through rate: 100 million clicks/day.
• Average: 100 M / 86,400 s = about 1,160 clicks/s. Peak at 5x average is about 6,000 events/s. Ingestion volume is small; the hard part is correctness, not throughput.
• Event size: ~0.2 KB. Raw storage: 100 M x 0.2 KB = 20 GB/day, 1.8 TB for 90 days before compression, roughly 0.5 TB compressed.
• Aggregates: say 2 million distinct ads active per day. Minute-level rows per day: 2 M ads x 1,440 minutes would be 2.9 billion rows if every ad clicked every minute, but most ads are sparse; assume 5% density, so ~150 M rows/day at ~50 bytes = 7.5 GB/day, about 5.5 TB over 2 years. This is a modest columnar table.
• Query load: a few thousand dashboard queries per second at most; each top-K query touches at most 60 minute-buckets.
• Ingest bandwidth: 6,000 x 0.2 KB = 1.2 MB/s peak. Trivial, and worth saying out loud because it reframes the problem correctly.

High-level design

Two paths share one durable log. Ad frontends write events to a partitioned, replicated log (partitioned by ad_id so all events for one ad land in one partition in order). A streaming aggregator consumes the log, deduplicates by click_id within a bounded window, and emits per-minute counts keyed by (ad_id, minute, country) to an aggregate store. A batch job replays the raw log from durable object storage nightly, computes exact counts with full deduplication, and overwrites the aggregate rows for that day. The query service reads the aggregate store and, for top-K, either a pre-materialised per-minute heap or an on-demand scan over one hour of rows.

flowchart LR
  FE[Ad serving frontends] --> Log[Partitioned event log]
  Log --> Agg[Streaming aggregator with dedup]
  Log --> Raw[Raw event archive in object storage]
  Agg --> Store[Aggregate store keyed by ad minute country]
  Raw --> Batch[Nightly batch recompute]
  Batch --> Store
  Store --> Query[Query service]
  Query --> Dash[Dashboards]
  Query --> Bill[Billing export]
  Agg --> TopK[Per-minute top-K materialiser]
  TopK --> Store

The log is the contract between the two paths. Because both compute from the same immutable events, disagreement between them is a bug you can find, not a mystery.

Data model & APIs

Raw event (log record) click_id (uuid), ad_id, campaign_id, user_id, country, ts_event (client), ts_ingest (server), attributes (map).

Aggregate table (columnar, partitioned by day, sorted by ad_id, minute): ad_id, minute_bucket, country, click_count, source (stream|batch), version. The source and version columns let the batch path overwrite streaming rows without ambiguity and let readers prefer batch rows when both exist.

Top-K table: minute_bucket, country, rank, ad_id, click_count holding the top 1,000 per minute so hourly top-100 can be approximated by merging 60 lists (see the deep dive on why this is approximate).

Dedup state: per aggregator partition, a set of click_id seen in the last N hours, backed by a compact probabilistic filter plus an exact store for the most recent window.

APIs

• POST /events : batch of click events; returns per-event ack. Idempotent on click_id.
• GET /ads/{ad_id}/clicks?from=&to=&country= : returns minute buckets and total. Header indicates whether any bucket is still stream-sourced (not yet reconciled).
• GET /ads/top?window=1h&k=100&country= : returns ranked list with counts.
• GET /reconciliation/{day} : status of the batch overwrite and delta between stream and batch totals.
• Internal: replay(partition, from_offset, to_offset) to rebuild aggregates after a bug.

Deep dives

Exactly-once counting, and what that phrase really means

No network gives exactly-once delivery; what you can build is effectively-once processing. Three places duplicate: the client retrying, the frontend re-publishing after a log timeout, and the aggregator reprocessing after a crash. Handle each separately.

• Client and frontend duplicates carry the same click_id. The aggregator keeps a dedup set per partition. Because the log is partitioned by ad_id, all copies of a click land in the same partition, so the set is local and needs no coordination.
• Aggregator crash duplicates are solved by making the output commit atomic with the input offset commit. Concretely, the aggregator writes a checkpoint containing (partition, offset, dedup set snapshot, pending minute counts) to durable storage, and only then commits the offset. On restart it reloads the checkpoint and resumes from the recorded offset. Any events between the checkpoint and the crash are reprocessed, but the dedup set catches them.
• Downstream writes to the aggregate store must be idempotent too: write count for (ad_id, minute, country, version) as an upsert, never an increment. Increments are where double counting sneaks in.

Interviewers push on how big the dedup set gets. At 6,000 events/s, one hour is 21.6 M ids; a 16-byte id in a hash set is ~350 MB per hour across the fleet, divided over partitions, which is affordable for a few hours. Beyond that window, fall back to the batch path for exactness and accept that a click arriving six hours late twice may be counted twice in the streaming view but not in billing.

Late events, watermarks and when to close a minute

A minute bucket cannot be finalised the moment the wall clock passes it, because events for that minute are still arriving. The aggregator tracks a watermark per partition: the event timestamp below which it believes no more events will arrive, computed as the max event time seen minus an allowed lateness (say 5 minutes). Buckets older than the watermark are emitted and marked closed. Events arriving after that go to one of two places: a correction path that re-emits the bucket with a higher version, or a "late" side output that only the batch path reads. The choice depends on how much dashboard churn is acceptable. For ads, a good answer is: apply corrections for up to one hour, then leave it to nightly reconciliation.

The reason to use event time rather than ingest time is billing fairness: a click made at 23:59 belongs to that day even if it arrived at 00:03; that is why the distinction exists.

Top-K over a sliding hour is the genuinely hard query

Per-minute top-K lists do not compose into an exact hourly top-K: an ad that is 1,001st in every minute could be 50th over the hour. Options:

1. Exact: scan all (ad_id, count) rows for the 60 minutes, sum, and take the top 100. With 2 M active ads and sparse density that is on the order of tens of millions of rows; a columnar store can do it in a few seconds, which is acceptable for a dashboard with caching but not for interactive slicing.
2. Approximate with error bounds: keep per-minute lists of the top 1,000 plus a sketch (a count-min sketch per minute) so any ad's hourly count can be estimated; merge lists, then verify candidates against the sketch. Bound the error and show it in the UI.
3. Pre-aggregate sliding windows: materialise top-K for 1-minute, 5-minute and 1-hour tumbling windows in the streaming job. Queries snap to window boundaries. This is what most production dashboards actually do, trading query flexibility for cheap reads.

A strong candidate proposes (3) for the dashboard and (1) for billing-grade reports, and explains that the filters (country) multiply the materialised state by the number of filter values, which is why the dimensions must stay low-cardinality.

The lambda-style reconciliation and why it is not optional here

Billing needs an exact number and an audit trail. The nightly batch job reads the raw archive, deduplicates globally (a sort by click_id across the whole day, no time-window limit), applies any fraud flags that arrived during the day, and rewrites the day's aggregate rows with source=batch. Readers prefer batch rows. The reconciliation report compares stream totals to batch totals per ad; a delta above a threshold pages the on-call because it means the dedup window or the watermark is mis-tuned. Interviewers like to hear that the batch path is the safety net that lets the streaming path be simple, and that you would not attempt to make the streaming path billing-grade on its own.

What breaks first

The aggregator's per-partition state. Partitioning by ad_id is correct for dedup locality but creates skew: a viral ad can send 30% of all clicks to one partition. Mitigate with sub-partitioning of hot ads (ad_id + salt) and a second-stage merge of the salted counts, accepting that dedup for that ad now spans a few partitions, so the dedup set for hot ads is sharded by click_id hash within the ad's sub-partitions. Most candidates miss that salting breaks the single-partition dedup assumption; catching it is an L6 signal.

Failure modes & follow-ups

• Aggregator falls behind by 20 minutes. Watermarks stall, dashboards go stale but stay correct. Scale by adding consumers and repartitioning; never skip events. Show consumer lag as a first-class metric.
• Aggregate store loses a day of rows. Replay from the raw archive; this is why raw events are kept 90 days and why the archive write is on the critical path for durability, not an afterthought.
• A bug undercounts for a week. Bump the aggregator version, replay from the log for the affected offsets, and let version ordering on upsert overwrite bad rows. Explain that this is only possible because outputs are upserts keyed by version.
• Clock skew on clients. Clamp client timestamps to within a window of server ingest time; treat wild values as ingest-time.
• Can you count impressions too? Impressions are 100x clicks (600 K/s peak); the same architecture works, but the dedup set becomes memory-bound and you would move to a probabilistic filter with a small false-positive rate, which undercounts slightly and is acceptable for impressions but not for billed clicks.

Level rubric

• L4 pass: Draws log, stream aggregator, aggregate store and query service. Explains dedup by click_id and per-minute buckets. Gets the arithmetic right and notes throughput is modest.
• L5 pass: Adds the batch reconciliation path and explains why billing reads batch rows. Describes checkpoint-plus-offset commit for crash safety and upserts instead of increments. Handles late events with a watermark and a defined lateness policy. Explains why per-minute top-K does not compose and proposes materialised windows.
• L6 pass: Identifies partition skew from hot ads and reconciles salting with dedup locality. Quantifies dedup memory and picks a window from the numbers. Proposes a versioned-output scheme that makes replay after a bug safe, and a reconciliation report with alerting as an operational contract. Discusses which guarantees the streaming path deliberately does not give.

Company variations

• Google. This is a slice of Ads reporting and Ads-adjacent interviewers pose it readily, usually to L5+ candidates; expect the round to be decided by "the aggregator crashes after writing counts but before committing its offset — what happens?" A version-keyed upsert with a bounded dedup window passes; "we use exactly-once mode" without the mechanism behind it does not.
• Meta. Expect the framing pulled toward a consumer feature — counting likes or video views in near-real-time rather than ad billing — so lead with how the freshness-vs-exactness split (dashboard estimate vs. billing-grade number) changes when the number drives a user-visible counter instead of an invoice.
• Amazon. The operational cost of the dedup state and the reconciliation job (what pages on-call when stream and batch totals diverge) tends to get more attention than the query API; have a dive-deep story ready since finding a root cause in a discrepancy report maps directly onto that principle.
• Apple. The round tends to stay on one deep piece — most likely the watermark/late-event policy or the exactly-once mechanics — rather than covering ingestion through query serving end to end.
• Microsoft. Clarify early whether this sits behind an Azure-style analytics pipeline or an internal telemetry system, since that shifts whether the interviewer wants a streaming-engine-specific answer or a more general watermark-and-replay discussion; thinking out loud through the crash-recovery case is rewarded even before you land on checkpointed offsets.
• Netflix. Given the senior-skewed bar and the streaming-infrastructure culture, be ready to volunteer the partition-skew-from-hot-items problem and the batch-reconciliation safety net unprompted — this is one of the higher-depth design rounds in the guide.

Problem

You are implementing a growable array on top of fixed-size blocks of memory. When the array is full and another element is appended, you must allocate a new block, copy every existing element into it, and free the old one.

Three growth policies are on the table:

• Doubling: new capacity = 2 × old capacity.
• Factor 1.5: new capacity = ⌈1.5 × old capacity⌉.
• Additive: new capacity = old capacity + 16.

For each policy, derive the total number of element copies performed over n appends starting from an empty array, and hence the amortized cost per append. Then implement the array with a configurable growth policy and a counter that records every element copy, so the derivation can be checked empirically.

• Copying one element costs 1. Allocation and freeing cost nothing for this analysis.
• Start with capacity 1 under every policy.

Examples

• Doubling, n = 8 appends from capacity 1: resizes happen when going to sizes 2, 3, 5 (capacities 1 → 2 → 4 → 8), copying 1 + 2 + 4 = 7 elements in total. Seven copies for eight appends: under one copy per append on average.
• Doubling, n = 1,000,000: total copies = 1 + 2 + 4 + ... + 524,288 = 1,048,575, just over n and always under 2n. Amortized cost ≈ 1 copy plus the write itself.
• Additive by 16 from capacity 1, n = 1,000,000: a resize every 16 appends, copying 1, 17, 33, ... elements over about 62,500 resizes. Total ≈ 16 × (1 + 2 + ... + 62,500) ≈ 31 billion copies. Amortized cost ≈ n / 32 ≈ 31,000 copies per append, which is Θ(n).

Hints

1. Write down the sizes of the arrays that get copied. Under doubling they form a geometric series; what does that sum to?
2. Under additive growth the copied sizes form an arithmetic series. What does that sum to?
3. For the accounting view: charge each append 3 units. One pays for the write. Where do the other two go, and why is the bank never negative at a resize?

Approach

Aggregate method. Under a multiplicative policy with factor g, the arrays that get copied have sizes c, gc, g²c, ... up to at most n. The sum of a geometric series with ratio g is bounded by its largest term times g/(g − 1). For doubling that bound is 2n; for factor 1.5 it is 3n. So n appends cost O(n) copies in total, which is O(1) per append amortized, even though any single append can cost Θ(n).

Under additive growth by a constant k, the copied sizes are k, 2k, 3k, ..., roughly n/k terms, which sums to about n²/(2k). That is Θ(n²) total, so Θ(n) per append amortized. Growing by a constant does not help, no matter how large the constant: it only changes the constant factor of a quadratic.

Accounting method (the more illuminating one, because it explains why rather than just summing). Charge each append 3 tokens. One token pays for writing the element into its slot. The other two are saved with the element. When the array of capacity c fills up and doubles, the c/2 elements added since the last resize each carry two saved tokens, c tokens in total, which is exactly enough to pay for copying all c elements into the new block. The bank never goes negative, so the true cost of n appends is at most 3n.

Why doubling and not more? A larger factor copies less but wastes more memory: right after a resize, the array is only 1/g full. Factor 2 wastes up to half. Factor 1.5 wastes up to a third, and has a subtle allocator benefit: the freed blocks from earlier resizes can eventually be coalesced to fit a later one, which is impossible with exact doubling. CPython's list uses roughly 1.125×, Java's ArrayList 1.5×, Go slices 2× until 256 elements and then taper toward 1.25×. All are multiplicative; none are additive.

Solution (Python)

class DynamicArray:
    """Fixed-block growable array that counts element copies.

    growth is either a float factor (>1) or a tuple ("add", k) for additive growth.
    """

    def __init__(self, growth=2.0, initial_capacity: int = 1):
        self._growth = growth
        self._cap = max(1, initial_capacity)
        self._data = [None] * self._cap
        self._n = 0
        self.copies = 0          # total element copies performed by resizes
        self.resizes = 0

    def _next_capacity(self) -> int:
        if isinstance(self._growth, tuple):        # ("add", k)
            return self._cap + self._growth[1]
        return max(self._cap + 1, math.ceil(self._cap * self._growth))

    def _grow(self) -> None:
        new_cap = self._next_capacity()
        new_data = [None] * new_cap
        for i in range(self._n):                   # the expensive part
            new_data[i] = self._data[i]
        self.copies += self._n
        self.resizes += 1
        self._data, self._cap = new_data, new_cap

    def append(self, x) -> None:
        if self._n == self._cap:
            self._grow()
        self._data[self._n] = x
        self._n += 1

    def __len__(self) -> int:
        return self._n

    def __getitem__(self, i: int):
        if not 0 <= i < self._n:
            raise IndexError(i)
        return self._data[i]

    def capacity(self) -> int:
        return self._cap


def amortized_copies_per_append(growth, n: int) -> float:
    arr = DynamicArray(growth)
    for i in range(n):
        arr.append(i)
    return arr.copies / n

Complexity

Time: a single append is O(1) except at a resize, where it is O(current size). Over n appends the total is O(n) for any constant multiplicative factor (at most 2n copies for doubling, 3n for factor 1.5), and Θ(n²) for additive growth. Amortized per append: O(1) versus Θ(n). Space: O(n) for both, but the multiplicative policy holds up to (g − 1)/g of the block unused right after a resize, and during the copy both blocks are live, so peak usage briefly reaches (1 + g) × n slots.

Follow-ups

• Does shrinking the array when it gets sparse keep amortized O(1)? Only if the shrink threshold is far from the grow threshold. Halving the capacity when the array drops to 1/2 full is a trap: an alternating append/pop at the boundary triggers a resize on every operation. Shrinking at 1/4 full, to half the capacity, restores the O(1) amortized bound, because after any resize the array is exactly half full and needs Θ(n) operations before the next one.
• Amortized versus average-case: what is the difference? Amortized is a worst-case guarantee over any sequence of operations, with no probability involved. Average-case assumes a distribution over inputs. A dynamic array's append is amortized O(1) for every adversarial sequence; a hash table's insert is average-case O(1) but can be Θ(n) on adversarial keys.
• When does amortized O(1) not suffice? Latency-sensitive systems: a single append that copies a hundred million elements stalls the caller for tens of milliseconds even though the average is fine. Real-time systems either preallocate, or use structures with worst-case bounds such as a chunked list (a list of fixed blocks, so no element ever moves) or incremental resizing that copies a few elements per operation.

Company variations

• Google. Usually a two-minute detour inside a coding round: the candidate uses a list, says append is O(1), and the interviewer asks "always?" A good answer states the geometric-series bound in one sentence and mentions that constant growth is quadratic. A related question asks for the same analysis on a hash table's rehash or a string builder.
• Meta. Expect this as a quick complexity challenge right after you claim append is O(1); give the geometric-series bound in a sentence and move on, since the round rewards finishing problems over a long derivation.
• Amazon. The interviewer is listening for whether you can rigorously justify a complexity claim rather than assert it; walk the aggregate or accounting argument through explicitly, which is the root-cause rigor the Dive Deep principle rewards.
• Apple. On an infrastructure or systems team, expect a real follow-up into the latency spike a large resize causes and how incremental resizing or chunked lists avoid it; on an app team the question is more likely to stop at "why doubling, not adding a constant?"
• Microsoft. Narrate the accounting-method argument (charge 3 tokens, two saved per append) as you derive the bound — interviewers here commonly reward that visible reasoning over a bare assertion of O(1) amortized.
• Netflix. Given a production-reliability lens, raise the "does amortized O(1) suffice for a latency-sensitive path?" question yourself and name preallocation or chunked lists as the fix, rather than stopping at the amortized-cost derivation.

Tests

def test():
    # correctness as a container
    a = DynamicArray()
    for i in range(1000):
        a.append(i * i)
    assert len(a) == 1000 and a[0] == 0 and a[999] == 999 * 999
    try:
        a[1000]; assert False
    except IndexError:
        pass

    n = 100_000
    # doubling: total copies = final capacity - 1 < 2n, so amortized < 2 copies per append
    assert amortized_copies_per_append(2.0, n) < 2.0
    # factor 1.5: bounded by 3n in theory, comfortably under 2n in practice
    assert amortized_copies_per_append(1.5, n) < 3.0
    # additive growth: quadratic, roughly n/32 copies per append for k = 16
    add = amortized_copies_per_append(("add", 16), 20_000)
    assert add > 20_000 / 40, add
    # doubling copies exactly the geometric series 1 + 2 + ... + 2^k < n
    d = DynamicArray(2.0)
    for i in range(n):
        d.append(i)
    assert d.copies == d.capacity() - 1 and d.capacity() >= n
    # resizes grow logarithmically for doubling, linearly for additive
    assert d.resizes <= 20
    e = DynamicArray(("add", 16))
    for i in range(1600):
        e.append(i)
    assert e.resizes == 100          # capacity 1 + 16 per resize must reach 1600
    print("ok")
test()