Data structures & algorithms
Curated patterns for Python coding interviews. Each file covers one pattern with explanation + 3-5 canonical problems, with Python-idiomatic solutions.
New here? Start with Common data structures and their features — a reference of the data structures themselves (main features, operation costs, and the Python type for each). The sections below are algorithmic patterns that operate on those structures.
Sections
- Arrays strings — two pointers, sliding window, prefix sums
- Hashmaps sets — counting, top-K, dedup
- Linked lists — reverse, cycle detection, merge
- Trees — DFS/BFS, BST validation, LCA, serialization
- Graphs — BFS, DFS, topological sort, union-find, shortest path
- Dp — memoization, tabulation, classic problems
- Recursion backtracking — permutations, subsets, N-queens
- Sorting searching — binary search variants, quickselect
- Python specific —
bisect,heapq,deque, idiomatic patterns
How to use this
Don’t memorize solutions. Memorize the pattern and recognize when it applies. A coding interview is mostly about identifying which pattern fits the problem in 30 seconds, then implementing it cleanly.
Suggested practice approach:
- Read the pattern explanation.
- Try the first problem on paper or whiteboard, no IDE.
- Compare with the solution. If you got it: move on. If not: redo it from scratch tomorrow.
- After all patterns, do mixed practice (LeetCode “Top 75” or NeetCode 150).
Big-O quick reference
| Structure | Access | Search | Insert | Delete |
|---|---|---|---|---|
array (list) |
O(1) | O(n) | O(1) end / O(n) middle | O(n) |
| linked list | O(n) | O(n) | O(1) | O(1) given node |
hash map (dict) |
— | O(1) avg | O(1) avg | O(1) avg |
| BST (balanced) | O(log n) | O(log n) | O(log n) | O(log n) |
| heap | — | O(n) | O(log n) | O(log n) min/max |
deque |
O(1) ends | O(n) | O(1) ends | O(1) ends |
| Algorithm | Time | Space |
|---|---|---|
| Linear search | O(n) | O(1) |
| Binary search | O(log n) | O(1) |
| Quicksort (avg) | O(n log n) | O(log n) |
| Mergesort | O(n log n) | O(n) |
| BFS / DFS | O(V+E) | O(V) |
| Dijkstra (heap) | O((V+E) log V) | O(V) |
Added patterns
| Folder | File | Pattern |
|---|---|---|
10_stacks_queues/ |
Monotonic stack | monotonic stack and deque — turns O(n^2) into O(n) |
11_intervals/ |
Intervals | merge, overlap, sweep line — and which key to sort by |
06_dp/ |
2D dynamic programming | 2D DP: knapsack, LCS, edit distance |
04_trees/ |
BSTs and tries | BST invariant and deletion; tries for prefix problems |
12_greedy_and_bits/ |
Greedy algorithms and bit manipulation | greedy justification, XOR tricks, bitmasks |