Python solution with detailed explanation


  • 0
    G

    Solution

    Design Phone Directory https://leetcode.com/problems/design-phone-directory/

    Algorithm

    • stack and set([]). stack stores the next available number.
    • Initialize stack with 0. Allocate the number on the top of the stack. When you release a number, push it on the stack.
    • Notice we push x+1 to the stack in get if stack becomes empty after popping. Why? Imagine first three gets: cache{0,1,2}. st=[3], then say three removes 0,1,2. This makes stack as st=[3,0,1,2]. Then we do 4 gets. At 4th get, we have stack as [3]. We pop and stack is empty - so we add 3+1 =4 back to stack.
    • Notice that the bottom most element in the stack will be the last number in sequence used so far.
    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.cache, self.st, self.maxNumbers = set([]), [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.st[-1] == self.maxNumbers:
                return -1
            else:
                x = self.st.pop()
                self.cache.add(x)
                if len(self.st) == 0:
                    self.st.append(x+1)
                return x
    
        def check(self, number):
            """
            Check if a number is available or not.
            :type number: int
            :rtype: bool
            """
            return True if number not in self.cache else False
    
        def release(self, number):
            """
            Recycle or release a number.
            :type number: int
            :rtype: void
            """
            if number in self.cache:
                self.cache.remove(number)
                self.st.append(number)
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.