## Google Interview Question for SDE-3s

Country: United States
Interview Type: Written Test

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

Union find and dfs

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

Since there's a constraint that all points in a cluster has to be within 5 units, that means they have to fit in a 5x5 square.
Then the problem is finding the square that contains the most points.

``````public void FindMaxClusters(int[,] plot, int clusterSize){
int xMax = plot.GetLength(0);
int yMax = plot.GetLength(1);

int maxPoints = 0;
// loop through the plot and all possible squares
for(int i=clusterSize -1; i<xMax; I++){
for(int j=clusterSize -1; j<yMax; j++){
// get number of points in this square
// or we can return a list of points instead of an int
int numberOfPoints = GetNumberOfPoints(I -clusterSize -1, I, j - clusterSize - 1, j);
if(numberOfPoints > maxPoints)
maxPoints = numberOfPoints;
}
}
}``````

If the points are very sparse, and we know the location of each point, then we can only check the areas around each point.

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

1) Sort array by x coordinate. First, merge all the points in sequential order as long as diff x < 5. compare i th with i+1th, it is sorted. If not then start a new cluster from the next element.

2) Now you have clusters that satisfy the first condition.

3) Now for every cluster sort by Y coordinate, and do the step 1 for Y co-ordinate. Split the cluster if necessary along y.

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

``````1) Sort array by x coordinate. First, merge all the points in sequential order as long as diff x < 5. compare i th with i+1th, it is sorted. If not then start a new cluster from the next element.

2) Now you have clusters that satisfy the first condition.

3) Now for every cluster sort by Y coordinate, and do the step 1 for Y co-ordinate. Split the cluster if necessary along y.``````

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

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

1) Sort array by x coordinate. First, merge all the points in sequential order as long as diff x < 5. compare i th with i+1th, it is sorted. If not then start a new cluster from the next element.

2) Now you have clusters that satisfy the first condition.

3) Now for every cluster sort by Y coordinate, and do the step 1 for Y co-ordinate. Split the cluster if necessary along y.

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.