Dynamic Programming Interview Questions
- 0of 0 votes
AnswersCode an algorithm for a game consisting of two players. The input is a positive integer x. Each round, a player deducts a perfect square from the number. The player can choose any perfect square as long as it is less than or equal to the current number and greater than 0. The current player wins if the number becomes 0 after his deduction.
- Thomas June 19, 2019 in United States| Report Duplicate | Flag | PURGE
Salesforce SDE-2 Dynamic Programming - 0of 0 votes
AnswersGiven two strings, A and B, of equal length, find whether it is possible to cut both strings at a common point such that the first part of A and the second part of B form a palindrome.
- nemishsangani96 March 23, 2019 in India
Extension1. How would you change your solution if the strings could be cut at any point (not just a common point)?
Extension2. Multiple cuts in the strings (substrings to form a palindrome)? Form a palindrome using a substring from both strings. What is its time complexity?| Report Duplicate | Flag | PURGE
Algorithm Coding Computer Science Data Structures Dynamic Programming String Manipulation - 9of 9 votes
Answersprint hockey stick number in pascal triangle where row of triangle can be upto 30000 and length of stick can be upto 100.
- Randhir September 09, 2018 in India| Report Duplicate | Flag | PURGE
Wissen Technology Software Developer Coding Data Structures Dynamic Programming Java - 0of 0 votes
AnswersGiven a wall, which is made up of two types of bricks (Porus / opaque ). Porus bricks allow water pass through them. Opaque won't. Find whether water reaches to ground, if there is any rainfall.
- gopi.komanduri June 11, 2018 in India for Office
Water can flow from top to bottom, diagonally, horizontally as well. Only flowing from bottom to top is not possible.| Report Duplicate | Flag | PURGE
Microsoft SDE-3 Algorithm Arrays Brain Storming Coding Data Structures Dynamic Programming Problem Solving Programming Skills - 0of 0 votes
AnswersThe wildcard regex can include the characters * and + .
- alex May 17, 2018 in United States
‘+’ – matches any single character or empty character!
‘*’ – Matches any sequence of characters (including the empty sequence) For example,
Text = "baaabab":
regex = "ba*a++", output : true
regex = "ba*a+", output : true
regex = "a*ab", output : false
//empty string
Text=""
Regex= "+" , output : true| Report Duplicate | Flag | PURGE
Google Software Engineer Dynamic Programming - 0of 0 votes
AnswersYou are given a set of N horizontal lines which are connected by equal number of vertical lines to form squares of size 1x1. Now some segments are removed. You need to count the number of squares of all sizes (1x1, 2x2, ..., NxN) with all sides present.
- imunique August 30, 2017 in India
Image : https://he-s3.s3.amazonaws.com/media/uploads/1ce3516.png
In the above example you see four horizontal and vertical lines and few missing segments. Now you need to count the number of squares of all sizes with all sides.
Input :
First line is a positive integer N, number of horizontal and vertical lines.
Second line is positive integer M, number of segments removed.
Then there are m lines, each containing V,i,j or H,i,j where i and j are positive integers. H,i,j indicates a horizontal missing segment in the ith horizontal line between the jth and (j+1)th point on the line. V,i,j represents a gap in ith vertical line between the jth and (j+1)th point on the line.
Output :
Is the total number of squares in the figure with all sides along the remaining lines in the figure.
Sample Input :
4
4
H,2,1
H,3,1
V,2,2
V,2,3
Output :
5
Explanation : Here in this figure we have 4 squares of size 1x1 and 1 square of size 3x3, hence total is 5.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm Data Structures Dynamic Programming Online Test Problem Solving - 0of 0 votes
AnswerProblem:
- yangsuli August 13, 2017
Given 100 stones, two players alternate to take stones out. One can take any number from 1 to 15; however, one cannot take any number that was already taken. If in the end of the game, there is k stones left, but 1 - k have all been previously taken, one can take k stones. The one who takes the last stone wins. How can the first player always win?
My Idea
Use recursion (or dynamic programming). Base case 1, where player 1 has a winning strategy.
Reducing: for n stones left, if palyer 1 takes m1 stones, he has to ensure that for all options player 2 has (m2), he has a winning strategy. Thus the problem is reduced to (n - m1 - m2).
Follow Up Question:
If one uses DP, the potential number of tables to be filled is large (2^15), since the available options left depend on the history, which has 2^15 possibilities.
How can you optimize?
I don't have a great answer to the follow up question。。。| Report Duplicate | Flag | PURGE
Huawei Software Engineer Dynamic Programming - 0of 0 votes
AnswersFind max sum of sub array.
- purva7 July 24, 2017 in United States| Report Duplicate | Flag | PURGE
GE (General Electric) Software Developer Dynamic Programming - 0of 0 votes
AnswersMerge the overlapping intervals.
- purva7 July 24, 2017 in United States| Report Duplicate | Flag | PURGE
Expedia Software Developer Dynamic Programming - 1of 1 vote
AnswersFind max sum of subarray
- purva7 July 24, 2017 in United States| Report Duplicate | Flag | PURGE
Expedia Software Developer Dynamic Programming - 9of 9 votes
AnswersFind the number of ways you can have breakfast in 'n' days, given Bread-butter can be eaten every day, Pizza can be eaten every alternate day and Burger can be eaten every two days.
- gopalakshintala June 19, 2017 in India| Report Duplicate | Flag | PURGE
Microsoft Applications Developer Dynamic Programming - 0of 0 votes
AnswersA mission-critical production system has n stages that have to be performed sequentially; stage
- tanvirmahmud201505039 June 08, 2017 in India
i is performed by machine Mi. Each machine Mi has a probability ri of functioning reliably and
a probability 1 − ri of failing (and the failures are independent). Therefore, if we implement
each stage with a single machine, the probability that the whole system works is r1 · r2 · · · rn.
To improve this probability we add redundancy, by having mi copies of the machine Mi that
performs stage i. The probability that all mi copies fail simultaneously is only (1 − ri)mi, so the
probability that stage i is completed correctly is 1 − (1 − ri)mi and the probability that the whole
system works is Qni=1(1 − (1 − ri)mi). Each machine Mi has a cost ci, and there is a total budget
B to buy machines. (Assume that B and ci are positive integers.)
Given the probabilities r1, . . . , rn, the costs c1, . . . , cn, and the budget B, find the redundancies
m1, . . . , mn that are within the available budget and that maximize the probability that the
system works correctly| Report Duplicate | Flag | PURGE
Accountant Dynamic Programming - 0of 0 votes
AnswersQ 2. You are given a chess game board of size NxN. You have find out positions(i,j), where you can place N queens so that, none of the queens can kill each other without making their first move.
- sonesh April 28, 2017 in United States| Report Duplicate | Flag | PURGE
Hitachi Data Systems Software Engineer / Developer Algorithm Coding Dynamic Programming Matrix - 2of 2 votes
AnswersGiven a sorted array with "n" elements, distributed them into "k" nearly equally weighing buckets.
- reddy88 April 02, 2017 in United States
Space is not constraint.
Ex: [1,3,6,9,10]
bucket size: 3
output:[10],[9,1],[3,6]| Report Duplicate | Flag | PURGE
Amazon SDE-2 Dynamic Programming - 1of 1 vote
AnswersGiven an array arr and a number n, you have to find whether there exist a subset in arr whose sum is n. You have to print length of the subset.
- mohit February 17, 2017 in India
1. There exists only one subset like that
2. All number in arr are positive| Report Duplicate | Flag | PURGE
Amazon SDE1 Dynamic Programming - 2of 2 votes
AnswersGiven N stacks, each stack contains Si elements, find the maximum sum of the M numbers in the N stacks. To get the number of the stack, only supporting get the top number. For example, S=[1,200,1,2,3], if you want to get the number 200, you need choose 3,2,1 first.
- jeffrey November 28, 2016 in United States
EX:
S1=[1,1,100,3]
S2=[2000,2,3,1]
S3=[10,1,4]
the maximum sum of the 3 numbers in the above stacks is 3+100+3=107.
Any better solution for this problem?| Report Duplicate | Flag | PURGE
Google Software Engineer Dynamic Programming - 2of 2 votes
AnswersGiven a matrix of positive integers, you have to reach from the top left corner to the bottom right in minimum cost. You can only go one square right, down or diagonally right-down. Cost is the sum of squares you've covered. Return the minimum cost.
- mrityunjay21 July 26, 2016 in India for Payments
e.g.
4 5 6
1 2 3
0 1 2
Answer: 8 (4+1+0+1+2)| Report Duplicate | Flag | PURGE
Amazon SDE-2 Dynamic Programming - 0of 0 votes
AnswersGiven an integer array A of size N. Find the number of increasing sub-sequences of this array with length >= 1 and GCD = 1.
- abhibhagia June 26, 2016 in India
A sub-sequence of an array is obtained by deleting some (or none) elements and maintaining the relative order of the rest of the elements.
Example:-
[1] = 1
[1,2] = 2
[1,2,3] = 5| Report Duplicate | Flag | PURGE
ThoughtWorks Senior Software Development Engineer Dynamic Programming - 0of 0 votes
AnswersGiven N balloons, if you burst ith balloon you get Ai−1∗Ai+1 coins and then (i-1)th and (i+1)th balloons become adjacent. Find maximum number of coins you can gather.
- pbox May 14, 2016 in India
If you have single balloon then you will get value written on it.
Example
if you have 4 balloons and coins associated for them are....
1 2 3 4 then you will get 20 maximum.| Report Duplicate | Flag | PURGE
AMD Developer Program Engineer Dynamic Programming - 0of 0 votes
AnswersThere is a garden of strawberry plants represented by a 2D, square array.Each plant represents an element in the matrix ie it has a number of strawberries. If a plant doesnt have strawberries it is denoted by 0. If 0 is encountered you cannot travel through that path.
- topCoder September 27, 2015 in United States
You can start from any cell along the left border of this ground (i.e the matrix) and travel until it finally stops at one cell in the right border, and you can only move to up/down/right. You can only visit each cell once. Calculate the maximum number of berries is obtained.
Backtracking using Dynamic programming is one of the methods i have thought of.
Also there some special conditions:
a.Even in the left border and right border, we can go up and down.
b. When we are at the top cell of one column, we can still go up, which demands us to
pay all current strawberries , then we will be teleported to the bottom cell of this column and vice
versa.
Input: user enters dimensions of ground ie size of matrix and the matrix itself
Output: is the maximum number of strawberries collected without encountering 0; in case we do we display 0.
Till now i have managed to find the largest value in the first column of the matrix but i am facing difficulty in testing the neighbours of that cell.
Also i am not able to store the position of the cell which i started from or even mark it.
Input
4 4
-1 4 5 1
2 -1 2 4
3 3 -1 3
4 2 1 2
output
23
Input
4 4
-1 4 5 1
2 -1 2 4
3 3 -1 -1
4 2 1 2
output
22| Report Duplicate | Flag | PURGE
Walmart Labs Algorithm C++ Coding Dynamic Programming - 0of 0 votes
AnswerMinimum number of moves to collect all the objects and reach the given point in a NxM matrix
- po55ible August 16, 2015 in United States
:- There is a maze of size n*n. Tom is sitting at (0,0). Jerry is sitting in another cell (the position of Jerry is input). Then there are k pieces of cheese placed in k different cells (k <= 10). Some cells are blocked while some are not. Tom can move to 4 cells at any point of time (left, right, up, down one position). Tom has to collect all the pieces of cheese and then reach to Jerry’s cell. You need to print the minimum no. of steps required to do so.| Report Duplicate | Flag | PURGE
Dynamic Programming - 0of 0 votes
AnswersGiven a matrix of n*n. Each cell contain 0, 1, -1.
- ritwik_pandey August 09, 2015 in India
0 denotes there is no diamond but there is a path.
1 denotes there is diamond at that location with a path
-1 denotes that the path is blocked.
Now you have start from 0,0 and reach to last cell & then return back to 0,0 collecting maximum no of diamonds.
While going to last cell you can move only right and down.
While returning back you can move only left and up.| Report Duplicate | Flag | PURGE
SumoLogic SDE-3 Dynamic Programming - 2of 2 votes
AnswersFind how many numbers of length n are there such that each number is at least 4 smaller/greater than the number before and after it.
- coolProgrammer August 02, 2015 in United States
Eg: if n = 5, such numbers are 39518, 15951, etc.| Report Duplicate | Flag | PURGE
Google Software Developer Dynamic Programming - 0of 0 votes
AnswersThere are buses taking various routes and each route has some stops. Given a matrix of stops and distances (distance between two stops for connected stops), find all cluster of stops of any size with all stops in a cluster fully connected and are at a distance not greater than D.
- emptycup July 06, 2015 in India
Assume that the routes are bi-directional.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm Dynamic Programming - 0of 0 votes
AnswersGiven a 5 x 5 Grid comprising of tiles numbered from 1 to 25 and a set of 5 start-end point pairs.
- ranjankumar.jsr0 June 27, 2015 in United States
For each pair,find a path from the start point to the end point.
The paths should meet the below conditions:
a) Only Horizontal and Vertical moves allowed.
b) No two paths should overlap.
c) Paths should cover the entire grid
Input:
Input consist of 5 lines.
Each line contains two space-separated integers,Starting and Ending point.
Output:
Print 5 lines. Each line consisting of space-separated integers,the path for the corresponding start-end pair.
Assume that such a path Always exists.
In case of Multiple Solution,print any one of them.
Sample Input(Plaintext Link)
1 22
4 17
5 18
9 13
20 23
Sample Output(Plaintext Link)
1 6 11 16 21 22
4 3 2 7 12 17
5 10 15 14 19 18
9 8 13
20 25 24 23| Report Duplicate | Flag | PURGE
Student Dynamic Programming - 0of 2 votes
AnswersDesign an optimised algorithm to solve snakes and ladders with the least amount of roles possible under the assumption that you get whatever role you want when you role the dice.
- abc March 26, 2015 in United Kingdom for Graduate| Report Duplicate | Flag | PURGE
Google Software Engineer Dynamic Programming - 5of 5 votes
AnswersGiven a number "n", find the least number of perfect square numbers sum needed to get "n"
- tazo March 12, 2015 in United States
Example:
n=12, return 3 (4 + 4 + 4) = (2^2 + 2^2 + 2^2) NOT (3^2 + 1 + 1 + 1)
n = 6, return 3 (4 + 1 + 1) = (2^2 + 1^2 + 1^2)| Report Duplicate | Flag | PURGE
Google Dynamic Programming - 3of 3 votes
AnswersFind longest substring with "m" unique characters in a given string.
- tazo March 12, 2015 in United States
input: aabacbeabbed
output:
4 (aaba) for 2 unique characters
6 (aabacb) for 3 unique characters| Report Duplicate | Flag | PURGE
Google Dynamic Programming Problem Solving - 5of 5 votes
Answersyou have given array of Size N and two numbers M, K. K is size of subarray and M is count of subarray.
- SK January 21, 2015 in India
You have to return sum of max M subarray of size K (non-overlapping)
N = 7, M = 3 , K = 1
A={2 10 7 18 5 33 0} = 61 — subsets are: 33, 18, 10 (top M of size K)
M=2,K=2
{3,2,100,1} = 106 - subsets are: (3,2), (100,1) 2 subsets of size 2| Report Duplicate | Flag | PURGE
Directi Senior Software Development Engineer Algorithm Dynamic Programming