Question

Formatted question description: https://leetcode.ca/all/379.html

Design a phone directory that initially has maxNumbers empty slots that can store numbers. The directory should store numbers, check if a certain slot is empty or not, and empty a given slot.

Implement the PhoneDirectory class:

PhoneDirectory(int maxNumbers) Initializes the phone directory with the number of available slots maxNumbers.
int get() Provides a number that is not assigned to anyone. Returns -1 if no number is available.
bool check(int number) Returns true if the slot number is available and false otherwise.
void release(int number) Recycles or releases the slot number.

Example 1:

Input
["PhoneDirectory", "get", "get", "check", "get", "check", "release", "check"]
[[3], [], [], [2], [], [2], [2], [2]]
Output
[null, 0, 1, true, 2, false, null, true]

Explanation
PhoneDirectory phoneDirectory = new PhoneDirectory(3);
phoneDirectory.get();      // It can return any available phone number. Here we assume it returns 0.
phoneDirectory.get();      // Assume it returns 1.
phoneDirectory.check(2);   // The number 2 is available, so return true.
phoneDirectory.get();      // It returns 2, the only number that is left.
phoneDirectory.check(2);   // The number 2 is no longer available, so return false.
phoneDirectory.release(2); // Release number 2 back to the pool.
phoneDirectory.check(2);   // Number 2 is available again, return true.

Constraints:

1 <= maxNumbers <= 10⁴
0 <= number < maxNumbers
At most 2 * 10⁴ calls will be made to get, check, and release.

Algorithm

To allocate numbers, an array nums is essential for storing all potential numbers. It’s important to initialize this array with distinct numbers. Additionally, use a parallel array used of the same length to track whether a number at a specific position has been allocated. A variable idx will indicate the currently allocated position.

`get()` Function:

No Number Available: If idx is less than 0, it signifies that no number can be allocated, so return -1.
Allocate Number: Otherwise, retrieve nums[idx], mark the number as used (set used[idx] to true), decrement idx by 1, and return the fetched number.

`check()` Function:

Simply verify if the corresponding entry in used is false (indicating availability).

`release()` Function:

If the number is already unallocated (marked as false in used), return immediately.
If the number is allocated (true in used), increment idx by 1, reassign the number to nums[idx], and mark it as unallocated (false) in used.

Alternative Lightweight Algorithm

A phone directory can also be implemented using an array in tandem with a queue. The array tracks the availability of numbers, while the queue holds unassigned numbers.

Initialization:

In the constructor, initialize the array (all elements as true) and the queue (filled with numbers from 0 to maxNumbers - 1).

`get` Operation:

Queue Empty: If the queue is empty (no available numbers), return -1.
Allocate Number: If not, dequeue a number, set its corresponding array status to false (indicating allocation), and return this number.

`check` Operation:

Directly inspect the array to determine if the number is available. Return false immediately if the number is out of bounds (less than 0 or greater or equal to maxNumbers).

`release` Operation:

Avoid Redundancy: Only release a number if it’s currently in use. If it’s already available, no action is needed.
Releasing: If the number is in use, offer it back to the queue and update its status in the array to true.

Code

class PhoneDirectory {
    int maxNumbers;
    boolean[] available;
    Queue<Integer> unused;

    /** Initialize your data structure here
        @param maxNumbers - The maximum numbers that can be stored in the phone directory. */
    public PhoneDirectory(int maxNumbers) {
        this.maxNumbers = maxNumbers;
        available = new boolean[maxNumbers];
        unused = new LinkedList<Integer>();
        for (int i = 0; i < maxNumbers; i++) {
            available[i] = true;
            unused.offer(i);
        }
    }
    
    /** Provide a number which is not assigned to anyone.
        @return - Return an available number. Return -1 if none is available. */
    public int get() {
        if (unused.isEmpty())
            return -1;
        else {
            int next = unused.poll();
            available[next] = false;
            return next;
        }
    }
    
    /** Check if a number is available or not. */
    public boolean check(int number) {
        if (number < 0 || number >= maxNumbers)
            return false;
        else
            return available[number];
    }
    
    /** Recycle or release a number. */
    public void release(int number) {
        if (!available[number]) {
            unused.offer(number);
            available[number] = true;
        }
    }
}

/**
 * Your PhoneDirectory object will be instantiated and called as such:
 * PhoneDirectory obj = new PhoneDirectory(maxNumbers);
 * int param_1 = obj.get();
 * boolean param_2 = obj.check(number);
 * obj.release(number);
 */

//////

import java.util.HashSet;
import java.util.LinkedList;

public class Design_Phone_Directory {
    public class PhoneDirectory {

        int max;
        HashSet<Integer> set; // assigned number
        LinkedList<Integer> queue; // available number

        /**
         * Initialize your data structure here
         *
         * @param maxNumbers - The maximum numbers that can be stored in the phone directory.
         */
        public PhoneDirectory(int maxNumbers) {
            set = new HashSet<Integer>();
            queue = new LinkedList<Integer>();
            for (int i = 0; i < maxNumbers; i++) {
                queue.offer(i);
            }
            max = maxNumbers - 1;
        }

        /**
         * Provide a number which is not assigned to anyone.
         *
         * @return - Return an available number. Return -1 if none is available.
         */
        public int get() {
            if (queue.isEmpty()) {
                return -1;
            }

            int e = queue.poll();
            set.add(e);
            return e;
        }

        /**
         * Check if a number is available or not.
         */
        public boolean check(int number) {
            return !set.contains(number) && number <= max;
        }

        /**
         * Recycle or release a number.
         */
        public void release(int number) {
            if (set.contains(number)) {
                set.remove(number);
                queue.offer(number);
            }
        }
    }
}

//////

class PhoneDirectory {

    private boolean[] provided;

    /**
       Initialize your data structure here
        @param maxNumbers - The maximum numbers that can be stored in the phone directory.
     */
    public PhoneDirectory(int maxNumbers) {
        provided = new boolean[maxNumbers];
    }

    /**
       Provide a number which is not assigned to anyone.
        @return - Return an available number. Return -1 if none is available.
     */
    public int get() {
        for (int i = 0; i < provided.length; ++i) {
            if (!provided[i]) {
                provided[i] = true;
                return i;
            }
        }
        return -1;
    }

    /** Check if a number is available or not. */
    public boolean check(int number) {
        return !provided[number];
    }

    /** Recycle or release a number. */
    public void release(int number) {
        provided[number] = false;
    }
}

/**
 * Your PhoneDirectory object will be instantiated and called as such:
 * PhoneDirectory obj = new PhoneDirectory(maxNumbers);
 * int param_1 = obj.get();
 * boolean param_2 = obj.check(number);
 * obj.release(number);
 */

// OJ: https://leetcode.com/problems/design-phone-directory/
// Time: O(1)
// Space: O(N)
class PhoneDirectory {
private:
    unordered_set<int> pool;
public:
    PhoneDirectory(int maxNumbers) {
        while (maxNumbers--) pool.insert(maxNumbers);
    }
    int get() {
        if (pool.empty()) return -1;
        int ans = *pool.begin();
        pool.erase(pool.begin());
        return ans;
    }
    bool check(int number) {
        return pool.find(number) != pool.end();
    }
    void release(int number) {
        if (check(number)) return;
        pool.insert(number);
    }
};

from collections import deque

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.available = [True] * maxNumbers
    # use extra space deque, to get faster get() call
    self.q = deque([i for i in range(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.q:
      self.available[self.q[0]] = False
      return self.q.popleft()
    return -1

  def check(self, number):
    """
    Check if a number is available or not.
    :type number: int
    :rtype: bool
    """
    return self.available[number]

  def release(self, number):
    """
    Recycle or release a number.
    :type number: int
    :rtype: void
    """
    if not self.available[number]:
      self.available[number] = True
      self.q.append(number)

# Your PhoneDirectory object will be instantiated and called as such:
# obj = PhoneDirectory(maxNumbers)
# param_1 = obj.get()
# param_2 = obj.check(number)
# obj.release(number)

379 - Design Phone Directory

Question

Algorithm

`get()` Function:

`check()` Function:

`release()` Function:

Alternative Lightweight Algorithm

Initialization:

`get` Operation:

`check` Operation:

`release` Operation:

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

get() Function:

check() Function:

release() Function:

Alternative Lightweight Algorithm

Initialization:

get Operation:

check Operation:

release Operation:

Code

All Problems

All Solutions

`get()` Function:

`check()` Function:

`release()` Function:

`get` Operation:

`check` Operation:

`release` Operation: