> 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 >
Doesn't seem right. Firstly, the heap property itself is lost. Secondly, the 'trick' of adding numbers to the root doesn't ensure constant space. The bigger the value gets the more bits you'd need to store. -- 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.
