Python for Interviews

collections: Counter, defaultdict & deque

The collections helpers interview solutions use for counting, grouping and queues.

Medium, about 60 minutes to practise.

1Understand

The idea

Counter counts in one line and compares multisets with ==; defaultdict(list) groups without checking whether a key exists; deque gives O(1) pops from both ends, which a list cannot. Reaching for the right one keeps solutions short and avoids accidental O(n) operations.

Intuition

Counter, defaultdict and deque remove boilerplate that hides bugs. Counter builds frequencies in one call and compares multisets with ==. defaultdict(list) (or int) means you never write "if key missing, create then append".

deque gives O(1) append/pop/appendleft/popleft. A normal list's pop(0) is O(n) and quietly kills BFS and sliding-window solutions.

Reach for the helper that matches the operation you need; the code stays short and the complexity stays honest.

What you will be able to do

  • Count with Counter and most_common
  • Group with defaultdict(list)
  • Use deque for O(1) appends and pops at both ends

2See it

Walkthrough

Counter and defaultdict

words = ["aa", "ab", "aa"], count frequencies, then group by first letter.

1 / 4

i
aa
ab
aa
012
i → index 0

count

  • ∅ empty

Counter (or a plain dict) tallies each word. Start empty.

count = Counter()

Counter and defaultdict are O(n) to build. deque ops at either end are O(1); list pop(0) is O(n). Reading a missing key on defaultdict creates it, fine when grouping, surprising when you only meant to probe.

Read the walkthrough as text

Group anagrams, then process as a queue. Given words ["eat","tea","tan","ate","nat","bat"].

1. Group with a canonical key: In code:

  • from collections import defaultdict
  • groups = defaultdict(list)
  • for w in words:
  • key = tuple(sorted(w))
  • groups[key].append(w)
  1. You get three groups: eat/tea/ate, tan/nat, bat.
  2. If you later need FIFO processing of group keys, use deque(groups.keys()) and popleft(), never list.pop(0).

Counter("ate") == Counter("tea") is the short anagram check when you only need equality, not grouping.

3Recognise it

Kinds of problems (4)

Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.

  • Counter and most_common

    Example. Top k frequent elements or compare two multisets.

    How. Counter(iterable) builds counts; most_common(k) and counter equality check anagrams.

  • defaultdict for grouping and adjacency lists

    Example. Group strings by length or build graph adjacency.

    How. defaultdict(list) so graph[u].append(v) never needs an if u not in graph.

  • deque as a queue

    Example. BFS layer by layer or simulate a ticket line.

    How. append right, popleft() for FIFO; both ends are O(1) unlike list.pop(0).

  • OrderedDict for recency

    Example. LRU cache ordering (or “move to end” semantics).

    How. OrderedDict.move_to_end(key) after access; popitem(last=False) drops oldest.

Common mistakes

Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.

  • Hand-rolled counting where Counter fits

    Why it happens. A manual dict loop is what you learn first.

    How it fails. Twenty lines of if ch not in freq: freq[ch]=1 else: freq[ch]+=1 when Counter(text) is one line and clearer.

    Fix. Counter for frequencies, defaultdict for grouping, deque for queues, reach for collections first.

  • list.pop(0) instead of deque.popleft()

    Why it happens. list.pop(0) reads like “pop from the front”.

    How it fails. BFS with q = [] and q.pop(0) each step shifts the whole array, O(n) per layer, O(n²) total.

    Fix. from collections import deque; queue.append(...) and queue.popleft() for FIFO in O(1).

  • Reading a defaultdict creates missing keys

    Why it happens. defaultdict feels like a normal dict for reads.

    How it fails. if len(g[u]) == 0 on defaultdict(list) inserts u with [] even when you only meant to probe.

    Fix. Use `u in g` or g.get(u) when probing; save defaultdict for writes that should auto-create.

4Check yourself

Concept check

A short quiz on this lesson before you practise. Optional, and it does not gate coding.

Ready to practise?

Mastery comes from solving. The lesson is optional context.

All lessons