Data Structures in Python interview questions

25 questions from the Data Structures in Python course, each with the correct answer and an explanation. Try to answer before you open the answer.

Foundations: Complexity and Python's Object Model

1. What does amortised O(1) mean for list.append?

  1. Occasional resizes are expensive, but the average cost over many appends is constant
  2. Every append takes exactly the same time
  3. Append is O(n) always
  4. Append never allocates memory
Show answer

Answer: Occasional resizes are expensive, but the average cost over many appends is constant

Over-allocation spreads the cost of occasional copies across many cheap appends.

Lesson: Why Data Structures and Big-O Matter

2. Why does `[[0] * 3] * 3` behave unexpectedly when you modify one row?

  1. Lists cannot be nested
  2. Integers are mutable
  3. It creates a tuple
  4. The outer list holds three references to the same inner list
Show answer

Answer: The outer list holds three references to the same inner list

Multiplying a list repeats references, not copies.

Lesson: Python's Object Model: References, Mutability and Copies

3. What does sys.getsizeof(some_list) measure?

  1. The total memory of the list and all elements
  2. The number of elements
  3. Only the list object itself, including its array of references, not the referenced elements
  4. Disk usage
Show answer

Answer: Only the list object itself, including its array of references, not the referenced elements

getsizeof is shallow: elements are separate objects.

Lesson: Measuring Time and Memory

Sequences: Lists, Tuples and Strings

4. What is the time complexity of list.insert(0, x) for a list of n items?

  1. O(1)
  2. O(log n)
  3. O(n)
  4. O(n log n)
Show answer

Answer: O(n)

Every existing reference must shift one position to the right.

Lesson: Lists: Python's Dynamic Array

5. Why can a tuple of strings be used as a dictionary key while a list cannot?

  1. Tuples are faster
  2. Tuples are immutable and hashable; lists are mutable and unhashable
  3. Lists cannot hold strings
  4. Dictionaries only accept tuples
Show answer

Answer: Tuples are immutable and hashable; lists are mutable and unhashable

Keys must be hashable, and their hash must not change.

Lesson: Tuples, namedtuple and dataclasses

6. Why is "".join(parts) preferred over repeated += for building a long string?

  1. Strings are immutable, so repeated += may copy the growing string each time, while join computes the size once
  2. join sorts the parts
  3. join is the only way to concatenate
  4. It uses less Unicode
Show answer

Answer: Strings are immutable, so repeated += may copy the growing string each time, while join computes the size once

join allocates the result once and copies each part once.

Lesson: Strings, Bytes and Efficient Text Building

Hash Tables: dict, set and collections

7. Since which Python version is dict insertion order guaranteed by the language?

  1. 3.7
  2. 2.7
  3. 3.5
  4. 3.12
Show answer

Answer: 3.7

It was a CPython implementation detail in 3.6 and became a language guarantee in 3.7.

Lesson: Dictionaries: Hash Tables in Practice

8. What is the most efficient way to remove duplicates from a list while preserving the original order?

  1. set(items)
  2. sorted(items)
  3. items.sort()
  4. list(dict.fromkeys(items))
Show answer

Answer: list(dict.fromkeys(items))

dict.fromkeys keeps first occurrences in insertion order; a plain set does not preserve order.

Lesson: Sets and Frozensets

9. Which collections type returns 0 for missing keys and provides most_common()?

  1. OrderedDict
  2. ChainMap
  3. Counter
  4. deque
Show answer

Answer: Counter

Counter is a dict subclass designed for counting.

Lesson: Counter, defaultdict, OrderedDict and ChainMap

Stacks, Queues, Linked Lists and Heaps

10. Which structure gives O(1) removal from the front of a sequence?

  1. list.pop(0)
  2. tuple slicing
  3. collections.deque.popleft()
  4. str.lstrip
Show answer

Answer: collections.deque.popleft()

deque supports O(1) operations at both ends.

Lesson: Stacks and Queues with list and deque

11. Why are linked lists rarely the fastest choice in Python?

  1. They cannot store integers
  2. Each node is a separate object with overhead, and C-implemented list and deque are faster for most workloads
  3. They are always O(n²)
  4. Python forbids them
Show answer

Answer: Each node is a separate object with overhead, and C-implemented list and deque are faster for most workloads

Object overhead and pointer chasing outweigh their theoretical benefits in most Python programs.

Lesson: Linked Lists

12. What is the time complexity of heapq.heapify on a list of n items?

  1. O(n)
  2. O(n log n)
  3. O(log n)
  4. O(1)
Show answer

Answer: O(n)

Bottom-up heap construction runs in linear time.

Lesson: Heaps and Priority Queues

Trees and Tries

13. Which traversal of a binary search tree visits values in sorted order?

  1. In-order
  2. Pre-order
  3. Post-order
  4. Level-order
Show answer

Answer: In-order

In-order visits the left subtree, the node, then the right subtree.

Lesson: Binary Trees and Traversals

14. What is the worst-case search time in an unbalanced BST with n keys?

  1. O(1)
  2. O(log n)
  3. O(n log n)
  4. O(n)
Show answer

Answer: O(n)

Sorted insertions create a chain-like tree with height n.

Lesson: Binary Search Trees and Sorted Collections

15. What is the cost of looking up a word of length m in a trie?

  1. O(n) in the number of words
  2. O(log n)
  3. O(m), independent of the number of stored words
  4. O(n·m)
Show answer

Answer: O(m), independent of the number of stored words

Each character moves one level down the trie.

Lesson: Tries for Prefix Search

Graphs

16. Which representation uses O(V + E) space and suits sparse graphs?

  1. Adjacency matrix
  2. A single list of vertices
  3. Adjacency list
  4. A V by V NumPy array
Show answer

Answer: Adjacency list

Adjacency lists store only the edges that exist.

Lesson: Representing Graphs

17. Why does BFS find the shortest path in an unweighted graph?

  1. It visits nodes randomly
  2. It explores nodes in order of their distance (number of edges) from the start
  3. It uses recursion
  4. It sorts the edges first
Show answer

Answer: It explores nodes in order of their distance (number of edges) from the start

Level-by-level exploration reaches each node first by a shortest route.

Lesson: Breadth-First and Depth-First Search

18. What does a topological sort require of the graph?

  1. It must be a directed acyclic graph (DAG)
  2. It must be undirected
  3. It must be weighted
  4. It must be complete
Show answer

Answer: It must be a directed acyclic graph (DAG)

A cycle means no order can put every vertex after all its prerequisites.

Lesson: Dijkstra's Algorithm and Topological Sort

Advanced Structures and Memory

19. Which two optimisations make union-find operations nearly constant time?

  1. Path compression and union by rank or size
  2. Sorting and hashing
  3. Recursion and memoisation
  4. Binary search and heaps
Show answer

Answer: Path compression and union by rank or size

Together they keep the trees extremely shallow.

Lesson: Union-Find (Disjoint Set Union)

20. Which two OrderedDict methods make an O(1) LRU cache straightforward?

  1. sort and reverse
  2. append and pop(0)
  3. keys and values
  4. move_to_end and popitem(last=False)
Show answer

Answer: move_to_end and popitem(last=False)

move_to_end updates recency and popitem(last=False) evicts the oldest entry.

Lesson: Caches: LRU with OrderedDict and functools

21. What does __slots__ (or dataclass(slots=True)) save?

  1. Disk space
  2. CPU cores
  3. The per-instance __dict__, reducing memory and speeding attribute access
  4. Import time
Show answer

Answer: The per-instance __dict__, reducing memory and speeding attribute access

Slotted classes store attributes in fixed slots instead of a dictionary.

Lesson: Memory-Efficient Structures: slots, array, generators and NumPy

Choosing Structures, Custom Containers, Patterns and Revision

22. Which structure best supports adding and removing items at both ends in O(1)?

  1. list
  2. set
  3. collections.deque
  4. tuple
Show answer

Answer: collections.deque

deque is designed for efficient operations at both ends.

Lesson: Choosing the Right Data Structure

23. If you subclass collections.abc.Sequence and implement __getitem__ and __len__, what do you get for free?

  1. Nothing
  2. Methods such as __contains__, __iter__, index, count and __reversed__
  3. Automatic sorting
  4. Thread safety
Show answer

Answer: Methods such as __contains__, __iter__, index, count and __reversed__

The ABC provides mixin methods built on the abstract ones.

Lesson: Building Custom Containers

25. What is the average time complexity of checking `x in some_set`?

  1. O(n)
  2. O(log n)
  3. O(n log n)
  4. O(1)
Show answer

Answer: O(1)

Sets are hash tables, giving constant average-time membership tests.

Lesson: Revision and Interview Questions

← Back to the course