The Student Room Group
Uni students - Complete our survey >>
Uni students - Complete our survey >>
Uni students - Complete our survey >>

need help with this "I have a computer file containing 1,000,000 non-negative integer

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?

dnt knw how to write the program?
Reply 1
Avatar for Planto
Planto
16
The quickest way in this situation would be to evaluate all of the numbers - keeping track of the largest one - and then just start incrementing for new members.

But the problem description kind of sounds like it's asking for a sort-and-search kind of method.
Reply 2
Avatar for DFranklin
DFranklin
18
Original post by Planto
The quickest way in this situation would be to evaluate all of the numbers - keeping track of the largest one - and then just start incrementing for new members.
This is fairly obviously optimal (you can't do better than looking at every item) and meets the specification.

But the problem description kind of sounds like it's asking for a sort-and-search kind of method.
In the real world, yeah. For an artificial question I'd go with your answer - an honest examiner should recognize it meets the given requirements, even if it's not what he had in mind.
Reply 3
Avatar for Bac009
Bac009
Set the new member number to 1. Check if its already in use. If so Increment. Repeat.

Once you do set a new member, store the value + 1 so that you dont have to start your 'search' from the beginning again.
Reply 4
Avatar for mug51
mug51
9
excel does wonders, you can use that

list all the 1,000,000 numbers in column A
in column B, list say the numbers 1-1000 (drag to increment)
in column C use the formula '=VLOOKUP(B1,$A$1:colondollar:A$100000000,1,FALSE)' in the first cell then drag to replicate all the way down to C1000
use the search tool and find which cells in column C have N/A, they are all the unallocated numbers

and repeat to find numbers great than 1000

stupid smiley in my formula
(edited 13 years ago)
Reply 5
Avatar for Planto
Planto
16
Original post by Bac009
Set the new member number to 1. Check if its already in use. If so Increment. Repeat.


This would be horribly inefficient. In the worst case, the file contains all numbers 1 to 1,000,000, meaning that by your method you have to iterate over the entire list 1,000,000 times before you find an unused number, meaning a grand total of 1,000,000,000,000 evaluations.
Reply 6
Avatar for Bac009
Bac009
Original post by Planto
This would be horribly inefficient. In the worst case, the file contains all numbers 1 to 1,000,000, meaning that by your method you have to iterate over the entire list 1,000,000 times before you find an unused number, meaning a grand total of 1,000,000,000,000 evaluations.


You still have to iterate over the entire thing to find the "largest" number anyway. My way fills in the blanks and breaks up the "processing time" over several runs. Also - store the position to prevent repeat processing.

EDIT: Sorry I just reread your statement. You are correct. :-)
(edited 13 years ago)

Quick Reply

Related discussions

Latest

Trending

Trending

Articles for you