30 Days DSA Interview Preparation Planby@samirpaul

# 30 Days DSA Interview Preparation Plan

by Samir P.October 21st, 2022

In this repository, I have stored solutions to various problems and concepts of **Data Structures and Algorithms** in Python3 in a structured manner. In various folders of the above topics, you can find questions and concepts related to that topic. In the [SamirPaul1/DSAlgo/main/Main/02_DynamicProgramming] section, all the questions not covered in **Ada Vermama Verma's are included. The repository is hosted by Samir Paul, who uses it to help students understand Python's programming.

## 30 Days Interview Preparation Plan🎯

Day1: (Arrays)

• Sort an array of 0’s 1’s 2’s without using extra space or sorting Algo
• Repeat and Missing Number
• Merge two sorted Arrays without extra space
• Merge Overlapping Subintervals
• Find the duplicate in an array of N+1 integers.

Day2: (Arrays)

• Set Matrix Zeros
• Pascal Triangle
• Next Permutation
• Inversion of Array (Using Merge Sort)
• Rotate Matrix

Day3: (Arrays/maths)

• Search in a 2D matrix
• Pow(X,n)
• Majority Element (>N/2 times)
• Majority Element (>N/3 times)
• Grid Unique Paths
• Reverse Pairs (Leetcode)
• Go through Puzzles from GFG (Search on your own)

Day4: (Hashing)

• 2 Sum problem
• 4 Sum problem
• Longest Consecutive Sequence
• Largest Subarray with 0 sum
• Count the number of subarrays with the given XOR (this clears a lot of problems)
• Longest substring without repeat

• Find the middle of LinkedList
• Merge two sorted Linked List
• Remove the N-th node from the back of LinkedList
• Delete a given Node when a node is given. (0(1) solution)

Day6:

• Find the intersection point of Y LinkedList
• Detect a cycle in Linked List
• Reverse a LinkedList in groups of size k
• Check if a LinkedList is a palindrome or not.
• Find the starting point of the Loop of LinkedList

Day7: (2-pointer)

• Clone a Linked List with random and next pointer
• 3 sum
• Trapping rainwater
• Remove Duplicate from the Sorted array
• Max consecutive ones

Day8: (Greedy)

• N meeting in one room
• Minimum number of platforms required for a railway
• Job sequencing Problem
• Fractional Knapsack Problem
• Greedy algorithm to find the minimum number of coins
• Activity Selection (it is the same as N meeting in one room)

Day9 (Recursion):

• Subset Sums
• Subset-II
• Combination sum-
• Combination sum
• Palindrome Partitioning
• K-th permutation Sequence

Day10: (Recursion and Backtracking)

• Print all Permutations of a string/array
• N queens Problem
• SudokuSolver
• M Coloring Problem
• Rat in a Maze
• Word Break -> print all ways

Day11 : (Binary Search)

• The N-th root of an integer (use binary search) (square root, cube root, ..)
• Matrix Median
• Find the element that appears once in the sorted array, and the rest element appears twice (Binary search)
• Search element in a sorted and rotated array/ find pivot where it is rotated
• Median of 2 sorted arrays
• K-th element of two sorted arrays
• Allocate a Minimum Number of Pages
• Aggressive Cows

Day12: (Bits) (Optional, very rare topic in interviews, but if you have time left, someone might ask)

• Check if a number if a power of 2 or not in O(1)
• Count total set bits
• Divide Integers without / operator
• Power Set (this is very important)
• Find MSB in o(1)
• Find the square of a number without using multiplication or division operators.

Day13: (Stack and Queue)

• Implement Stack Using Arrays
• Implement Queue Using Arrays
• Implement Stack using Queue (using single queue)
• Implement Queue using Stack (0(1) amortized method)
• Check for balanced parentheses
• Next Greater Element
• Sort a Stack

Day14:

• Next Smaller Element
• LRU cache (vvvv. imp)
• LFU Cache (Hard, can be ignored)
• Largest rectangle in a histogram (Do the one-pass solution)
• Sliding Window Maximum
• Implement Min Stack
• Rotten Orange (Using BFS)
• Stock Span Problem
• Find the maximum or minimum of every window size
• The Celebrity Problem

Day15: (String)

• Reverse Words in a String
• Longest Palindrome in a string
• Roman Number to Integer and vice versa
• Implement ATOI/STRSTR
• Longest Common Prefix Rabin Karp

Day16: (String)

• Prefix Function/Z-Function
• KMP Algo / LPS(pi) array
• Minimum characters needed to be inserted in the beginning to make it palindromic.
• Check for Anagrams Count and Say Compare version numbers

Day17: (Binary Tree)

• In-order Traversal (with recursion and without recursion)
• Pre-order Traversal (with recursion and without recursion)
• Post-order Traversal (with recursion and without recursion)
• Left View Of Binary Tree
• Bottom View of Binary Tree
• Top View of Binary Tree

Day18: (Binary Tree)

• Level order Traversal / Level order traversal in spiral form
• Height of a Binary Tree
• Diameter of Binary Tree
• Check if the Binary tree is height-balanced or not
• LCA in Binary Tree
• Check if the two trees are identical or not

Day 19: (Binary Tree)

• Maximum path sum
• Construct Binary Tree from inorder and preorder
• Construct Binary Tree from Inorder and Postorder
• Symmetric Binary Tree
• Flatten Binary Tree to LinkedList
• Check if Binary Tree is the mirror of itself or not

Day 20: (Binary Search Tree)

• Populate Next Right pointers of the Tree
• Search the given Key in BST Construct BST from the given keys.
• Check if a BT is BST or not
• Find the LCA of two nodes in BST
• Find the in-order predecessor/successor of a given Key in BST.

Day21: (BinarySearchTree)

• Floor and Ceil in a BST
• Find K-th smallest and K-th largest element in BST (2 different Questions)
• Find a pair with a given sum in BST
• BST iterator Size of the largest BST in a Binary Tree
• Serialize and deserialize Binary Tree

Day22: (Mixed Questions)

• Binary Tree to Double Linked List
• Find the median in a stream of running integers.
• K-th largest element in a stream.
• Distinct numbers in the Window.
• K-th largest element in an unsorted array.
• Flood-fill Algorithm

Day23: (Graph)

• Clone a graph (Not as easy as it looks)
• DFS
• BFS
• Detect A cycle in Undirected Graph/Directed Graph
• Topo Sort
• Number of islands (Do in Grid and Graph both)
• Bipartite Check

Day24: (Graph)

• SCC(using KosaRaju’s Algo)
• Dijkstra's algorithm
• Bellman-Ford Algo
• Floyd Warshall Algorithm
• MST using Prim’s Algo
• MST using Kruskal’s Algo

Day25: (Dynamic Programming)

• Max Product Subarray
• Longest Increasing Subsequence
• Longest Common Subsequence
• 0-1 Knapsack
• Edit Distance
• Maximum sum increasing subsequence
• Matrix Chain Multiplication

Day26: (DP)

• Maximum sum path in the matrix, (count paths and similar types do, also backtrack to find the maximum path)

• Coin change

• Subset Sum

• Rod Cutting

• Egg Dropping

• Word Break

• Palindrome Partitioning (MCM Variation)

• Maximum profit in Job scheduling

### For core revision</>

Day27:

• Revise OS notes that you would have made during your sem
• If not made notes, spend 2 or 3 days and make notes from Knowledge Gate.

Day28:

• Revise DBMS notes that you would have made during your semesters.
• If not made notes, spend 2 or 3 days and make notes from Knowledge Gate.

Day29:

• Revise CN notes, that you would have made during your sem.
• If not made notes, spend 2 or 3 days and make notes from Knowledge Gate.

Day30:

• Make a note of how you will represent your projects, and prepare all questions related to tech which you have used in your projects.
• Prepare a note that you can say for 3-10 minutes when he asks you that say something about the project.

## Data Structures & Algorithms for Coding Interview

In this repository, I have stored solutions to various problems and concepts of Data Structures and Algorithms in Python3 in a structured manner.✨

Topics Covered:

• Dynamic Programming

• Sorting Algorithms

• Object-Oriented Programming

• Binary Trees

• Graph Algorithms

• Heap

• Matrix

• Trie

• Binary Search

• Backtracking

• Stack

• Queue

• Greedy

• String

• Bit Manipulation

• Array

• HashMap

• DFS BFS

• Two Pointers

• Math

• Recursion

In various folders of the above topics, you can find questions and concepts related to that topic.

• For learning Dynamic Programming, we need to relate the concepts learned in one question to apply to another problem💡. In the Dynamic Programming section, you can find all the questions covered and not covered in Aditya Verma's dynamic programming playlist folder-wise with my handwritten notes.✍️

• If you are preparing for an interview from Striver’s SDE Sheet then the 30-Days-SDE-Sheet-Practice will be helpful to you. Here I have stored solutions to questions of each day with short notes to each solution, as short notes about the approach are very helpful during revision.🎯

• In the Questions-Sheet directory, you can find questions asked by top product-based companies.

• There is a collection of books and pdfs on various important computer science fundamentals in the BOOKS-and-PDFs directory.📚

View this repository in an online VSCode-like interface▶️ https://samirpaul.in/DSAlgo 🚀

I am continuously trying to improve this repository by adding new questions and concepts related to the respective topic. Please feel free to contribute to this repository.💻

If you appreciate my work, please give a star(🌟) to this repository. It motivates me. ❤️🚀

L O A D I N G
. . . comments & more!