Data Structures and 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
• LinkedList
• 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.

• 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.📚

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.💻

View this repository with improved user experience▶️https://samirpaul.in/DSAlgo🚀

Things you can contribute to:

• Update the existing solution 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.

---

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	<->
Array	Find the maximum and minimum element in an array	<->
Array	Find the “Kth” max and min element of an array	<->
Array	Given an array which consists of only 0, 1 and 2. Sort the array without using any sorting algo	<->
Array	Move all the negative elements to one side of the array	<->
Array	Find the Union and Intersection of the two sorted arrays.	<->
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	<->
Array	Merge 2 sorted arrays without using Extra space.	<->
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 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🎯

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://github.com/SamirPaulb/system-design-primer

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

3. https://github.com/shashank88/system_design