Assign numbers

There are numbers in between 0-9999999999 (10-digits) which are assigned to someone.

Write two methods called "getNumber" and "requestNumber" as follows: 

Number getNumber();

boolean requestNumber(Number number);

getNumber method should find out a number that did not assigned than marks it as assigned and return that number.

requestNumber method checks the number is assigened or not. If it is assigened returns false, else marks it as assigned and return true.

Design a data structure to keep those numbers and implement those methods

I like this problem a lot because it tests you two things: how to handle large data that may not fit into memory and how to use bits. I am good at neither. :(

Well, first, memory. So we have 10^10 numbers, each number takes 4 byte, so in total we will have ...eh... 40 GB data (thank you, Google!). It definitely cannot fit into the memory, so how should we deal with it? Remember 4 byte = 32 bits, so 1 integer takes 32 bits, can we only use 1 bit? That can reduce the memory to 40 / 32 ~ 1.25 GB, if we have a machine with 2 GB memory, we can handle it!

Yup, here comes the second, the BitSet. I wasn't quite familiar with the concept. A bit set is a vector of bits that grows as needed.  Each component of the bit set has a boolean value. So consider if I initialize a BitSet with initial size of 32, by flipping each component in the set (true -> false or false -> true), we can get 2^32 numbers, and that fits our problem set.

For the requestNumber() part, I use a hashSet to store all added numbers, this will allow retrieval of the number takes only O(1) time.

/**
 * 
 *There are numbers in between 0-9999999999 (10-digits) which are 
 *assigned to someone (does not matter which number assigned to whom) 
 *Write two methods called "getNumber" and "requestNumber" as follows 
 *
 *Number getNumber(); 
 *boolean requestNumber(Number number); 
 *
 *getNumber method should find out a number that 
 *did not assigned than marks it as assigned and return that number. 
 *requestNumber method checks the number is assigned or not. 
 *If it is assigned returns false, else marks it 
 *as assigned and return true. 
 *design a data structure to keep those numbers and implement those methods
 * @author shirleyyoung
 *
 */
import java.util.*;
public class AssignNumbers {
 private static BitSet bits = new BitSet(32);
 private static Set numbers = new HashSet ();
 private static void toBitSet(int number) {
  int index = 0;
  while (number != 0) {
   if (number % 2 != 0)
    bits.set(index);
   index++;
   // >> signed
   // >>> unsigned
   number = number >> 1;
  }
 }
 
 private static int toInteger() {
  int value = 0;
  for (int i = 0; i < bits.length();i++) {
   value += bits.get(i) ? (1 << i) : 0;
  }
  return value;
 }
 
 public static int getNumber() {
  if (!numbers.contains(toInteger())) {
   numbers.add(toInteger());
   return toInteger();
  }
  else {
   for (int i = 0; i < 32; i++) {
    bits.flip(i);
    if (!numbers.contains(toInteger())) {
     numbers.add(toInteger());
     return toInteger();
    }
   }
  }
  return -1;
 }
 public static boolean requestNumber(int number) {
  if (numbers.contains(number))
   return false;
  else {
   numbers.add(number);
   toBitSet(number);
   return true;
  }
 }

 public static void main(String[] args) {
  System.out.println(getNumber());
  //System.out.println(requestNumber(123));
  //System.out.println(requestNumber(123));
  //System.out.println(getNumber());
  for (int i = 0; i < 1000; i++) {
   System.out.println(getNumber());
  }

 }
}