[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.
[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.
[algogeeks] Re: count number of set bits in an (big) array (Asked in Google interview)
You can use this logic to find number of bits set :-
int count = 0;
foreach(int x in array){
if(x < 0)
count--; //for the sign bit will be counted below.
while(x){
x &= x-1;
count++;
}
}
Thanks
Monish
On Sunday, May 12, 2013 1:05:31 AM UTC+5:30, rahul sharma wrote:
>
> I was searching for google questions and got this question.Use look up to
> do it in bext way
>
>
> What is best time complexity for this..
> plz post algo too
>
>
>
>
--
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: What data structures will you use to implement a text editor. Size of editor can be changed and you also need to save the styling information for all the text like italic, bold etc.
You could also use Fly Weight pattern to implement this. http://en.wikipedia.org/wiki/Flyweight_pattern On Saturday, May 25, 2013 10:24:09 PM UTC+5:30, Nishant Pandey wrote: > > In one of the interview it was asked, can some one suggest good DS for > this. > > Thanks > > -- 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] How will you implement a stack using a priority queue. Push and pop should be in O(1)
Hi Nishant
As per the question, (priority queue) PQ is used to implement stack. With
PQ, you cannot do push and pop both in O(1). If you use heap tree(max heap
assuming you increase priority for upcoming pushed objects or min-heap
otherwise) for PQ, it will take O(log n) for each operation push and pop.
This is what Ankur is also trying to indicate.
Thanks
Monish
On Sunday, May 26, 2013 12:49:48 PM UTC+5:30, Nishant Pandey wrote:
>
> @Ankur... what ever we are inserting we are inserting at the head of the
> list, so its O(1).
> we are overriding Enque method with Push().
>
>
> On Sun, May 26, 2013 at 10:15 AM, Ankur Khurana
>
> > wrote:
>
>> but in this approach , How is Push having O(1) complexity ?
>>
>>
>> On 25 May 2013 17:52, rohit jangid >wrote:
>>
>>> you are doing it correct.
>>>
>>>
>>> On Sat, May 25, 2013 at 5:37 PM, Nishant Pandey
>>>
>>> > wrote:
>>>
I am not getting the y priority Q is getting used for this question, as
in case of P Queue, things are arranged as per the priority so when we
will
insert the data we can simply increament the priority.
Algo would be like this :
Enque(q, data) {
push(q, data, increrase the prioroty);
}
int Deque() {
return pop();
}
here higher priority one shuld be poped first.
PLEASE SUGGEST if any good approach some one is having other than this ?
--
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+...@googlegroups.com .
>>>
>>>
>>>
>>> --
>>> Rohit Jangid
>>> http://rohitjangid.com
>>> Graduate
>>> Deptt. of Computer Engineering
>>> NSIT, Delhi University, India
>>>
>>> --
>>> 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+...@googlegroups.com .
>>>
>>>
>>>
>>
>>
>>
>> --
>> Regards,
>> Ankur Khurana
>> Software Developer Engineer,
>> Microsoft India Development Center,
>> Hyderabad.
>>
>> --
>> 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+...@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.
