Question

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

 379	Design Phone Directory

 Design a Phone Directory which supports the following operations:
     get: Provide a number which is not assigned to anyone.
     check: Check if a number is available or not.
     release: Recycle or release a number.

 Example:

 // Init a phone directory containing a total of 3 numbers: 0, 1, and 2.
 PhoneDirectory directory = new PhoneDirectory(3);

 // It can return any available phone number. Here we assume it returns 0.
 directory.get();

 // Assume it returns 1.
 directory.get();

 // The number 2 is available, so return true.
 directory.check(2);

 // It returns 2, the only number that is left.
 directory.get();

 // The number 2 is no longer available, so return false.
 directory.check(2);

 // Release number 2 back to the pool.
 directory.release(2);

 // Number 2 is available again, return true.
 directory.check(2);

 @tag-linkedlist

Algorithm

Since numbers are to be allocated, an array nums is definitely needed to store all the numbers that can be allocated. Note that it must be initialized to different numbers. Then use an array of equal length used to mark whether the number at a certain position has been used, and use a variable idx to indicate the position currently allocated.

In the get() function, first judge

If idx is less than 0, it means that no number can be allocated, and -1 is returned.
Otherwise, take out nums[idx] and mark that the number has been used. Note that idx will also be decremented by 1, and return to the previously taken number.

For the check() function, directly check whether the corresponding value is 0 in the used function.

Finally, implement the release() function. If the number has not been used, return directly; otherwise, increment idx by 1, and assign the number to nums[idx], and then mark it as 0 in used

Code

Java

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);
            }
        }
    }
}

// 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);
    }
};

class PhoneDirectory:
    def __init__(self, maxNumbers: int):
        """
        Initialize your data structure here
        @param maxNumbers - The maximum numbers that can be stored in the phone directory.
        """
        self.provided = [False] * maxNumbers

    def get(self) -> int:
        """
        Provide a number which is not assigned to anyone.
        @return - Return an available number. Return -1 if none is available.
        """
        for i in range(len(self.provided)):
            if not self.provided[i]:
                self.provided[i] = True
                return i
        return -1

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

    def release(self, number: int) -> None:
        """
        Recycle or release a number.
        """
        self.provided[number] = False


# 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)

############

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.taken = [True] * maxNumbers
    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.taken[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.taken[number]

  def release(self, number):
    """
    Recycle or release a number.
    :type number: int
    :rtype: void
    """
    if not self.taken[number]:
      self.taken[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)

Another solution, lightweighted.

A Phone Directory can be designed using an array and a queue. The array stores whether a number is available. The queue stores the numbers that are not assigned to anyone.

In the constructor, initialize the array and the queue. Initially, all elements in the array are true, and all numbers from 0 to maxNumbers - 1 are offered to the queue.

For operation get, check whether the queue is empty or not. If the queue is empty, then there is no available number, so return -1. If the queue is not empty, then poll a number from the queue, set the state of the polled number in the array to false, and return the number.

For operation check, simply check the array to see whether the number is available or not. If the number is out of bound (less than 0 or greater than or equal to maxNumbers), then return false directly.

For operation release, there is a trick that should pay attention to. It is possible to release a number that is already available, so if the number is already available, do not do any operation. Only if the number is used, it should be released. Offer the number to the queue and set the state of the number in the array to true.

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);
 */

// 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);
    }
};

class PhoneDirectory:
    def __init__(self, maxNumbers: int):
        """
        Initialize your data structure here
        @param maxNumbers - The maximum numbers that can be stored in the phone directory.
        """
        self.provided = [False] * maxNumbers

    def get(self) -> int:
        """
        Provide a number which is not assigned to anyone.
        @return - Return an available number. Return -1 if none is available.
        """
        for i in range(len(self.provided)):
            if not self.provided[i]:
                self.provided[i] = True
                return i
        return -1

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

    def release(self, number: int) -> None:
        """
        Recycle or release a number.
        """
        self.provided[number] = False


# 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)

############

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.taken = [True] * maxNumbers
    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.taken[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.taken[number]

  def release(self, number):
    """
    Recycle or release a number.
    :type number: int
    :rtype: void
    """
    if not self.taken[number]:
      self.taken[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

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions