Python Data Structures and the collections Module

Python gives you powerful data structures out of the box, and coding rounds reward knowing them. Picking deque over a list for a queue or heapq for “top K” often turns a slow answer into the optimal one — and shows real Python fluency.

1. What is the time complexity of common list, dict and set operations?

• list: index and append O(1); insert or pop at the front O(n); x in list O(n); sort O(n log n).
• dict: get, set, delete and in are O(1) on average.
• set: add, remove and in O(1) average; union and intersection O(len of sets).

The classic fix for slow code: replace repeated x in big_list with a set.

seen = set()
duplicates = []
for x in [4, 2, 4, 7, 2]:
    if x in seen:            # O(1) instead of scanning a list
        duplicates.append(x)
    seen.add(x)
print(duplicates)            # [4, 2]

2. Why use deque instead of a list for a queue?

list.pop(0) and insert(0, x) shift every element — O(n). collections.deque adds and removes at both ends in O(1), and maxlen gives you a fixed-size window that drops old items automatically.

from collections import deque

queue = deque(["task1", "task2"])
queue.append("task3")       # enqueue
print(queue.popleft())      # task1 — O(1)

last_three = deque(maxlen=3)
for reading in [10, 12, 11, 15, 14]:
    last_three.append(reading)
print(list(last_three))     # [11, 15, 14]

3. When do you use defaultdict and Counter?

defaultdict(factory) creates a missing key with a default value, removing “if key not in dict” checks — perfect for grouping. Counter counts hashable items and supports most_common() and arithmetic between counters.

from collections import defaultdict, Counter

orders = [("Pune", 499), ("Delhi", 250), ("Pune", 120)]
by_city = defaultdict(list)
for city, amount in orders:
    by_city[city].append(amount)
print(dict(by_city))          # {'Pune': [499, 120], 'Delhi': [250]}

votes = Counter(["yes", "no", "yes", "yes"])
print(votes.most_common(1))   # [('yes', 3)]

4. How does sorting with key work? Is Python's sort stable?

sorted() returns a new list; list.sort() sorts in place. Pass key to sort by a computed value and reverse=True for descending. Python uses TimSort, which is stable, so you can sort by several keys — or use a tuple key in one pass.

students = [("Asha", "CSE", 9.1), ("Ravi", "ECE", 8.4), ("Meera", "CSE", 9.1)]
# by CGPA descending, then name ascending
ranked = sorted(students, key=lambda s: (-s[2], s[0]))
print([s[0] for s in ranked])     # ['Asha', 'Meera', 'Ravi']

5. How do you find the K largest items efficiently?

heapq implements a min-heap on a plain list. heapq.nlargest(k, items) runs in O(n log k) — better than sorting everything when k is small. For a stream, keep a heap of size k and push or replace as items arrive.

import heapq

scores = [72, 95, 61, 88, 99, 54, 91]
print(heapq.nlargest(3, scores))     # [99, 95, 91]

heap = []
for s in scores:                     # streaming version
    heapq.heappush(heap, s)
    if len(heap) > 3:
        heapq.heappop(heap)
print(sorted(heap, reverse=True))    # [99, 95, 91]

6. What are namedtuple and dataclass, and how do they differ?

Both give names to fields instead of using indexes. A namedtuple is an immutable tuple — light, hashable and unpackable. A dataclass is a regular class with generated methods, which can be mutable or frozen, have defaults, methods and type hints. Use namedtuple for small immutable records, dataclass for richer models.

from collections import namedtuple
from dataclasses import dataclass

Point = namedtuple("Point", "x y")
p = Point(3, 4)
print(p.x, p[1])           # 3 4

@dataclass
class Item:
    name: str
    qty: int = 1

7. How does bisect help with sorted lists?

bisect finds insertion points in a sorted list with binary search — O(log n) to search, though inserting is still O(n) because elements shift. It is perfect for grading bands, time-slot lookups and keeping a list sorted as you add items.

import bisect

cutoffs = [40, 60, 75, 90]
grades = ["F", "C", "B", "A", "A+"]

def grade(score):
    return grades[bisect.bisect_right(cutoffs, score)]

print([grade(s) for s in [35, 60, 82, 95]])   # ['F', 'C', 'B', 'A+']

8. How do set operations simplify problems?

Union |, intersection &, difference - and symmetric difference ^ answer “common”, “missing” and “only in one” questions in one line, in linear time.

applied = {"Asha", "Ravi", "Meera", "Kabir"}
selected = {"Ravi", "Kabir", "Zoya"}
print(applied & selected)    # {'Ravi', 'Kabir'}
print(applied - selected)    # not selected
print(selected - applied)    # {'Zoya'} — selected without applying?