I am starting with Dynamic Programming. I will try to solve 5 DP questions on daily basis.
As of now I am totally alien to DP, hence I will start from the basics and build up on that to move towards Advance DP Problems.
Anyone who wants to learn and practice Dynamic Programming is welcome to solve the Problems that I post in this repository.
You can create a directory of your own name in this repository and add the Problems that you have solved in the directory
You should make a README of the Problems that you had a hard time in solving, that way you can revise them later.
That's it lets try to master DP starting from the bottom.
-
Additionally I will post some aptitude questions daily, so that you get prepared for Interview aptitude Rounds. You can find the Aptitude questions from this website IndiaBix. There are lots of questions on this website.
-
To make this more exciting, You should start a timer as you start solving question. You should enter the time taken by you to solve the question in your readme. At the end of the day the person who solves most questions in Minimum time will be winner of the day!
-
If you are applying for Off-campus jobs, You can join this telegram channel which posts Software Developer Jobs daily, You should take some time daily to fill the forms for these jobs/internships
-
You can also keep track of the jobs you applied for in the readme.
-
Before we start solving DP problems, you should probably want to read what is DP and what types of Problems can be solved using DP.
Here are some good articles to get you started.
Algorithms: Greedy Algorithm Questions
- Minimize the sum of product
- Ishaan Loves Chocolates
- Smallest number
- Message Spreading
- Swap and Maximize
Aptitude: - Solve Aptitude Questions, Complete Problems on Train
Algorithms : Read - Jump Search
- Interpolation Search
- Exponential Search
- Why is Binary Search preferred over Ternary Search?
Algorithms: Greedy Algorithm Questions
- Largest number possible
- Minimum Operations
- N meetings in one room
- Maximize Toys
- Shop in Candy Store
Aptitude: - Solve Aptitude Questions, Complete Problems on Train - Data Sufficiency
- Solve Aptitude Questions, Complete Problems on Height and Distance
Algorithms : Read - Radix Sort
- Counting Sort
- Bucket Sort
- Comb Sort
Algorithms: Greedy Algorithm Questions
- Fractional Knapsack
- Largest number with given sum
- Huffman Decoding-1
- Fact Digit Sum
- Check if it is possible to survive on Island
Aptitude: - Solve Aptitude Questions, Complete Problems on Simple Interest
- Solve Aptitude Questions, Complete Problems on Simple Interest - Data Sufficiency 1
- Solve Aptitude Questions, Complete Problems on Simple Interest - Data Sufficiency 2
Algorithms : Read - Pigeonhole Sort
- Cycle Sort
- Interpolation search vs Binary search
- Stability in sorting algorithms
Algorithms: Greedy Algorithm Questions
- Smallest number with sum of digits as N and divisible by 10^N
- Huffman Decoding
- Maximum sum of increasing order elements from n arrays
- Minimum Swaps for Bracket Balancing
- Raju and coins
Aptitude: - Solve Aptitude Questions, Complete Problems on Profit and Loss
- Solve Aptitude Questions, Complete Problems on Simple Interest - Data Sufficiency 1
- Solve Aptitude Questions, Complete Problems on Simple Interest - Data Sufficiency 2
- Solve Aptitude Questions, Complete Problems on Simple Interest - Data Sufficiency 3
- Solve Aptitude Questions, Complete Problems on Simple Interest - Data Sufficiency 4
Algorithms : Read - When does the worst case of Quicksort occur?
- Lower bound for comparison based sorting algorithms
- Which sorting algorithm makes minimum number of memory writes?
- Find the Minimum length Unsorted Subarray, sorting which makes the complete array sorted
Algorithms: Greedy Algorithm Questions
- Hungry Pizza Lovers
[x] Theft at World Bank- Choose and Swap
- Largest Permutation
- Minimize the heights
Aptitude: - Solve Aptitude Questions, Complete Problems on Percentage
- Solve Aptitude Questions, Complete Problems on Calender
Algorithms : Read - Merge Sort for Linked Lists
- Sort a nearly sorted (or K sorted) array
- Iterative Quick Sort
- QuickSort on Singly Linked List
- NOTE: Before Attempting the Question read the articles. So that you can understand the theory behind the questions! Algorithms: Greedy Algorithm Questions
- Minimum Spanning Tree
- Implementing Dijkstra | Set 1 (Adjacency Matrix)
- Job Sequencing Problem
- Page Faults in LRU
- Geek collects the balls
Aptitude: - Solve Aptitude Questions, Complete Problems on Average
- Solve Aptitude Questions, Complete Problems on Average - Data Sufficiency 1
- Solve Aptitude Questions, Complete Problems on Average - Data Sufficiency 2
Algorithms : Read - Applications of Minimum Spanning Tree Problem
- Kruskal’s Minimum Spanning Tree Algorithm | Greedy Algo-2
- Graph and its representations
- Dijkstra’s shortest path algorithm | Greedy Algo-7
- NOTE: Before Attempting the Question read the articles of Day 1. So that you can understand the theory behind the questions! Algorithms: Greedy Algorithm Questions
- Coin Piles
[ ] Minimum Cost Path[ ] Min Coin[ ] Water Connection Problem- 7 Segment Display
Aptitude: - Solve Aptitude Questions, Complete Problems on Volume and Surface Area
- Solve Aptitude Questions, Complete Problems on Volume and Surface Area - Data Sufficiency 1
- Solve Aptitude Questions, Complete Problems on Volume and Surface Area - Data Sufficiency 2
- Solve Aptitude Questions, Complete Problems on Simplification
Algorithms: Greedy Algorithm Questions
- Print first n Fibonacci Numbers
- Padovan Sequence
- Count numbers containing 4
- 0 - 1 Knapsack Problem
- [Revisit the Questions that you couldn't do in one go or took lot of time]
Aptitude: - Solve Aptitude Questions, Complete Problems on Numbers - Complete pages 1-5
Algorithms: Greedy Algorithm Questions
- Maximum sum increasing subsequence
- Maximize The Cut Segments
- Count all possible paths from top left to bottom right
- Stickler Thief
- Minimum number of Coins
- [Revisit the Questions that you couldn't do in one go or took lot of time]
Aptitude: - Solve Aptitude Questions, Complete Problems on Numbers - Complete pages 6-10
- Count number of hops
- Gold Mine Problem
[ ] Shortest Common Supersequence- Nth catalan number
- Reach the Nth point
Aptitude: - Solve Aptitude Questions, Complete Problems on Numbers - Complete pages 11-15
- Longest Palindromic Subsequence
- Maximize Dot Product
- Number of Unique Paths
[ ] Reach a given score- Friends Pairing Problem
Aptitude: - Solve Aptitude Questions, Complete Problems on H.C.F and L.C.M
- Solve Aptitude Questions, Complete Problems on Surds and Indices
- Rod Cutting
- Knapsack with Duplicate Items
[ ] Palindromic patitioning- Paths to reach origin
- Count of strings that can be formed using a, b and c under given constraints
Aptitude: - Solve Aptitude Questions, Complete Problems on Chain Rule
- Solve Aptitude Questions, Complete Problems on Boats and Streams
- Solve Aptitude Questions, Complete Problems on Logarithm
- Coin Change
- Subset Sum Problem
- Subset with sum divisible by m
[ ] nCr- Perfect Sum Problem
- Divisor Game
- Best Time to Buy and Sell Stock
- Min Cost Climbing Stairs
- Is Subsequence
- Climbing Stairs Aptitude:
- Solve Aptitude Questions, Complete Problems on Stocks and Shares
- Solve Aptitude Questions, Complete Problems on True Discount
Read Articles: - Largest divisible pairs subset
- Maximum Subarray
- Range Sum Query - Immutable
[ ] House Robber- Matrix Block Sum
- Count Square Submatrices with All Ones
- Counting Bits
- Minimum Cost Tree From Leaf Values
- Stone Game
- Stone Game II
- Minimum Falling Path Sum
- Climbing Stairs
- Painting Fence Algorithm
- Repetitive Addition Of Digits
- Count even length
- Sequence of Sequence
- Longest Common Subsequence
- Longest Repeating Subsequence
- Longest Increasing Subsequence
- Maximum sum increasing subsequence
- LCS of three strings
- Maximum Sum Bitonic Subsequence
Aptitude: [ ] Solve Aptitude Questions, Complete Problems on Odd Man Out and Series
- Max length chain
- Longest subsequence-1
- Maximum sum Problem
- Largest square formed in a matrix
- Pairs with specific difference
- Minimum cost to fill given weight in a bag
- Minimum number of jumps
- Path in Matrix
- Adjacents are not allowed
- Minimum steps to minimize n as per given condition
- Edit Distance
- Minimum Time
- Longest Common Substring
- Sum of all substrings of a number
- Max Sum without Adjacents
- Reach a given score
- BBT counter
- Paths to reach origin
- Count the number of ways to tile the floor of size n x m using 1 x m size tiles
- Count all possible paths from top left to bottom right
- Number of ways
- Kadane's Algorithm
[ ] Size of array after repeated deletion of LIS- Convert to Strictly increasing array
- Ways to sum to N
- Delete without head pointer
- Finding the numbers
- Implement two stacks in an array
- Generate binary string
- Rat in a Maze Problem - I
- Group Anagrams Together
- Equal
- Binary Tree to BST
- Clone a Binary Tree
- K-Concatenation
- Ugly Numbers
- k largest elements
- Print Diagonally
- N meetings in one room
- Roads and Libraries
- Check If two Line segments Intersect
- Check Mirror in N-ary tree
- Majority Element
- Generalised Fibonacci numbers
- Find Missing And Repeating
- Job Sequencing Problem
- Next larger element
- Smallest distinct window
- Sorted matrix
- Phone directory
- First non-repeating character in a stream
- Infix to Postfix
- Largest square formed in a matrix
- Count Number of SubTrees having given Sum
- Solve the Sudoku
- Max Circular Subarray Sum
- Nth catalan number
- Set Bits
- Convert Level Order Traversal to BST
- Print adjacency list ---> using Matrix, Adjacency List and unordered set in which searching and inserting takes O(1) time.
- Graph representations using set and hash
- Find a Mother Vertex in a Graph
- Transitive closure of a Graph
- Transitive Closure of a Graph using DFS
- Find k-cores of an undirected graph
- Iterative Depth First Traversal of Graph
- Count the number of nodes at given level in a tree using BFS.
- Count all possible paths between two vertices
- Minimum initial vertices to traverse whole matrix with given conditions
- Shortest path to reach one prime to other by changing single digit at a time
- Water Jug problem using BFS
- Count number of trees in a forest
- BFS using vectors & queue as per the algorithm of CLRS
- Level of Each node in a Tree from source node (using BFS)
- Construct binary palindrome by repeated appending and trimming
- Transpose graph
- Path in a Rectangle with Circles
- Detect cycle in an undirected graph
- Detect cycle in a directed graph
- Detect a negative cycle in a Graph | (Bellman Ford)
[ ] Cycles of length n in an undirected and connected graph- Detecting negative cycle using Floyd Warshall
- Check whether a given graph is Bipartite or not
- Check if there is a cycle with odd weight sum in an undirected graph
- Check if a graphs has a cycle of odd length
- Clone a Directed Acyclic Graph
- Check loop in array according to given constraints
- Disjoint Set (Or Union-Find) | Set 1 (Detect Cycle in an Undirected Graph)
- Union-Find Algorithm | Set 2 (Union By Rank and Path Compression)
- Union-Find Algorithm | (Union By Rank and Find by Optimized Path Compression)
- Magical Indices in an array
- Topological Sorting
- All Topological Sorts of a Directed Acyclic Graph
- Kahn’s algorithm for Topological Sorting
- Maximum edges that can be added to DAG so that remains DAG
- Longest path between any pair of vertices ----> Do this for a DAG
- Longest Path in a Directed Acyclic Graph
[ ] Longest Path in a Directed Acyclic Graph | Set 2---> Do in shortest Paths- Topological Sort of a graph using departure time of vertex
- Given a sorted dictionary of an alien language, find order of characters
[x] Prim’s Minimum Spanning Tree (MST) | Greedy Algo-5---> Done in Day 6, But should be revised once again!- Applications of Minimum Spanning Tree Problem
- Prim’s MST for Adjacency List Representation | Greedy Algo-6
- Kruskal’s Minimum Spanning Tree Algorithm | Greedy Algo-2
- Boruvka’s algorithm | Greedy Algo-9
- Minimum cost to connect all cities
- Steiner Tree Problem
[x] Reverse Delete Algorithm for Minimum Spanning Tree---> More efficient approach in connectivity using articulation point- Bridge Edge in Graph
- Total number of Spanning Trees in a Graph
- Floyd Warshall
- Minimum Product Spanning Tree
- Find the element that appears once in an array where other elements occur Thrice
- Detect if two integers have opposite signs
- Add 1 to a given number
- Multiply a given Integer with 3.5
- Turn off the rightmost set bit
- Find whether a given number is a power of 4 or not
- Compute modulus division by a power-of-2-number
- Rotate bits of a number
- Find the Number Occurring Odd Number of Times
- Check for Integer Overflow
- Count set bits in an integer
- Count number of bits to be flipped to convert A to B
- Efficient way to multiply with 7
- Program to find whether a no is power of two
- Position of rightmost set bit
- Binary representation of a given number
- Find position of the only set bit
- How to swap two numbers without using a temporary variable?
- Swap two nibbles in a byte
- How to turn off a particular bit in a number?
- Russian Peasant (Multiply two numbers using bitwise operators
- Add two bit strings
- Write your own strcmp that ignores cases
- Check if two numbers are equal without using arithmetic and comparison operators
- Find XOR of two number without using XOR operator
- XOR counts of 0s and 1s in binary representation
- Calculate XOR from 1 to n.
- Equal Sum and XOR
- Swap three variables without using temporary variable
- Check if a number has bits in alternate pattern | Set 1
- XOR of two numbers after making length of their binary representations equal
- Count minimum bits to flip such that XOR of A and B equal to C
- Efficient method for 2’s complement of a binary string
- Toggle case of a string using Bitwise Operators
- Toggling k-th bit of a number
- Convert decimal fraction to binary number
- Toggle all the bits of a number except k-th bit.
- Set the rightmost unset bit
-
Convert a binary number to octal - Check in binary array the number represented by a subarray is odd or even
- Toggle the last m bits
- Numbers with alternative 1's
- Unset bits in the given range
- Find the largest number with n set and m unset bits
- Find the smallest number with n set and m unset bits
- Sum of numbers with exactly 2 bits set
- Check if binary representation of a given number and its complement are anagram
- Check a number is odd or even without modulus operator
- Bitwise recursive addition of two integers
- Print bitwise AND set of a number N
- Fast average of two numbers without division
- Maximum XOR-value of at-most k-elements from 1 to n
- Swap every two bits in bytes
- Check if a number is divisible by 8 using bitwise operators
-
Number of Reflexive Relations on a Set - For every set bit of a number toggle bits of other
- Toggle bits of a number except first and last bits
- Check if given four integers (or sides) make rectangle
- Toggle first and last bits of a number
- Toggle all even bits of a number
- Set the Left most unset bit
- Maximum XOR using K numbers from 1 to n
- Number of Steps to Reduce a Number to Zero
- XOR Operation in an Array
- Convert Binary Number in a Linked List to Integer
- Hamming Distance
- Sort Integers by The Number of 1 Bits
- Single Number
- Number Complement
- Prime Number of Set Bits in Binary Representation
- Binary Number with Alternating Bits
- Majority Element
- Find the Difference
- Missing Number
- Number of 1 Bits
[ ] Binary Watch- Convert a Number to Hexadecimal
- Power of Two
- Power of Four
- Reverse Bits
- Count Triplets That Can Form Two Arrays of Equal XOR ---> try to do in O(n^2) or O(1)
- Counting Bits
- XOR Queries of a Subarray
- Number of Good Ways to Split a String
- Pseudo-Palindromic Paths in a Binary Tree
- Letter Case Permutation
- Single Number III
- Minimum Flips to Make a OR b Equal to c
- Subsets
-
Pyramid Transition Matrix - Maximum XOR of Two Numbers in an Array
- Maximum of Absolute Value Expression
- Single Number II
- Maximum Product of Word Lengths
- Sum of Two Integers
- Total Hamming Distance
- Maximum Length of a Concatenated String with Unique Characters
-
Maximum Number of Occurrences of a Substring
- Number of Steps to Reduce a Number in Binary Representation to One
- Check If a String Contains All Binary Codes of Size K
- Bitwise AND of Numbers Range
- Repeated DNA Sequences
-
UTF-8 Validation - Bitwise ORs of Subarrays
- Integer Replacement
- Maximum Score Words Formed by Letters
- Smallest Sufficient Team
- Find a Value of a Mysterious Function Closest to Target
- Number of Ways to Wear Different Hats to Each Other
- Number of Valid Words for Each Puzzle
- Find Longest Awesome Substring
- Find if there is a path of more than k length from a source
- Tug of War
- The Knight’s tour problem | Backtracking-1
- Rat in a Maze | Backtracking-2
- N Queen Problem | Backtracking-3
- m Coloring Problem | Backtracking-5
- Hamiltonian Cycle | Backtracking-6
- Permutation of numbers such that sum of two consecutive numbers is a perfect square
- Dijkstra’s shortest path algorithm | Greedy Algo-7
- Dijkstra’s Algorithm for Adjacency List Representation | Greedy Algo-8
- Johnson’s algorithm for All-pairs shortest paths
- Shortest path with exactly k edges in a directed and weighted graph
- Dial’s Algorithm (Optimized Dijkstra for small range weights)
- Printing Paths in Dijkstra’s Shortest Path Algorithm
- Shortest Path in a weighted Graph where weight of an edge is 1 or 2
- Multistage Graph (Shortest Path)
- Shortest path in an unweighted graph
- Minimize the number of weakly connected nodes
- Betweenness Centrality (Centrality Measure)
- Comparison of Dijkstra’s and Floyd–Warshall algorithms
- Karp’s minimum mean (or average) weight cycle algorithm
- 0-1 BFS (Shortest Path in a Binary Weight Graph)
- Find minimum weight cycle in an undirected graph
- Minimum Cost Path with Left, Right, Bottom and Up moves allowed
- Minimum edges to reverse to make path from a source to a destination
- Find Shortest distance from a guard in a Bank