Know your tools cold

Pick one language and own its standard library. The 10 seconds spent recalling syntax mid-interview is 10 seconds you can't spend thinking.

from collections import defaultdict, Counter, deque
import heapq, bisect
from functools import cache

d = defaultdict(list)
c = Counter("banana")            # {'a':3,'n':2,'b':1}

heapq.heappush(h, (priority, item))    # min-heap; negate for max
i = bisect.bisect_left(arr, x)         # O(log n) on sorted

@cache
def f(i, j): ...

for i, v in enumerate(arr): ...
arr.sort(key=lambda x: (x[0], -x[1]))

const m = new Map<string, number>();
m.set("k", 1); m.get("k"); m.has("k");
const s = new Set<number>();

// Default sort is string — beware!
arr.sort((a, b) => a - b);

// No built-in heap — write one or import. Sketch:
class MinHeap<T> { push(v:T){}; pop():T|undefined { return undefined; } }

// shift() is O(n) — fine for n < 10^4
const q: number[] = [];
q.push(1); q.shift();

List / dynamic array

What it is. A dynamic array — an ordered, index-able row of slots that grows as you append (Python list, TS array []). "Dynamic" means you never declare a size; the runtime quietly allocates a bigger backing block and copies over when it fills up. It is your default container: when in doubt, start with a list.

Key operations and cost. Reading or writing by index (a[i]) is O(1) — the address is computed directly from the index. Appending to the end (a.append(x) / a.push(x)) is amortised O(1): individual grows cost O(n) to copy, but spread over many appends the average is constant. The expensive moves are anything that shifts elements: inserting or deleting at the front or middle (a.insert(0, x), a.pop(0)) is O(n) because every following element slides over. Searching for a value with x in a is O(n).

When to reach for it. Whenever order matters and you mostly read by index or append at the end — building results, stacks (append/pop at the end are both O(1)), and any "scan once" pass. Do not use it as a queue (see deque below).

Dict / hash map

What it is. A hash map: a collection of key → value pairs where a hash function turns each key into a slot address, so you can jump straight to a value without scanning (Python dict, TS Map). This is the single most useful structure in interviews — it converts "search the whole list" (O(n)) into "look it up" (O(1) average).

Key operations and cost. Insert d[k] = v, read d[k], membership k in d, and delete del d[k] are all O(1) on average. The "average" caveat matters: in a rare pathological case (many keys colliding into one slot) operations degrade toward O(n), but for interview purposes treat them as O(1). Keys must be hashable (immutable) — strings, numbers, and tuples work; lists and dicts cannot be keys.

When to reach for it. Counting, grouping, memoising, de-duplicating, "have I seen X and where?", and any time you map one thing to another. The classic Two Sum trick — store each number's index as you go, then check if target - x is already in the map — is a hash map turning an O(n²) double loop into a single O(n) pass.

Set

What it is. A hash map with keys but no values — an unordered collection of distinct items (Python set, TS Set). It answers exactly one question well: "is this thing in here?"

Key operations and cost. Add (s.add(x)), membership (x in s), and remove are O(1) average. Sets also give you fast algebra: union a | b, intersection a & b, and difference a - b, each roughly O(len) of the smaller operand.

When to reach for it. De-duplication (list(set(xs))), seen-tracking during traversal (mark visited nodes in BFS/DFS), and any "is X present?" check where you don't need an associated value. Reach for a dict instead when you need to remember something about each key, not just its presence.

Tuple

What it is. An immutable, fixed-size, ordered group of values — (row, col), (priority, item). Because it can't be changed after creation, it is hashable, which means a tuple can be a dict key or a set member (a list cannot).

Key operations and cost. Index access is O(1). Tuples compare element-by-element, left to right, so (1, 9) < (2, 0) — this is why pushing (priority, item) tuples onto a heap sorts by priority automatically.

When to reach for it. Packaging a small fixed bundle: grid coordinates as a visited-set member, multiple return values, or a composite sort/heap key like (priority, tiebreak, item).

deque — and why a list is a bad queue

What it is. A double-ended queue (collections.deque) — a list-like structure built for O(1) pushes and pops at both ends. Internally it is a chain of blocks rather than one flat array, so adding or removing at the front does not shift everything.

Key operations and cost. append / pop (right end) and appendleft / popleft (left end) are all O(1). The trade-off: random access by index in the middle is O(n), so it is not a list replacement — it's a queue/stack specialist.

When to reach for it: list vs deque for queues. A queue is first-in-first-out — you add at one end and remove from the other. The trap is using a plain list and calling list.pop(0) to dequeue: that is O(n) per pop because every remaining element slides down one slot, turning a BFS over n items into O(n²). A deque's popleft() is O(1). Rule: any time you need FIFO — most famously breadth-first search — use a deque, never a list. (A stack, by contrast, is fine on a plain list: append/pop at the end are both O(1).)

from collections import deque
q = deque([start])              # BFS frontier
while q:
    node = q.popleft()          # O(1)  —  list.pop(0) would be O(n)!
    for nxt in neighbors(node):
        q.append(nxt)           # O(1)

heapq — the priority queue

What it is. A binary heap (Python's heapq) — a tree-shaped structure kept as a plain list, where the rule "every parent ≤ its children" guarantees the smallest element is always at index 0. It is a min-heap: it efficiently hands you the minimum, over and over, without fully sorting.

Key operations and cost. heapq.heappush(h, x) and heapq.heappop(h) are O(log n) (the element bubbles up or sinks down one tree level at a time). Peeking the minimum is O(1) — just read h[0]. Building a heap from an existing list with heapq.heapify(h) is O(n), cheaper than n separate pushes.

When to reach for it. "Give me the smallest/largest repeatedly" problems: Dijkstra's shortest path, merging k sorted lists, scheduling by priority, or "top-k" (keep a size-k heap). Two interview reflexes: Python's heap is min-only, so for a max-heap negate the values (push -x, pop and negate back); and push tuples (priority, item) so it orders by priority for free — add a tiebreaker like an insertion counter if items themselves aren't comparable.

Counter

What it is. A specialised dict subclass (collections.Counter) that tallies how many times each item appears. Counter("banana") gives {'a':3,'n':2,'b':1} in one line.

Key operations and cost. Building it from an iterable is O(n). A missing key returns 0 instead of raising, so c[x] += 1 always works. c.most_common(k) returns the k highest-frequency items. Counters even support arithmetic: c1 - c2 subtracts counts.

When to reach for it. Frequency questions: anagram checks (Counter(a) == Counter(b)), "most common element," and any tally you would otherwise build with a manual dict and an if key not in d dance.

defaultdict

What it is. A dict (collections.defaultdict) that auto-creates a default value the first time you touch a missing key. defaultdict(list) makes an empty list on demand; defaultdict(int) makes a 0.

Key operations and cost. Same O(1)-average operations as a regular dict; the only difference is that reading a missing key inserts and returns the default rather than raising KeyError.

When to reach for it. Grouping (groups[key].append(item) with no setup), building adjacency lists for graphs (graph[u].append(v)), and accumulating counts. It removes the boilerplate of checking "is this key here yet?" before every update.

OrderedDict

What it is. A dict (collections.OrderedDict) that remembers insertion order and can cheaply move a key to the end or pop from either end. Note: since Python 3.7 a plain dict also preserves insertion order, so OrderedDict's remaining edge is its order-manipulation methods.

Key operations and cost. Normal dict ops are O(1). The extras: move_to_end(k) is O(1), and popitem(last=False) pops the oldest entry in O(1).

When to reach for it. The textbook case is an LRU cache: on access, move_to_end the key; when full, popitem(last=False) evicts the least-recently-used entry — both O(1).

bisect — binary search on a sorted list

What it is. The bisect module performs binary search on an already-sorted list — the same halving search the walkthrough traced above. It finds where a value belongs, or inserts while keeping the list sorted.

Key operations and cost. bisect_left(a, x) and bisect_right(a, x) return an insertion index in O(log n) — left gives the position before any equal values, right after them. insort(a, x) inserts in sorted order, but is O(n) overall because the array still has to shift elements to make room (the search is O(log n), the move is O(n)).

When to reach for it. Lookups and range counts on sorted data: "how many values are < x" is bisect_left(a, x); "first element ≥ x" is a[bisect_left(a, x)]. The non-negotiable precondition is that the list must already be sorted — binary search on unsorted data is silently wrong.

Quick reference: cost cheat sheet

Structure        Typical op                Cost
list / array     index a[i] / append       O(1) (append amortised)
                 insert/pop front or mid   O(n)
                 x in a (search)           O(n)
dict / hash map  get / set / del / in      O(1) average
set              add / remove / in         O(1) average
tuple            index access              O(1)
deque            append/pop both ends      O(1)
                 index in the middle       O(n)
heap (heapq)     push / pop                O(log n)
                 peek min (h[0])           O(1)
                 heapify(list)             O(n)
Counter          build from iterable       O(n)
defaultdict      get / set                 O(1) average
OrderedDict      move_to_end / popitem     O(1)
bisect           bisect_left/right         O(log n)
                 insort (search + shift)   O(n)

Pitfalls that bite in interviews

• A list as a queue is O(n) per pop. list.pop(0) shifts every remaining element, so a FIFO loop becomes O(n²). Use collections.deque and popleft() for any queue or BFS.
• Mutable default arguments. def f(acc=[]) creates the list once, at definition time, and reuses it across every call — so values leak between calls. Use def f(acc=None): acc = acc or [] instead. The same trap applies to {} as a default.
• Python's heap is min-only. For a max-heap, push the negation (-x) and negate again on pop. Forgetting this returns the wrong extreme.
• TS sort is lexicographic by default. [10, 2, 1].sort() yields [1, 10, 2] because numbers are compared as strings. Always pass (a, b) => a - b for numeric order.
• "O(1) average" is not "always O(1)." Hash structures can degrade with adversarial keys, and a single append can trigger an O(n) resize — fine amortised, but worth a sentence if asked about worst case.
• bisect needs a sorted list. Binary search on unsorted data returns a wrong answer with no error. Sort first (O(n log n)) or keep the list sorted as you build it.
• Lists and dicts can't be hash keys. They're mutable, so use a tuple when you need a composite key or a grid coordinate in a set.