Directi Interview Question
Software Engineer / DevelopersTeam: Ads
Country: India
Interview Type: In-Person
It is possible in O(n), just traverse the whole matrix horizontally twise and then vertically once. We also need to add the water patches in any continous patch while traversing horizontally and vertically.
it seems like a 8connected pixals in image processing. so define to variables namely max_counter and conter. traverse every pixal and check it whether it is connected or not
it connected increase counter. compare with max_counter. thus you know how max patches in one image. do it for others also compare max_counters ..it seems lengthy
it is definitely computer vision problem(image processing) problem.the algo will require 2 passes along with 2 data structures to maintain connectivity and region info.Within 1st top down pass it will store entries of all connected areas( marked with water )encountered in left right fashion,also it will label each newly found region and store entry in 1st data structure.Later onward when if during same pass the 2 different regions are found connected then the entry will made in second data structure indicating they belongs to same region.
Intention of second pass is to connect all the regions with the help of data structures in bottom up manner. all connected regions from 2nd data structure can be assigned same label.At the same time we can calculate number of involved pixels(grid blocks )to calculate area of region.Then region with largest area can be found
I wud sit with a gun and shoot d Interviewer if he dares to ask this question to a fresh candidate.I will drill so many holes in his body and then frame a question in his own words to find out the number of holes that are oozing blood and the patches that are plain.I wud let him decide whetherhe wants to choose 0 or 1 for a hole.ask him to map it and then talk to me..
int maxSizeRectangle(int a[][100], int m, int n) // O(n3)
{
int max = 0;
int x[n];
int c ;
// Calculate the prefix sum along columns.
for(int i = 1; i < m; i++)
{
for(int j = 0; j < n; j++)
{
a[i][j] += a[i-1][j];
}
}
// The actual solution. O(n3)
for(int i = 0; i < m; i++)
{
for(int j = -1; j < i; j++)
{
c = 1;
for(int k = 0; k < n; k++)
{
if(j >= 0)
x[k] = a[i][k] - a[j][k];
else
x[k] = a[i][k];
if(k != 0)
{
if(x[k] == x[k-1])
c++;
else
c = 1;
// if(c == x[k] && x[k] == (i - j) && c > max)
if(x[k] == (i - j) && c * x[k] > max)
{
max = c * x[k];
}
}
}
}
}
return max;
}
We need to do BFS for finding the continuous patch of Water....At the end we need to see which connected component has maximum value by adding up all the 1's encountered...O(m+n) is the running time...
- Anonymous September 14, 2011