Collections Interview Drill and Checkpoint
A review of this module. Skip it if you feel confident; the next module does not need it.
Fix the mistakes
The slips that cost marks in this module. Spot each one, then check the fix.
This checkpoint mixes everything from the module. For each task, name the operation that must be fast, pick the structure, then say its cost in one sentence. That habit is what interviewers listen for.
Pick the structure first
A support desk needs to know if a ticket id was seen before, and to serve tickets oldest first. Two different needs, two structures.
from collections import dequeseen = set()waiting = deque()for ticket in ['T3', 'T1', 'T3', 'T2']: if ticket not in seen: seen.add(ticket) waiting.append(ticket)print(waiting.popleft(), len(seen))Example 1 · First repeated item with a set
ids = ['A', 'B', 'C', 'B', 'A']seen = set()for i in ids: if i in seen: print(i) break seen.add(i)B
What this code does
- A set makes each check O(1), so the whole scan is O(n).
- A list for seen would make it O(n squared).
The set answers 'seen before?' in O(1) on average. The deque serves the oldest ticket in O(1). A list would make both steps O(n).
Predict the output
Puzzles mix aliasing, copies and stable sorting. Work out each line on paper, then compare it with the output of the program.
a = [1, 2, 3]b = ac = a[:]a += [4]print(b, c)rows = [('b', 2), ('a', 2), ('c', 1)]print(sorted(rows, key=lambda r: r[1]))Example 2 · Top two frequent words
from collections import Counterwords = 'a b a c b a d'.split()counts = Counter(words)ranked = sorted(counts.items(), key=lambda kv: (-kv[1], kv[0]))print(ranked[:2])[('a', 3), ('b', 2)]What this code does
- Counter counts in O(n).
- The tuple key sorts by count descending, then word, so ties are predictable.
Example 3 · Moving average with a deque
from collections import dequewindow = deque(maxlen=3)for price in [10, 20, 30, 40, 50]: window.append(price) if len(window) == 3: print(sum(window) / 3)20.0 30.0 40.0
What this code does
- maxlen=3 drops the oldest price automatically.
- Each step costs O(3), a constant, so the total is O(n).
a += [4] extends the shared list, so b sees it and the copy c does not. The sort is stable, so ('b', 2) stays before ('a', 2).
Spot the bug
A loop deletes finished orders from the list it is looping over. The result looks right on small data and fails on neighbours.
orders = ['done', 'done', 'open', 'done']for o in orders: if o == 'done': orders.remove(o)print(orders)orders = [o for o in ['done', 'done', 'open', 'done'] if o != 'done']print(orders)The loop leaves one 'done' behind because the list shifts left. The comprehension builds the correct list in one pass.
Module quiz
Questions from the whole module. Your first answer is your score.
Problems
Graded easy to hard, using everything from this module.
Try each one yourself first. Use the hint if you get stuck. Mark it as done when it works.
Exercise 1· Easy
Count the vowels in "inventory" and print the count.
3
Exercise 2· Easy
Print the sorted list of distinct values in [5, 3, 5, 1, 3, 9].
[1, 3, 5, 9]
Exercise 3· Medium
Print True if "listen" and "silent" are anagrams, using Counter.
True
Exercise 4· Medium
Print the first repeated id in ["A", "B", "C", "B", "A"].
B
Exercise 5· Medium
Group ["eat", "tea", "tan", "ate", "nat", "bat"] into lists of anagrams. Print the groups as a list of lists in first-seen order.
[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]
Exercise 6· Hard
From the text "a b a c b a d" print the two most frequent words with their counts, breaking ties alphabetically.
[('a', 3), ('b', 2)]Exercise 7· Hard
For prices [10, 20, 30, 40, 50] print the average of every window of 3, one per line, using a deque.
20.0 30.0 40.0
Exercise 8· Hard
Merge the overlapping intervals in [[1, 3], [8, 10], [2, 6], [15, 18]] and print the result.
[[1, 6], [8, 10], [15, 18]]
Interview questions
Questions interviewers ask on this topic.
What's next
You finished the preview of Collections Questions
Python Programming has 21 sections, 110 modules and 609 lessons. An account opens every lesson and saves your progress.
Finish up
Mark complete & continue
Next: Iterators and Generators