**Solution**

**Design Phone Directory** https://leetcode.com/problems/design-phone-directory/

**Algorithm**

- stack and set([]). stack stores the next available number.
- Initialize stack with 0. Allocate the number on the top of the stack. When you release a number, push it on the stack.
- Notice we push x+1 to the stack in get if stack becomes empty after popping. Why? Imagine first three gets: cache{0,1,2}. st=[3], then say three removes 0,1,2. This makes stack as st=[3,0,1,2]. Then we do 4 gets. At 4th get, we have stack as [3]. We pop and stack is empty - so we add 3+1 =4 back to stack.
- Notice that the bottom most element in the stack will be the last number in sequence used so far.

```
class PhoneDirectory(object):
def __init__(self, maxNumbers):
"""
Initialize your data structure here
@param maxNumbers - The maximum numbers that can be stored in the phone directory.
:type maxNumbers: int
"""
self.cache, self.st, self.maxNumbers = set([]), [0], maxNumbers
def get(self):
"""
Provide a number which is not assigned to anyone.
@return - Return an available number. Return -1 if none is available.
:rtype: int
"""
if self.st[-1] == self.maxNumbers:
return -1
else:
x = self.st.pop()
self.cache.add(x)
if len(self.st) == 0:
self.st.append(x+1)
return x
def check(self, number):
"""
Check if a number is available or not.
:type number: int
:rtype: bool
"""
return True if number not in self.cache else False
def release(self, number):
"""
Recycle or release a number.
:type number: int
:rtype: void
"""
if number in self.cache:
self.cache.remove(number)
self.st.append(number)
```