Google Interview Question for SDE1s


Country: United States




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

This is a famous swipe line algorithm used to solve this problem.
First let's have a data structure that stores segments [le, ri] and can answer these questions:
1) query1(X) : how many segments are there with le > X.
2) query2(X) : how many segments are there with ri < X.
3) total number of segments in data structure.
4) Add segment
5) Delete segment
Then let's create a vector of events:

struct Event {
  int x;
  bool rectangle_start;  // True if it is the start of rectangle, false otherwise.
  int y1, y2;
};

After we sort this array we can add events one by one and using the data structure described before we can update global answer if that is the beginning of the rectangle:

ret += DS.total_number_of_segments() - DS.query1(y2) - DS.query2(y1);
   DS.add_segment(current_event);

If it is the end of the rectangle we remove the segment:

DS.remove_segment(current_segment);

Total complexity is O(nlogn) if we use set for DS.

- Alex February 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

You need to project them on axis X and form massiv on begins end ends of their sides. Then you do the same on Y axis. After that we consiver all rectangles that fits int some interval of another interval. And check wther those rects are intersect.

- glebstepanov1992 January 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Did I understand you right?
By projecting all edges of rectangle to X & Y-axis, you are getting (X1, X2) and (Y1, Y2) of rect_1.
Similarly for all rectangles.
<X1, X2>, <X3, X4> ... <X2n, X2n+1>
<Y1, Y2>, <Y3, Y4> ... <Y2n, Y2n+1>

Now, sort all (X1, X2) and (Y1, Y2) based on 2nd element of pair.
if there is overlap of any two interval in <X1, X2> <Xk, Xk+1>, then check corresponding <Y1, Y2> <Yk, Yk+1>. if that too overlap then this rectangle do overlap.
M i rite?
If not, then please explain your algo a little bit more.

Also, does it also consider the case mentioned by "srikantaggarwal".
What if rectangles are not parallel to axis?

- SK January 28, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yep,you are right. but if they are not parallel to axis, i have no idea((

- glebstepanov1992 January 28, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Instead of finding which intersect, find the conditions where they dont intersect. There are total 4 conditions which tell if two rectangles intersect or not. For all the rectangles that pass those 4 conditions, means they intersect.

- Anonymous January 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yep,but your solution needs O(n^2) where n is a number of rectangler. My solution, which uses sorting do detect intervals intersection needs O(NlogN).

- glebstepanov1992 January 28, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It is not nlogn. Worst case complexity is O(n2) if all rectangles have same projections on X axis and non-intersecting projections on Y axis.

- yo yo honey singh November 11, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

New free career cup android app

store/apps/details?id=com.andersoncouncil.careercup.ui

- AppBuilder January 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can we assume that the edges of the rectangle are parallel to the X and Y axis?

- srikantaggarwal January 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I have a solution O(n^2) though for a larger number of rectangles it may not work.

simply add a boundary check whether a particular point falls in that boundary.

boolean boundary(Rec r,point p)
{
	if(p.x>=r.p1.x &&p.x<=r.p2.x&&p.y<=r.p1.y&&p.y>=r.p3.y)return true;
	return false;
}

now for each rectangle save them in a list while saving just check whether any of them falls within the boundary of any other in the already existing list.
the boundary check is an O(1) operation and for each element t we are checking (t-1) elements. O(n^2) operations.

- hirajhil January 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;
A working O(2Nlog2N + Nm) solution, where N is the number of rectangles and m is the average number of rectangles whose x projection intersect. The solution uses two sorted sets: one of all x endpoints and another of all y endpoints. An endpoint is rectangle start and a rectangle end on a particular axis.

public class IntersectingRectangles {

	static class Endpoint implements Comparable<Endpoint> {
		Rect rect;
		boolean isStart;
		double val;
		Endpoint(Rect r, boolean start, double v){ 
			rect = r;
			isStart = start;
			val = v;
		}
		public int compareTo(Endpoint other){
			int ret;
			double diff= this.val - other.val;
			if(diff == 0) ret = 0;
			else ret = (diff>0)?1:-1;

			if(ret == 0){
				ret = this.isStart?1:-1;
				if(this.rect != other.rect){
					ret = -ret;
				}
			}
			return ret;
		}

	}

	static class Rect {

		Rect (double minX, double minY, double maxX, double maxY){
			xStart = new Endpoint(this, true, minX);
			xEnd = new Endpoint(this, false, maxX);
			yStart = new Endpoint(this, true, minY);
			yEnd = new Endpoint(this, false, maxY);

		}
		Endpoint xStart;
		Endpoint xEnd;
		Endpoint yStart;
		Endpoint yEnd;
	}




	public static int getNumIntersecting(Rect [] rects){
		TreeSet<Endpoint> sortedByX = new TreeSet<>();
		for(Rect r: rects){
			sortedByX.add(r.xStart);
			sortedByX.add(r.xEnd);
		}

		TreeSet<Endpoint> sortedByY = new TreeSet<>();
		int ret =0;
		for(Endpoint ep: sortedByX){
			Rect r  = ep.rect;
			if(ep.isStart){
				ret+= countIntersections(sortedByY.subSet(r.yStart, false,r.yEnd, false),
						r.yStart.val, r.yEnd.val);
				sortedByY.add(r.yStart); sortedByY.add(r.yEnd);
			} else {
				sortedByY.remove(r.yStart); sortedByY.remove(r.yEnd);
			}
		}
		return ret>0?ret+1:0; // count the first square with whom an intersection is found
	}

	private static int countIntersections(Set<Endpoint> eps, double minY, double maxY){
		HashSet<Rect> rects = new HashSet<>();
		for(Endpoint ep : eps){
			rects.add(ep.rect);
		}
		return rects.size();
	}

	public static void main(String[] args) {
		Rect [] rects = {
			
			new Rect(1, 1, 3, 3),
			new Rect(2, 5, 4, 6),
			new Rect(2.5,2,3.5,5.5)
		};
		System.out.println(getNumIntersecting(rects));
		
	}
	

}

- konst May 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is very similar to Alex's solution. And the complexity could be further improved if we use Alex's mysterious DS...

- konst May 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It's a good solution, however one scenario is missing here:
you won't count rectangles "nested by Y". Here is an example.
if we have rectangles {0, 0, 3, 5}, {1, 1, 4, 4} and {2, 2, 5, 3} this algo reports 0. But there are 3 pairs of intersected rectangles.
Alex's solution here in the thread covers this case: we subtract all the rectangle which are completely below the current one and completely above the current one from total number of rectangles that have intersection with the current one by X.

- Alex M. April 20, 2017 | Flag


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