Hi Jagdish, I think your solution looks good. The only thing about extra space to store count can be dealt with like this in my view:
1) Do a scan of numbers and determine the max number. 2) Create a max heap (Root is the largest number so by step 1 we have determined the Root for the heap). 3) Whenever a number repeats instead of storing the count store modify the number to (number + ROOT Value) ie for 2 which is repeated twice 2 + 3 +3 = 8 instead of 2:3 as you give in your example. 4) Since in a heap no number can be greater than root value whenever a number greater than ROOT (here 3) is accessed/encountered we know the frequency by subtracting till the number is < root value. For example when you see 8 subtract value 3 till number is less than 3. Which means 8-3-3 or frequency =2 for the number. Number of subtractions is the frequency of occurrence. So we don't need extra space to determine frequency but with some extra computation can determine the count at runtime. There can be better ways than addition but you get the basic idea of not using any extra space O(k). What do you think? Personally I feel space isn't that big a issue specially if its linear but interviewer is the boss ;-) Regards, Sachin On Tue, May 18, 2010 at 7:01 PM, Jagadish M <jagadis...@gmail.com> wrote: > > 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<algogeeks%2bunsubscr...@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<algogeeks%2bunsubscr...@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<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://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.
