## Dynamic Programming Interview Questions

- 0of 0 votes
Problem:

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。。。

- 0of 0 votes
Find max sum of sub array.

- 0of 0 votes
Merge the overlapping intervals.

- 0of 0 votes
Find max sum of subarray

- 0of 0 votes
Find 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.

- 0of 0 votes
A mission-critical production system has n stages that have to be performed sequentially; stage

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

- 0of 0 votes
Q 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.

- 2of 2 votes
Given a sorted array with "n" elements, distributed them into "k" nearly equally weighing buckets.

Space is not constraint.

Ex: [1,3,6,9,10]

bucket size: 3

output:[10],[9,1],[3,6]

- 0of 0 votes
Given 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.

1. There exists only one subset like that

2. All number in arr are positive

- 1of 1 vote
Given 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.

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?

- 2of 2 votes
Given 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.

e.g.

4 5 6

1 2 3

0 1 2

Answer: 8 (4+1+0+1+2)

- 0of 0 votes
Given an integer array A of size N. Find the number of increasing sub-sequences of this array with length >= 1 and GCD = 1.

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

- 0of 0 votes
Imput Output

81 --> 9^2 --> 1 (as its only 9)

82 --> 9^2 + 1^2 --> 2 (as 9 & 1)

6 ->> 2^2 + 1^2 + 1^2 --> 3 (as 3 elements 9, 1 & 1)

SO how can we solve this question

- 0of 0 votes
Given 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.

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.

- 0of 0 votes
There 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.

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

- 0of 0 votes
Minimum number of moves to collect all the objects and reach the given point in a NxM matrix

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

- 0of 0 votes
Given a matrix of n*n. Each cell contain 0, 1, -1.

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.

- 2of 2 votes
Find 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.

Eg: if n = 5, such numbers are 39518, 15951, etc.

- 0of 0 votes
There 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.

Assume that the routes are bi-directional.

- 0of 0 votes
Given a 5 x 5 Grid comprising of tiles numbered from 1 to 25 and a set of 5 start-end point pairs.

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

- 0of 2 votes
Design 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.

- 4of 4 votes
Given a number "n", find the least number of perfect square numbers sum needed to get "n"

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)

- 3of 3 votes
Find longest substring with "m" unique characters in a given string.

input: aabacbeabbed

output:

4 (aaba) for 2 unique characters

6 (aabacb) for 3 unique characters

- 5of 5 votes
you have given array of Size N and two numbers M, K. K is size of subarray and M is count of subarray.

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

- 1of 1 vote
You have 81 balls. 80 balls have the same weight. 1 ball is the lightest one. What would be the minimum possible way to find the lightest ball ?

(Use Dynamic Programming)

- 8of 8 votes
Given a string (1-d array) , find if there is any sub-sequence that repeats itself.

Here, sub-sequence can be a non-contiguous pattern, with the same relative order.

Eg:

1. abab <------yes, ab is repeated

2. abba <---- No, a and b follow different order

3. acbdaghfb <-------- yes there is a followed by b at two places

4. abcdacb <----- yes a followed by b twice

The above should be applicable to ANY TWO (or every two) characters in the string and optimum over time.

In the sense, it should be checked for every pair of characters in the string.

- 0of 0 votes
Lets assume I have a paper in the size of 8" by 11". How would I go about designing an algorithm that optimally fit smaller cards onto the paper.

Now I don't have the actual card dimensions but for this example lets assume the smaller cards are 3" by 4", 7" by 2" and 5" by 3".

- 2of 2 votes
The stepping number:

A number is called as a stepping number if the adjacent digits are having a difference of 1. For eg. 8,343,545 are stepping numbers. While 890, 098 are not. The difference between a ‘9’ and ‘0’ should not be considered as 1.

Given start number(s) and an end number(e) your function should list out all the stepping numbers in the range including both the numbers s & e.

- 0of 0 votes
Given an array[0, n-1], each number of the array is positive int. Your task is adding the operators,"+","*", "(",")" (add, multiply, parenthesis) to maximize the result . The position in the array is Fixed.

For example, "2,1,1,2", you can get (2+1)*(2+1)=9.

Follow up, if the number may be negative , how to solve it ?

- -1of 1 vote
Design a system like friend's functionality in facebook. should have all features of facebook's friends functionality. like for each person , he can have any number of friends , he will get suggestions for new firends , showing common friends if we visits any other profile . algo should be scalable , robust .