## student student Interview Question for Students Students

• 0

Country: India

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

This is the problem of largest area histogram. Compute sum of rows by iterative deepening (row-wise), and for every 1-D array generated get largest area histogram for it.
Finally return the maximum.
----------------------------------------------------------
Program to find largest area of histogram.

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

----------------------------------------------------

Program to get 1-D array by summing each row every time.
---------------------------------------------------------

``````#define ROW 10
#define COL 10

int find_max_matrix(int A[ROW][COL])
{
int i, j;
int max, cur_max;
cur_max = 0;

//Calculate Auxilary matrix
for (i=1; i<ROW; i++)
for(j=0; j<COL; j++)
{
if(A[i][j] == 1)
A[i][j] = A[i-1][j] + 1;
}

//Calculate maximum area in S for each row
for (i=0; i<ROW; i++)
{
max = largestArea(A[i], COL);
if (max > cur_max)
cur_max = max;
}

//Regenerate Oriignal matrix
for (i=ROW-1; i>0; i--)
for(j=0; j<COL; j++)
{
if(A[i][j])
A[i][j] = A[i][j] - A[i-1][j];
}

return cur_max;
}``````

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

i have also tried it by creating histogram. but after creating the histogram i am not able to calculate the max area. by using stack it seems some difficult to me. so i m giving my code. can you please correct it. there is something wrong which i m not able to found.

//calculating maximum area from histogram
int area=0;
int maxarea=0;
int col=0;

for(i=0; i<m; i++)
{
for( j=0; j<n-1; j++)
{ //if(B[i][j]==0)
// area=area;
if(B[i][j]>=B[i][j+1])
{
col=col+1;
area=col*B[i][j+1];
}
if(B[i][j]==0)
{}
else
area=col*B[i][j+1];
if(maxarea<area)
maxarea=area;

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

@sneha: I think your logic is not correct. This will work only of the matrix has one row only.
If matrix has more than 1 ro, it will fail.

Check my code.

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

@nitingupta180: Nice & optimal solution.

The algorithm for largestArea() could be made a little more faster, if you see that you only need the first loop (for computing L). That loop can be modified like so: whenever you pop an element from the stack you update the result with the rectangle corresponding to that element (you know where it starts and you know that it ends here at i). You also need to take care of elements not popped at the end of the loop.

However, I think that the solution that computes both L and R is easier to understand.

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

Ohh good, looks like CC has added code editor out of the box. This is very good, now code actually looks like a code.

Thanks Mrs Gayle.

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

Is this O(N^3) time ? (assumin matrix is N by N)

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

No, it is O(N^2) because the largestArea() function runs in O(N) time. This is because if you count the total operations done in the most inner loop "while (!St.empty())" you'll see it is O(N) (you can't pop more than N elements).

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

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

Can be done in O(n2)
Here is the alog:
a[n][n]
O/p: updating 4 points of a rectangle (A, B, C, D)

1. Start from a and find out first 1 in the array
A = step1 output
2. Loop starts from step 1 element (i, j)
{ a. another loop to get 1 in the same colomn (starting from end towards j) }, if no 1 exists in the current col, then increment A colomn number and start from begenning.
{ b. B = stepa output
{ c. From B start another loop to get corresponding right edge by getting extreme in the same row, if no 1 found decrement B row number and start from step a
{ d. C = output of stepc }
{ e. start a loop at C , to find top point in the same col }, if not found decrement C and start from step c }
{ d. if D and A are on the same col, break all loops (A, B, C, D is the output)
{ If ( D and A are not in the same col, then get tow pointer from A and D and find out common element where both have 1, we can search until we reach the B, if not found rectangle doesnt exists with the given data, other wise return A, B , C and D }

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

Consider this matrix
0 1 1 0 0
0 0 0 1 1
0 1 0 1 1
0 1 1 1 0
0 1 1 1 0
1 0 1 1 0

At every row i will do a[i] && a[i+i]
Which will give me if i am able to form any new rectangles
Simultaneously i will maintain a max heap of rectangles
Rectangle = corner1, corner2, area.
Optional step
I will remove a rectangle if it is evident there can be no more 1's added to it and it is not the Max area rectangle.
I will then do a a[i] && a[i-1] and see if the any previous rectangles can be increased in size.
If so i will do so.
In the end i will output the max from heap.

here's how it will go

Just showing this for explanation i am not changing the array or taking extra array.
0 1 1 0 0
0 0 0 2 2
0 0 0 2 2
0 6 6 6 0
0 6 6/8 6/8 0
0 0 8 8 0

List of Rectangles
1 corner1,corner2 size=2
3 corner1,corner2 size=4
6 corner1,corner2 size=6
8 corner1,corner2 size=4
Max Size = 6

Complexity -- I am only scanning the array once. But each time i may have to look at all the previous rectangles which may be.

O( rows * (number of rectangles) )

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

It looks like a nice idea. But can you please elaborate ur explanation by giving some pseudocode.

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

use a new matrix sum[row][column] which represents the sum of left 1s and top 1s
say
1,1,0,1,0
0,1,1,1,0
1,1,1,0,1
1,0,1,1,0
you'll have a new matrix sum={1,1} sum={2,1}, etc
so you can check from bottom right to top left of this matrix to get the each rectangle's area, and each element will be visited once, which has time complexity O(row*column).

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

can someone plz give me O(N log^3( N)) solution for this problem

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

change all 0 to a negetive infinite and then maximum sum algo for 2D

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

Why do we need to change 0s to negative infinite value. We can find the maximum sum for the given array itself..

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

Oh....Ok...Got it !!!Kandane's Algorithm requires it

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

How to apply kandane's algo for 2d array

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

I think this question is to fine the max rectangle with all 1's and not the max sum.

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.