How do you implement the containers you usually import?

In this article

1. Before you start
2. Why interviewers ask this
3. The containers you usually import, from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

This page belongs to the machine coding rounds guide, which explains how these rounds are run.

Why interviewers ask this

A candidate who calls a library container without knowing its cost cannot reason about it when the program is slow. Interviewers therefore ask you to build the container from an array and say what each operation costs.

Candidates report prompts such as designing a simple hash map without the Standard Template Library (STL), writing a min-heap with enqueue, dequeue and peek, and explaining how a concurrent hash map locks. These are candidate reports, not a statement of what any company asks.

A weak answer recites the library's behaviour ("a hash map is constant time"). A strong answer writes the code, names the assumption behind each cost, and says what breaks: a skewed hash, a resize that forgets to re-place keys, a heap index off by one. Ask first whether the standard library is allowed, because the prompt often forbids it.

The containers you usually import, from first principles

Binary heap

A binary heap is a complete binary tree stored in an array in which every parent is ordered before its children, so the smallest item of a min-heap always sits at the first index and can be read in constant time while insert and removal take logarithmic time.

Load factor

The load factor is the ratio of stored entries to buckets. A hash table grows when that ratio passes a chosen maximum; a higher maximum saves space but makes lookups slower, and a lower maximum does the reverse.

Ring buffer

A ring buffer is a fixed-size array used as a queue by keeping a head index and an item count and wrapping indexes with modulo, so enqueue and dequeue both take constant time and no element is ever shifted.

In plain words

A hash map works like a coat-check desk. The attendant turns your ticket into a hook number. The coat goes on that hook. Later, the same rule finds it again.

Two tickets can map to one hook. Then the attendant keeps both coats on that hook in a short row. The analogy breaks when the cloakroom grows. A real attendant keeps the old hook numbers. A hash map cannot, because its rule depends on how many hooks exist, so every coat must be re-hung.

A heap is a pile that always keeps the smallest item on top. A queue is a line where the first to arrive is the first to leave.

In one precise sentence, each container is a plain array plus an index rule: hash modulo length for the map, parent and child formulas for the heap, head plus count modulo length for the queue.

Step 1: A key finds its bucket by hashing

A hash map hashes a key to a bucket index. The hash function turns any key into an integer, and that integer modulo the number of buckets is the index. The input is a key and the output is a bucket number.

The hash alone cannot decide whether the key is present, so the code compares keys with equality inside the bucket. Python's data model states the rule: "The only required property is that objects which compare equal have the same hash value". Unequal keys may share a hash, and both are stored.

For your own key class, the same page advises combining the components that take part in equality by packing them into a tuple and hashing the tuple. User-defined classes compare by identity by default, so only an object is equal to itself unless you define equality.

You now know how a key finds a bucket. The next step handles two keys that find the same one.

Step 2: Collisions are chained and a resize re-places every key

A collision is two different keys that map to the same bucket. The common fix is called chaining: each bucket holds a short list, and a lookup scans only that list.

Chains grow as the table fills, so the table tracks its entry count against a threshold. Java's HashMap documents a default capacity of 16 and a default load factor of 0.75, and says a higher load factor saves space but raises lookup cost (Oracle, HashMap). When entries exceed the load factor times the capacity, the table is rehashed so that it has approximately twice the number of buckets (Oracle, HashMap).

A resize doubles the buckets and re-places every key. The failure is to double the array and leave the entries where they were. The index is the hash modulo the new length, so a lookup now searches a different bucket and misses a key that is still stored. The Worked example counts how many keys vanish.

class HashMap:
    def __init__(self, capacity=4, load_factor=0.75):
        self.buckets = [[] for _ in range(capacity)]
        self.size = 0
        self.load_factor = load_factor

    def _index(self, key):
        return hash(key) % len(self.buckets)

    def put(self, key, value):
        bucket = self.buckets[self._index(key)]
        for pair in bucket:
            if pair[0] == key:
                pair[1] = value
                return
        bucket.append([key, value])
        self.size += 1
        if self.size > self.load_factor * len(self.buckets):
            self._resize()

    def get(self, key, default=None):
        for k, v in self.buckets[self._index(key)]:
            if k == key:
                return v
        return default

    def remove(self, key):
        bucket = self.buckets[self._index(key)]
        for i, (k, _) in enumerate(bucket):
            if k == key:
                del bucket[i]
                self.size -= 1
                return True
        return False

    def _resize(self):
        old = self.buckets
        self.buckets = [[] for _ in range(2 * len(old))]
        for bucket in old:
            for k, v in bucket:
                self.buckets[self._index(k)].append([k, v])

The code replaces a value when the key already exists, counts only new keys, and builds the larger array before re-placing, so _index already uses the new length.

Step 3: A heap lives in an array and repairs itself by sifting

A binary heap is stored in an array and repaired by sifting. In zero-based indexing the parent of index i sits at (i - 1) // 2, the left child at 2*i + 1 and the right child at 2*i + 2, as the binary heap chapter gives them.

Insert adds the new element at the end, the first free slot, and then sift-up swaps it with its parent while it is smaller than the parent. Extract moves the last element to the root and sift-down swaps it with its smaller child until neither child is smaller. Insert and extract are logarithmic because a repair walks at most the height of the tree, and peek is constant because the minimum sits at index 0. Some texts call the two repairs heapify-up and heapify-down; they are the same operations as sift-up and sift-down.

Choosing the smaller child in sift-down is the detail that keeps the order valid on both sides. Swapping with the larger child would put a bigger value above a smaller one.

class MinHeap:
    def __init__(self):
        self.a = []

    def peek(self):
        return self.a[0]

    def push(self, x):
        a = self.a
        a.append(x)
        i = len(a) - 1
        while i > 0 and a[(i - 1) // 2] > a[i]:
            p = (i - 1) // 2
            a[p], a[i] = a[i], a[p]
            i = p

    def pop(self):
        a = self.a
        top = a[0]
        last = a.pop()
        if a:
            a[0] = last
            i, n = 0, len(a)
            while True:
                left, right, small = 2 * i + 1, 2 * i + 2, i
                if left < n and a[left] < a[small]:
                    small = left
                if right < n and a[right] < a[small]:
                    small = right
                if small == i:
                    break
                a[i], a[small] = a[small], a[i]
                i = small
        return top

Step 4: A queue is a ring buffer over a fixed array

A queue is a ring buffer that wraps indexes with modulo. A queue serves items in first in, first out (FIFO) order, so the oldest item leaves first.

A Python list is a poor queue because the Python wiki lists insert on a list as linear time and popping from index 0 shifts every remaining item, so an insert or pop at index 0 of a list is linear, while collections.deque has constant-time popleft and appendleft. From scratch, a ring buffer avoids shifting entirely. Keep a head index and a count. Enqueue writes at (head + count) % capacity. Dequeue reads at the head and advances it modulo the capacity.

Tracking the count, not only a tail index, is what tells a full queue from an empty one: with only head and tail indexes, both states can look identical.

class RingQueue:
    def __init__(self, capacity):
        self.slots = [None] * capacity
        self.head = 0
        self.count = 0

    def enqueue(self, x):
        if self.count == len(self.slots):
            raise OverflowError("queue is full")
        self.slots[(self.head + self.count) % len(self.slots)] = x
        self.count += 1

    def dequeue(self):
        if self.count == 0:
            raise IndexError("queue is empty")
        x = self.slots[self.head]
        self.slots[self.head] = None
        self.head = (self.head + 1) % len(self.slots)
        self.count -= 1
        return x

1 · Hash to a bucket2 · Chain and resize3 · Heap as array and tree4 · Ring buffer wrapsReplay

Step-by-step description

1. Keys 5, 9 and 13 all map to bucket 1 of 4.
2. A resize re-places every key; skipping it strands 5 and 13.
3. Parent and child indexes link the array to the tree.
4. The fifth item wraps to slot 0; the head is at index 1.

• 5, 9 and 13 all land in bucket 1 and form a chain of three.
• 9 lands in bucket 1, 2 in bucket 2, and 5 and 13 share bucket 5.
• Keys 5 and 13 would still sit in bucket 1 while lookups search bucket 5.
• The slots read 5, 2, 3, 4 with the head at index 1.

Worked example

Take a toy hash table with four buckets and a load factor of three quarters, so it grows when it holds more than three entries (illustrative values). Insert the keys 5, 9, 13 and 2. In CPython a small integer hashes to itself (the script prints hash(5), hash(9) and hash(13) to confirm it), so 5, 9 and 13 all land in bucket 1 and form a chain of three.¹

Inserting key 2 goes to bucket 2 and brings the count to four, which exceeds three, so the table doubles to eight buckets and re-places every key: 9 lands in bucket 1, 2 in bucket 2, and 5 and 13 share bucket 5.¹ Had the code doubled the array without re-placing, keys 5 and 13 would still sit in bucket 1 while lookups search bucket 5, so two of the four keys would be unreachable.¹ For Java's defaults of 16 buckets and 0.75, the threshold is 12, the 13th entry triggers the resize, and the table grows to 32 buckets with a new threshold of 24.¹

For the heap, insert 5, 3, 8, 1 into a min-heap. The finished array [1, 3, 8, 5] read as a tree has 1 at the root, 3 and 8 below it, and 5 below 3. The array goes [5], then [3, 5] after one swap, then [3, 5, 8], then [1, 3, 8, 5] after two more swaps, three swaps in total.¹ Extracting the minimum returns 1, moves the last element 5 to the root giving [5, 3, 8], and one sift-down swap with the smaller child gives [3, 5, 8].¹

To build a heap from [5, 3, 8, 1, 9, 2, 7], start at the last internal node, index floor(7/2) − 1, which is 2, and sift down indexes 2, 1 and 0. The result is [1, 3, 2, 5, 9, 8, 7] after four swaps.¹ Inserting the same seven items one by one also takes four swaps here. The gap appears at scale: building from n insertions costs n times log n, while building in place costs a linear number of steps, per the binary heap chapter.

The worst case is 2 swaps at 7 items, 9 at 1,000 items and 19 at 1,000,000 items, because the height of a heap is the floor of log base two of n.¹

For the queue, use four slots. Enqueue 1, 2 and 3, dequeue 1, then enqueue 4 and 5. The fifth item wraps to slot 0, the slots read 5, 2, 3, 4 with the head at index 1, and the dequeue order is 2, 3, 4, 5.¹

Text description of the diagram

• The worst case is 2 swaps at 7 items, 9 at 1,000 items and 19 at 1,000,000 items.
• The height of a heap is the floor of log base two of n.

Trade-offs and edge cases

A hash map is fast on average but linear when every key collides. The Python wiki lists dictionary get, set and delete as constant time on average and linear in the worst case, and says the average assumes a hash function good enough to make collisions uncommon and keys chosen uniformly at random. Say that assumption aloud: a poor hash or adversarial keys turn every lookup into a scan of one long chain.

A binary heap reads the minimum in constant time but cannot search quickly, because only the parent-child order is kept, not a sorted order. A ring buffer queue is constant time but has a fixed size, so the code above raises an error when full; a growable queue must copy into a larger array, as the hash map does.

Text description of the diagram

• Chaining keeps keys 5, 9 and 13 in one chain in bucket 1 and key 2 in bucket 2.
• Linear probing places 2 in slot 0, 5 in slot 1, 9 in slot 2 and 13 in slot 3.

More edge cases:

• Presizing: Java's HashMap documentation says that if the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur, so a known size lets you skip resizes.
• Mutable keys: a key whose hash changes after insertion is stored in the wrong bucket. Hash only fields that do not change.
• Chaining versus open addressing: open addressing stores entries in the array itself and probes for the next free slot. Take four slots and the keys 5, 9, 13 and 2 with no resize (illustrative). Chaining keeps keys 5, 9 and 13 in one chain in bucket 1 and key 2 in bucket 2, while linear probing places 2 in slot 0, 5 in slot 1, 9 in slot 2 and 13 in slot 3.¹ CPython's dictionary uses open addressing rather than chaining. Chaining is shorter to write under time pressure.
• Threads: the code on this page is not safe for several threads; the follow-ups below cover the Java concurrent map.

For bounded structures built on these containers, see the least-recently-used cache implementation in Python and time-based key-value stores and expiring caches.

How to answer it in an interview

The spoken structure: name the array and buckets, say how collisions and equality work, describe the resize and why keys are re-placed, then state the cost and the limits.

Common mistakes

• "Dictionary lookup is always constant time." (wrong) It is constant on average and linear in the worst case, according to the Python wiki. (right) "Constant time on average, assuming well-spread hashes."
• "Equal hashes mean equal keys." (wrong) The required property runs the other way: equal objects must have equal hashes (Python data model). (right) "Equal hash is a hint; I confirm with equality."
• "After growing the array I can leave the entries in place." (wrong) The index depends on the length, so keys become unreachable. (right) "I re-place every key into the larger array."
• "Building a heap is n log n." (wrong) Bottom-up sift-down over the internal nodes is linear (binary heap chapter). (right) "Building in place is linear; n separate inserts are n log n."
• "size() on a concurrent map is exact." (wrong) The Java Platform, Standard Edition (SE) 8 documentation says the results of aggregate status methods including size, isEmpty and containsValue are typically useful only when a map is not undergoing concurrent updates in other threads. (right) "It is an estimate while writers are active."

Follow-up questions

How is ConcurrentHashMap locking implemented so that it supports multithreading?

Since Java 8, ConcurrentHashMap locks per bucket: an insert into an empty bucket uses compare-and-swap (CAS), an update to a non-empty bucket synchronises on that bucket's first node, and reads take no lock; Java 7 and earlier locked one of a fixed set of internally partitioned segments instead. The primary reference for the Java 8 design is the "Overview" implementation comment in the OpenJDK source (checked 2026-10-26); the Baeldung guide is a secondary pointer to the same idea.

The Java SE 8 documentation states the contract: retrieval operations do not entail locking, and there is no support for locking the entire table. The Java 7 version took a concurrency level that defaulted to 16 as a hint for internal sizing (Java SE 7). The Java SE 26 page adds that neither key nor value can be null.

If the hashes of two objects are equal, are the objects equal?

No. Equal objects must have equal hashes, which is the only property Python's data model requires (Python documentation); the reverse fails because there are more possible keys than possible hash values, so by the pigeonhole principle some unequal keys must share a hash (and many more share a bucket after the modulo). A table therefore checks equality after the hash.

What is the time complexity of a Python dictionary lookup?

Constant time on average and linear time in the worst case, with the average assuming well-spread hashes (Python wiki). A duplicate search that checks a seen set before adding each item is linear overall on average, because each of the n membership checks is constant time on average.

How do you write a FIFO in Verilog?

A hardware FIFO is the ring buffer of Step 4 held in registers or memory: a write pointer, a read pointer and full and empty flags derived from them. Ask whether the design has one clock or two, because two clocks need the pointers synchronised across clock domains, which changes the design. Strong answers add one extra pointer bit to tell full from empty and, for two clocks, pass Gray-coded pointers (only one bit changes per step) through two-flop synchronisers.

How do you design a doubly linked list with insert, delete and search?

Give each node previous and next references and add two sentinel nodes at the ends, so insert and delete take constant time when you hold the node and need no special case for the ends. Search walks the list in linear time. A hash map from keys to nodes plus this list is the core of the least-recently-used cache.

How do you build a heap from n items?

Run sift-down on every internal node from index floor(n/2) − 1 back to the root, which costs a linear number of steps, against n times log n for n successive inserts (binary heap chapter). More design practice is in the low level design interview questions and the in-memory database assessment.

Sources

1. TimeComplexity - Python Wiki — python.org (accessed 2026-10-26), 26 Oct 2026
2. Python data model: object.__hash__ — Python documentation (accessed 2026-10-26), 26 Oct 2026
3. ConcurrentHashMap, Java SE 8 API — Oracle (accessed 2026-10-26), 26 Oct 2026
4. ConcurrentHashMap.java, Overview implementation comment (OpenJDK) — OpenJDK (accessed 2026-10-26), 26 Oct 2026
5. ConcurrentHashMap, Java SE 7 API — Oracle (accessed 2026-10-26), 26 Oct 2026
6. ConcurrentHashMap, Java SE 26 API — Oracle (accessed 2026-10-26), 26 Oct 2026
7. HashMap, Java SE API — Oracle (accessed 2026-10-26), 26 Oct 2026
8. Binary heap chapter — ledger.khushal.net (accessed 2026-10-26), 26 Oct 2026
9. A Guide to ConcurrentMap — Baeldung (accessed 2026-10-26), 26 Oct 2026