Data Structures

Source: Concepts adapted from Ace the Data Science Interview — Chapter 9 (“Coding”) by Kevin Huo & Nick Singh. Rewritten in original wording for this course.

Know what each structure is good at, the usual Big-O, and implement a tiny version in both Python and C++. Interviewers care that you can build the tool, not only name it.

Structure	Access	Search	Insert / delete	Notes
Array / list	$O(1)$ index	$O(N)$ unsorted	End often amortized $O(1)$	Off-by-one
Stack	top $O(1)$	—	push/pop $O(1)$	LIFO
Queue	front $O(1)$	—	enqueue/dequeue $O(1)$	FIFO
Linked list	$O(N)$	$O(N)$	$O(1)$ at known node	Pointer bugs
Hash map	—	avg $O(1)$	avg $O(1)$	Collisions
Balanced BST	$O(\log N)$	$O(\log N)$	$O(\log N)$	Skew → $O(N)$
Heap	min/max $O(1)$	$O(N)$	$O(\log N)$	Priority queues
Graph (adj list)	—	BFS/DFS $O(V+E)$	—	Sparse-friendly

Quiz

Overview & complexity

1 / 5

Which structure is usually best for O(1) average lookup by key?

Pick an answer to see if you are right.

Arrays / dynamic arrays

Consecutive elements, $O(1)$ index. Weak for search/delete of arbitrary values unless sorted. Patterns: two pointers, prefix sums, in-place tricks. Python list and C++ vector are dynamic arrays (amortized $O(1)$ append).

Quiz

Arrays

1 / 3

Appending to the end of a dynamic array is typically…

Pick an answer to see if you are right.

Stack (implement me)

LIFO: push / pop / peek at one end. Use for DFS, undo, balanced brackets, expression evaluation.

Quiz

Stacks

1 / 3

After push(1), push(2), pop(), peek() returns…

Pick an answer to see if you are right.

Lab: Stack — Python

Commands: PUSH x, POP, PEEK, SIZE. Print one line per POP/PEEK (value or EMPTY). Ignore POP/PEEK on empty by printing EMPTY.

Queue (implement me)

FIFO: enqueue rear, dequeue front. Core of BFS.

Quiz

Queues

1 / 3

After enqueue(1), enqueue(2), dequeue(), next dequeue returns…

Pick an answer to see if you are right.

Lab: Queue — Python & C++

Commands: ENQ x, DEQ, FRONT, SIZE.

Linked lists

Nodes with next (optionally prev). Strong at insert/delete given a pointer; weak at random access. Classics: reverse, cycle detection, merge, remove k-th from end.

Quiz

Linked lists

1 / 3

Reversing a singly linked list in O(1) extra space uses…

Pick an answer to see if you are right.

Lab: Reverse linked list — Python & C++

Input: n then n ints. Output: reversed values.

Hash maps (implement a tiny one)

Key → bucket via hash; average $O(1)$ get/set. Collisions: chaining or open addressing. Classics: two-sum, frequencies, anagrams.

Quiz

Hash maps

1 / 3

With a good hash and load factor, expected get/put is…

Pick an answer to see if you are right.

Lab: Chaining hash map — int→int

Commands: PUT k v, GET k (print value or MISSING), SIZE.

Trees & BST (implement insert + inorder)

Binary tree traversals: in-order LNR, pre-order NLR, post-order LRN. BST: left ≤ node ≤ right → balanced search $O(\log N)$.

Quiz

Trees & BST

1 / 3

Order in-order steps for one node.

OrderDrag the handle to rearrange — top should be first.

Drag items into the correct order (or use ↑↓), then check.

Lab: BST insert + inorder

Commands: INS x then finally INORDER prints sorted keys.

Heaps

Min-heap: parent ≤ children; root is minimum. Insert/delete $O(\log N)$ via sift. Use for top-$k$, Dijkstra, streaming median (two heaps).

Quiz

Heaps

1 / 3

In a binary min-heap array, children of index i are…

Pick an answer to see if you are right.

Lab: Min-heap push / pop

Commands: PUSH x, POP (print min or EMPTY), SIZE.

Graphs

Adjacency list vs matrix. BFS (queue) / DFS (stack). Both $O(V+E)$.

Quiz

Graphs

1 / 3

For a sparse social graph, prefer…

Pick an answer to see if you are right.

Lab: Graph + BFS order

Input: n m then m undirected edges, then start. Print BFS visit order (neighbors explored in ascending node id).

Application drills

Wire the structures into classic interview prompts (Python shown; same ideas apply in C++).

Prev: Approach & Big-O · Next: Algorithms · Interview set: Easy coding problems.