## Directi Interview Question for Software Engineer / Developers

• 0

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
4
of 4 vote

This can be solved using dynamic programming, you can look at the solution to this problem in this very good video tutorial

Comment hidden because of low score. Click to expand.
1
of 1 vote

done using dynamic programming

``````//it contains max price possible for each length
int maxPrice[N+1]={0};
int i=1;
while(i<=N)
{
for(int j=0;j<i;j++)
{
if(maxPrice[i]<(maxPrice[j]+price[i-j]))
{
maxPrice[i]=maxPrice[j]+price[i-j];
}
}
i++;
}
return maxPrice[N];``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

This can be solved using dynamic programming, you can look at the solution to this problem in this very good video tutorial

Comment hidden because of low score. Click to expand.
0
of 0 vote

See Cormen , Page - 360...by Dynamic Programming

Comment hidden because of low score. Click to expand.
0
of 0 vote

clrs pd problem rod cut

Comment hidden because of low score. Click to expand.
0
of 0 vote

Can't it be done using all pairs shortest paths problem in graph?
Initially take all edges to be of length 1 as in the given example.

While relaxing, take the price of that length rather than just length and do it. Somone please say if I'm wrong

Comment hidden because of low score. Click to expand.
0
of 0 vote

Can't it be done using all pairs shortest paths problem in graph?
Initially take all edges to be of length 1 as in the given example.

Instead of taking min(D[i,j],D[i,k]+D[k,j]), take min(PRICE(D[i,j]),PRICE(D[i,k]+D[k,j])), take the price of that length rather than just length and do it. Somone please say if I'm wrong

Comment hidden because of low score. Click to expand.
0
of 0 vote

Isn't this an oral question.

You divide the rod in

``(int) N / 6``

pieces of 6. Then for the remaining

``N % 6``

pieces devide as follows

``````1 -- 1
2 -- 2
3 -- 3
4 -- 2, 2
5 -- 2, 3``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

it is essentially equivalent of 0/1 knapsack problem
where
lengths array coreespond to weight
value correspond to value/profit
input lenght of rod correspond to the capacity of knapsack

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include<stdio.h>
int max(int a,int b){
return a>b?a:b;
}
int main(){
int length[]={0,1,2,3,4,5,6,7,8};
int price[]={0,1,5,8,9,10,17,17,20};
int n=sizeof(price)/sizeof(*price);
int N=12,i,L;
int cut[N+1];
for(i=0;i<=N;i++)
cut[i]=price*i;
for(i=2;i<=N;i++){
for(L=2;L<=n && L<=i;L++){
if(L==i)
cut[i]=max(cut[i],price[L]);
else
cut[i]=max(cut[i],cut[L]+cut[i-L]);
}
}
printf("%d\n",cut[N]);
return 0;
}``````

Comment hidden because of low score. Click to expand.
-1
of 3 vote

calculate price/length: for the given example it is..
1, 2.5, 2.67 , 2.25, 2, 2.42, 2.125, 2.5

here the length 3 have maximum price.. cut the piece of length N into pieces of length 3..
Benefit = number_of_pieces * 2.67

in addition there may be piece of length 2 or 1 give rise to additional cost of 2.5 or 1..

Comment hidden because of low score. Click to expand.
0

You can have cuts which should be of integer length like 1,2 ,3 etc you cannot have fractional cuts

Comment hidden because of low score. Click to expand.
0

it is not a fractional cut.. at the end i have pieces of length 3 and a piece of length either 2 or 1 or 0(if the N is divisble by 3)

Comment hidden because of low score. Click to expand.
0

you do need a recursive algm. try your soln on N=4

Comment hidden because of low score. Click to expand.
0

u calculated it wrong for length = 6

Comment hidden because of low score. Click to expand.
0

The price for a given length is given. You can't divide the price again by the length of rod. In the given example, rod of length 3 costs 9, not something u calculated

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.