On May 18, 8:29 am, Terence <technic....@gmail.com> wrote:
> How do you maintain the heap? Could you explain in detail for the
> following example:
> 1 2 3 3 2 1 1 1 2 3 (n=10, k=3)
Basically, in each node we maintain the key and its count.
Initially, heap has the first element.
1:1
Search for 2 and insert( since its not found)
1:1
/
2:1
Search for 3 and insert ( since its not found).
1:1
/ \
2:1 3:1
Search for 3; since 3 is already there increment its count by 1.
1:1
/ \
2:1 3:2
Search for 2; since 2 is already there increment its count by 1.
1:1
/ \
2:2 3:2
and so on...
Since, there are only k distinct keys the heap size will at most be k;
so each search/insert/increment operation takes O(log k) time.
Jagadish
http://www.cse.iitb.ac.in/~jagadish
>
> On 2010-5-17 22:38, Jagadish M wrote:
>
>
>
> > The best algorithm I can think of is to maintain a heap of k elements.
> > Takes O(n log k) time.
> > Is anything told about the values of the keys? If the keys have values
> > less than N, then it is possible to do
> > what you say, i.e sort them in place.
>
> > -Jagadish
> >http://www.cse.iitb.ac.in/~jagadish
>
> > On May 13, 7:06 pm, divya<sweetdivya....@gmail.com> wrote:
>
> >> This problem was asked in google phone interview. We have N element
> >> array with k distinct keys(No relation between k& N given so assume
> >> k<N)
> >> What is the best method to sort this array without using any extra
> >> memory? Please elaborate.
>
> >> --
> >> You received this message because you are subscribed to the Google Groups
> >> "Algorithm Geeks" group.
> >> To post to this group, send email to algoge...@googlegroups.com.
> >> To unsubscribe from this group, send email to
> >> algogeeks+unsubscr...@googlegroups.com.
> >> For more options, visit this group
> >> athttp://groups.google.com/group/algogeeks?hl=en.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group
> athttp://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
