Data-Structures-and-Algorithms

This repository provides all the topics under DSA you need to know for an SDE Interview or competitive programming.

Topics

1. Array
2. LinkedList
3. Greedy Algorithms
4. Recursion
5. Backtracking
6. Binary Search
7. Heaps
8. Stacks and Queues
9. Strings
10. STL
11. Binary Tree and BST
12. Trees
13. Graphs
14. Dynamic Programming
15. Tries
16. Bit Manipulation
17. Range Queries
18. Number Theory
19. Geometry
20. Additional Topics

Array

• Sorting Algorithms
• Prefix/Suffix Sum
• Two Pointers
• Sliding Window
• Count Inversions
  • Using Merge Sort
  • Using Fenwick Tree
  • Using Ordered Set
• Kadane’s Algorithm
• Dutch National Flag
• Boyre Moore Voting Algorithms
• All Subsets Generation
  • Using Recursion
  • Using Bitmasks
• Permutation
• Quick Select

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

• DFS/BFS Traversal
• DP on Trees
• Height/Level and Diameter
• Binary Lifting
  • Finding kth parent of a node
  • Path aggregates
• Euler Tour (and Range Queries) or Flattening the tree
• LCA of two nodes
  • Using SQRT decomposition <O(N), O(SQRT(N))>*
  • Using Binary Lifting <O(N LOGN, O(LOGN)>
  • Using EulerTour and RMQ
    • (Sparse Table) <O(N + NLOGN), O(1)> [Better Choice]
    • (Segment Tree) <O(N), O(LOGN)>
• Heavy Light Decomposition
• Centroid Decomposition**

• Note: *<O(N), O(SQRT(N))> means O(N) precomputation and O(SQRTN) query processing

• Query	Query and Update
  Subtree Queries	Precompute	Euler Tour
  Path Queries	Binary Lifting	HLD

Resources

• Pepcoding - Euler Tour
• CSES Problem Set

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
  • Kruskals Algo
  • Prims Algo
• Strongly Connected Components
  • Kosaraju Algo
  • Tarjans Algo
• Finding Bridges
• Finding Articulation Points

  Resource

• Strivers Playlist
• CSES Graph

DP

• 0/1 Knapsack
• Unbounded Knapsack
• Longest Common Subsequence
• Matrix Chain Multiplication
• DP on Trees
• Bitmask DP
• Digit DP
• DP on Ranges

Resources

• Atcoder DP Problems
• CSES DP
• Kartik Arora
• Striver’s Playlist
• Aditya Verma
• DP Handbook - Arpan Banerjee

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)))>
  • Properties of GCD
• 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
  • Number of Divisors/Sum of Divisors formulae
  • Chicken McNugget Theorem
  • Legendre’s formula
  • Catalan Numbers
  • Dearrangments
  • Josephus Problem
  • Burnside Lemma
  • Star and Bar Theorem

    Resources

  • PPT

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