LeetCode 379: Design Phone Directory

Problem Restatement

We need to design a phone directory.

The directory starts with maxNumbers available numbers:

0, 1, 2, ..., maxNumbers - 1

We need to support three operations:

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

The problem statement defines these operations for the PhoneDirectory class.

Input and Output

Example class shape:

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:

directory = PhoneDirectory(3)

The available numbers are:

0, 1, 2

Call:

directory.get()

This may return 0.

Now 0 is used.

Call:

directory.get()

This may return 1.

Now 0 and 1 are used.

Call:

directory.check(2)

This returns:

True

because 2 is still available.

Call:

directory.get()

This may return 2.

Now no numbers are available.

Call:

directory.get()

This returns:

-1

Call:

directory.release(1)

Now 1 is available again.

Call:

directory.check(1)

This returns:

True

First Thought: Boolean Array

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

used[number] = True

means the number is assigned.

used[number] = False

means the number is available.

Then check(number) is easy:

return not used[number]

release(number) is also easy:

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:

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:

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.

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

Implementation

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:

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:

if not self.available_queue:
    return -1

Otherwise, pop one available number:

number = self.available_queue.popleft()

Then mark it as unavailable:

self.available_set.remove(number)

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

return number in self.available_set

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

if number in self.available_set:
    return

Then we make the number available again:

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

Testing

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: