DSA in Python: heapq, collections and bisect for Coding Tests

A coding-test solution can produce every correct visible answer and still fail the last hidden cases. The usual cause is an O(n^2) loop where the setter expected O(n log n) or O(n). Python already provides the core machinery for many of these tasks: heapq for repeated minimum selection, collections for counting, grouping and queues, and bisect for binary search on sorted lists. The skill is recognising which problem each tool removes.

The three built-ins and the problem each one kills

Use heapq when you repeatedly need the smallest remaining value without sorting the full collection after every change. Common signals are top K, k-way merge, priority scheduling and shortest-path work.

Use collections.Counter for frequencies, defaultdict for grouping or accumulation without repeated key checks, and deque for queue or double-ended operations. These replace a surprising amount of slow or noisy hand-written code.

Use bisect when the list is already sorted and you need an insertion boundary, an insertion position, or the count of values below a threshold. It performs the search in O(log n), though inserting into a Python list can still cost O(n) because later elements shift.

The broader DSA interview questions for placements guide helps you connect these tools to the patterns interviewers name.

heapq: a min-heap is just a list

heapq works in place on an ordinary list. The smallest item is at index 0, but the remaining list is a heap representation, not a fully sorted sequence.

The calls worth knowing are:

• heapq.heapify(a), which rearranges a full list into a heap in O(n)

• heapq.heappush(a, x), which inserts in O(log n)

• heapq.heappop(a), which removes and returns the minimum in O(log n)

• heapq.heappushpop(a, x), which combines a push and pop efficiently

• heapq.nsmallest(k, items) and heapq.nlargest(k, items) for a small number of extremes

Trace this example:

import heapq

a = [5, 1, 8, 3, 9, 2]
heapq.heapify(a)
print(a)
smallest = heapq.heappop(a)
print(smallest, a)

After heapify, one valid result is [1, 3, 2, 5, 9, 8]. Check the heap property by index. At index 0, 1 <= 3 and 1 <= 2. At index 1, 3 <= 5 and 3 <= 9. At index 2, 2 <= 8. Every parent is no greater than its children.

heappop returns 1. The remaining heap is [2, 3, 8, 5, 9]. Again, 2 <= 3, 2 <= 8, 3 <= 5, and 3 <= 9, so the property still holds. Notice that [2, 3, 8, 5, 9] is not globally sorted, and it does not need to be.

For a maximum-oriented heap pattern, the traditional portable technique is to push -x and negate the popped result. For pairs such as (priority, task), Python compares the first field, then later fields to break ties. Make sure those later fields are mutually comparable or include a numeric sequence counter.

collections: Counter, defaultdict, deque

Counter is a frequency dictionary with useful reporting methods:

from collections import Counter

freq = Counter("mississippi")

The counts are i: 4, s: 4, p: 2, and m: 1. There are 11 characters in total, and 4 + 4 + 2 + 1 = 11, so the frequency sum checks against the input length. freq.most_common(2) returns [('i', 4), ('s', 4)] for this input because the tied letters retain their first-seen order.

Combine frequencies with a heap for top K:

top_three = heapq.nlargest(
    3,
    freq.items(),
    key=lambda pair: pair[1],
)

The result is [('i', 4), ('s', 4), ('p', 2)]. If u is the number of unique values, selecting k items this way is typically O(u log k), which is useful when k is much smaller than u.

defaultdict(list) is ideal for grouping:

from collections import defaultdict

groups = defaultdict(list)
for word in words:
    groups[word[0]].append(word)

There is no separate if key not in groups branch. Be careful, though: reading groups[key] creates a missing key with its default value. Use key in groups or groups.get(key) when a read must not mutate the mapping.

deque is the correct queue for BFS and many sliding-window problems. Its append, appendleft, pop and popleft operations are O(1) at either end. A list's pop(0) is O(n) because every remaining reference shifts left.

bisect: binary search you do not have to write

bisect_left finds the first valid insertion position, before any equal values. bisect_right finds the position after existing equal values.

from bisect import bisect_left, bisect_right, insort

arr = [1, 3, 5, 7, 9]
left = bisect_left(arr, 5)    # 2
right = bisect_right(arr, 5) # 3

Index 2 is where the existing 5 begins, and index 3 is immediately after it. Therefore right - left = 3 - 2 = 1, which is the number of 5s. The same boundary pattern counts values in a range: values from low through high inclusive equal bisect_right(arr, high) - bisect_left(arr, low).

insort(arr, 6) produces [1, 3, 5, 6, 7, 9]. Finding index 3 takes O(log n), but making space in the list takes O(n). insort preserves sorted order conveniently; it does not turn list insertion into logarithmic work.

The traps that fail hidden cases

Building a heap by n pushes costs O(n log n), while heapify builds from a batch in O(n). Use heapify when all starting values are already available.

Do not sort a heap list and then expect to continue as though nothing changed conceptually. A sorted ascending list happens to satisfy the min-heap property, but repeated full sorting wastes the performance benefit. Use heap operations for updates.

Do not use list.pop(0) for BFS. On a large graph, those shifts can turn queue handling into quadratic work. Use deque.popleft().

Do not call bisect on unsorted input. It assumes sorted order and does not validate the list for you. The returned index can look believable while being meaningless.

Finally, define tie-breaking explicitly when the question demands it. Counter.most_common preserves encounter order for equal counts, but a problem may ask for alphabetical, numeric or earliest-index order. Encode that rule instead of relying on an accidental output.

How coding tests probe these

Problem wording often gives away the tool. "K largest" or "K most frequent" suggests a heap, often combined with Counter. "Process the next smallest" suggests a priority queue. "Group by key" suggests defaultdict. "First in, first out" suggests deque. "Insertion position", "count below x" or "count in a sorted range" suggests bisect.

KnowledgeGate's data-structures practice spans heaps, hash tables, queues and sorted arrays. Use that variety to practise recognition, not just syntax. Before coding, state the required operation and its target complexity in one line.

The Placement Preparation category gives these drills their interview context.

Short version and next step

Use heapq for repeated minimum selection, Counter for frequencies, defaultdict for grouping, deque for O(1) operations at both ends, and bisect for boundaries in an already sorted list. Keep the caveats with the names: heaps are not sorted lists, missing defaultdict reads can insert, insort still shifts elements, and ties need the problem's own rule.

Now write and trace one example for each tool, then solve timed problems where the correct container changes the complexity. DSA Using Python gives you that structured practice route.