Week 1: Arrays & Strings
- Arrays:
* Use prefix sums for range queries.
* Sliding window for subarray problems.
* Two pointers for sorted arrays and subarray sums.
* Kadane’s Algorithm for maximum subarray sum.
- Strings:
* Hashing/Rolling hash for substring matching.
* KMP Algorithm for pattern search.
* Sliding window for anagrams & substrings.
Week 2: Linked List
- Single Linked List:
* Fast/slow pointers for cycle detection.
* Reversal using iterative & recursive methods.
- Doubly Linked List:
* Easier backtracking, but higher memory cost.
- Problems:
* LRU Cache implementation.
* Merge K sorted linked lists using min-heap.
Week 3: Stacks & Queues
- Stack:
* Next Greater Element using stack.
* Balanced parentheses problem.
- Queue:
* Implement stack using 2 queues & vice versa.
* Sliding Window Maximum using deque.
Week 4: Recursion & Backtracking
- Recursion:
* Break problem into subproblems with base case.
* Use memoization to optimize overlapping calls.
- Backtracking:
* Try all options, undo (backtrack) on failure.
* Problems: N-Queens, Sudoku Solver, Word Search.
Week 5: Binary Trees
- Traversals: Inorder, Preorder, Postorder, Level-order (BFS).
- Diameter of Tree = longest path between 2 nodes.
- Lowest Common Ancestor (LCA) using recursion.
- Height-balanced tree check using DFS.
Week 6: Binary Search Trees (BST)
- Properties: Left < Root < Right.
- Inorder Traversal = Sorted Array.
- Common Problems: Kth Smallest, Floor/Ceil, LCA.
Week 7: Graphs
- Traversals: BFS (queue), DFS (stack/recursion).
- Cycle detection: Union-Find (undirected), DFS (directed).
- Shortest Paths: Dijkstra, Bellman-Ford, Floyd-Warshall.
- Minimum Spanning Tree: Kruskal, Prim.
Week 8: Dynamic Programming
- Key Idea: Optimal substructure + overlapping subproblems.
- Common Patterns: Knapsack, LIS, Matrix Paths, DP on Trees.
- Bottom-up vs Top-down (memoization).
Week 9: Greedy Algorithms
- Works when local optimum → global optimum.
- Problems:
* Activity Selection (Earliest finish time).
* Huffman Encoding.
* Minimum Spanning Tree (Prim’s, Kruskal’s).
Week 10: Heaps & Hashing
- Heap:
* Max-heap, Min-heap.
* Heapify: O(n).
* Kth largest/smallest using heaps.
- Hashing:
* Hashmaps for frequency counting.
* Hashset for duplicates/subarray sums.
Week 11: Tries & Bit Manipulation
- Tries:
* Used for prefix matching, autocomplete, dictionary.
* Insert, Search: O(L) where L = word length.
- Bit Manipulation:
* XOR properties → Find unique element.
* Subset generation using bits.
Week 12: Mixed Revision + Mock Tests
- Revise all patterns:
* Sliding Window, Two Pointers, Binary Search on Answers.
* DP patterns (1D, 2D, subsequence, partition).
* Graph algorithms (BFS/DFS, shortest path, MST).
- Take 2–3 mock OAs simulating real conditions.
