vizlearn

Count things with a dictionary

Interview QuestionsBy Updated

Four ways to write the same loop — get, setdefault, defaultdict and Counter — all O(n). For the k most common, do not sort everything: a heap of size k gives O(n log k), which matters when n is huge and k is ten.

Overview

The four idioms

counts[x] = counts.get(x, 0) + 1 needs no import and makes the default explicit. counts.setdefault(x, 0) is the same idea and reads worse for counting. defaultdict(int) lets you write counts[x] += 1 directly. Counter(seq) does the whole loop in C.

They are all O(n). Reach for Counter in real code and be able to write the get version when an interviewer asks you not to import anything.

Dicts, sets & hashingCoding problemEasy

Step through it

What to watch

  • Each item costs one lookup and one write, whatever the dictionary holds.
  • The counter grows only with distinct items.
  • Nothing is ever searched for.

Say this out loud

"Counter for the counting. For top-k I'd use heapq.nlargest rather than sorting - O(n log k) instead of O(n log n), which is the difference that matters when n is a billion."

Count things with a dictionary

Count the frequency of each item in a sequence. Now find the k most common.

One trap in defaultdict

Reading a missing key from a defaultdict creates it. if counts[x] > 5 silently inserts x with value 0, so a loop that only reads can grow the dictionary without anyone noticing.

Use .get() or in when you are only asking. Counter does not have this problem: reading a missing key returns 0 without inserting.

Top-k without sorting

Sorting all the counts is O(m log m) in the number of distinct items. Keeping a heap of size k is O(m log k), which is what heapq.nlargest and Counter.most_common(k) do.

For "top 10 of a billion" that is the difference between a practical job and an impossible one, and it is the answer the question is actually fishing for. Bucket sort by count is O(m) when the counts are bounded — worth mentioning as the linear option.

Run it in Python

The four idioms producing identical counts, the defaultdict read trap caught in the act, and top-k timed three ways on a large input.

counting.pyPython 3
Output
How the code works
  1. counts.get(x, 0) + 1The version to write when told not to import anything. The default removes the "first time?" branch without hiding what is happening.
  2. d["never_added"] > 5A read that inserts. defaultdict creates on any missing lookup, so a loop that only inspects can grow the dictionary silently.
  3. heapq.nlargest(k, ...)Keeps a heap of size k rather than sorting m items: O(m log k). Counter.most_common(k) does the same thing.
  4. Counter(big)One pass in C. The counting is never the bottleneck — the question is always what you do with the counts afterwards.
Change one thing
  • Raise the value range to 5,000,000 so nearly every item is distinct. The sort/heap gap widens as m grows.
  • Implement top-k with bucket sort by count. O(m) when counts are bounded, which beats both.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.


    



Check yourself
0 of 3
Answer without scrolling back up.
  1. Reading a missing key from a defaultdict:
  2. Finding the k most common items is best done with:
  3. Counting n items with a dictionary costs:





 Cheat sheet
Count things with a dictionary
Four ways to write the same loop — get, setdefault, defaultdict and Counter — all O(n). For the k most common, do not sort everything: a heap of size k gives O(n log k), which matters when n is huge and k is ten.
INTERVIEW · vizlearn.in/interview/counting-with-dictionaries.html
More in Interview
InterviewWhat is the complexity of this code?InterviewWhy are Python strings immutable?InterviewWhat does slicing a string cost?InterviewDoes len() count characters or bytes?
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact