My methodology is to use two LinkedLists, one for storing assignedNumbers, and one for storing free Numbers. Also using a hashtable to store the index of a number in assignedNumbers. All operations are O(1) but I'm still getting a TLE :/

public class PhoneDirectory {

```
int maxNumbers;
LinkedList assignedNumbers;
LinkedList freeNumbers;
HashMap<Integer, Integer> pos;
public PhoneDirectory(int maxNumbers) {
this.maxNumbers = maxNumbers;
assignedNumbers = new LinkedList<Integer>();
freeNumbers = new LinkedList<Integer>();
pos = new HashMap<Integer, Integer>();
}
public int get() {
if(freeNumbers.size() > 0) {
int number = (Integer)freeNumbers.pollFirst();
assignedNumbers.add(number);
pos.put(number, assignedNumbers.size()-1);
return number;
} else {
if(assignedNumbers.size() < maxNumbers) {
int number = assignedNumbers.size();
assignedNumbers.add(number);
pos.put(number, assignedNumbers.size()-1);
return number;
} else {
return -1;
}
}
}
public boolean check(int number) {
return !pos.containsKey(number);
}
public void release(int number) {
if(pos.containsKey(number)) {
int index = pos.get(number);
if(index == assignedNumbers.size()-1) {
assignedNumbers.remove(index);
} else {
int lastNumber = (Integer)assignedNumbers.pollLast();
assignedNumbers.set(index, lastNumber);
pos.put(lastNumber, pos.get(number));
}
pos.remove(number);
freeNumbers.add(number);
}
}
```

}