Adobe Interview Question Software Engineer / Developers
Are you sure your Algo would work.I'm nearly 99% sure that it wont work. The problem can be solved using dynamic programming.
sort all the boxes as per length and then its simply find the Length of Longest increasing subsequence.
int stacking(vector<vector<int> > V){
sort(V.begin(),V.end());
vector<int> best(V.size(),1);int ans=1;
for(int i=0;i<V.size();i++){
for(int j=0;j<i;j++){
if(V[j]<V[i])
best[i] = max(best[i],best[j]+1);
}
ans = max(ans,best[i]);
}
return ans;
}
Chenna: your algo has bad complexity but works.
Madhav: your algo fails 100% cause a box of dimensions 2,3,4 won't fit in 8,2,3 but volume of the first one is smaller than the second one
dude check before you post. As per my algo 2,3,4 wont fit in 8,2,3 and I'm not sorting as per the volumes dude!
sorry dude.I made a small mistake in code.Instead of writing V[j]<V[i] I should have written V[i][0]>V[j][0] &&
V[i][1]>V[j][1] && V[i][2]>V[j][2]. I'm sure it will work now
hey, thought I'd try your algo, since you claim mine doesn't work (logically it should, I'll try to code when I have time)
What is exactly the input for your function? if I input the following is it valid?
int main(){
vector<int> k; vector<vector<int> >arr;
int i1=2,i2=3,i3=4;
k.push_back(i1);k.push_back(i2);k.push_back(i3);arr.push_back(k);k.clear();
i1=8,i2=2,i3=4;
k.push_back(i1);k.push_back(i2);k.push_back(i3);arr.push_back(k);k.clear();
cout<<stacking(arr);
}
I tried your code as below, and answer i got is
MaxLength:: 14 // answer should be 1 , I also tried other ones that actually fit, am I doing anything wrong?
#include <vector>
#include <iostream> // std::cout
using namespace std;
int stacking(vector<vector<int> > V){
sort(V.begin(),V.end());
vector<int> best(V.size(),1);
cout<<"Given Array:: ";
for(int ii=0;ii<V.size();++ii)
cout<<"["<<V[ii][0]<<","<<V[ii][1]<<","<<V[ii][2]<<"], ";
cout<<endl;
int ans=1;
for(int i=0;i<V.size();i++){
for(int j=0;j<i;j++){
if(V[i][0]>V[j][0] &&V[i][1]>V[j][1] && V[i][2]>V[j][2])
best[i] = max(best[i],best[j]+1);
}
ans = max(ans,best[i]);
}
return ans;
}
int main()
{
vector<int> k;
vector<vector<int> >arr;
int i1=2,i2=3,i3=4; k.clear();k.push_back(i1);k.push_back(i2);k.push_back(i3);arr.push_back(k);
i1=4,i2=3,i3=2;
k.clear();k.push_back(i1);k.push_back(i2);k.push_back(i3);arr.push_back(k);
i1=3,i2=2,i3=4;
k.clear();k.push_back(i1);k.push_back(i2);k.push_back(i3);arr.push_back(k);
cout<<"MaxLength::"<<stacking(arr);
}
//DOESNT WORK :(
I got the output to be 1 ! for the given input no box can fit in another [2,3,4], [3,2,4], [4,3,2]. For this the answer must be 1 isnt it?
madhav,
>> sort all the boxes as per length and then its simply find the Length of Longest increasing subsequence.
I think we should sort such that, all length, breadth, and height are in sorted order.
For Example, for the below input the answer is 3 if we sort based on length alone.
444, 568, 567, 788
But the answer is 4
just try out with this solution..
if lenght ,breadth and height is given as 4,6,8 then make a three digit number out of it i.e 468.
do this with all the dimensions given and put that three digit number into an array.
sort this array using radix sort starting from the left most digit of that number and proceeding to the rightmost number.
after getting the sorted array traverse from largest to smallest thereby checking if any of the dimensions of lower one is not equal to its own corresponding dimension. if they are found to be equal just leave that block and proceed to next block down the array and keep on adding them and finally one would get largest subset required.
It's a DAG graph(if box 'a' fit box 'b' there is an edge from 'a' to 'b') , so we need to find the longest path in this graph.
You are write but that would take O(n^2) extra space. The dynamic programming algo takes O(n) extra space only
You are write but that would take O(n^2) extra space. The dynamic programming algo takes O(n) extra space only
My approach:
>>
>> Constructing trees...
>> Box 1 dim: 7,8,9 Make it as root1. The root also has a counter
>> associated with it. Now count1=1.
>> Then Box 2 dim: 5,6,8 < 7,8,9. Make it as a left child of root1 and
>> count1=2.
>> Box 3 dim: 5,8,7 doesn't fit in any and hence make it a tree by itself
>> i.e root2 its count2=1.
>> Box 4 dim: 4,4,4 it can be made as the left child of box 2 as well as
>> Box 3.
>> count1=3, count2=2.
>> Print the reverse inorder traversal of the highest counter valued
>> tree.
>>
>> Please correct me if I'm wrong.
similar to longest increasing subsequence problem but here ordered not by the order of elements in sequence but ordered by the volume instead.
1. sort all boxes in decreasing order in volume.
v1 > v2 > v3 > .......... vn
2. now create subproblem h[j] = max no of boxes that i can fit into one another s.t. jth box goes the most inside. thus,
h(j) = max(h(i)) where i<j and width(i) > width(j);depth(i)>depth(j);height(i)>height(j) (strictly)
3. find max(h(j)) for j in [1...n]
pseudocode:
box[1...n]: array containing boxes
h[1...n] : array to store subprob solns
h[1] = 1;
qsort(box,1,n)
for(j=2;j<=n;j++)
{
h[j]=0;
for(i=j-1;i>=1;i--)
{
max = 0;
if(box[i].w > box[j].w && .... && ... && h(i) > max)
max = h(i);
}
}
for all j in 1 to n find max(h(j)) which is the soln
Given n cuboids, compute volume for each => O(n)
- chennavarri November 03, 2010sort all these cuboids based on volume => O(nlogn)
create an array to store count for each cuboid, count[n]
start from the lowest volume and check for the dimension conditions x<x',y<y',z<z'
if satisfies then increment count for that
=> O(n(n-1)/2)
Now the count array contains sum of values from 1:k, if k is the maximal path,
take max(count) O(n)
and solve k(k+1)/2 = maxVal
which gives k
total complexity:
O( n + nlogn + n(n-1)/2 + n) => O(n^2)