[algogeeks] Re: Google Interview Question: In how many intervals does a number exists
Adding to the question. See inline. On Sunday, June 9, 2013 12:50:46 PM UTC+5:30, Monish Gupta wrote: > > There are n Intervals. *1 <= n <= 1,000,000.* *Limits of interval are > within 64 bit signed int.* 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 -> 2 as 2 lies in *2* intervals. viz. [2,3], [1,4] > 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] Re: Google Interview Question: In how many intervals does a number exists
Can you tell the 'size' of your array 'f' if the intervals are [0, 10],
[10, 9223372036854775808] ?
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 Mon, Jun 10, 2013 at 10:12 PM, sunny wrote:
> yeah interval tree and binary indexed tree is a one solution which will
> give you answer in log(n) time for each query ,but if i got all the
> interval at the beigning of time i can get solution in O(1) time by O(n
> ) preprocessing take array f initialize with zero,now for each
> interval(l,r) do f[l]++ and f[r+1]-- once you are done wi all queries take
> prefix sum value of each index will tell you in how many interval it was
>
>
> On Sunday, June 9, 2013 12:50:46 PM UTC+5:30, Monish Gupta wrote:
>>
>> 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.
[algogeeks] Re: Google Interview Question: In how many intervals does a number exists
Monish, please take a look at a similar problem about poor elephants in
the neighboring topic started today. I believe the problem has a similar
solution. Each start point increases the no. of active intervals by one;
each end point decreases it. So, we do the following:
1. Convert the input array of pairs (BTW, the points don't have to be of an
integral type!) into the following vector:
{ {2,+1}, {3,-1}, {3, +1}, {4, -1}...} This takes O(N) time and O(N)
additional memory
2. Sort the vector by: a) ascending .first; b) descending .second -- this
makes sure we count the intervals properly in case multiple intervals start
and end at the same point. Complexity is O(N*logN).
3. Convert "relative" counters to "absolute"; complexity is O(N).
int count = 0;
for (int i = 0; i < v.size(); ++i) {
count += v.second;
assert (count >=0);
v.second = count;
}
assert (count == 0);
4. After this preparation work ( O(N*logN) time, O(N) memory), answering
the question about the number of intervals for any numbers takes O(logN) --
use lower_bound() to binary search in the sorted vector.
On Sunday, June 9, 2013 3:20:46 AM UTC-4, Monish Gupta wrote:
>
> 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.
[algogeeks] Re: Google Interview Question: In how many intervals does a number exists
typo mistake "take prefix sum of f and see each index value..."continue
On Sunday, June 9, 2013 12:50:46 PM UTC+5:30, Monish Gupta wrote:
>
> 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.
[algogeeks] Re: Google Interview Question: In how many intervals does a number exists
yeah interval tree and binary indexed tree is a one solution which will
give you answer in log(n) time for each query ,but if i got all the
interval at the beigning of time i can get solution in O(1) time by O(n
) preprocessing take array f initialize with zero,now for each
interval(l,r) do f[l]++ and f[r+1]-- once you are done wi all queries take
prefix sum value of each index will tell you in how many interval it was
On Sunday, June 9, 2013 12:50:46 PM UTC+5:30, Monish Gupta wrote:
>
> 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.
