Coding Interview: How Do You Implement a Dynamic Array and Prove Amortized O(1) Append?

Problem and Applicable Scenarios

Using a fixed array, implement a dynamic array with get(index), set(index, value), and append(value). Resize when full, explain the growth policy, boundary behavior, worst-case and amortized append time, and compare linear with geometric growth.

Assume references or fixed-size values, zero-based indexes, exceptions for out-of-range access, and append on an empty array. A public interview bank connects dynamic-array/vector implementation with Microsoft, memory management, and amortized analysis; MIT 6.006 lists dynamic-array append as amortized Θ(1).

What the Interviewer Is Evaluating

• Whether you separate size from capacity and maintain the invariant that valid items occupy the first size slots.
• Whether you choose geometric growth instead of adding one slot at a time.
• Whether you can prove the amortized bound with aggregate, accounting, or potential analysis rather than asserting O(1).
• Whether you cover zero capacity, integer overflow, allocation failure, shrinking, and middle insertion.

Clarifying Questions Before Answering

• Is only tail append required, or also middle insert, delete, and pop? Those change the complexity story.
• Are values fixed-size? Are reference semantics, iterator invalidation, or thread safety required?
• Is the goal fewer copies, lower memory overhead, or a hard latency ceiling?
• Is shrinking required? If so, should its threshold be separate from the growth threshold to avoid thrashing?

30-Second Answer Framework

I would store a backing array, size, and capacity. Append writes directly when a slot is free. When full, it allocates a larger array, copies the first size elements, and writes the new value. Geometric growth such as doubling is the key: the total number of copied elements over n appends is a geometric series below 2n, so total work is O(n) and append is O(1) amortized. The resize call itself is still O(n), so this is not a worst-case O(1) guarantee per call.

Step-by-Step Deep Dive

State and Invariant

Maintain three fields: backing array data, number of valid elements size, and allocated slots capacity. Always keep size at least zero and no greater than capacity; valid elements occupy [0, size). Append writes data[size] and increments size. get and set accept only [0, size), never an uninitialized capacity slot.

Geometric Growth Policy

When size == capacity, allocate at least max(1, capacity * 2), copy the old elements, and replace the backing reference. Capacity zero needs a special case, or multiplication still produces zero. Doubling creates a run of cheap appends comparable to the current size; a larger factor copies less often but leaves more unused space.

~~~java final class DynamicArray { private Object[] data = new Object[0]; private int size = 0;

public void append(Object value) { if (size == data.length) { int next = Math.max(1, data.length * 2); Object[] grown = new Object[next]; System.arraycopy(data, 0, grown, 0, size); data = grown; } data[size++] = value; }

public int size() { return size; }

public Object get(int index) { check(index); return data[index]; }

public void set(int index, Object value) { check(index); data[index] = value; }

private void check(int index) { if (index < 0 || index >= size) throw new IndexOutOfBoundsException(); } } ~~~

Object[] is a common way to illustrate implementation under generic type erasure; production code still needs an explicit policy for nulls, allocation failure, and concurrency. The invariant and complexity do not depend on Java.

The Amortized Proof

Assume capacity starts at 1 and doubles. Across n appends, ordinary writes cost n constants; resize copies occur at capacities 1, 2, 4, 8, and so on, for a total below 2n. Total work is therefore below 3n plus initialization, giving O(1) amortized cost per operation.

This is a guarantee over a worst-case sequence, not an average over random inputs. The append that triggers a resize still copies Θ(n) elements, so one call has O(n) worst-case time. get and set are O(1) worst case, and the backing storage is O(n).

Linear Growth and Shrinking

Adding only c slots at a time makes the copy costs roughly c + 2c + ...; inserting n elements costs Θ(n²), so append degrades to Θ(n) amortized. Geometric growth is usually the better trade-off, though a larger factor increases peak unused space.

If pop is supported, shrink below a low-water mark. Keep growth and shrink thresholds apart—for example, double when full and halve below one quarter—to avoid repeated moves when append and pop alternate. Shrinking preserves amortized O(1) tail operations but adds release and copy pauses.

Testable Boundaries

Test the first append to an empty array, append at exact capacity, repeated growth, duplicate references, negative indexes, index == size, huge capacities, overflow, and allocation failure. A controlled copy counter can verify that n appends perform Θ(n) total copies; checking only final contents would let a quadratic linear-growth implementation pass.

High-Quality Sample Answer

I would separate the backing array, size, and capacity, with valid elements always in the first size positions. Append writes into free capacity; when full, it allocates twice the capacity, copies the old elements, and then writes the value. An initial zero capacity gets a one-slot special case.

The doubling proof is the important part: over n appends, resize copies stay below 2n; adding n constant writes gives O(n) total work and O(1) amortized append. The resize call itself remains O(n), so amortized cost is not a per-call latency ceiling. Linear growth costs Θ(n²) in total copies. If shrinking is required, I would use hysteresis and test empty input, bounds, overflow, and allocation failure.

Common Mistakes

• Add one slot whenever full → total copying becomes quadratic → use geometric growth and show the series.
• Call append worst-case O(1) → ignore the resize copy → distinguish one-call O(n) from sequence amortized O(1).
• Validate get against capacity → return an uninitialized slot → require index to be at least zero and below size.
• Double a zero capacity → the array never grows → use a minimum capacity of one.
• Shrink immediately at low usage → alternating append/pop causes repeated moves → separate growth and shrink thresholds.

Follow-Up Questions and Responses

What if every append must have O(1) worst-case time?

A contiguous array resize performs O(n) migration, so it cannot promise that hard bound as written. A segmented array, incremental migration, or known upper-bound preallocation can change the trade-off, at the cost of locality, index constants, or space. First confirm that the requirement is truly worst-case.

What changes if the growth factor is 1.25 instead of 2?

Any factor strictly greater than 1 still gives amortized O(1) tail append, but copies happen more often and spare space is lower. As the factor approaches 1, constants grow; choose using memory budget, allocator behavior, and latency goals rather than Big-O alone.

How do you prove linear growth is O(n²)?

If each resize adds c slots, the j-th resize copies about jc elements. The first n elements trigger about n/c resizes, so the total is c + 2c + ... + (n/c)c = Θ(n²). Amortized append is therefore Θ(n).

How does middle insertion change the complexity?

Even with spare capacity, middle insertion shifts a suffix and is O(n) worst case. Resize copying is additional work; dynamic arrays are optimized for random access and tail operations, not every kind of insertion.

How would concurrent append work?

Use a lock, single-thread ownership, or an atomic-index protocol with coordinated resizing. Making size atomic alone does not protect the whole check-capacity, allocate, copy, and publish sequence. If concurrency is not required, state the single-thread boundary explicitly.