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

- code reviewer May 30, 2019 | Flag Reply
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.

- Anonymous May 31, 2019 | Flag Reply
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.

- Minhaz May 31, 2019 | Flag Reply
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.

- Minhaz May 31, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry about multiple posts!

- nooooob May 31, 2019 | Flag
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.

- Minhaz May 31, 2019 | 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