Interview Question
Country: United States
an here is a more detailed explanation of the algorithm
www dot drdobbs dot com slash database slash 184410529
Thanks for the info and sorry for the duplicate question. This was just a question I got in an interview recently and didn't get right.
Original anonymous: I may be misunderstanding your answer, but if I'm not, it doesn't seem correct to me. It's not enough to take the max blocks because they must be aligned in a particular way to count...
Ok, I guess this approach makes sense to me. You just haven't described it fully. You haven't described the algorithm for finding a max block once you've prepared the temporary array you showed. WIth 3 5 3, it's easy to see the max block is 9, but how about for something you can't just eyeball, like 0 3 5 2 1 3 4 3 2? I'm not saying it can't be done -- there's a straightforward n^2 algo, and better algos are probably possible.
#include <stdio.h>
#include <malloc.h>
using namespace std;
int min(int a, int b, int c)
{
return ((a<b)?((a<c)?a:c):((b<c)?b:c));
}
int Largest_matrix(int input[5][5], int temp[5][5], int size)
{
int i, j;
int max=0; // this variable stores maximum value
/* last row values storing in temp*/
for(i=size-1, j=0; j < size; j++ )
temp[i][j] = input[i][j] ^ 1;
/* last column values storing in temp */
for(i = 0, j=size-1; i< size-1; i++)
temp[i][j] = input[i][j] ^ 1;
for( i = size-2; i>=0 ; i-- )
for(j=size-2; j>=0 ; j-- )
{
if( (input[i][j] == 0) && !( input[i][j] ^ input[i+1][j] ^ input[i+1][j+1] ^ input[i][j+1] ) )
{
temp[i][j] = 1 + min(temp[i+1][j], temp[i+1][j+1],temp[i][j+1]);
if(max < temp[i][j] )
max = temp[i][j];
}
else
{
temp[i][j] = input[i][j]^1;
}
}
return max;
}
int main()
{
int input[5][5] = {
{1,0,0,0,1},
{0,0,0,0,0},
{0,0,0,0,0},
{1,0,1,0,0},
{0,0,0,0,0}
};
int temp[5][5] = {0};
printf("\n largest matrix is %d\n", Largest_matrix(input, temp, 5));
for(int i=0; i<5; i++ )
{
for(int j=0; j<5; j++ )
printf("%d, ", temp[i][j] );
printf("\n");
}
}
// you have a 2D array of 1's and 0's
// find the size of largest block of 0's
// Code not compiled
#include <stdio.h>
int ReturnLargestBlockSize(int [][] array)
{
//create a 2-D array which contains the entry of the size of the block which would get created with that position
//as the bottom right position
// as you iterate over the array , check for 1s and 0s
// in case you find a zero in position array[i,j] , check its neighbors: i-1, j-1 ; i-1,j ; i,j-1
// if all are 0, then update the new postion's value as shown in the code
// the assumuption here is a block is either a square or a rectangle
//I hope this is the correct way of determining the rows and columns
int rows = sizeof(array)/sizeof(array[0]);
int cols = sizeof(array[0])/sizeof(array[0][0]);
int i, j =0;
int max = 0;
//create the array and initialise it to zero
int[rows][cols] blockSizeArray ;
for(i=0; i< rows; i++)
{
for (j=0;j<cols;j++)
{
blockSizeArray[i][j] = 0;
}
}
for(i=0; i<rows;i++)
{
for(j=0;j<cols;j++)
{
if(array[i][j] == 0)
{
if((i == 0) || (j ==0))
{
blockSizeArray[i][j] = 1;
}
else
{
int diag = array[i-1][j-1];
int top = array[i-1][j];
int left = array[i][j-1];
//if all the neighbors are 0, update the blockSize
if(!(diag & top & left)
{
blockSizeArray[i][j] = blockSizeArray[i-1][j] + blockSizeArray[i][j-1] + blockSizeArray[i-1][j-1];
if(blockSizeArray[i][j] > max)
{
max = blockSizeArray[i][j];
}
}
}
}
}
}
return max;
}
void main()
{
int[][] array = {{1, 0, 1, 0, 0, 0, 1, 0 },
{1, 0, 0, 0, 0, 0, 1, 1 },
{1, 1, 1, 0, 0, 0, 1, 1 }}
int value = ReturnLargestBlockSize(array);
}
go from left to right on colums, keeping a vector with max number of 0 for each row.
- Anonymous April 25, 2012at each step find the max block from this vector.
values of the vector:
col:
1 2 3 4 5 6 7 8
vector(as column)
0, 1, 0, 1, 2, 3, 0, 1
0, 1, 2, 3, 4, 5, 0, 0
0, 0, 0, 1, 2, 3, 0, 0
for each vector fin max block:
eg for the vector
3
5
3
maxblock = 9