Dynamic Programming – Maximum Product Cutting Problem.
Objective: Given a rope of length n meters, write an algorithm to cut the rope in such a way that product of different lengths of rope is maximum. At least one cut has to...
Category: Software Development Engineer (SDE)
Dynamic Programming – Minimum Numbers are Required Whose Square Sum is Equal To a Given Number
Objective: Given a number, Write an algorithm to find out minimum numbers required whose square is equal to the number. This question has been asked in the Google Interview for Software Developer position.This is...
Dynamic Programming – Longest Common Substring
Objective: Given two string sequences write an algorithm to find, find the length of longest substring present in both of them. This problem has been asked in Amazon and Microsoft interviews. Approach to solve...
Dynamic Programming – Longest Common Subsequence
Objective: Given two string sequences, write an algorithm to find the length of longest subsequence present in both of them. These kind of dynamic programming questions are very famous in the interviews like Amazon,...
Dynamic Programming – Rod Cutting Problem
Objective: Given a rod of length n inches and a table of prices pi, i=1,2,…,n, write an algorithm to find the maximum revenue rn obtainable by cutting up the rod and selling the pieces....
Dynamic Programming – Coin Change Problem
Objective: Given a set of coins and amount, Write an algorithm to find out how many ways we can make the change of the amount using the coins given. This is another problem in...
Dynamic Programming – Minimum Cost Path Problem
Objective: Given a 2D-matrix where each cell has a cost to travel. You have to write an algorithm to find a path from left-top corner to bottom-right corner with minimum travel cost. You can...
All N Length Strings from Given String of Length K
Objective: Print All N Length Strings from Given String of Length K where characters can appear multiple time. Example: String k = “ALGO” N=2 Result: AA LA GA OA AL LL GL OL AG...
Generate Well Ordered Passwords of a Given Length K
Objective: Generate Well Ordered Passwords of a Given Length K. Well ordered means that digits should be in increasing order in every generated password. Example: K = 7 1234567 1234568 1234569 1234578 1234579 1234589...
Print All N Length Strings from Given Number K
Objective: Given Number K, Print all the strings of N length. Example: N = 2, K = 3 [1, 1] [2, 1] [3, 1] [1, 2] [2, 2] [3, 2] [1, 3] [2, 3]...
Print All Possible Subsets with Sum equal to a given Number
Objective: Given a number N, Write an algorithm to print all possible subsets with Sum equal to N This question has been asked in the Google for software engineer position. Example: N=4 1111 112...
Dynamic Programming – Maximum size square sub-matrix with all 1s
Objective: Given a matrix of 0’s and 1’s (binary matrix). Find out Maximum size square sub-matrix with all 1’s. Example: Approach: Base Cases: If only one row is given then cells with 1’s will...
The Word Break Problem
Objective : Given an string and a dictionary of words, find out if the input string can be broken into a space-separated sequence of one or more dictionary words. Example: dictionary = [“I” ,...
Dynamic Programming – Longest Increasing Subsequence
Objective: The longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence in a given array such that all elements of the subsequence are sorted in increasing order. OR Given...
Backtracking – Knight’s Tour Problem
Objective : A knight’s tour is a sequence of moves of a knight on a chessboard such that the knight visits every square only once. If the knight ends on a square that is...