Directi Interview Question for Software Engineer / Developers


Team: Ads
Country: India
Interview Type: In-Person




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

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 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

do bfs on matrix???

- Anonymous October 02, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

flood fill

- Anonymous September 12, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Maze Problem

- Learner September 13, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Anonymous September 14, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

why horizontally twice....?

- ptntialunrlsd February 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- rc October 08, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- aj October 11, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- unknown October 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- jackass October 26, 2011 | 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