[algogeeks] Google Interview Question: In how many intervals does a number exists
There are n Intervals. Given a set of m numbers, tell in how many intervals
does each number exists.
Example: 4 Intervals: [2,3] [3,4] [1,4] [3,10]. Numbers {2,4,11}
For 2 - 1 as 2 lies only in 1 interval [2,3]
For 4 - 3 as 4 lies in 3 intervals
For 11 - 0 as 11 lies in none of the given 4 intervals.
It can be easily done in O(m*n) by traversing n intervals for each number
in the given set of m numbers. How would improve this?
Note: I could not fully recall, but I have seen very similar question in
codechef but could not find the same.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Google Interview Question: In how many intervals does a number exists
2-2 as 2 lies in [2,3] and [1,4] ?
On Sun, Jun 9, 2013 at 12:50 PM, Monish Gupta monish.gup...@gmail.comwrote:
There are n Intervals. Given a set of m numbers, tell in how many
intervals does each number exists.
Example: 4 Intervals: [2,3] [3,4] [1,4] [3,10]. Numbers {2,4,11}
For 2 - 1 as 2 lies only in 1 interval [2,3]
For 4 - 3 as 4 lies in 3 intervals
For 11 - 0 as 11 lies in none of the given 4 intervals.
It can be easily done in O(m*n) by traversing n intervals for each number
in the given set of m numbers. How would improve this?
Note: I could not fully recall, but I have seen very similar question in
codechef but could not find the same.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Google Interview Question: In how many intervals does a number exists
Read up on Interval trees http://en.wikipedia.org/wiki/Interval_tree.
Programmers should realize their critical importance and responsibility in
a world gone digital. They are in many ways similar to the priests and
monks of Europe's Dark Ages; they are the only ones with the training and
insight to read and interpret the scripture of this age.
On Sun, Jun 9, 2013 at 12:20 AM, Monish Gupta monish.gup...@gmail.comwrote:
There are n Intervals. Given a set of m numbers, tell in how many
intervals does each number exists.
Example: 4 Intervals: [2,3] [3,4] [1,4] [3,10]. Numbers {2,4,11}
For 2 - 1 as 2 lies only in 1 interval [2,3]
For 4 - 3 as 4 lies in 3 intervals
For 11 - 0 as 11 lies in none of the given 4 intervals.
It can be easily done in O(m*n) by traversing n intervals for each number
in the given set of m numbers. How would improve this?
Note: I could not fully recall, but I have seen very similar question in
codechef but could not find the same.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
