Design-a-Data-Structure Questions

Combining maps, lists, heaps and binary search to hit every operation's target complexity.

"Design a data structure that supports X, Y and Z" questions (LRU cache, min stack, time-based key-value store, hit counter) sit halfway between algorithms and LLD. There's no single algorithm to recognize. Instead, you combine basic structures so that every operation meets its required complexity. One method works for almost all of them.

The method

List each operation with its target complexity. If the interviewer doesn't give one, ask, or propose one: "I'll aim for O(1) get and put."
For each operation, name the structure that makes it fast:
Lookup by key → hash map
Order of insertion or recency → linked list or deque
Min, max or top-k → heap or sorted structure
Search by time or version → sorted list plus binary search
Prefix queries → trie
Combine them, and decide what each one stores so they stay in sync. The usual trick is that the map points *into* the other structure: key → list node or key → index.
Walk through each operation and check that every structure is updated. Most bugs are a structure that someone forgot to update.

The common combinations

Worked example: get-random in O(1)

import random

class RandomizedSet:
    def __init__(self):
        self.vals, self.pos = [], {}

    def insert(self, val):
        if val in self.pos:
            return False
        self.pos[val] = len(self.vals)
        self.vals.append(val)
        return True

    def remove(self, val):
        if val not in self.pos:
            return False
        i, last = self.pos[val], self.vals[-1]
        self.vals[i], self.pos[last] = last, i     # move the last element into the hole
        self.vals.pop()
        del self.pos[val]
        return True

    def get_random(self):
        return random.choice(self.vals)

[!WARNING] Removing the last element In remove, when val is itself the last element, the code still works: it writes last into its own slot, then pops it and deletes it from the map. Trace this edge case out loud. It's the most common follow-up check on this question.

Worked example: time-based key-value store

import bisect
from collections import defaultdict

class TimeMap:
    def __init__(self):
        self.times = defaultdict(list)
        self.values = defaultdict(list)

    def set(self, key, value, timestamp):        # timestamps increase per key
        self.times[key].append(timestamp)
        self.values[key].append(value)

    def get(self, key, timestamp):
        i = bisect.bisect_right(self.times[key], timestamp)
        return self.values[key][i - 1] if i else ""

Discussing trade-offs

Interviewers often ask for alternatives. Have one ready:

Lazy vs. eager cleanup: expire old hits when a query arrives (simple, but one query may do a lot of work), or with a fixed-size circular buffer (bounded memory, but needs a fixed window).
Time vs. memory: the snapshot array stores only changes rather than copying the array on every snapshot.
Amortized costs: a queue built from two stacks is O(1) amortized, not worst case. Say so.
Thread safety: wrap the public methods in a lock, and say where contention would become a problem. See Concurrency & Thread Safety.

[!INTERVIEW] Write the API first Start with the class and its method signatures, each with a one-line comment giving its complexity. Then fill in the bodies. This makes your plan reviewable in 30 seconds and keeps you from forgetting an operation.

[!TIP] Practice LRU Cache · LFU Cache · Min Stack · Time-Based Key-Value Store · Snapshot Array · Design Hit Counter · Design Underground System · Maximum Frequency Stack · Design Browser History