Skip to content
Tutorials Center
My learning

Topics

Lesson 43 of 77 ยท CS Fundamentals Interview Questions

Complexity and Data Structure Questions

Answer Big O and data structure interview questions: arrays vs linked lists, hash tables, heaps and trees, with Python code you can run and measure.

Almost every coding interview starts with the same two skills: estimate how an algorithm scales, and pick the data structure whose strengths match the job. These questions are short, so interviewers expect crisp answers with a reason, not a memorized table. This lesson gives you the reasoning and lets you count operations yourself.

Background: Big O, Hash tables, Heaps and Binary trees.

The four structures to know cold

Array Fast by index, slow to insert.
Linked list Fast to splice, slow to search.
Hash table Fast lookup by key.
Heap Fast access to the smallest.
1 / 2

Reasoning about Big O

Q: What does O(n) mean, and how do you find it? Big O describes how the number of steps grows with input size n, ignoring constants and lower-order terms. To find it, count how many times the innermost work runs. One loop over n items is O(n). A loop inside a loop over the same data is O(nยฒ). Halving the problem each step (binary search) is O(log n). Sorting is O(n log n).

Two follow-ups appear often. Sequential blocks add (O(n) then O(n) is O(n)); nested blocks multiply. And space complexity counts extra memory you allocate, not the input itself.

Python Counting steps instead of guessing

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Multiply n by 10 and the linear count grows tenfold, the quadratic count a hundredfold, and the halving count barely moves. That sentence is a good answer to "why does it matter?".

Q: What is amortized O(1)? A dynamic array doubles its capacity when full. One append occasionally costs O(n) to copy, but averaged over many appends each costs O(1). See Amortized analysis.

Arrays versus linked lists

Q: When would you choose a linked list over an array? Arrays store items contiguously: indexing is O(1) and iteration is cache-friendly, but inserting or deleting in the middle shifts everything after it, which is O(n). A linked list stores nodes with pointers: inserting after a node you already hold is O(1), but reaching the k-th item takes O(k). In practice arrays win far more often because of memory locality. Linked lists make sense when you need constant-time splicing and already hold node references, such as inside an LRU cache.

Python A tiny linked list

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

insert_after touched two pointers no matter how long the list was. Finding the node, however, walked the list.

Hash tables

Q: How does a hash table work and why is lookup O(1)? A hash function turns a key into an integer; the integer modulo the bucket count chooses a bucket. Lookup jumps straight to one bucket instead of scanning. Two keys can land in the same bucket (a collision); common fixes are chaining (each bucket holds a small list) and open addressing (probe for the next free slot). When the table gets too full, it resizes and rehashes. Lookup is O(1) on average and O(n) in the worst case when everything collides.

Be ready for: "What makes a good key?" It must be hashable (immutable in Python) and equal keys must hash equally.

Python A chaining hash table that shows collisions

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

"ant" and "tan" have the same letters, so this simple hash sends them to the same bucket: a collision, resolved by chaining.

Heaps and priority queues

Q: What is a heap and when do you use one? A min-heap is a complete binary tree where every parent is less than or equal to its children, so the smallest item is always at the root. Reading it is O(1); push and pop are O(log n). Use it for "give me the smallest or largest next" repeatedly: top-k, merging sorted lists, schedulers, Dijkstra. In Python use heapq, which is a min-heap; negate numbers for a max-heap. Building a heap from n items with heapify is O(n), not O(n log n).

Python Top-k with heapq

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The loop keeps a min-heap of size 3, so memory is O(k) and time is O(n log k). The root heap[0] is the third-largest score.

Trees

Q: Why use a binary search tree, and what is its weakness? In a BST, left values are smaller and right values are larger, so search, insert and delete follow one path from the root: O(h), where h is the height. A balanced tree has h around log n. An unbalanced one, such as inserting sorted data, degrades to a linked list with h = n. Self-balancing trees (AVL, red-black) keep the height logarithmic.

Structure Access Search Insert Delete
Array O(1) O(n) O(n) O(n)
Linked list O(n) O(n) O(1) at a known node O(1) at a known node
Hash table n/a O(1) avg O(1) avg O(1) avg
Balanced BST n/a O(log n) O(log n) O(log n)
Binary heap min only: O(1) O(n) O(log n) O(log n) pop min

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. A loop runs n times and inside it runs another loop n times. What is the complexity?

    Nested loops multiply: n times n steps.
  2. 2. Which operation is O(n) on a dynamic array but O(1) on a linked list when you already hold the node?

    An array shifts later items; a linked list just rewires two pointers.
  3. 3. What is the cost of looking up a key in a hash table when many keys collide into one bucket?

    Average lookup is O(1), but a single overloaded bucket must be scanned.
  4. 4. How do you keep the k largest items of a stream in O(k) memory?

    The min-heap's root is the smallest of the current top k, so it is the one to discard.

Summary

  • Big O counts growth: sequential blocks add, nested blocks multiply, halving gives log n.
  • Arrays have O(1) indexing and O(n) middle inserts; linked lists are the reverse and rarely win in practice.
  • Hash tables give O(1) average lookup; explain buckets, collisions and resizing.
  • Heaps give O(1) peek and O(log n) push and pop; use them for top-k and scheduling.
  • BST operations cost O(height), so balance matters.

Next: Array and String Patterns.