Skip to content

Latest commit

 

History

History
1001 lines (767 loc) · 113 KB

README.md

File metadata and controls

1001 lines (767 loc) · 113 KB

Data Structures & Algorithms for Coding Interview

Stars Forks Size Hits language

If you appreciate my work, please 🌟 this repository. It motivates me. 🚀🚀

DSA banner

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:

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

View this repository in online VS Code: https://samirpaul.in/DSAlgo DSAlgo

DSA Online VSCode

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.

Things you can contribute to:

  • Update the existing solution Codacy Badge with a better one (better complexity).
  • Add new questions and solutions in Python3 to the respective directory.
  • Add new resources to BOOKS-and-PDFs & Questions-Sheet.
  • Solve issues raised by other people or yourself.
  • Provide well-documented source code with detailed explanations.

Stargazers over time

Star History


More Resources:

Click to expand!👇

List of Important Questions:✨

The following list of questions was recommended by Love Babbar on this video. I have documented all those questions here.✌️

Topic Important DSA Questions Link
Topic: Problem: Related Link
<->
Array Reverse the array (char) https://leetcode.com/problems/reverse-string/
Array Remove the maximum and minimum element in an array https://leetcode.com/problems/removing-minimum-and-maximum-from-array/
Array Find the "Kth" largest element of an array https://leetcode.com/problems/kth-largest-element-in-an-array/
Array Given an array which consists of only 0, 1 and 2. Sort the array without using any sorting algo https://leetcode.com/problems/sort-colors/
Array Move all the negative elements to one side of the array <->
Array Find the Union and Intersection of the two sorted arrays. Intersection of the two sorted arrays.(Leetcode)
Array Write a program to cyclically rotate an array by one. https://leetcode.com/problems/rotate-array/
Array find Largest sum contiguous Subarray [V. IMP] https://leetcode.com/problems/maximum-subarray/
Array Minimise the maximum difference between heights [V.IMP] https://leetcode.com/problems/smallest-range-ii/
Array Minimum no. of Jumps to reach end of an array https://leetcode.com/problems/jump-game
Array Find duplicate in an array of N+1 Integers https://leetcode.com/problems/find-the-duplicate-number/
Array Merge 2 sorted arrays without using Extra space. https://leetcode.com/problems/merge-sorted-array/
Array Kadane's Algorithm https://leetcode.com/problems/maximum-subarray/
Array Merge Intervals <->
Array Next Permutation <->
Array Count Inversion <->
Array Best time to buy and Sell stock <->
Array find duplicate in an array of N+1 Integers <->
Array Merge 2 sorted arrays without using Extra space. <->
Array Kadane's Algorithm https://leetcode.com/problems/maximum-subarray/
Array Merge Intervals https://leetcode.com/problems/merge-intervals/
Array Next Permutation https://leetcode.com/problems/next-permutation/
Array Count Inversions <->
Array Best time to buy and Sell stock https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
Array find all pairs on integer array whose sum is equal to given number <->
Array find common elements In 3 sorted arrays <->
Array Rearrange the array in alternating positive and negative items with O(1) extra space <->
Array Find if there is any subarray with sum equal to 0 https://leetcode.com/problems/subarray-sum-equals-k/
Array Find factorial of a large number <->
Array find maximum product subarray <->
Array Find longest coinsecutive subsequence <->
Array Given an array of size n and a number k, fin all elements that appear more than " n/k " times. <->
Array Maximum profit by buying and selling a share atmost twice <->
Array Find whether an array is a subset of another array <->
Array Find the triplet that sum to a given value <->
Array Trapping Rain water problem <->
Array Chocolate Distribution problem <->
Array Smallest Subarray with sum greater than a given value <->
Array Three way partitioning of an array around a given value <->
Array Minimum swaps required bring elements less equal K together <->
Array Minimum no. of operations required to make an array palindrome <->
Array Median of 2 sorted arrays of equal size <->
Array Median of 2 sorted arrays of different size <->
Array Subarray Sums Divisible by K
Array Continuous Subarray Sum
<->
<->
Matrix Spiral traversal on a Matrix <->
Matrix Search an element in a matriix <->
Matrix Find median in a row wise sorted matrix <->
Matrix Find row with maximum no. of 1's <->
Matrix Print elements in sorted order using row-column wise sorted matrix <->
Matrix Largest Rectangle in Histogram
Matrix Maximum size rectangle https://practice.geeksforgeeks.org/problems/max-rectangle/1
Matrix Find a specific pair in matrix <->
Matrix Rotate matrix by 90 degrees <->
Matrix Kth smallest element in a row-cpumn wise sorted matrix <->
Matrix Common elements in all rows of a given matrix <->
String Reverse a String <->
String Check whether a String is Palindrome or not <->
String Find Duplicate characters in a string <->
String Why strings are immutable in Java? <->
String Write a Code to check whether one string is a rotation of another <->
String Write a Program to check whether a string is a valid shuffle of two strings or not <->
String Count and Say problem <->
String Write a program to find the longest Palindrome in a string.[ Longest palindromic Substring] <->
String Find Longest Recurring Subsequence in String <->
String Print all Subsequences of a string. <->
String Print all the permutations of the given string <->
String Split the Binary string into two substring with equal 0’s and 1’s <->
String Word Wrap Problem [VERY IMP]. <->
String EDIT Distance [Very Imp] <->
String Find next greater number with same set of digits. [Very Very IMP] <->
String Balanced Parenthesis problem.[Imp] <->
String Word break Problem[ Very Imp] <->
String Rabin Karp Algo <->
String KMP Algo <->
String Convert a Sentence into its equivalent mobile numeric keypad sequence. <->
String Minimum number of bracket reversals needed to make an expression balanced. <->
String Count All Palindromic Subsequence in a given String. <->
String Count of number of given string in 2D character array <->
String Search a Word in a 2D Grid of characters. <->
String Boyer Moore Algorithm for Pattern Searching. <->
String Converting Roman Numerals to Decimal <->
String Longest Common Prefix <->
String Number of flips to make binary string alternate <->
String Find the first repeated word in string. <->
String Minimum number of swaps for bracket balancing. <->
String Find the longest common subsequence between two strings. <->
String Program to generate all possible valid IP addresses from given string. <->
String Write a program tofind the smallest window that contains all characters of string itself. <->
String Rearrange characters in a string such that no two adjacent are same <->
String Minimum characters to be added at front to make string palindrome <->
String Given a sequence of words, print all anagrams together <->
String Find the smallest window in a string containing all characters of another string <->
String Recursively remove all adjacent duplicates <->
String String matching where one string contains wildcard characters <->
String Function to find Number of customers who could not get a computer <->
String Transform One String to Another using Minimum Number of Given Operation <->
String Check if two given strings are isomorphic to each other <->
String Recursively print all sentences that can be formed from list of word lists <->
Searching & Sorting Find first and last positions of an element in a sorted array <->
Searching & Sorting Find a Fixed Point (Value equal to index) in a given array https://leetcode.com/problems/find-pivot-index/
Searching & Sorting Search in a rotated sorted array https://leetcode.com/problems/search-in-rotated-sorted-array/
Searching & Sorting square root of an integer <->
Searching & Sorting Maximum and minimum of an array using minimum number of comparisons <->
Searching & Sorting Optimum location of point to minimize total distance https://leetcode.com/problems/best-meeting-point/
Searching & Sorting Find the repeating and the missing <->
Searching & Sorting find majority element <->
Searching & Sorting Searching in an array where adjacent differ by at most k <->
Searching & Sorting find a pair with a given difference <->
Searching & Sorting find four elements that sum to a given value <->
Searching & Sorting maximum sum such that no 2 elements are adjacent <->
Searching & Sorting Count triplet with sum smaller than a given value <->
Searching & Sorting merge 2 sorted arrays <->
Searching & Sorting print all subarrays with 0 sum <->
Searching & Sorting Product array Puzzle <->
Searching & Sorting Sort array according to count of set bits <->
Searching & Sorting minimum no. of swaps required to sort the array <->
Searching & Sorting Bishu and Soldiers <->
Searching & Sorting Rasta and Kheshtak <->
Searching & Sorting Kth smallest number again Using Min Heap
Searching & Sorting Find pivot element in a sorted array <->
Searching & Sorting K-th Element of Two Sorted Arrays <->
Searching & Sorting Aggressive cows <->
Searching & Sorting Book Allocation Problem https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/
Searching & Sorting EKOSPOJ: <->
Searching & Sorting Job Scheduling Algo <->
Searching & Sorting Missing Number in AP <->
Searching & Sorting Smallest number with atleastn trailing zeroes infactorial <->
Searching & Sorting Painters Partition Problem: <->
Searching & Sorting ROTI-Prata SPOJ <->
Searching & Sorting DoubleHelix SPOJ <->
Searching & Sorting Subset Sums <->
Searching & Sorting Findthe inversion count <->
Searching & Sorting Implement Merge-sort in-place <->
Searching & Sorting Partitioning and Sorting Arrays with Many Repeated Entries <->
LinkedList Write a Program to reverse the Linked List. (Both Iterative and recursive) <->
LinkedList Reverse a Linked List in group of Given Size. [Very Imp] https://leetcode.com/problems/reverse-nodes-in-k-group/
LinkedList Write a program to Detect loop in a linked list. <->
LinkedList Write a program to Delete loop in a linked list. <->
LinkedList Find the starting point of the loop.  <->
LinkedList Remove Duplicates in a sorted Linked List.
LinkedList Remove Duplicates from Sorted List II
LinkedList Remove Duplicates in a Un-sorted Linked List.
LinkedList Write a Program to Move the last element to Front in a Linked List. <->
LinkedList Add “1” to a number represented as a Linked List. <->
LinkedList Add two numbers represented by linked lists. <->
LinkedList Intersection of two Sorted Linked List. <->
LinkedList Intersection Point of two Linked Lists. <->
LinkedList Merge Sort For Linked lists.[Very Important] <->
LinkedList Quicksort for Linked Lists.[Very Important] <->
LinkedList Find the middle Element of a linked list. <->
LinkedList Check if a linked list is a circular linked list. <->
LinkedList Split a Circular linked list into two halves. <->
LinkedList Write a Program to check whether the Singly Linked list is a palindrome or not. <->
LinkedList Deletion from a Circular Linked List. <->
LinkedList Reverse a Doubly Linked list. <->
LinkedList Find pairs with a given sum in a DLL. <->
LinkedList Count triplets in a sorted DLL whose sum is equal to given value “X”. <->
LinkedList Sort a “k”sorted Doubly Linked list.[Very IMP] <->
LinkedList Rotate DoublyLinked list by N nodes. <->
LinkedList Rotate a Doubly Linked list in group of Given Size.[Very IMP] <->
LinkedList Can we reverse a linked list in less than O(n) ? <->
LinkedList Why Quicksort is preferred for. Arrays and Merge Sort for LinkedLists ? <->
LinkedList Flatten a Linked List <->
LinkedList Sort a LL of 0's, 1's and 2's <->
LinkedList Clone a linked list with next and random pointer <->
LinkedList Merge K sorted Linked list <->
LinkedList Multiply 2 no. represented by LL <->
LinkedList Delete nodes which have a greater value on right side <->
LinkedList Segregate even and odd nodes in a Linked List <->
LinkedList Program for n’th node from the end of a Linked List <->
LinkedList Find the first non-repeating character from a stream of characters <->
Binary Trees level order traversal <->
Binary Trees Reverse Level Order traversal <->
Binary Trees Height of a tree <->
Binary Trees Diameter of a tree <->
Binary Trees Mirror of a tree <->
Binary Trees Inorder Traversal of a tree both using recursion and Iteration <->
Binary Trees Preorder Traversal of a tree both using recursion and Iteration <->
Binary Trees Postorder Traversal of a tree both using recursion and Iteration <->
Binary Trees Left View of a tree <->
Binary Trees Right View of Tree https://leetcode.com/problems/binary-tree-right-side-view/
Binary Trees Top View of a tree https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/
Binary Trees Bottom View of a tree <->
Binary Trees Zig-Zag traversal of a binary tree https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/
Binary Trees Check if a tree is balanced or not <->
Binary Trees Diagnol Traversal of a Binary tree https://www.youtube.com/watch?v=e9ZGxH1y_PE
Binary Trees Boundary traversal of a Binary tree https://www.youtube.com/watch?v=0ca1nvR0be4
Binary Trees Construct Binary Tree from String with Bracket Representation <->
Binary Trees Convert Binary tree into Doubly Linked List <->
Binary Trees Convert Binary tree into Sum tree <->
Binary Trees Construct Binary tree from Inorder and preorder traversal <->
Binary Trees Find minimum swaps required to convert a Binary tree into BST <->
Binary Trees Check if Binary tree is Sum tree or not <->
Binary Trees Check if all leaf nodes are at same level or not <->
Binary Trees Check if a Binary Tree contains duplicate subtrees of size 2 or more [ IMP ] <->
Binary Trees Check if 2 trees are mirror or not <->
Binary Trees Sum of Nodes on the Longest path from root to leaf node <->
Binary Trees Check if given graph is tree or not. [ IMP ] <->
Binary Trees Find Largest subtree sum in a tree <->
Binary Trees Maximum Sum of nodes in Binary tree such that no two are adjacent <->
Binary Trees Print all "K" Sum paths in a Binary tree <->
Binary Trees Find LCA in a Binary tree <->
Binary Trees Find distance between 2 nodes in a Binary tree <->
Binary Trees Kth Ancestor of node in a Binary tree <->
Binary Trees Find all Duplicate subtrees in a Binary tree [ IMP ] <->
Binary Trees Tree Isomorphism Problem <->
Binary Trees Copy List with Random Pointer
Binary Search Trees Fina a value in a BST <->
Binary Search Trees Deletion of a node in a BST <->
Binary Search Trees Find min and max value in a BST <->
Binary Search Trees Find inorder successor and inorder predecessor in a BST <->
Binary Search Trees Check if a tree is a BST or not <->
Binary Search Trees Populate Inorder successor of all nodes <->
Binary Search Trees Find LCA of 2 nodes in a BST <->
Binary Search Trees Construct BST from preorder traversal <->
Binary Search Trees Convert Binary tree into BST <->
Binary Search Trees Convert a normal BST into a Balanced BST <->
Binary Search Trees Merge two BST [ V.V.V>IMP ] <->
Binary Search Trees Find Kth largest element in a BST <->
Binary Search Trees Find Kth smallest element in a BST <->
Binary Search Trees Count pairs from 2 BST whose sum is equal to given value "X" <->
Binary Search Trees Find the median of BST in O(n) time and O(1) space <->
Binary Search Trees Count BST ndoes that lie in a given range <->
Binary Search Trees Replace every element with the least greater element on its right <->
Binary Search Trees Given "n" appointments, find the conflicting appointments <->
Binary Search Trees Check preorder is valid or not <->
Binary Search Trees Check whether BST contains Dead end <->
Binary Search Trees Largest BST in a Binary Tree [ V.V.V.V.V IMP ] <->
Binary Search Trees Flatten BST to sorted list <->
Binary Search Trees Check Completeness of a Binary Tree
Binary Search Trees Non-overlapping Intervals
Binary Search Trees Largest BST in Binary Tree https://leetcode.com/problems/maximum-sum-bst-in-binary-tree/
Greedy Activity Selection Problem <->
Greedy Job SequencingProblem <->
Greedy Huffman Coding <->
Greedy Water Connection Problem <->
Greedy Fractional Knapsack Problem <->
Greedy Greedy Algorithm to find Minimum number of Coins <->
Greedy Maximum trains for which stoppage can be provided <->
Greedy Minimum Platforms Problem <->
Greedy Buy Maximum Stocks if i stocks can be bought on i-th day <->
Greedy Find the minimum and maximum amount to buy all N candies <->
Greedy Minimize Cash Flow among a given set of friends who have borrowed money from each other Optimal Account Balancing
Greedy Minimum Cost to cut a board into squares <->
Greedy Number of Islands <->
Greedy Find maximum meetings in one room https://www.lintcode.com/problem/919
Greedy Maximum product subset of an array <->
Greedy Maximize array sum after K negations <->
Greedy Maximize the sum of arr[i]*i <->
Greedy Maximum sum of absolute difference of an array <->
Greedy Maximize sum of consecutive differences in a circular array <->
Greedy Minimum sum of absolute difference of pairs of two arrays <->
Greedy Program for Shortest Job First (or SJF) CPU Scheduling <->
Greedy Program for Least Recently Used (LRU) Page Replacement algorithm <->
Greedy Smallest subset with sum greater than all other elements <->
Greedy Chocolate Distribution Problem <->
Greedy DEFKIN -Defense of a Kingdom <->
Greedy DIEHARD -DIE HARD <->
Greedy GERGOVIA -Wine trading in Gergovia <->
Greedy Picking Up Chicks <->
Greedy CHOCOLA –Chocolate <->
Greedy ARRANGE -Arranging Amplifiers <->
Greedy K Centers Problem <->
Greedy Minimum Cost of ropes <->
Greedy Find smallest number with given number of digits and sum of digits <->
Greedy Rearrange characters in a string such that no two adjacent are same <->
Greedy Find maximum sum possible equal sum of three stacks <->
Greedy Maximum Sub-String after at most K changes https://leetcode.com/problems/maximize-the-confusion-of-an-exam/
BackTracking Rat in a maze Problem <->
BackTracking Printing all solutions in N-Queen Problem <->
BackTracking Word Break Problem using Backtracking <->
BackTracking Remove Invalid Parentheses <->
BackTracking Sudoku Solver <->
BackTracking m Coloring Problem <->
BackTracking Print all palindromic partitions of a string <->
BackTracking Subset Sum Problem <->
BackTracking The Knight’s tour problem <->
BackTracking Tug of War <->
BackTracking Find shortest safe route in a path with landmines <->
BackTracking Combinational Sum <->
BackTracking Find Maximum number possible by doing at-most K swaps <->
BackTracking Print all permutations of a string <->
BackTracking Find if there is a path of more than k length from a source <->
BackTracking Longest Possible Route in a Matrix with Hurdles <->
BackTracking Print all possible paths from top left to bottom right of a mXn matrix <->
BackTracking Partition of a set intoK subsets with equal sum <->
BackTracking Find the K-th Permutation Sequence of first N natural numbers <->
Stacks & Queues Implement Stack from Scratch <->
Stacks & Queues Implement Queue from Scratch <->
Stacks & Queues Implement 2 stack in an array <->
Stacks & Queues find the middle element of a stack <->
Stacks & Queues Implement "N" stacks in an Array <->
Stacks & Queues Check the expression has valid or Balanced parenthesis or not. <->
Stacks & Queues Reverse a String using Stack <->
Stacks & Queues Design a Stack that supports getMin() in O(1) time and O(1) extra space. <->
Stacks & Queues Find the next Greater element <->
Stacks & Queues The celebrity Problem https://www.youtube.com/watch?v=CiiXBvrX-5A
Stacks & Queues Arithmetic Expression evaluation https://leetcode.com/problems/evaluate-reverse-polish-notation/
Stacks & Queues Evaluation of Postfix expression https://www.youtube.com/watch?v=422Q_yx2yA8
Stacks & Queues Implement a method to insert an element at its bottom without using any other data structure. <->
Stacks & Queues Reverse a stack using recursion <->
Stacks & Queues Sort a Stack using recursion <->
Stacks & Queues Merge Overlapping Intervals <->
Stacks & Queues Largest rectangular Area in Histogram <->
Stacks & Queues Length of the Longest Valid Substring <->
Stacks & Queues Expression contains redundant bracket or not <->
Stacks & Queues Implement Stack using Queue <->
Stacks & Queues Implement Stack using Deque <->
Stacks & Queues Stack Permutations (Check if an array is stack permutation of other) <->
Stacks & Queues Implement Queue using Stack <->
Stacks & Queues Implement "n" queue in an array <->
Stacks & Queues Implement a Circular queue <->
Stacks & Queues LRU Cache Implementationa <->
Stacks & Queues Reverse a Queue using recursion <->
Stacks & Queues Reverse the first “K” elements of a queue <->
Stacks & Queues Interleave the first half of the queue with second half <->
Stacks & Queues Find the first circular tour that visits all Petrol Pumps <->
Stacks & Queues Minimum time required to rot all oranges <->
Stacks & Queues Distance of nearest cell having 1 in a binary matrix <->
Stacks & Queues First negative integer in every window of size “k” <->
Stacks & Queues Check if all levels of two trees are anagrams or not. <->
Stacks & Queues Sum of minimum and maximum elements of all subarrays of size “k”. <->
Stacks & Queues Minimum sum of squares of character counts in a given string after removing “k” characters. <->
Stacks & Queues Queue based approach or first non-repeating character in a stream. <->
Stacks & Queues Next Smaller Element <->
Heap Implement a Maxheap/MinHeap using arrays and recursion. <->
Heap Sort an Array using heap. (HeapSort) <->
Heap Maximum of all subarrays of size k. <->
Heap “k” largest element in an array <->
Heap Kth smallest and largest element in an unsorted array <->
Heap Merge “K” sorted arrays. [ IMP ] <->
Heap Merge 2 Binary Max Heaps <->
Heap Kth largest sum continuous subarrays <->
Heap Leetcode- reorganize strings <->
Heap Merge “K” Sorted Linked Lists [V.IMP] <->
Heap Smallest range in “K” Lists <->
Heap Median in a stream of Integers <->
Heap Check if a Binary Tree is Heap <->
Heap Connect “n” ropes with minimum cost <->
Heap Convert BST to Min Heap <->
Heap Convert min heap to max heap <->
Heap Rearrange characters in a string such that no two adjacent are same. <->
Heap Minimum sum of two numbers formed from digits of an array <->
Graph Create a Graph, print it <->
Graph Implement BFS algorithm <->
Graph Implement DFS Algo <->
Graph Detect Cycle in Directed Graph using BFS/DFS Algo <->
Graph Detect Cycle in UnDirected Graph using BFS/DFS Algo <->
Graph Search in a Maze <->
Graph Minimum Step by Knight <->
Graph flood fill algo <->
Graph Clone a graph <->
Graph Making wired Connections <->
Graph word Ladder <->
Graph Dijkstra algo <->
Graph Implement Topological Sort <->
Graph Minimum time taken by each job to be completed given by a Directed Acyclic Graph <->
Graph Find whether it is possible to finish all tasks or not from given dependencies <->
Graph Find the no. of Isalnds <->
Graph Given a sorted Dictionary of an Alien Language, find order of characters <->
Graph Implement Kruksal’sAlgorithm <->
Graph Implement Prim’s Algorithm <->
Graph Total no. of Spanning tree in a graph <->
Graph Implement Bellman Ford Algorithm <->
Graph Implement Floyd warshallAlgorithm <->
Graph Travelling Salesman Problem <->
Graph Graph ColouringProblem <->
Graph Snake and Ladders Problem <->
Graph Find bridge in a graph <->
Graph Count Strongly connected Components(Kosaraju Algo) <->
Graph Check whether a graph is Bipartite or Not <->
Graph Detect Negative cycle in a graph <->
Graph Longest path in a Directed Acyclic Graph <->
Graph Journey to the Moon <->
Graph Cheapest Flights Within K Stops <->
Graph Oliver and the Game <->
Graph Water Jug problem using BFS <->
Graph Water Jug problem using BFS <->
Graph Find if there is a path of more thank length from a source <->
Graph M-ColouringProblem <->
Graph Minimum edges to reverse o make path from source to destination <->
Graph Paths to travel each nodes using each edge(Seven Bridges) <->
Graph Vertex Cover Problem <->
Graph Chinese Postman or Route Inspection <->
Graph Number of Triangles in a Directed and Undirected Graph <->
Graph Minimise the cashflow among a given set of friends who have borrowed money from each other <->
Graph Two Clique Problem <->
Trie Construct a trie from scratch <->
Trie Find shortest unique prefix for every word in a given list <->
Trie Word Break Problem (Trie solution)
Trie Given a sequence of words, print all anagrams together <->
Trie Implement a Phone Directory <->
Trie Print unique rows in a given boolean matrix <->
Dynamic Programming Coin ChangeProblem <->
Dynamic Programming Knapsack Problem <->
Dynamic Programming Binomial CoefficientProblem <->
Dynamic Programming Permutation CoefficientProblem <->
Dynamic Programming Program for nth Catalan Number <->
Dynamic Programming Matrix Chain Multiplication  <->
Dynamic Programming Edit Distance <->
Dynamic Programming Subset Sum Problem <->
Dynamic Programming Friends Pairing Problem <->
Dynamic Programming Gold Mine Problem <->
Dynamic Programming Assembly Line SchedulingProblem <->
Dynamic Programming Painting the Fenceproblem <->
Dynamic Programming Maximize The Cut Segments <->
Dynamic Programming Longest Common Subsequence <->
Dynamic Programming Longest Repeated Subsequence <->
Dynamic Programming Longest Increasing Subsequence <->
Dynamic Programming Space Optimized Solution of LCS <->
Dynamic Programming LCS (Longest Common Subsequence) of three strings <->
Dynamic Programming Maximum Sum Increasing Subsequence <->
Dynamic Programming Count all subsequences having product less than K <->
Dynamic Programming Longest subsequence such that difference between adjacent is one <->
Dynamic Programming Maximum subsequence sum such that no three are consecutive <->
Dynamic Programming Egg Dropping Problem <->
Dynamic Programming Maximum Length Chain of Pairs <->
Dynamic Programming Maximum size square sub-matrix with all 1s <->
Dynamic Programming Maximum sum of pairs with specific difference <->
Dynamic Programming Min Cost PathProblem <->
Dynamic Programming Maximum difference of zeros and ones in binary string <->
Dynamic Programming Minimum number of jumps to reach end <->
Dynamic Programming Minimum cost to fill given weight in a bag <->
Dynamic Programming Minimum removals from array to make max –min <= K <->
Dynamic Programming Longest Common Substring <->
Dynamic Programming Count number of ways to reacha given score in a game <->
Dynamic Programming Count Balanced Binary Trees of Height h <->
Dynamic Programming LargestSum Contiguous Subarray [V>V>V>V IMP ] <->
Dynamic Programming Smallest sum contiguous subarray <->
Dynamic Programming Unbounded Knapsack (Repetition of items allowed) <->
Dynamic Programming Word Break Problem <->
Dynamic Programming Largest Independent Set Problem <->
Dynamic Programming Partition problem <->
Dynamic Programming Longest Palindromic Subsequence <->
Dynamic Programming Count All Palindromic Subsequence in a given String <->
Dynamic Programming Longest Palindromic Substring <->
Dynamic Programming Longest alternating subsequence <->
Dynamic Programming Weighted Job Scheduling <->
Dynamic Programming Coin game winner where every player has three choices <->
Dynamic Programming Count Derangements (Permutation such that no element appears in its original position) [ IMPORTANT ] <->
Dynamic Programming Maximum profit by buying and selling a share at most twice [ IMP ] <->
Dynamic Programming Optimal Strategy for a Game <->
Dynamic Programming Optimal Binary Search Tree <->
Dynamic Programming Palindrome PartitioningProblem <->
Dynamic Programming Word Wrap Problem <->
Dynamic Programming Mobile Numeric Keypad Problem [ IMP ] <->
Dynamic Programming Boolean Parenthesization Problem <->
Dynamic Programming Largest rectangular sub-matrix whose sum is 0 <->
Dynamic Programming Largest area rectangular sub-matrix with equal number of 1’s and 0’s [ IMP ] <->
Dynamic Programming Maximum sum rectangle in a 2D matrix <->
Dynamic Programming Maximum profit by buying and selling a share at most k times <->
Dynamic Programming Find if a string is interleaved of two other strings <->
Dynamic Programming Maximum Length of Pair Chain <->
Dynamic Programming Partition Equal Subset Sum https://leetcode.com/submissions/detail/561942165/
Dynamic Programming Target Sum
Bit Manipulation Count set bits in an integer <->
Bit Manipulation Find the two non-repeating elements in an array of repeating elements <->
Bit Manipulation Count number of bits to be flipped to convert A to B <->
Bit Manipulation Count total set bits in all numbers from 1 to n <->
Bit Manipulation Program to find whether a no is power of two <->
Bit Manipulation Find position of the only set bit <->
Bit Manipulation Copy set bits in a range <->
Bit Manipulation Divide two integers without using multiplication, division and mod operator <->
Bit Manipulation Calculate square of a number without using *, / and pow() <->
Bit Manipulation Power Set <->
Moore voting algorithm Majority Element https://www.youtube.com/watch?v=n5QY3x_GNDg
Moore voting algorithm Majority Element II https://www.youtube.com/watch?v=yDbkQd9t2ig
30 Days Interview Preparation Plan:🎯

https://github.com/SamirPaulb/DSAlgo/tree/main/30-Days-SDE-Sheet-Practice

Originally the below sheet was prepared by Raj Vikramaditya A.K.A Striver. I have documented this sheet here in markdown.

Day1: (Arrays)

  1. Sort an array of 0’s 1’s 2’s without using extra space or sorting algo

  2. Repeat and Missing Number

  3. Merge two sorted Arrays without extra space

  4. Kadane’s Algorithm

  5. Merge Overlapping Subintervals

  6. Find the duplicate in an array of N+1 integers.

Day2: (Arrays)

  1. Set Matrix Zeros

  2. Pascal Triangle

  3. Next Permutation

  4. Inversion of Array (Using Merge Sort)

  5. Stock Buy and Sell

  6. Ro tate Matrix

Day3: (Arrays/maths)

  1. Search in a 2D matrix

  2. Pow(X,n)

  3. Majority Element (>N/2 times)

  4. Majority Element (>N/3 times)

  5. Grid Unique Paths

  6. Reverse Pairs (Leetcode)

  7. Go through Puzzles from GFG** (Search on own)

Day4: (Hashing)

  1. 2 Sum problem

  2. 4 Sum problem

  3. Longest Consecutive Sequence

  4. Largest Subarray with 0 sum

  5. Count number of subarrays with given XOR (this clearsa lot of problems)

  6. Longest substring without repeat

Day5: (LinkedList)

  1. Reverse a LinkedList

  2. Find middle of LinkedList

  3. Merge two sorted Linked List

  4. Remove N-th node from back of LinkedList

  5. Delete a given Node when a node is given. (0(1) solution)

  6. Add two numbers as LinkedList

Day6:

  1. Find intersection point of Y LinkedList

  2. Detect a cycle in Linked List

  3. Reverse a LinkedList in groups of size k

  4. Check if a LinkedList is palindrome or not.

  5. Find the starting point of the Loop of LinkedList

  6. Flattening of a LinkedList**

  7. Rotate a LinkedList

Day7: (2-pointer)

  1. Clone a Linked List with random and next pointer

  2. 3 sum

  3. Trapping rainwater

  4. Remove Duplicate from Sorted array

  5. Max consecutive ones

Day8: (Greedy)

  1. N meeting in one room

  2. Minimum number of platforms required for a railway

  3. Job sequencing Problem

  4. Fractional Knapsack Problem

  5. Greedy algorithm to find minimum number of coins

  6. Activity Selection (it i

  7. s same as N meeting in one room)

Day9 (Recursion):

  1. Subset Sums

  2. Subset-II

  3. Combination sum-

  4. Combination sum

  5. Palindrome Partitioning

  6. K-th permutation Sequence

Day10: (Recursion and Backtracking)

  1. Print all Permutations of a string/array

  2. N queens Problem

  3. SudokuSolver

  4. M coloring Problem

  5. Rat in a Maze

6.Word Break -> print all ways

Day11 : (Binary Search)

  1. N-th root of an integer (use binary search) (square root, cube root, ..)

  2. Matrix Median

  3. Find the element that appears once in sorted array, and rest element appears twice (Binary search)

  4. Search element in a sorted and rotated array/ find pivot where it is rotated**

  5. Median of 2 sorted arrays

  6. K-th element of two sorted arrays

  7. Allocate Minimum Number of Pages

  8. Aggressive Cows

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

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

Day13: (Stack and Queue)

  1. Implement Stack Using Arrays

  2. Implement Queue Using Arrays

  3. Implement Stack using Queue (using single queue)

  4. Implement Queue using Stack (0(1) amortised method)

  5. Check for balanced parentheses

  6. Next Greater Element

  7. Sort a Stack

Day14:

  1. Next Smaller Element Similar to previous question next greater element, just do pop the greater elements out ..

  2. LRU cache (vvvv. imp)

  3. LFU Cache (Hard, can be ignored)

4.Largest rectangle in histogram (Do the one pass solution)

Two pass

One pass

  1. Sliding Window maximum video
  2. Implement Min Stack
  3. Rotten Orange (Using BFS)
  4. Stock Span Problem
  5. Find maximum of minimums of every window size 10.The Celebrity Problem

Day15: (String)

  1. Reverse Words in a String
  2. Longest Palindrome in a string
  3. Roman Number to Integer and vice versa
  4. Implement ATOI/STRSTR
  5. Longest Common Prefix
  6. Rabin Karp

Day16: (String)

  1. Prefix Function/Z-Function
  2. KMP algo / LPS(pi) array
  3. Minimum characters needed to be inserted in the beginning to make it palindromic.
  4. Check for Anagrams
  5. Count and Say
  6. Compare version numbers

Day17: (Binary Tree)

  1. Inorder Traversal (with recursion and without recursion)
  2. Preorder Traversal (with recursion and without recursion)
  3. Postorder Traversal (with recursion and without recursion)
  4. LeftView Of Binary Tree
  5. Bottom View of Binary Tree
  6. Top View of Binary Tree**

Day18: (Binary Tree)

  1. Level order Traversal / Level order traversal in spiral form
  2. Height of a Binary Tree
  3. Diameter of Binary Tree
  4. Check if Binary tree is height balanced or not
  5. LCA in Binary Tree
  6. Check if two trees are identical or not**

Day 19: (Binary Tree)

  1. Maximum path sum
  2. Construct Binary Tree from inorder and preorder
  3. Construct Binary Tree from Inorder and Postorder
  4. Symmetric Binary Tree
  5. Flatten Binary Tree to LinkedList
  6. Check if Binary Tree is mirror of itself or not

Day 20: (Binary Search Tree)

  1. Populate Next Right pointers of Tree
  2. Search given Key in BST
  3. Construct BST from given keys.
  4. Check is a BT is BST or not
  5. Find LCA of two nodes in BST
  6. Find the inorder predecessor/successor of a given Key in BST.**

Day21: (BinarySearchTree)

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

Day22: (Mixed Questions)

  1. Binary Tree to Double Linked List
  2. Find median in a stream of running integers.
  3. K-th largest element in a stream.
  4. Distinct numbers in Window.
  5. K-th largest element in an unsorted array.
  6. Flood-fill Algorithm

Day23: (Graph) Theory

  1. Clone a graph (Not that easy as it looks)
  2. DFS
  3. BFS
  4. Detect A cycle in Undirected Graph/Directed Graph
  5. Topo Sort
  6. Number of islands (Do in Grid and Graph both)
  7. Bipartite Check

Day24: (Graph) Theory

  1. SCC(using KosaRaju’s algo)
  2. Djisktra’s Algorithm
  3. Bellman Ford Algo
  4. Floyd Warshall Algorithm
  5. MST using Prim’s Algo
  6. MST using Kruskal’s Algo

Day25: (Dynamic Programming)

  1. Max Product Subarray
  2. Longest Increasing Subsequence
  3. Longest Common Subsequence
  4. 0-1 Knapsack
  5. Edit Distance
  6. Maximum sum increasing subsequence
  7. Matrix Chain Multiplication

Day26: (DP)

  1. Maximum sum path in matrix, (count paths, and similar type do, also backtrack to find the maximum path)
  2. Coin change
  3. Subset Sum
  4. Rod Cutting
  5. Egg Dropping
  6. Word Break
  7. Palindrome Partitioning (MCM Variation)
  8. Maximum profit in Job scheduling For core revision</>

Day27:

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

Day28:

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

Day29:

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

Day30:

  1. Make a note of how will your represent your projects, and prepare all questions related to tech which you have used in your projects. Prepare a note which you can say for 3-10 minutes when he asks you that say something about the project.
System Design Concepts:📚
  1. https://samirpaul.in/posts/system-design-course

  2. https://github.com/SamirPaulb/system-design

  3. https://www.freecodecamp.org/news/systems-design-for-interviews

  4. https://www.geeksforgeeks.org/system-design-tutorial

  5. https://youtube.com/playlist?list=PLMCXHnjXnTnvo6alSjVkgxV-VH6EPyvoX