Data Structures & Algorithms
Complexity Analysis
- Always analyze time AND space complexity
- Big O: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)
- Amortized analysis for dynamic structures
Core Data Structures
| Structure | Access | Search | Insert | Delete | Use When |
|---|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) | Random access, cache locality |
| Hash Map | O(1) | O(1) | O(1) | O(1) | Key-value lookup |
| Linked List | O(n) | O(n) | O(1) | O(1) | Frequent insert/delete |
| Binary Search Tree | O(log n) | O(log n) | O(log n) | O(log n) | Sorted data |
| Heap | O(1) top | O(n) | O(log n) | O(log n) | Priority queue |
| Graph | - | O(V+E) | O(1) | O(E) | Relationships, paths |
Algorithm Patterns
- Two Pointers — sorted arrays, palindromes
- Sliding Window — subarray/substring problems
- Binary Search — sorted data, search space reduction
- DFS/BFS — tree/graph traversal
- Dynamic Programming — overlapping subproblems, optimal substructure
- Greedy — locally optimal choices lead to global optimum
- Divide & Conquer — merge sort, quick sort
Choosing the Right Structure
- Need O(1) lookup? → Hash Map
- Need sorted order? → BST / Sorted Array
- Need LIFO? → Stack
- Need FIFO? → Queue
- Need priority? → Heap
- Need relationships? → Graph
- Need prefix search? → Trie