It seems that the intent of the problem was to work with the file to
find one unused number. If preprocessing can be done, just list the
numbers that are available (e.g., mark their availability in a bit
table) and use them one by one. If the member numbers are unbounded,
just list enough numbers to last a while and then do the preprocessing
again when you run out of them.
Dave
On Feb 22, 8:01 am, Ridvan <[EMAIL PROTECTED]> wrote:
> Well if some preprocessing may be done just store the largest number
> and increase it.
>
> If the number has to be somewhere in between the 1000000 numbers I
> would do it in this way:
> Define a Range class: Range{int min, int max}
>
> In the preprocessing split the numbers to free Ranges.
>
> Define Heap<Range> Where Range1>Range2 when (Range1.max-
> Range1.min)>(Range2.max-Range2.min).
>
> When you need a new number - take the Range from the top and split it
> - O(lgN)
>
> Then add 2 new Ranges to the Heap - O(lgN)
>
> On Feb 20, 11:52 am, "shekhar deo" <[EMAIL PROTECTED]> wrote:
>
>
>
> > Please let me know the best solution for this problem :
>
> > > I have a computer file containing 1,000,000 non-negative integers, in
> > > no particular order. Imagine that they are the membership numbers of
> > > people who are enrolled in my internet club. A new person wants to join
> > > the club, and we need to find an unused number to allocate to them. How
> > > would you find, in a reasonable time, a number that was not already in the
> > > file?
>
> > > -- Hide quoted text -
>
> - Show quoted text -
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
