Data Structures & Algorithms
Master the fundamental data structures and algorithms that underpin all software — arrays, linked lists, trees, graphs, sorting, and more — with typed Python implementations and complexity analysis.
Arrays & Dynamic Arrays
How arrays work in memory, dynamic resizing, and amortized complexity analysis.
-
- Define arrays and contiguous memory layout
- Explain O(1) indexing
- Contrast static vs dynamic arrays
-
- Explain doubling strategy
- Analyze amortized O(1) push
- Describe shrinking policy
-
- Implement all vector operations
- Handle edge cases (out of bounds, empty)
- Analyze each operation's complexity
Linked Lists
Pointer-based data structures — singly linked, doubly linked, and the tradeoffs against arrays.
-
- Describe node/pointer structure
- Compare linked list vs array
- Implement core operations
-
- Implement insert/erase/reverse/search
- Analyze time complexity
-
- Explain doubly linked list structure
- Compare singly vs doubly
- Identify practical use cases
Stacks & Queues
LIFO and FIFO abstractions — array-backed stacks, linked list queues, and circular buffers.
Hash Tables
Hash functions, collision resolution, and the data structure behind every dictionary and set.
-
- Explain hash functions and their properties
- Describe chaining collision resolution
- Analyze average-case performance
-
- Implement hash table with linear probing
- Handle tombstone deletion
- Explain table doubling
-
- Compare chaining vs open addressing
- Explain Python dict internals
- Identify when to use hash tables
Trees & Traversal
Tree structures, BFS and DFS traversals, and binary search on sorted data.
-
- Define tree terminology (root, leaf, height, depth)
- Distinguish tree types (binary, n-ary, complete, balanced)
- Explain applications
- [ ] Tree Traversal
- Implement BFS (level-order) using queue
- Implement DFS (inorder, preorder, postorder)
- Analyze complexity
- [ ] Binary Search
- Implement iterative and recursive binary search
- Analyze O(log n)
- Identify applications
Binary Search Trees & Heaps
Ordered tree structures for efficient search, insertion, and priority queue operations.
-
- Define BST property
- Implement insert, search, and traversal
- Analyze performance
-
- Implement BST deletion (3 cases)
- Implement validation
- Find in-order successor
-
- Explain heap property and array representation
- Implement max-heap
- Describe priority queue
- [ ] Heap Sort
- Implement heap sort in-place
- Analyze O(n log n) time / O(1) space
- Compare to other sorts
Sorting Algorithms
From elementary O(n²) sorts to divide-and-conquer O(n log n) algorithms and linear-time special cases.
- [ ] Elementary Sorts
- Implement insertion sort and selection sort
- Analyze O(n²) time complexity
- Explain when elementary sorts are appropriate (small n)
- [ ] Merge Sort
- Implement merge sort
- Analyze O(n log n) time and O(n) space complexity
- Explain merge sort stability
- [ ] Quick Sort
- Implement quick sort with partition
- Analyze average O(n log n) and worst O(n²)
- Explain pivot selection strategies
-
- Compare all sorts by time, space, and stability
- Explain Ω(n log n) comparison lower bound
- Describe counting sort and radix sort
Graphs
Graph representations, traversal algorithms, shortest paths, and minimum spanning trees.
-
- Define graph terminology
- Compare adjacency matrix vs adjacency list
- Analyze space and time tradeoffs
-
- Implement BFS using a queue
- Implement DFS recursively and iteratively
- Apply to cycle detection, connected components, topological sort
- [ ] Shortest Paths
- Implement Dijkstra's algorithm
- Explain negative weight limitation
- Describe Bellman-Ford algorithm
-
- Define minimum spanning trees
- Implement Kruskal's algorithm with union-find
- Explain Prim's algorithm
Algorithm Design
Recursion, backtracking, dynamic programming, and bitwise operations — the algorithmic thinking toolkit.
-
- Identify problems suited for recursion
- Implement the backtracking pattern
- Understand tail recursion
-
- Identify overlapping subproblems and optimal substructure
- Implement memoization and tabulation
- Solve classic DP problems
-
- Perform common bit manipulations
- Understand 2's complement representation
- Count set bits efficiently