This repository provides all the topics under DSA you need to know for an SDE Interview or competitive programming.
Topics
- Array
- LinkedList
- Greedy Algorithms
- Recursion
- Backtracking
- Binary Search
- Heaps
- Stacks and Queues
- Strings
- STL
- Binary Tree and BST
- Trees
- Graphs
- Dynamic Programming
- Tries
- Bit Manipulation
- Range Queries
- Number Theory
- Geometry
- Additional Topics
Array
LinkedList
- Reversing a LL
- Slow and fast pointer technique
- Doubly and circular LL
Resources
- Leetcode Problems
Greedy
- Activity Selection
- Minimum number of platforms required
- Fractional Knapsack
Recursion
BackTracking
Binary Search
Heaps
Stack and Queues
- Next/Previous Greater/Smaller Element in O(N)
- Doubly Ended Queue - Deque
- Circular Queue
- Sort Stack using Stack
- Implement Queue using Stacks
- Implement Stack using Queues
- Valid Parentheses Expression
- Min Stack Problem (Get min of the stack in O(1))
- Real-life use cases and applications
Strings
- String Hashing
- KMP Algorithm
- Z Algorithm
- Rabin Karp Algo
- Manacher Algorithm
Resources
- CP-Algorthms
STL (C++)
- Unordered set, set and implementation
- Unordered map, map and implementation
- Lower bound and Upper bound
- Sorting with custom comparator
- Min Heap and Max Heap (priority_queue<>)
Binary Tree and BST
- AVL Trees
- Red Black Trees
- B/B+ Trees
- Traversal
- Serialization and Deserialization
Trees
Resources
Graph
- Representation
- DFS traversal
- BFS traversal
- Multisource BFS
- Detecting cycles (Both directed/undirected using DFS/BFS)
- Topological Sorting (using DFS/BFS - Kahn’s Algo)
- Bipartite Check (using DFS/BFS)
- Shortest Path
- BFS (edge weight = 1)
- 0/1 BFS (edge weight = 0 or x, where x >= 0)
- Bellman-Ford (no negative cycles)
- SPFA (optimized BF)
- Dijkstra (no negative edge, least TC)
- Floyd Warshal (no negative cycles, small graphs)
- Detecting negative cycles using Bellman Ford and Floyd Warshal
- Disjoint Set Union
- Union by rank
- Union by size
- Path compression in findParent()
- Minimum Spanning Tree
- Strongly Connected Components
- Kosaraju Algo
- Tarjans Algo
- Finding Bridges
- Finding Articulation Points
Resource
- Strivers Playlist
- CSES Graph
DP
Resources
Tries
- Implementation (Insert, Search, StartsWith)
- Number of distinct substrings in a string
- Power Set
- XOR queries on arrays
Resources
- Striver Playlist
Bit Manipulation
- Representation and operations (AND OR XOR NOT)
- Set or check a bit position, toggle, get last bit, etc
- Generating all subsets
- Builtin C++ functions (__builtin_popcount(), etc.)
- Properties of XOR
- Optimisation techniques using bitmasking
Range Queries
- Prefix/Suffix Sum Array
- Difference Array (Range Updates Point Query)
- Sparse Table
- <O(NLOGN), O(1)> Time Complexity
- O(NLOGN) Space Complexity
- Use for idempotent/overlap friendly function - MIN, MAX, GCD, AND, OR
- Fenwick Tree / Binary Indexed Tree
- Ordinary BIT (Point Update and Range Query)
- Reverse BIT (Range Update and Point Query)
- 2 BITs (Range Updates and Range Queries)
- Segment Tree (Point Update Range Query)
- Fenwick tree supports SUM query but Seg tree can support any associative o/p - MIN, MAX, GCD, AND, OR, XOR.
- It takes more memory
- Lazy Segment Tree (Range Update Range Query)
- Index/ Coordinate compression
Number Theory
- Primality Test
- Sieve of Eratosthenes <O(N*LOG(LOGN)), O(1)>
- Segmented Sieve - Finding primes in a range
- Linear Sieve - Finding primes less than 1e7 in O(N)
- Can be used to compute the smallest prime factor of all numbers b/w [1, 1e6]
- Prime factorization
- Trial Division O(SQRTN)
- Using sieve <O(N*LOG(LOGN)), O(LOGN)>
- Binary Exponentiation
- Euclidean GCD <O(LOG(MIN(a,b)))>
- Extended Euclidean Algorithm
- Solving Linear Diophantine Equations.
- Finding the modular inverse of a number
- Modular Arithmetic
- Congruence
- Addition, Multiplication, Subtraction
- Calculation of Modulo Inverse
𝑎^−1 mod m
- Only exists when
gcd(a, m) = 1
- Fermat’s Little Theorem and Binary Exponentiation (only when
m
is prime)
- Euler theorem and Extended Euclidean Theorem
- Binomial Coefficient (both with and without the mod)
- Euler Totient Function
- Using Factorisation O(SQRTN)
- Using Sieve O(NLOG(LOG(N)))
- Misc
Geometry
- Sweep Line Algorithms
- Convex Hull
- Closest Pair Problem
Additional Topics
- Expected Value and Probability
- Burnside Lemma
- Game Theory (Nim / Sprague Grundy)
- Flows and Cuts
- Sqrt decomposition (Mo’s Algorithm)
- Meet in the Middle
- Offline Queries
- Reservoir Sampling
- 2 SAT