   Type like pro

Get Find and Delete all O(1)

Problem

You will have to design a telephone directory where the following operations would be supported.
1. GET: It will provide a number which is not assigned to anyone
2. CHECK: Given a number it will tell whether it is assigned to anyone or not
3. RELEASE: It will recycle or release a number

Normal solutions

We can implement an array of numbers, then
GET will have O(n), because we need to find through the list for available numbers
CHECK will have O(1)
RELEASE will have O(1)

If we implement via linked list of available numbers, then
GET  will have O(1) as we can return the head
CHECK will have O(n) as we will have to iterate through the linked list
RELEASE will have O(1) as we can just add it at the head.

Solution

We can have all 3 operations in O(1) by a combination of array and linked list. every number is represented by a doubly linked node in its corresponding array location and a doubly linked list runs through the nodes in the array.
GET will have O(1) as we can remove the head of the linked list in O(1) time.
CHECK will have O(1) as we can directly go to the array index, as every index contain the corresponding number's node. Then we can check the availability in the node.
RELEASE will have O(1) as we can go to the node directly by array index and then add it to the doubly linked list. We can add the node to the head in O(1) time.

In this arrangement we can also check the availability of a given number and get that particular number as well. For example if somebody wants a beautiful or lucky number from the directory.

Code

```public class TelephoneDirectory
{
public static void main(String[] args)
{
Directory directory = new Directory(5);
int number1 = directory.getAvailableNumber();
System.out.println(number1);
int number2 = directory.getAvailableNumber();
System.out.println(number2);
System.out.println(directory.isAvailable(3));
int number3 = directory.getAvailableNumber();
System.out.println(number3);
System.out.println(directory.isAvailable(3));
int number4 = directory.getAvailableNumber();
System.out.println(directory.isAvailable(3));
System.out.println(number4);
int number5 = directory.getAvailableNumber();
System.out.println(number5);
int number6 = directory.getAvailableNumber();
System.out.println(number6);
int number7 = directory.getAvailableNumber();
System.out.println(number7);
directory.release(3);
System.out.println(directory.isAvailable(3));
int number8 = directory.getAvailableNumber();
System.out.println(number8);
System.out.println(directory.isAvailable(3));
}

private static class Directory
{
Node[] nodes;

public Directory(int maxNumbers)
{
nodes = new Node[maxNumbers];
for (int i = 0; i < maxNumbers; ++i)
{
nodes[i] = new Node(i);
if (i != 0)
{
nodes[i].previous = nodes[i - 1];
nodes[i - 1].next = nodes[i];
}
}
nodes[maxNumbers - 1].next = nodes;
nodes.previous = nodes[maxNumbers - 1];
}

public int getAvailableNumber()
{
return -1;
else
{
}
return temp;
}

public boolean isAvailable(int number)
{
return nodes[number].available;
}

public void release(int number)
{
if (nodes[number].available == false)
{
nodes[number].available = true;
{
nodes[number].next = nodes[number];
nodes[number].previous = nodes[number];
} else
{
}
}
}

private static class Node
{
boolean available = true;
Node next;
Node previous;
int number;

public Node(int number)
{
this.number = number;
}
}
}

}

```