## Dynamic Programming Interview Questions

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

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

- 4of 4 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 .

- 0of 2 votes
How to design a multi key hash map ( key count can be dynamic. if there are two keys , initiallly which can be used to find the value , keys can be increased to three as well ex: consider school structure. Intially , consider , student id is key , later , should be searchable even with key name , later with grade.

- 1of 3 votes
Design a telephone directory for large ppl (he gave example like design for India). fields will be , first name , last name , number . this should be searchable with first name , last name , number as welll.

later added more complexity like do the same for organisation where even it contains designations. so this should be searchable with designations.

- -1of 9 votes
Find minimum number of steps to reach the end of array from start (array value shows how much you can move).

- 0of 0 votes
Coin Change Problem

-----------------------------

Given an unlimited supply of coins of denominations C1, C2, ..., CN we wish to make change for a value V. Give an algorithm for producing change with minimum number of coins.

You have to print the denominations selected.

- 1of 1 vote
Given a binary matrix of 0 and 1. Find the longest sequence of 1's either row wise or column wise.

For example

0 0 0 0 0 0

0 1 1 1 0 0

0 0 0 1 0 0

It should return 1 1 1

- 2of 2 votes
give me the code for :

Given a string say "I am a human being" the output should reverse all letters of each word but not the whole string as such.

Eg: O/p should be "I ma a namuh gnieb"

I somewhat wrote the code, but i was asked what if there are extra spaces etc.

(i am able to write the code sitting at my desktop at one short but there front of interviewer i am struggling. Need to build up my confidence)

let me know the best and optimised way of writing this code.

Also i suggest people to aviod using inbuilt functions as much as possible

My Answer is as below in perl`#i want the reverse of the letters of all words in a string #eg Input is "I am a human being" then o/p shud be "I ma a namuh gnieb" $str="I am a human being"; @arr=split(' ',$str); print @arr; for($i=@arr-1;$i>=0;$i--) { $_=@arr[$i]; ####intead of above for loop if we use foreach(@arr) then it will reverse the whole string @word=split('',$_); { foreach $n (@word) { unshift(@final,$n); } } } print "\n @final \n";`