Sunday, October 23, 2016

Design Phone Directory

Design a Phone Directory which supports the following operations:
  1. get: Provide a number which is not assigned to anyone.
  2. check: Check if a number is available or not.
  3. release: Recycle or release a number.
Example:
// Init a phone directory containing a total of 3 numbers: 0, 1, and 2.
PhoneDirectory directory = new PhoneDirectory(3);

// It can return any available phone number. Here we assume it returns 0.
directory.get();

// Assume it returns 1.
directory.get();

// The number 2 is available, so return true.
directory.check(2);

// It returns 2, the only number that is left.
directory.get();

// The number 2 is no longer available, so return false.
directory.check(2);

// Release number 2 back to the pool.
directory.release(2);

// Number 2 is available again, return true.
directory.check(2);

The problem actually requires us to utilize BitSet. Of course we can use Map or other advance data structure. However, it is said that these data structure may cause TLE.
If you don't know about BitSet, check this. The idea is to use BitSet as an availability check. If a phone number is assigned, the bit is assigned to 1. All bits are initialized to 0. We maintain a variable to check the smallest available phone number (index of the bits) we have. There are two benefits of doing this: 1. if this variable reaches the maximum number (size of the BitSet), we know there is no available phone number, so we can directly return -1; 2. Whenever a phone number is released, the released one should have higher priority to be assigned, thus if we find if the number to release is smaller than our smallestAvailable, we can assign the number to it.


public class PhoneDirectory {

    private final BitSet phoneSet;
    private final int maxNumber;
    private int smallestAvailable;

    public PhoneDirectory(int maxNumbers) {
        this.phoneSet = new BitSet(maxNumbers);
        this.maxNumber = maxNumbers;
        this.smallestAvailable = 0;
    }
    public int get(){
        if (smallestAvailable == maxNumber) {
            return -1;
        }
        int toReturn = smallestAvailable;
        phoneSet.set(toReturn);
        smallestAvailable = phoneSet.nextClearBit(toReturn);
        return toReturn;
    }

    public boolean check(int number){
        return phoneSet.get(number) == false;
    }

    public void release(int number){
        if (!phoneSet.get(number)) {
            return;
        }
        phoneSet.clear(number);
        if (number < smallestAvailable) {
            smallestAvailable = number;
        }
    }
}



2 comments:

  1. Thanks for the valuable information and insights you have so provided here... original site

    ReplyDelete
  2. Admiring the time and effort you put into your blog and detailed information you offer!.. bookmetoday.com

    ReplyDelete