Google Phone Number Assignment

Telecomm.java

/*
  Phone numbers are assigned to all the customers (in Canada, where
  the phone number format is xxx xxx xxxx). We have three functions to do:

  * isTaken? : is this number taken?
  * iGaveOut : takes a number and marks it as taken.
  * giveMeNumber : takes no arguments and returns a random number not taken.

  Describe a data structure that can accomplish these functions
  in the fastest possible time.
 */

// This solution presents a Trie as the selected data structure.
// Assuming a constant size of a phone number, we achieve constant time
// for all three functions. This has space implications (time was favoured).

import java.util.*;
import java.lang.Math.*;

class Telecomm
{
  public static void main(String[] args) {
    Telecommunication tc = new Telecommunication();
  }
}


class Telecommunication
{
  Trie t;
  int phoneNumLength = 10;

  public Telecommunication() {
    t = new Trie(0, phoneNumLength);
  }

  public boolean isTaken(String number) {
    Trie tr = t;
    for(int i = 0; i < phoneNumLength; i++) {
      int digit = Character.getNumericValue(number.charAt(i));
      // If that part of the Trie doesn't exist, the number isn't taken
      if(tr.isEmpty(digit)) {
        return false;
      } else if(tr.isFull()) {
        // If it's full, it's definitely taken
        return true;
      }
      // Go to the next level of the Trie otherwise
      tr = tr.num[digit];
    }
    // The number exists in the Trie if we have got this far
    return true;
  }

  public void iGaveOut(String number) {
    Trie tr = t;
    for(int i = 0; i < phoneNumLength; i++) {
      int digit = Character.getNumericValue(number.charAt(i));
      // If that part of the Trie doesn't exist, we need to create it
      if(tr.isEmpty(digit)) {
        tr.num[digit] = new Trie(tr.level + 1, phoneNumLength);
      }
      // Mark that it has an additional leaf and proceed
      tr.addChild();
      tr = tr.num[digit];
    }
  }

  public String giveMeNumber() {
    Trie tr = t;
    String number = "";

    for(int i = 0; i < phoneNumLength; i++) {
      // Finding a suitable digit
      for(int j = 0; j < 10; j++) {
        // If that part of the Trie doesn't exist, we can use the left trees
        if(tr.isEmpty(j)) {
          number += Integer.toString(j);
          // and we are done
  return addZeroes(number);
        } else if(!tr.isFull()) {
          // Go down the next part of the Trie
          // if there is a candidate number (not full)
          number += Integer.toString(j);
          tr = tr.num[j];
          break;
        }
        // If the tree is full, we go to the next iteration
      }
    }

    // Assertion
    if(isTaken(number)) {
      System.err.println("ERROR: Giving a number that is taken");
      System.exit(1);
    }
    return number;
  }

  // Append zeros to the string until it is the length of the phone number
  private String addZeroes(String number) {
    while(number.length() < phoneNumLength) {
      number += "0";
    }
    return number;
  }

  // Debugging mechanism
  public void printTrie(Trie tr) {
    if(tr == null) {
      return;
    }

    for(int i = 0; i <= 9; i++) {
      if(!tr.isEmpty(i)) {
        System.out.println("Level: " + tr.level);
        System.out.println(i);
        printTrie(tr.num[i]);
      }
    }
  }
}


class Trie
{
  Trie[] num;
  int level;
  int childrenTaken;
  int length;

  public Trie(int level_, int length_) {
    num = new Trie[10];
    level = level_;
    length = length_;
    childrenTaken = 0;
  }

  public void addChild() {
    childrenTaken++;
  }

  // Is this part of the Trie full?
  public boolean isFull() {
    // Base case at the last level of the Trie
    if(level == length-1) {
      return true;
    }

    return ((int) Math.pow(10, (length-1)-level)) == childrenTaken;
  }

  // Is this part of the Trie empty?
  public boolean isEmpty(int dig) {
    return (num[dig] == null);
  }
}