## Oracle Interview Question for Software Engineer / Developers

• 1
of 1 vote

Country: United States

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

This is the classical unbounded knapsack problem.

O(N^2) time O(N) space.

``````int knapsack(int length, const vector<int>& V, const vector<int>& L)
{
vector<int> M(length+1,0);
for(int len=1; len<=length; len++) {
for(int j=0; j<L.size(); j++) {
if( L[j] <= len )
M[len] = max(M[len], M[len-L[j]] + V[j]);
}
}
return M[length];
}``````

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

array v is the values of rods with length as index i.e. v is the value of rod of length 2.
b is the array of max benefit of rod of length as index. b 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 will be 0 as there is no value for no rod. b is v as we can not have any more combinations.

``````public int getMaxBenifit(int n) {
int sum = 0;
int val = 0;
b = 0;
b = v;
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;
}
}``````

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

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;

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];
}``````

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

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

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

both works.

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

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;

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

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

Your solution wouldn't work if N is greater than the size of V[]. E.g., when the total length of the steel rod is 100.

``int max =  V[i];   // this is invalid when N is greater than the size of V[]``

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.