Design Phone Directory

medium design hash set queue

Problem

Design a phone directory supporting get() (any free number), check(num) (is it free?), release(num).

Inputn=3; get() = 0; get() = 1; check(2) = true; get() = 2; check(2) = false; release(2); check(2) = true

Output[0,1,true,2,false,true]

Internal state: free queue and used set track numbers in O(1) ops.

ops (g / c i / r i ;)

from collections import deque
class PhoneDirectory:
    def __init__(self, n):
        self.free = deque(range(n))
        self.used = set()
    def get(self):
        if not self.free: return -1
        x = self.free.popleft()
        self.used.add(x)
        return x
    def check(self, x):
        return x not in self.used
    def release(self, x):
        if x in self.used:
            self.used.discard(x)
            self.free.append(x)

class PhoneDirectory {
  constructor(n) {
    this.free = [];
    for (let i = 0; i < n; i++) this.free.push(i);
    this.used = new Set();
  }
  get() {
    if (!this.free.length) return -1;
    const x = this.free.shift();
    this.used.add(x);
    return x;
  }
  check(x) { return !this.used.has(x); }
  release(x) {
    if (this.used.has(x)) { this.used.delete(x); this.free.push(x); }
  }
}

class PhoneDirectory {
    Deque free = new ArrayDeque<>();
    Set used = new HashSet<>();
    public PhoneDirectory(int n) {
        for (int i = 0; i < n; i++) free.add(i);
    }
    public int get() {
        if (free.isEmpty()) return -1;
        int x = free.poll(); used.add(x); return x;
    }
    public boolean check(int x) { return !used.contains(x); }
    public void release(int x) {
        if (used.remove(x)) free.add(x);
    }
}

class PhoneDirectory {
    queue freeQ;
    unordered_set used;
public:
    PhoneDirectory(int n) { for (int i = 0; i < n; i++) freeQ.push(i); }
    int get() {
        if (freeQ.empty()) return -1;
        int x = freeQ.front(); freeQ.pop(); used.insert(x); return x;
    }
    bool check(int x) { return !used.count(x); }
    void release(int x) {
        if (used.erase(x)) freeQ.push(x);
    }
};

Explanation

We are managing a pool of phone numbers 0 .. n-1 that can be handed out and given back. The clean way to do this is to keep two structures: a queue of free numbers and a set of used numbers, so every operation is instant.

At the start the free queue holds 0, 1, ..., n-1 and the used set is empty. get() pops the next number off the front of the free queue, marks it in the used set, and returns it. If the queue is empty it returns -1.

check(x) just asks the used set: a number is available exactly when it is not in used. release(x) reverses a get — it removes x from used and pushes it back onto the free queue so it can be handed out again.

Both the queue pop and the set lookups are O(1), so every call is constant time.

Example with n = 3: get() returns 0, get() returns 1. check(2) is true (still free). get() returns 2; now check(2) is false. After release(2), 2 goes back to free, so check(2) is true again.

Time: O(1) per op Space: O(n)