# The Dynamic Container

> Build your own resizable list with no help from the standard library.

Canonical URL: <https://datadriven.io/problems/the_dynamic_container>

Domain: Python · Difficulty: hard · Seniority: L4

## Problem

Implement an ArrayList via an ops list: ['append', val] adds to the end, ['get', index] returns element at index, ['size'] returns current count, ['remove', index] deletes element at index. Return the list of return values excluding None: only get, size, and remove operations contribute to output (append returns nothing).

## Worked solution and explanation

### Why this problem exists in real interviews

This tests **low-level data structure implementation**: building a dynamic array (like Python's list) from scratch. It probes understanding of amortized resizing, capacity management, and index-based operations.

---

### Break down the requirements

#### Step 1: Manage capacity and size separately

Capacity is the allocated array size; size is the number of actual elements. Double capacity when size reaches capacity.

#### Step 2: Implement append with amortized O(1)

When full, allocate a new array of double size, copy elements, then append.

#### Step 3: Implement get and remove

`get(index)` returns the element at position. `remove(index)` shifts subsequent elements left.

---

### The solution

**Dynamic array with doubling resize strategy**

```python
class ArrayList:
    def __init__(self):
        self.capacity = 4
        self.data = [None] * self.capacity
        self._size = 0
    def append(self, val):
        if self._size == self.capacity:
            self.capacity *= 2
            new_data = [None] * self.capacity
            for i in range(self._size):
                new_data[i] = self.data[i]
            self.data = new_data
        self.data[self._size] = val
        self._size += 1
    def get(self, index: int):
        if index < 0 or index >= self._size:
            raise IndexError("Index out of range")
        return self.data[index]
    def size(self) -> int:
        return self._size
    def remove(self, index: int):
        if index < 0 or index >= self._size:
            raise IndexError("Index out of range")
        for i in range(index, self._size - 1):
            self.data[i] = self.data[i + 1]
        self.data[self._size - 1] = None
        self._size -= 1
```

> **Time and Space Complexity**
>
> **Time:** `append` is O(1) amortized (O(n) during resize). `get` is O(1). `remove` is O(n) due to shifting.
> 
> **Space:** O(capacity). At most 2x the number of elements due to doubling.

> **Interviewers Watch For**
>
> Whether you explain amortized analysis. The doubling strategy means n appends cost O(n) total, making each append O(1) amortized.

> **Common Pitfall**
>
> Forgetting to null out the last position after removal. Stale references prevent garbage collection in languages with manual memory management, and it is good practice in Python too.

---

## Common follow-up questions

- Why double instead of adding a fixed increment? _(Tests amortized analysis: doubling gives O(1) amortized, fixed increment gives O(n).)_
- How would you shrink the array when many elements are removed? _(Tests shrink-on-quarter-full strategy to avoid thrashing.)_
- What is the difference between this and Python's built-in list? _(Tests knowledge of CPython's over-allocation formula.)_
- How would you implement insert at a specific index? _(Tests shifting elements right before inserting.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_dynamic_container)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.