Skip to content

Data Structures

Knowing which data structure to reach for — and why — separates a scripting-level Python user from a practitioner. These questions test both theoretical knowledge and practical judgment.

Q1: What is the time complexity of common list operations?

Show answer

Python lists are backed by dynamic arrays. Understanding the complexity of each operation helps you avoid performance cliffs in loops.

Operation Complexity Notes
append(x) O(1) amortised Occasional resize is O(n), but amortised O(1)
insert(i, x) O(n) Shifts all elements from index i onward
pop() O(1) Removes from the end
pop(i) O(n) Shifts elements after index i
x in lst O(n) Linear scan
lst[i] O(1) Direct index access
len(lst) O(1) Stored as attribute
del lst[i] O(n) Shifts elements 
import time

n = 100_000

# insert at beginning is O(n) — slow for large lists
lst = list(range(n))
start = time.perf_counter()
for _ in range(1000):
    lst.insert(0, -1)
print(f"insert(0): {time.perf_counter() - start:.3f}s")

# append is O(1) — fast
lst2 = []
start = time.perf_counter()
for _ in range(100_000):
    lst2.append(1)
print(f"append: {time.perf_counter() - start:.3f}s")

The key gotcha: using a list as a queue (removing from the front with pop(0)) is O(n). Use collections.deque instead.

Q2: What is the time complexity of dictionary operations? How are dicts implemented?

Show answer

Python dicts are hash tables. Average case for lookup, insert, and delete is O(1).

Operation Average Worst Case
d[key] O(1) O(n) — hash collision
d[key] = val O(1) O(n)
key in d O(1) O(n)
del d[key] O(1) O(n)
iteration O(n) O(n)

Worst-case O(n) from hash collisions is rare in practice with modern CPython's hash randomisation (enabled by default since 3.3).

lookup_list = list(range(1_000_000))
lookup_dict = {i: True for i in range(1_000_000)}

target = 999_999

# O(n) — scans the whole list
print(target in lookup_list)   # True

# O(1) — hash table lookup
print(target in lookup_dict)   # True

As of Python 3.7, dicts preserve insertion order as part of the language spec — not just a CPython implementation detail.

Q3: When should you use a set instead of a list?

Show answer

Use a set when you need: - Membership testing — x in my_set is O(1) vs O(n) for a list - Deduplication — sets store only unique elements - Set operations — union, intersection, difference

data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]

# Deduplication
unique = set(data)
print(unique)   # {1, 2, 3, 4, 5, 6, 9}

# Membership — O(1)
print(5 in unique)   # True

# Set operations
a = {1, 2, 3, 4}
b = {3, 4, 5, 6}

print(a & b)    # {3, 4}        — intersection
print(a | b)    # {1, 2, 3, 4, 5, 6} — union
print(a - b)    # {1, 2}        — difference
print(a ^ b)    # {1, 2, 5, 6}  — symmetric difference

Sets are unordered and do not support indexing. Elements must be hashable (immutable types). A frozenset is an immutable set that can itself be used as a dict key or set member.

Q4: Why can tuples be used as dictionary keys but lists cannot?

Show answer

Dictionary keys must be hashable — they need a __hash__ method that returns the same value for equal objects throughout their lifetime.

Lists are mutable: you could change a list after using it as a key, which would corrupt the hash table. Python prevents this by making lists unhashable.

Tuples are immutable, so their hash value is stable.

# Tuple as dict key — valid
grid = {}
grid[(0, 0)] = "origin"
grid[(1, 2)] = "point A"
print(grid[(0, 0)])   # "origin"

# List as dict key — raises TypeError
try:
    d = {[1, 2]: "value"}
except TypeError as e:
    print(e)   # unhashable type: 'list'

However, a tuple containing a mutable object (like a list) is also unhashable:

try:
    d = {(1, [2, 3]): "value"}
except TypeError as e:
    print(e)   # unhashable type: 'list'

For composite keys in data science — e.g., (user_id, date) — tuples are the idiomatic choice.

Q5: What is collections.defaultdict and when does it beat a plain dict?

Show answer

defaultdict is a dict subclass that calls a factory function to supply default values for missing keys, avoiding KeyError.

from collections import defaultdict

# Plain dict — KeyError on missing key
d = {}
try:
    d["missing_key"].append(1)
except KeyError:
    print("KeyError!")

# defaultdict — auto-initialises missing keys
groups = defaultdict(list)
data = [("cat", "lion"), ("dog", "wolf"), ("cat", "tiger")]

for category, animal in data:
    groups[category].append(animal)

print(dict(groups))
# {'cat': ['lion', 'tiger'], 'dog': ['wolf']}

Common factory choices: - defaultdict(list) — group items by key - defaultdict(int) — frequency counts - defaultdict(set) — unique items per key

# Word frequency count
from collections import defaultdict

words = ["apple", "banana", "apple", "cherry", "banana", "apple"]
freq = defaultdict(int)
for word in words:
    freq[word] += 1

print(dict(freq))   # {'apple': 3, 'banana': 2, 'cherry': 1}

For pure counting, Counter (below) is even more concise. defaultdict shines for grouping.

Q6: What is collections.Counter and what can it do beyond counting?

Show answer

Counter is a dict subclass specialised for counting hashable objects. It is the most concise tool for frequency analysis.

from collections import Counter

words = ["apple", "banana", "apple", "cherry", "banana", "apple"]
freq = Counter(words)

print(freq)                        # Counter({'apple': 3, 'banana': 2, 'cherry': 1})
print(freq["apple"])               # 3
print(freq["durian"])              # 0  — missing keys return 0, not KeyError
print(freq.most_common(2))        # [('apple', 3), ('banana', 2)]

Counters support arithmetic:

c1 = Counter({"a": 3, "b": 2})
c2 = Counter({"a": 1, "b": 4, "c": 1})

print(c1 + c2)   # Counter({'b': 6, 'a': 4, 'c': 1})
print(c1 - c2)   # Counter({'a': 2})  — only positive results
print(c1 & c2)   # Counter({'a': 1, 'b': 2})  — min of each
print(c1 | c2)   # Counter({'b': 4, 'a': 3, 'c': 1})  — max of each

In data science, Counter is useful for: token frequency in NLP, value distribution checks, comparing class label distributions.

Q7: What is collections.deque and when should you use it over a list?

Show answer

deque (double-ended queue) supports O(1) appends and pops from both ends, whereas list's insert(0, x) and pop(0) are O(n).

from collections import deque

q = deque([1, 2, 3])

q.appendleft(0)    # O(1) — insert at front
q.append(4)        # O(1) — insert at back
print(q)           # deque([0, 1, 2, 3, 4])

q.popleft()        # O(1) — remove from front
q.pop()            # O(1) — remove from back
print(q)           # deque([1, 2, 3])

Use deque when: - Implementing a queue (FIFO) — append to right, popleft from left - Implementing a stack — append and pop from the same end (list is fine too) - Maintaining a sliding window — deque(maxlen=k) auto-discards old elements

# Rolling window of last 3 readings
window = deque(maxlen=3)
for reading in [10, 20, 30, 40, 50]:
    window.append(reading)
    print(list(window))
# [10]
# [10, 20]
# [10, 20, 30]
# [20, 30, 40]
# [30, 40, 50]

Q8: What are namedtuple and dataclass, and when would you choose each?

Show answer

Both provide named access to structured data. They differ in mutability, memory, and boilerplate.

namedtuple — immutable, memory-efficient (tuple under the hood), good for read-only records:

from collections import namedtuple

Point = namedtuple("Point", ["x", "y"])
p = Point(3.0, 4.0)

print(p.x, p.y)   # 3.0 4.0
print(p[0])        # 3.0 — still index-accessible
print(p._asdict()) # {'x': 3.0, 'y': 4.0}

dataclass — mutable by default, supports default values, type annotations, and methods:

from dataclasses import dataclass, field

@dataclass
class ModelConfig:
    learning_rate: float = 0.01
    max_depth: int = 5
    features: list = field(default_factory=list)

config = ModelConfig(learning_rate=0.001)
config.features.append("age")
print(config)
# ModelConfig(learning_rate=0.001, max_depth=5, features=['age'])

Use namedtuple for lightweight, immutable records. Use dataclass when you need mutability, methods, or complex defaults. Use @dataclass(frozen=True) for an immutable dataclass that is also hashable.

Q9: How do dict, set, and list comprehensions differ, and when should you prefer each?

Show answer

List comprehension — produces a list:

squares = [x**2 for x in range(6)]
print(squares)   # [0, 1, 4, 9, 16, 25]

Dict comprehension — produces a dictionary:

word_lengths = {word: len(word) for word in ["apple", "banana", "cherry"]}
print(word_lengths)   # {'apple': 5, 'banana': 6, 'cherry': 6}

Set comprehension — produces a set (unique values only):

data = [1, 2, 2, 3, 3, 3, 4]
unique_squares = {x**2 for x in data}
print(unique_squares)   # {1, 4, 9, 16}

All three support filtering with an if clause:

# Only even squares
even_squares = {x**2 for x in range(10) if x % 2 == 0}
print(even_squares)   # {0, 4, 16, 36, 64}

When to prefer each: - List: when order matters or you need duplicates - Set: when you need uniqueness or fast membership testing - Dict: when mapping keys to values - Generator expression (...): when the result is consumed once and memory is a concern

Q10: How would you implement a frequency count, a group-by, and a deduplication in pure Python?

Show answer

These three patterns appear constantly in data science preprocessing.

Frequency count:

from collections import Counter

data = ["cat", "dog", "cat", "bird", "dog", "cat"]
freq = Counter(data)
print(freq.most_common())   # [('cat', 3), ('dog', 2), ('bird', 1)]

Group-by (items → category → list of items):

from collections import defaultdict

records = [
    ("Alice", "Engineering"),
    ("Bob", "Marketing"),
    ("Carol", "Engineering"),
    ("Dave", "Marketing"),
]

by_dept = defaultdict(list)
for name, dept in records:
    by_dept[dept].append(name)

print(dict(by_dept))
# {'Engineering': ['Alice', 'Carol'], 'Marketing': ['Bob', 'Dave']}

Deduplication preserving order:

data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]

# dict.fromkeys preserves insertion order since Python 3.7
unique_ordered = list(dict.fromkeys(data))
print(unique_ordered)   # [3, 1, 4, 5, 9, 2, 6]

set(data) deduplicates but loses order. dict.fromkeys() deduplicates while preserving insertion order, with O(n) time complexity.

Q11: What is collections.OrderedDict and is it still relevant in Python 3.7+?

Show answer

OrderedDict was introduced to guarantee insertion-order preservation before Python 3.7. Since 3.7, regular dict preserves insertion order as a language guarantee.

OrderedDict is still useful for two things plain dicts cannot do:

  1. move_to_end() — reposition a key to the front or back:
from collections import OrderedDict

od = OrderedDict([("a", 1), ("b", 2), ("c", 3)])
od.move_to_end("a")         # move "a" to end
print(list(od.keys()))      # ['b', 'c', 'a']

od.move_to_end("c", last=False)  # move "c" to front
print(list(od.keys()))           # ['c', 'b', 'a']
  1. Order-sensitive equality — two OrderedDicts with the same keys in different orders are not equal:
from collections import OrderedDict

d1 = OrderedDict([("a", 1), ("b", 2)])
d2 = OrderedDict([("b", 2), ("a", 1)])

print(d1 == d2)              # False — order matters

print(dict(d1) == dict(d2))  # True — plain dicts ignore order

For LRU cache implementations and order-sensitive comparison logic, OrderedDict is still the right tool. For everything else, plain dict is sufficient in Python 3.7+.