PHASE 17Advanced ~30 min· topic 4 of 10

Topic 17.4

Interview Deep Dive: Coding Rounds in Python

In one line

The Python idioms that save minutes in a coding round: Counter, defaultdict, heapq, bisect, deque, slicing, sorted with key, and itertools, plus the time complexity of every built-in you will lean on and how to talk through a solution.

Think of it like this

A mechanic's toolbox. A good mechanic does not file a new wrench for each bolt. They reach for the right tool from a small, well-known set. In a coding round the interviewer is watching for the same thing: do you reach for Counter for counting, heapq for the top few, deque for a queue, bisect for a sorted list, instead of rebuilding them with loops?

Words you'll meet

New words in this topic, in plain English. Come back here whenever one feels fuzzy.

Time complexity: How the running time grows as the input size n grows, written like O(n) or O(log n).
Amortised O(1): Usually cheap, with an occasional expensive step that averages out, like list.append sometimes resizing.
Heap: A structure that always gives you the smallest item quickly. Python's heapq is a min-heap stored in a list.
Stable sort: A sort that keeps equal items in their original relative order.
Sentinel: A special marker value, such as None or a unique object(), meaning 'nothing yet'.
Monotonic deque: A deque kept in sorted order by removing items that can never matter again.
Hashable: Can be used as a dict key or set member: it has a stable hash and ==. Lists and dicts are not hashable.

Step by step

01Top-k frequent: three correct answers

Count with Counter(words). For k results you can call counts.most_common(k), which uses a heap internally when k is given. When the interviewer asks for a tie-break (higher count first, then alphabetical), use heapq.nsmallest(k, counts.items(), key=lambda kv: (-kv[1], kv[0])) or sort everything with the same key. State the cost: counting is O(n), the heap selection is O(m log k) for m distinct words.

main.pywhole filepython

import heapq
from collections import Counter

counts = Counter("the cat and the dog and the bird saw a cat".split())
print(heapq.nsmallest(3, counts.items(), key=lambda kv: (-kv[1], kv[0])))

02Group with defaultdict

To group anagrams, make a signature that is the same for every anagram of a word (the sorted letters) and use it as a dict key. defaultdict(list) creates the empty list on first use. Time is O(n * L log L) for n words of length L. If words are only lowercase letters you can build the key from a 26-count tuple in O(n * L).

03Sorting with keys and ties

To sort by several fields with mixed directions, return a tuple and negate the numeric field you want descending. Because the sort is stable you can also sort twice: first by the minor key, then by the major key. For strings that need descending order you cannot negate; sort by the secondary key first and use reverse=True for the primary, or sort in two passes.

04Sliding window maximum with a deque

Keep indexes in a deque so their values decrease from front to back. For each new number, pop smaller values off the back (they can never be a maximum while the new number is in the window), append the new index, and pop the front if it fell out of the window. Every index enters and leaves once, so the whole run is O(n), even though the window size is k. The second runnable example does this.

Sliding window maximum with a dequediagram

Rendering diagram…

05Prove complexity claims by counting

You can check in costs without a stopwatch. The third runnable example builds a Probe class that counts how many times == is called. Searching a list for the last item calls it n times; a set with a hash lookup calls it once. Counting operations is more reliable than timing, and it is exactly the argument you make out loud in an interview.

06How to talk through a round

Restate the problem and ask about edge cases (empty input, duplicates, negatives, very large n). Give the brute force and its complexity first, then the improvement and why it is faster. Write the code in a function with clear names. Test it aloud with a small example and one edge case. Finish with complexity in time and space. Writing correct plain Python beats a clever one-liner you cannot explain.

Try it yourself

1
Race the idioms
Solve 'top 2 most frequent words' three ways in the editor: with most_common(2), with heapq.nlargest, and by sorting the whole counts.items() list. Check that the three agree on the example, then add a tie and find which ones disagree. That is the follow-up an interviewer asks.
2
Count, don't time
In the third example, add deque: make Probe items sit in a deque, and count comparisons for last in the_deque. It is O(n) too. Then explain why a deque is still the better choice for a queue even though in is slow.

Code & diagrams

Counter, defaultdict, sorted with key, heapq and slicing New tab

Change the tie-break key to `(-kv[1], -len(kv[0]))` and see which word wins.

Expected output

counts: {'the': 3, 'cat': 2, 'and': 2, 'dog': 1, 'bird': 1, 'saw': 1, 'a': 1}
most_common(2): [('the', 3), ('cat', 2)]
top 3: [('the', 3), ('and', 2), ('cat', 2)]
anagram groups: [['bat'], ['eat', 'tea', 'ate'], ['tan', 'nat']]
sorted by age desc, name asc: [('Asha', 31), ('Chitra', 31), ('Ben', 25), ('Dev', 25)]
stable sort keeps ties in order: ['a', 'd', 'bb', 'cc']
heap pops: [1, 2, 3]
3 largest: [5, 4, 3]
reversed slice: [3, 2, 4, 1, 5] | every 2nd: [5, 4, 3] | copy: True

bisect, a monotonic deque and itertools New tab

`groupby` only groups neighbours. Try it on `'abab'` and see four groups.

Expected output

bisect_left(20): 1 | bisect_right(20): 3
after insort(25): [10, 20, 20, 25, 30, 50]
sliding window max: [3, 3, 5, 5, 6, 7]
pairwise: [(1, 2), (2, 4), (4, 7)]
accumulate: [1, 3, 6, 10]
combinations: [('a', 'b'), ('a', 'c'), ('b', 'c')]
product: [(0, 0), (0, 1), (1, 0), (1, 1)]
groupby: [('a', 3), ('b', 2), ('c', 1)]
deque maxlen=3 after append(4): [2, 3, 4]
rotate(1): [4, 2, 3]

Counting comparisons: list scan versus set lookup New tab

The numbers are operation counts, not times, so they are the same on every machine.

Expected output

n=10    list: 10    set: 1
n=100   list: 100   set: 1
n=1000  list: 1000  set: 1
same result: True

Complexity of the built-ins (CPython)text

Average cases unless stated. n is the size of the container, k the size of the slice or result.

list     append / pop()            O(1) amortised
         pop(0) / insert(0, x)     O(n)   shifts every element
         x in list / index / count O(n)
         list[i]                   O(1)
         slice a[i:j]              O(k)   builds a new list
         sort()                    O(n log n), stable, O(n) if already sorted
dict     get / set / del / in      O(1) average, O(n) worst case
set      add / remove / in         O(1) average, O(n) worst case
deque    append / appendleft /
         pop / popleft             O(1)
         d[i] in the middle        O(n)
heapq    heappush / heappop        O(log n)
         heapify                   O(n)
         nsmallest(k) / nlargest   O(n log k)
bisect   bisect_left / right       O(log n)
         insort                    O(n)   search is log n, the insert shifts
str      s + t                     O(len(s) + len(t)): build with "".join(parts)
         substring in s            O(n) typical; the naive worst case is O(n * m),
                                   and CPython 3.10+ avoids it for long patterns
len(x), x[i] on list/dict/str      O(1)
min / max / sum on an iterable     O(n)
set      a | b, a & b              O(len(a) + len(b)) average

Break it on purpose

Errors are the best teachers. Make each change, read the error, guess what went wrong, then reveal the answer.

Break #1

Sort a list with mixed types

Sort a list that contains both numbers and a string.

main.pywhole filepython

rows = [3, "a", 1]
print(sorted(rows))

terminal

$ python main.py

── what you'll see ──

Traceback (most recent call last):

File "main.py", line 2, in <module>

print(sorted(rows))

~~~~~~^^^^^^

TypeError: '<' not supported between instances of 'str' and 'int'

Myth vs fact

Myth

list.sort() and sorted() are slow, so a heap is always better for top-k.

Fact

Sorting is O(n log n) in fast C code. A heap with nsmallest is better when k is much smaller than n, but for small inputs sorting is simpler and often just as fast.

Myth

str += in a loop is always quadratic.

Fact

CPython sometimes optimises it, but nothing in the language guarantees it. Use ''.join(parts) for loops that build large strings.

Myth

dict lookups are always O(1).

Fact

They are O(1) on average, assuming a good hash. Many keys with the same hash degrade to O(n), which is why hash functions matter.

Interview problem

The problem

Top K frequent words, with follow-ups

Given a list of words and an integer k, return the k most frequent words, sorted by frequency from highest to lowest. If two words have the same frequency, the word that comes first alphabetically goes first. Words are lowercase letters only.

You're given

1 <= k <= the number of distinct words.
The input can have up to 100,000 words.
Return a list of strings.

The interviewer follows up

The words arrive as an endless stream and you cannot store them all. What changes?

The data is too big for one machine.

Pro corner

Extra depth for experienced readers. New to this? Skip it for now and come back later.

▸
Counter.most_common(k) with a k uses heapq.nlargest, so it is O(m log k). Without k it sorts all m distinct items. Ties come out in first-seen order, because the internal sort is stable.
▸
bisect accepts a key= argument from Python 3.10, so you can search a list of records by a field without building a separate list of keys.
▸
In the real interview, correctness and communication beat micro-optimisation. Know O(n log n) sorting is fine for n up to about a million in Python, and that an O(n^2) loop over 100,000 items is not.

Remember this

1
Count and group. A dictionary maps keys to values (Topic 4.4). collections.Counter counts hashable items (items that can be dict keys, Topic 4.5) in one line and has most_common(k). defaultdict(list) removes the "if key not in dict" boilerplate: groups[key].append(x). Grouping anagrams uses "".join(sorted(word)) as the key. Know that Counter ties come out in first-seen order, so if the problem needs a specific tie-break, sort with an explicit key.
2
Sort with a key (Topic 4.2). The O(...) marks below show how the time grows with the input size n. sorted(items, key=...) and list.sort(key=...) use Timsort: O(n log n) worst case, O(n) on already-sorted data, and stable (equal keys keep their input order). For "descending by one field, ascending by another" use a tuple key: key=lambda p: (-p[1], p[0]). Never use the old cmp style; functools.cmp_to_key exists for the rare case you need it.
3
Heaps for top-k. heapq is a min-heap on a plain list: heappush and heappop are O(log n), heapify is O(n), and nsmallest(k, items, key=...) / nlargest run in about O(n log k). For a max-heap, push negated values. For "the k most frequent" you do not need to sort everything: a heap of size k is enough.
4
Queues and windows. collections.deque gives O(1) appends and pops at both ends. A list gives O(n) for pop(0) and insert(0, x) because it shifts every element. Use deque for BFS (visiting a graph level by level) and sliding windows (a monotonic deque yields the window maximum in O(n)). deque(maxlen=k) keeps only the last k items automatically.
5
Sorted data. bisect_left(a, x) returns the first index where x could be inserted keeping a sorted; bisect_right returns the index after the last equal item. Both are O(log n). insort inserts in order but is O(n) because the list shifts. For a dynamic sorted collection that needs fast inserts you need a different structure (a heap, a balanced tree via a library, or sortedcontainers).
6
Slicing and itertools (Topics 4.2 and 9.4). a[::-1] reverses, a[::2] takes every second item, a[:] copies; slices make new lists in O(k). itertools supplies lazy building blocks: pairwise, accumulate (running totals), combinations, permutations, product, groupby (groups only consecutive equal keys, so sort first). Always know the cost of what you use: x in a_list is O(n) and x in a_set is O(1) on average. The DSA course (/dsa) works the same patterns problem by problem, and every solution there has a Python version.

Explain it without notes

Find the k most frequent words in a text, with ties broken alphabetically. State the time and space complexity.

Why is list.pop(0) slow and what do you use instead? What is the complexity of x in some_list versus x in some_set?

What is a stable sort, and how do you sort by one field descending and another ascending?

How does bisect_left differ from bisect_right? Give an example with duplicates.

How would you find the maximum of every window of size k in an array in O(n)?

Given a list of numbers and a target, return the indexes of two numbers that add up to the target, in O(n) time.

What goes wrong when you remove items from a list while looping over it, and what do you do instead?

Practice

Write group_anagrams(words) that returns a list of groups, each sorted, with the groups sorted too.

Write kth_largest(nums, k) using heapq in O(n log k), keeping a min-heap of size k.

Write first_unique_char(s) that returns the index of the first character that appears only once, or -1.

Trade-offs

↔
Built-in idiom versus hand-written loop. Idioms are shorter, faster and signal fluency, but if you cannot explain what Counter or heapq does underneath, write the loop instead. The interviewer may ask.
↔
Time versus space. A set or dict makes lookups O(1) at the cost of memory. Sorting in place uses almost no extra memory but is O(n log n). Say which resource the problem cares about.

Done when you can

Done when you can solve top-k frequent words three ways and state the cost of each.
Done when you can use defaultdict, Counter, deque, heapq and bisect without looking anything up.
Done when you can sort by multiple fields with mixed directions and explain stability.
Done when you can recite the complexity of list, dict, set, deque and heapq operations.
Done when you can walk through a problem aloud: clarify, brute force, improve, code, test, complexity.

Command Palette

Words you'll meet

Step by step

01Top-k frequent: three correct answers

02Group with defaultdict

03Sorting with keys and ties

04Sliding window maximum with a deque

05Prove complexity claims by counting

06How to talk through a round

Try it yourself

Race the idioms

Count, don't time

Code & diagrams

Break it on purpose

Sort a list with mixed types

Myth vs fact

Interview problem

Top K frequent words, with follow-ups

Pro corner

Remember this

Explain it without notes

Practice

Trade-offs

Done when you can