DSA Cheat Sheet for Google (AI/ML Role)
Arrays & Strings
- Sliding Window, Two Pointers, Prefix Sum
- Problems: Two Sum, 3Sum, Longest Substring Without Repeating, Merge Intervals
Hashing
- HashMap, HashSet, Frequency Counters
- Problems: Group Anagrams, Subarray Sum Equals K
Recursion & Backtracking
- Subset Generation, Permutations, N-Queens, Sudoku Solver
- Key: Prune search space, use memoization when possible
Sorting & Searching
- Binary Search, Quick Sort, Merge Sort, Rotated Array Search
- Problems: Search Insert Position, Median of Two Sorted Arrays
Linked List
- Reverse Linked List, Detect Cycle (Floyd's Algorithm), Merge K Sorted Lists
- Problems: Add Two Numbers, Reorder List
Stacks & Queues
- Monotonic Stack, Min Stack, Queue with Two Stacks
- Problems: Valid Parentheses, Largest Rectangle in Histogram
Trees
- DFS (Preorder, Inorder, Postorder), BFS, Lowest Common Ancestor
- Problems: Binary Tree Level Order Traversal, Serialize & Deserialize Tree
Graphs
- DFS, BFS, Union-Find, Dijkstra, Topological Sort
- Problems: Clone Graph, Course Schedule, Number of Islands
Heaps & Priority Queue
- Min Heap, Max Heap, Heapify
- Problems: Kth Largest Element, Sliding Window Maximum
Greedy Algorithms
- Interval Scheduling, Activity Selection, Huffman Coding
- Problems: Jump Game, Gas Station
Dynamic Programming (DP)
- 1D DP: Fibonacci, House Robber
- 2D DP: Knapsack, Matrix Paths, Edit Distance
- DP on Subsequences: LIS, Subset Sum, LCS
- Optimization: Space Reduction, Memoization
Bit Manipulation
- XOR tricks, Subset generation with bits
- Problems: Single Number, Power of Two
Maths for ML Engineer
- Probability & Statistics
- Linear Algebra (Matrix Multiplication, Eigenvalues, Eigenvectors)
- Calculus basics (Derivatives, Integrals in optimization)
- Optimization: Gradient Descent, Regularization
System Design for ML
- ML Pipeline: Data Preprocessing -> Model Training -> Deployment
- Serving ML models with APIs (Flask/FastAPI), scaling with Docker/Kubernetes
- Focus: Model monitoring, retraining, data pipelines
