Adobe Interview Question Software Engineer / Developers
Try this.............
#include <iostream.h>
void main()
{
cout<<"Hello World!"<<endl;
int node[6] = {10, 2, 1, 14, 13, 1};
int startIndx = 0;
int lastIndx = 0;
int width = 0;
int i = 0;
int cur = 0;
int curIndx = 0;
int curArea = 0;
int maxArea = 0;
int maxStart = 0;
int maxLast = 0;
while( curIndx < 6)
{
width = 0;
cur = node[curIndx];
i = startIndx = lastIndx = curIndx;
while ( (i<6) && (node[i++] >= node[curIndx]) )
{
width++;
lastIndx = i-1;
}
i = curIndx;
while( (i>=0) && (node[--i] >= node[curIndx]) )
{
width++;
startIndx = i;
}
curArea = width*node[curIndx];
cout << "CUR AREA IS : " << curArea << " for node " << cur << endl;
if (curArea >= maxArea)
{
maxArea = curArea;
maxStart = startIndx;
maxLast = lastIndx;
}
curIndx++;
}
cout << "Max Area is " << maxArea << " between Bar " << maxStart << " (Length " << node[maxStart] << ") and "
<< maxLast << " (Length " << node[maxLast] << ")" << endl;
}
BB, the complexity of the previous algorithm is O(n^2) in worst case.
I can modify the above algo and have an O(n) time and O(n) space
complexity. I cannot see how this can be O(n) time and O(1) space
because you clearly need a length n array to store the histogram
values which itself counts for O(n) space. Probably they should say no
additional non constant memory other than the given array.
There are two cases :
a) it may happen that the bar with maximum height will be the answer
or
b) small bar of same height may get combined to form a rectangle.
if i am not wrong you should be able to in one pass.
O(n)
let me know if u find anything wrong
int array[] = {10, 2, 1, 14, 13, 1};
For such inputs:
Step-1:
loop for each element of array
find max hignht and min hignht from the arrar.
Step-2:
as given width is static for each bar of histrogram
we are assuming the width as 'n'
Step-3:
area = ((max * width) > (min * (width * (sizeof(array)/sizeof(int))))) ? ((max * width)) : ((min * (width * (sizeof(array)/sizeof(int)))));
assuming that each unit of histogram is 1 if used or 0 if not used, then this can be represented by a two dimensional array of 0s and 1s
so the problem is to find biggest rectangle will all 1s
the levenstein distance algo an be used to find the biggest square where each indexa[i,j] represents the number of entries before itself including itself will make a square
while calculating distance matrix keep track of largest value found so far and its index
once done say if d[i,j] represents the max value, check d[i+k,j] for equal value as to d[i,j] consecutively where k varies from 1 to n-i-1 so if d[i,j] =4 and d[i+1,j]=4 but d[i+2.j]=0 then longest is 5, 4 ending at d[i+1,j]
this will give biggst rectangle horizontally
similarly
longest vertical rectangle can be found
max od vertical and horizontal is the biggest rectangle
int largestArea(int arr[], int len)
{
int area[len]; //initialize it to 0
int n, i, t;
stack<int> St; //include stack for using this #include<stack>
bool done;
for (i=0; i<len; i++)
{
while (!St.empty())
{
if(arr[i] <= arr[St.top()])
{
St.pop();
}
else
break;
}
if(St.empty())
t = -1;
else
t = St.top();
//Calculating Li
area[i] = i - t - 1;
St.push(i);
}
//clearing stack for finding Ri
while (!St.empty())
St.pop();
for (i=len-1; i>=0; i--)
{
while (!St.empty())
{
if(arr[i] <= arr[St.top()])
{
St.pop();
}
else
break;
}
if(St.empty())
t = len;
else
t = St.top();
//calculating Ri, after this step area[i] = Li + Ri
area[i] += t - i -1;
St.push(i);
}
int max = 0;
//Calculating Area[i] and find max Area
for (i=0; i<len; i++)
{
area[i] = arr[i] * (area[i] + 1);
if (area[i] > max)
max = area[i];
}
return max;
}
can i sort 2,1,4 and make 1,2,4 and then find max rect?
- xyZ January 16, 2009