title: Interview: System/API design
body: <p>This question was asked in one of the big software company. I have come up with a simple solution and I want to know what others feel about the solution.</p>
  
  <blockquote>
    <p>You are supposed to design an API and a backend for a system that can
    allot phone numbers to people living in a city. The phone numbers will
    start from 111-111-1111 and end at 999-999-9999. The API should enable
    the clients (people in the city) to do the following:</p>
    
    <ol>
    <li>When a client requests for a phone number, it allots one of the available numbers to them.</li>
    <li>Some clients may want fancy numbers, so they can specifically ask for a number to be alloted to them. If the requested number is
    available then the system allots it to them, otherwise the system
    allots any available number.</li>
    </ol>
    
    <p>The system need not have to know which number is alloted to which
    client. The same client may make successive requests and get multiple
    phone numbers for himself, but the system is not bothered. At any
    point of time, the system only knows which phone numbers are alloted
    and which phone numbers are free.</p>
  </blockquote>
  
  <p>The numbers from 111-111-1111 to 999-999-9999 roughly corresponds to 8 billion  numbers. Assuming that memory is not a constraint, I can think of the following two approaches (which are almost similar).</p>
  
  <ol>
  <li><p>Maintain a huge boolean array of length 8 billion and have a <code>next</code> pointer that points to an array index (<code>next</code> is initialized to zero). If the value pointed by <code>next</code> is not free, then forward <code>next</code> until a free number is found. When fancy numbers are requested, just check whether the corresponding index position is free and return the number. The downside of this approach is, when allocating numbers in a regular way, if there is a huge chunk (say 1 billion) numbers in the middle that was allocated by fancy allocation, then the <code>next</code> pointer has to be moved 1 billion times. </p></li>
  <li><p>To overcome the difficulty mentioned in the previos design, we can use some sort of a linked hashmap. We maintain a doubly linked list (this replaces the array in the previous design) and another array of the same length as the list where each element of the array points to a corresponding element in the list. So when allocating numbers in regular method, we advance a pointer in the linked list and mark nodes as and when we allocate (same as the previous method). When allocating fancy numbers, we can directly find the node in the list that corresponds to the special number requested by first indexing into the array and the following the pointer. Once the node is identified, short circuit the previous node and the next node so that we do not have to skip the used numbers one by one (which was the problem with the previous approach) when doing a regular allocation.</p></li>
  </ol>
  
  <p>Let me know whether I am on the right track. Please enlighten me with any important details that I am missing.</p>