DSA - 135 Days Roadmap

Day 0-15 : Learn Basics

Things to do :

1. Learn Programming Language Basics. [DONE]
2. Learn Time Complexity. [DONE]
3. Build up logical thinking by practicing "Pattern Problems" from "Leetcode". [DONE]
4. Learn STL in C++. [DONE]
5. Do basic maths :
   • Count Digits [DONE]
   • Reverse a number [DONE]
   • Check Palindrome [DONE]
   • GCD or HCF [DONE]
   • Armstrong Number [DONE]
   • Print all Divisors [DONE]
   • Check for Prime [DONE]
6. Learn basic "Recursion".
   • Understand Recursion by printing something N times.
   • Print 1 to N using recursion.
   • Print sum for first N numbers
   • Print factorial of N numbers
   • Check if a string is palindrome or not
   • Print Fibonacci Number
7. Learn Basic Hashing.
   • Count frequencies of array elements
   • Find highest/lowest frequency element

Day 15-25 : Sorting

Things to do :

1. Selection sort
2. Bubble sort
3. Insertion sort
4. Merge sort
5. Quick sort
6. Cycle sort
7. Heap sort

Day 25-40 : Binary Search

Things to do :

1. Binary Search on 1D Arrays
   • Binary search to find X in Sorted Array
   • Lower Bound and Upper Bound
   • Search Insert Position
   • Check if Input Array is sorted
   • Find the first and last occurrence of a given number in a sorted array
   • Count occurrence of a number in a sorted array with duplicates
   • Find peak element
   • Search in Rotated Sorted Array 1
   • Search in Rotated Sorted Array 2
   • Find minimum in Rotated Sorted Array
   • Single element in a sorted array
   • Find Kth element of two sorted arrays
   • Find how many times has an array been rotated
   • Order-Agnostic Binary Search
2. Binary Search on 2D Arrays
   • Search in a 2D Matrix
   • Find Peak Element
   • Matrix Median
3. Find Answers by Binary Search in Search Space
   • Find square root of a number in log n
   • Find Nth root of a number using BS
   • Koko Eating Bananas
   • Minimum days to make M Bouquets
   • Find the smallest Divisor
   • Capacity to Ship Packages within D Days
   • Median of two Sorted Arrays
   • Aggressive Cows
   • Book Allocation Problem
   • Split Array - Largets Sum
   • Kth missing positive number
   • Minimize max distance to Gas Station
   • Median of two Sorted Arrays
   • Kth element of two Sorted Arrays

Days 41-45 : Strings

Things to do :

1. Basic
   • Remove outermost parenthesis
   • Reverse words in a given string/palindrome check
   • Largest odd number in a string
   • Longest Common Prefix
   • Isomorphic String
   • Check whether one string is a rotation of another
   • Check if two strings are anagram of each other
2. Medium String Problem
   • Sort characters by frequency
   • Maximum Nesting Depth of Parenthesis
   • Roman Number to Integer and vice versa
   • Implement Atoi
   • Count Number of Substrings
   • Longest Palindromic Substring
   • Sum of beauty of all substring
   • Reverse every word in a string

Days 46-55 : LinkedList

Things to do :

1. Singly LinkedList
2. Doubly LinkedList
3. Medium level problems of LL
   • Middle of a linked list
   • Reverse a linked list
   • Detect if a linked list has a cycle in it
   • Find the starting point in LL
   • Length of loop in LL
   • Check if LL is palindrome or not
   • Segregate odd and even nodes in LL
   • Remove Nth node from the back of the LL
   • Delete the middle node of LL
   • Sort LL
   • Sort a LL of 0's and 1's by changing links
   • Find the intersection point of Y LL
   • Add 1 to a number represented by LL
   • Add two numbers in LL
4. Medium level problems of DLL
   • Delete all occurences of a key in DLL
   • Find pairs with given sum in DLL
   • Remove duplicates from sorted DLL
5. Hard level problems of LL
   • Reverse LL in a group of given size K
   • Rotate a LL
   • Flattening of LL
   • Clone a Linkedlist with random and next pointer

Days 56-65 : Recursion

Things to do :

1. Get a strong hold
   • Recursive implementation of atoi()
   • Pow(x, n)
   • Count Good numbers
   • Sort a stack using recursion
   • Reverse a stack using recursion
2. Subsequences Pattern
   • Generate all binary strings
   • Generate parenthesis
   • Print all subsequences/power set
   • Learn all pattern of subsequences
   • Count all subsequences with sum K
   • Combination Sum
   • Combination Sum 2
   • Combination Sum 3
   • Subset Sum 1
   • Subset Sum 2
   • Letter combinations of a phone number
3. Hard Level
   • Palindrome Partitioning
   • Word Search
   • N Queen
   • Rat in a Maze
   • Word Break
   • M Coloring Problem
   • Sudoku Solver
   • Expression Add Operators

Days 66-68 : Bit Manipulation

Things to do :

1. Basic
   • Introduction to Bit Manipulation
   • Check if i-th bit is set or not
   • Check if a number is odd or not
   • Check if a number is power of 2 or not
   • Count the number of set bits
   • Set/Unset the rightmost unset bit
   • Swap two numbers
   • Divide two integers without using multiplication, division or mod oeprator
2. Interview Problems
   • Count number of bits to be flipped to convert A to B
   • Find the number that appears odd number of times
   • Power Set
   • Find XOR of numbers from L to R
   • Find the two numbers appearing odd number of times
3. Advanced Maths
   • Print prime factors of a number
   • All divisors of a number
   • Sieve of Eratosthenes
   • Find prime factorization of a number using sieve
   • Power(n, x)

Days 69-78 : Stack and Queues

Things to do :

1. Learning
   • Implement stacks using arrays
   • Implement queue using arrays
   • Implement stacks using queue
   • Implement queue using stacks
   • Implement stacks using Linkedlist
   • Implement queue using Linkedlist
   • Check for balanced parenthesis
   • Implement Min Stack
2. Prefix, Infix, Postfix Conversion Problems
   • Infix to Postfix conversion using stack
   • Prefix to Infix Conversion
   • Prefix to Postfix Conversion
   • Postfix to Prefix Conversion
   • Postfix to Infix
   • Convert Infix to Prefix Notation
3. Monotonic Stack/Queue Problems
   • Next Greater Element 1
   • Next Greater Element 2
   • Next Smaller Element
   • Number of NGE's to the right
   • Trapping Rainwater
   • Sum of subarray minimum
   • Stock span problem
   • Asteroid Collision
   • Sum of subarray ranges
   • Remove K digits
   • Largest rectangle in a histogram
   • Maximal Rectangles
4. Implementation Problems
   • Sliding Window Maximum
   • Stock Span Problem
   • The Celebrity Problem
   • Rotten Oranges
   • LRU Cache
   • LFU Cache

Days 79-83 : Greedy Algorithms

Things to do :

1. Practice GFG Top 20 Greedy Algorithms Interview Questions

Days 84-100 : Binary Tree

Things to do :

1. Basic
   • Basic Tree Structure
   • Traversing a Binary Tree (Preorder, Postorder, Inorder)
   • Balanced Binary Search Tree
2. Problems
   • Find height or depth of a binary tree
   • Finding diameter of a tree using height of each node
   • Find number of Universal Value Subtrees in a Binary Tree
   • Find if a given Binary Tree is a Sub-Tree of another Binary Tree
   • Finding nodes at distance K from a given Node
   • Copy a binary tree where each node has a random pointer
   • Zigzag Traversal of Binary Tree
   • Check if Binary Tree is foldable
   • Threaded Binary Tree
   • Convert Binary Tree to Threaded Binary Tree
   • Sum of K smallest elements in Binary Search Tree

Days 101-110 : Graphs

Things to do :

1. BFS/DFS
2. Shortest Path Algo
3. Mininmum Spanning Tree
4. Union-Find

Days 111-120 : Dynamic Programming

Things to do :

1. Learn Basic
2. Problems
   • Climbing Stairs
   • Best time to buy and sell stock
   • Maximum Subarray
   • House Robber
3. Hard Problems
   • Solve Top 20 Dynamic Programming Interview Questions on GFG