CODEWITHSUNDEEP
algorithm
user4333994
user4333994

Reputation: 51

Given two ranges [a,b), [c,d), check if they intersect

The Google phone interview question I found from cscareerquestions was

Given two ranges [a,b), [c,d), check if they intersect.

http://www.reddit.com/r/cscareerquestions/comments/2xrzst/just_got_rejected_from_google_after_my_phone/

The interviewee said:

I just worked out the midpoints and the radii of the two ranges. Then checked if the difference in the midpoints were smaller than the radii summed.

The interviewer mentioned two things. When taking the difference, what if one is smaller than the other. I said, just check and make sure you do it the right way round. About 10 minutes after the call, I realised I could've just used the absolute value of the difference instead. Then he mentioned that the [) notation means inclusive, so you don't include the last value. So I just decremented the end of each range.

What is a good way to do this problem? Would someone explain using examples?

Upvotes: 3

Views: 396

Answers (1)

rici
rici

Reputation: 241691

Here's the textbook answer:

If two ranges don't intersect, one of them is entirely to the left of the other one, which is to say: b≤c or d≤a. The comparison is ≤ because the ranges are half-open; if b=c, for example, the ranges don't intersect because b is not in [a,b).

So the ranges intersect if the above is not true:

not (b≤c or d≤a) ≡ not b≤c  and not d≤a ≡ b>c and d>a

Now, what about real-life programming? Aside from the above, there is one other case where two ranges do not intersect: when one or both of them are empty.

That's important because empty ranges tend to show up, and they may have arbitrary endpoints. You certainly wouldn't want to report that [0,2) and [1,1) intersected, because they don't, and that could be an important bug.

So let's ask a different question: what is the intersection of two ranges? And the answer is pretty simple: the left-hand edge of the intersection is the greater of the left-hand edges of the two ranges, and the right-hand edge is the lesser of the right-hand edges. Mathematically:

[a,b) ∩ [c,d) ≡ [ max(a,c),min(b,d) )

Since a half-open range is empty if its right-hand edge is less than or equal to its left-hand edge, we can produce the more resilient definition:

Ranges Intersect [a,b), [c,d) ≡ min(b,d) > max(a,c)

Upvotes: 3

Related Questions