Directi Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
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
#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[1]*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;
}
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..
You can have cuts which should be of integer length like 1,2 ,3 etc you cannot have fractional cuts
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)
This can be solved using dynamic programming, you can look at the solution to this problem in this very good video tutorial
- Anonymous July 28, 2012youtube.com/watch?v=U-09Gs6cbsQ