Oracle Interview Question
Software Engineer / DevelopersCountry: United States
array v is the values of rods with length as index i.e. v[2] is the value of rod of length 2.
b is the array of max benefit of rod of length as index. b[2] is the maximum benifit we can get from rod of length 2.
// int[] v = {1,5,8,9}; // Array of values for each size
// int[] b = new int[val.length];
b[0] will be 0 as there is no value for no rod. b[1] is v[1] as we can not have any more combinations.
public int getMaxBenifit(int n) {
int sum = 0;
int val = 0;
b[0] = 0;
b[1] = v[1];
for(int k = 2; k<n; k++)
{
for(int i = i; i <= k ; i++) {
val = v[i] + b[k-i];
if(val > sum)
sum = val;
}
b[k] = sum;
}
}
space complexity = O ( N )
running complexity = O ( N^2 )
public static int rod_cutting(int V[], int N){
int B[] = new int[N+1];
B[0] = 0;
for(int i = 1; i <= N ; i++){
int max = V[i];
for(int j = 1; j < i; j++){
int current = V[j] + B[i-j];
max = Math.max(max,current);
}
B[i] = max;
}
return B[N];
}
Instead of the line
int current = V[j] + B[i-j];
shouldn't we use
int current = B[j] + B[i-j];
This way you get the maximum also for length j?
Here is an example with Memorization:
public static void main(String [] args)
{
int V [] = {0,1,5,8,9,10,17,17,20,24,30};
for(int i = 0; i < 10; i++){
rod_cutting(V,i);
}
}
public static void rod_cutting(int V[], int N){
int B[] = new int[N+1];
String path []= new String[N+1];
B[0] = 0;
for(int i = 1; i <= N ; i++){
int max = V[i];
path[i] = i + "ps ($" +V[i] +")";
for(int j = 1; j < i; j++){
int current = V[j] + B[i-j];
if(current > max){
max = current;
path[i] = j + "ps ($"+V[j]+") + " + (i-j) + "ps ($"+(B[i-j])+")";
}
}
B[i] = max;
}
System.out.println(path[N] + " = $" + B[N]);
}
Output:
null = $0
1ps ($1) = $1
2ps ($5) = $5
3ps ($8) = $8
2ps ($5) + 2ps ($5) = $10
2ps ($5) + 3ps ($8) = $13
6ps ($17) = $17
1ps ($1) + 6ps ($17) = $18
2ps ($5) + 6ps ($17) = $22
3ps ($8) + 6ps ($17) = $25
This is the classical unbounded knapsack problem.
O(N^2) time O(N) space.
- mombasa February 16, 2014