## 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 - 8of 8 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

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.