Interview Question


Country: United States




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

go from left to right on colums, keeping a vector with max number of 0 for each row.
at 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

- Anonymous April 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

i forgot, finding the max block should be the answer to
question id=9911848

- Anonymous April 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

an here is a more detailed explanation of the algorithm

www dot drdobbs dot com slash database slash 184410529

- Anonymous April 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Ash April 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- eugene.yarovoi April 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- eugene.yarovoi April 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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");
	}

}

- FIGHTER May 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Think as a histogram

- Arya June 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

// 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);
}

- bkp April 26, 2012 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More