Alright, I\'m stumped. Please note I\'m not looking for a solution here, but a n

Question

Alright, I'm stumped. Please note I'm not looking for a solution here, but a nudge in the right direction. I'm doing self-directed study, and this is my equivalent of asking my TA in section. As a frame of reference, this is a Data Structures and Algorithm Analysis course, and we've just covered sorting algorithms. Obviously there's some flaw in my thinking, because this must have an answer... The homework problem is below, along with my thoughts on it at the moment:

The input to this problem consists of a sequence of 7-digit phone numbers written as simple integers (e.g. 5551212 represents the phone number 555-1212). The sequence is provided via an Iterator<Integer>. No number appears in the input more than once but there is no other limit on the size of the input. Write precise (preferable Java-like) pseudocode for a method that prints out the phone numbers (as integers) in the list in ascending order. Your solution must not use more than 2MB of memory. (Note: It cannot use any other storage – hard drive, network, etc.) Explain why your solution is under the 2MB limit.

1) Valid numbers: Seven-digit phone numbers are in two parts, the exchange-code, which consists of the first 3 digits and can begin with any number 2-9 followed by any two numbers, and the station-code, which consists of the final 4 digits, and has no restrictions. Therefore, there are ( 8 * 10 * 10 ) * ( 10 * 10 * 10 * 10 ) = 8,000,000 possible phone numbers. Since no number appears more than once, we have a worst case scenario of 8,000,000 phone numbers

2) Data types and storage: These numbers will need to be stored as 32-bit integers, which will occupy 4 bytes of space each in the memory. We'll have a little overhead for the array in which they're stored and for the current routine: 2Mb = 2,097,152 bytes and 2,097,152 / 4 = 524,288 so we can realistically only process 500,000 phone numbers at a time.

3) Iterator: by it's nature we can read each phone number once. We cannot go back.

4) My thoughts so far: initially I started looking at a merge sort or quick sort routine. I also thought of using a merge sort and writing the intermediate arrays to file, then merging the files. The problem I see here is that we have to have the full list in order to split it or partition it, and at some point (presumably both the beginning and the end) we'll have an array containing all the phone numbers. I then thought about doing a bucket sort and just working on 500,000 at a time ( for i = 1 to 9 if number % 500000 == i then bucket ) but this requires 16 passes over the data, and we only get one.

So for now, I'm stumped. Any nudges would be greatly appreciated!

Explanation / Answer

Okay, this is crude but will fit all your requirements and should be fairly fast. Don't know Java, but it can be done in C. The key here is that you need only to know whether a particular phone number has been seen .. so you need only 1 bit per number.

If you allow all digits in all positions, thats 10 million phone numbers - which means 10 million bits, or 1,250,000 bytes of storage. Best thing is it's O(n) complexity.

So, in C/pseudo code:

char directory[1250000]; // initialized to zero

// a function to map a phone number onto a bit position:

void MapPhoneToBit(int phoneNumber, int *byteNumber, int *bitMask)
{
   *byteNumber = phoneNumber / 8;
   *bitMask = 0x80 >> (phoneNumber % 8); // >> is right shift, % is modulus
}

void SetNumberSeen(int phoneNumber)
{
   int byte, bit;
   MapPhoneToBit(phoneNumber, &byte, &bit);
   directory[byte] |= bit; // |= is "or equals"
}

int NumberWasSeen(int phoneNumber)
{
   int byte, bit;
   MapPhoneToBit(phoneNumber, &byte, &bit);
   return (directory[byte] & bit) != 0;
}

// pseudo code for mainline

main()
{
   while (more numbers)
   {
     phoneNumber = iterator.next;
     SetNumberSeen(phoneNumber);
   }

   for (phoneNumber = 2000000; phoneNumber < 10000000; phoneNumber++)
   {
     if (NumberWasSeen(phoneNumber))
       printf(phoneNumber);
   }
}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.