Welcome to Subscribe On Youtube

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 <= 104
  • 0 <= number < maxNumbers
  • At most 2 * 104 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)
    
    
  • type PhoneDirectory struct {
    	available map[int]bool
    }
    
    func Constructor(maxNumbers int) PhoneDirectory {
    	available := make(map[int]bool)
    	for i := 0; i < maxNumbers; i++ {
    		available[i] = true
    	}
    	return PhoneDirectory{available}
    }
    
    func (this *PhoneDirectory) Get() int {
    	for k := range this.available {
    		delete(this.available, k)
    		return k
    	}
    	return -1
    }
    
    func (this *PhoneDirectory) Check(number int) bool {
    	_, ok := this.available[number]
    	return ok
    }
    
    func (this *PhoneDirectory) Release(number int) {
    	this.available[number] = true
    }
    
    /**
     * Your PhoneDirectory object will be instantiated and called as such:
     * obj := Constructor(maxNumbers);
     * param_1 := obj.Get();
     * param_2 := obj.Check(number);
     * obj.Release(number);
     */
    
  • class PhoneDirectory {
        private available: Set<number> = new Set();
    
        constructor(maxNumbers: number) {
            for (let i = 0; i < maxNumbers; ++i) {
                this.available.add(i);
            }
        }
    
        get(): number {
            const [x] = this.available;
            if (x === undefined) {
                return -1;
            }
            this.available.delete(x);
            return x;
        }
    
        check(number: number): boolean {
            return this.available.has(number);
        }
    
        release(number: number): void {
            this.available.add(number);
        }
    }
    
    /**
     * Your PhoneDirectory object will be instantiated and called as such:
     * var obj = new PhoneDirectory(maxNumbers)
     * var param_1 = obj.get()
     * var param_2 = obj.check(number)
     * obj.release(number)
     */
    
    

All Problems

All Solutions