The Dynamic Container

A hard Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
hard
Seniority
L4
Asked in
Junglee Games

Problem

You're implementing a dynamic array from scratch (the kind that backs a built-in list) and exercising it with a replay log of commands in ops, where each entry's first element names the operation: ['append', val] adds val to the end, ['get', index] reads the element at that position, ['size'] reads the current element count, and ['remove', index] deletes the element at that position and shifts everything after it one place left. Manage your own backing storage that grows as elements are added rather than leaning on the standard library to resize for you. Replay the commands in order and return the values produced by the get and size operations only, in the order they occur, since append and remove produce no output.

Grow your own storage before the standard library does it for you.

Example 1

Input:

ops = [["append",10],["append",20],["append",30],["size"],["get",1],["remove",0],["get",0],["size"]]

Output:

[3,20,20,2]

Example 2

Input:

ops = [["size"],["append",5],["append",6],["append",7],["append",8],["append",9],["size"],["get",4],["remove",2],["get",2],["size"]]

Output:

[0,5,9,8,4]

Worked solution and explanation

What's really being tested

Strip the costume and this is two problems wearing one hat. The interesting half is the dynamic array itself: how do you grow fixed-size storage without paying O(n) on every single append? The boring-but-easy-to-botch half is the driver loop that replays ops and collects output from exactly the right operations. Candidates who reach for a plain Python list are answering the wrong question. The point is to show you know what list does under the hood: a backing buffer with spare capacity, doubled when it fills, so n appends cost O(n) total instead of O(n^2).

Break down the requirements

Step 1: Manage capacity and size separately

Capacity is the allocated array size; size is the number of actual elements. Track them as separate numbers, because the whole resizing trick lives in the gap between them.

Step 2: Grow on demand

When size reaches capacity, allocate a new array of double the size, copy elements over, then append. Doubling (not adding a fixed amount) is what keeps append O(1) amortized.

Step 3: Implement get and remove

get(index) returns the element at position in O(1). remove(index) shifts every subsequent element one slot left in O(n), then drops the count.

Step 4: Drive the class from a single entrypoint

The grader calls a single top-level driver, array_list_demo(ops). Define the ArrayList class inside the driver, then replay each op against one instance, collecting the return value of every get and size into a results list that you return.

The solution

Dynamic array with doubling resize strategy
def array_list_demo(ops: list[list]) -> list:
    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

    arr = ArrayList()
    results = []
    for op in ops:
        name = op[0]
        if name == "append":
            arr.append(op[1])
        elif name == "get":
            results.append(arr.get(op[1]))
        elif name == "size":
            results.append(arr.size())
        elif name == "remove":
            arr.remove(op[1])
    return results

Common follow-up questions