Data Structures: The shape of efficient programs

Pick the right structure and the problem becomes easy; that choice is most of the interview.

Data shape drives cost

Same problem, different container: array, list, tree or hash table changes lookup, insert and delete costs by orders of magnitude.

O(1) vs O(log n) vs O(n)

Complexity is the contract

Big-O states how cost scales with size, hiding constants. It predicts behavior at scale, where it is the only thing that matters.

What this course teaches

Nine units: arrays and lists, stacks and queues, trees, balanced trees and heaps, hash tables, sorting, graphs, dynamic programming, and the hard problem boundary.

Flashcard

O(1)

Constant time access

Hash table lookup and array indexing: cost independent of size.

Check your understanding

Nearest-neighbor search in an unsorted array is: