# LeetCode 379: Design Phone Directory

## Problem Restatement

We need to design a phone directory.

The directory starts with `maxNumbers` available numbers:

```python
0, 1, 2, ..., maxNumbers - 1
```

We need to support three operations:

| Operation | Meaning |
|---|---|
| `get()` | Return an available number and mark it as used |
| `check(number)` | Return whether `number` is available |
| `release(number)` | Make a used number available again |

If no number is available, `get()` must return `-1`.

The problem statement defines these operations for the `PhoneDirectory` class.

## Input and Output

| Method | Input | Output |
|---|---|---|
| `PhoneDirectory(maxNumbers)` | Number of slots | Initializes numbers from `0` to `maxNumbers - 1` |
| `get()` | None | An available number, or `-1` |
| `check(number)` | A number | `True` if available, otherwise `False` |
| `release(number)` | A number | Nothing |

Example class shape:

```python
class PhoneDirectory:

    def __init__(self, maxNumbers: int):
        ...

    def get(self) -> int:
        ...

    def check(self, number: int) -> bool:
        ...

    def release(self, number: int) -> None:
        ...
```

## Examples

Suppose we create:

```python
directory = PhoneDirectory(3)
```

The available numbers are:

```python
0, 1, 2
```

Call:

```python
directory.get()
```

This may return `0`.

Now `0` is used.

Call:

```python
directory.get()
```

This may return `1`.

Now `0` and `1` are used.

Call:

```python
directory.check(2)
```

This returns:

```python
True
```

because `2` is still available.

Call:

```python
directory.get()
```

This may return `2`.

Now no numbers are available.

Call:

```python
directory.get()
```

This returns:

```python
-1
```

Call:

```python
directory.release(1)
```

Now `1` is available again.

Call:

```python
directory.check(1)
```

This returns:

```python
True
```

## First Thought: Boolean Array

One simple design is to store whether each number is used.

```python
used[number] = True
```

means the number is assigned.

```python
used[number] = False
```

means the number is available.

Then `check(number)` is easy:

```python
return not used[number]
```

`release(number)` is also easy:

```python
used[number] = False
```

But `get()` becomes slow.

To find an available number, we may need to scan from `0` to `maxNumbers - 1`.

That makes `get()` take `O(n)` time.

We can do better.

## Key Insight

We need two things:

1. A fast way to get an available number.
2. A fast way to check whether a number is available.

A queue gives a fast way to take an available number.

A set gives a fast way to check whether a number is available.

So we store:

| Data Structure | Meaning |
|---|---|
| `available_queue` | Numbers that may be available for future `get()` |
| `available_set` | Numbers currently available |

When we allocate a number, we remove it from the set.

When we release a number, we add it back to both the queue and the set.

The set is important because `release(number)` may be called more than once. We should not add the same available number into the queue repeatedly.

## Algorithm

Initialize:

```python
available_queue = deque([0, 1, 2, ..., maxNumbers - 1])
available_set = {0, 1, 2, ..., maxNumbers - 1}
```

For `get()`:

1. If the queue is empty, return `-1`.
2. Pop a number from the left.
3. Remove it from `available_set`.
4. Return it.

For `check(number)`:

1. Return whether `number` exists in `available_set`.

For `release(number)`:

1. If `number` is already in `available_set`, do nothing.
2. Otherwise, add it to `available_set`.
3. Append it to `available_queue`.

## Correctness

The set `available_set` always contains exactly the numbers that are currently free.

At initialization, every valid number from `0` to `maxNumbers - 1` is free, so the set is correct.

When `get()` returns a number, that number becomes assigned. The algorithm removes it from `available_set`, so it no longer appears as available.

When `release(number)` is called for an assigned number, that number becomes free again. The algorithm inserts it into `available_set`, so future `check(number)` calls return `True`.

If `release(number)` is called for a number that is already free, the algorithm does nothing. This prevents duplicate copies of the same number from being added to the queue.

The queue stores numbers that can be returned by future `get()` calls. Since `release()` appends newly available numbers and `get()` removes returned numbers from the set, every returned number is available at the time it is returned.

Therefore all three operations follow the required behavior.

## Complexity

Let `n = maxNumbers`.

| Operation | Time | Space |
|---|---|---|
| Constructor | `O(n)` | `O(n)` |
| `get()` | `O(1)` | `O(1)` extra |
| `check(number)` | `O(1)` | `O(1)` extra |
| `release(number)` | `O(1)` | `O(1)` extra |

The queue and set together store at most `O(n)` numbers.

## Implementation

```python
from collections import deque

class PhoneDirectory:

    def __init__(self, maxNumbers: int):
        self.available_queue = deque(range(maxNumbers))
        self.available_set = set(range(maxNumbers))

    def get(self) -> int:
        if not self.available_queue:
            return -1

        number = self.available_queue.popleft()
        self.available_set.remove(number)
        return number

    def check(self, number: int) -> bool:
        return number in self.available_set

    def release(self, number: int) -> None:
        if number in self.available_set:
            return

        self.available_set.add(number)
        self.available_queue.append(number)
```

## Code Explanation

The constructor creates all available numbers:

```python
self.available_queue = deque(range(maxNumbers))
self.available_set = set(range(maxNumbers))
```

The queue gives us a fast `popleft()` operation.

The set gives us fast membership checks.

In `get()`, if no numbers are available, return `-1`:

```python
if not self.available_queue:
    return -1
```

Otherwise, pop one available number:

```python
number = self.available_queue.popleft()
```

Then mark it as unavailable:

```python
self.available_set.remove(number)
```

In `check(number)`, membership in the set gives the answer:

```python
return number in self.available_set
```

In `release(number)`, we first guard against duplicate releases:

```python
if number in self.available_set:
    return
```

Then we make the number available again:

```python
self.available_set.add(number)
self.available_queue.append(number)
```

## Testing

```python
def test_phone_directory():
    directory = PhoneDirectory(3)

    a = directory.get()
    b = directory.get()

    assert a in {0, 1, 2}
    assert b in {0, 1, 2}
    assert a != b

    remaining = ({0, 1, 2} - {a, b}).pop()
    assert directory.check(remaining) is True

    c = directory.get()
    assert c == remaining

    assert directory.get() == -1

    directory.release(b)
    assert directory.check(b) is True

    d = directory.get()
    assert d == b

    assert directory.check(b) is False

    directory.release(b)
    directory.release(b)

    assert directory.check(b) is True
    assert directory.get() == b
    assert directory.get() == -1

    print("all tests passed")

test_phone_directory()
```

Test meaning:

| Test | Why |
|---|---|
| First two `get()` calls | Returned numbers must be valid and different |
| `check(remaining)` | Confirms unused number is available |
| Third `get()` | Gets the last available number |
| Fourth `get()` | Returns `-1` when full |
| `release(b)` | Makes an assigned number reusable |
| Duplicate `release(b)` | Should not create duplicate availability |