Java AC solution using queue and set


  • 34
        Set<Integer> used = new HashSet<Integer>();
        Queue<Integer> available = new LinkedList<Integer>();
        int max;
        public PhoneDirectory(int maxNumbers) {
            max = maxNumbers;
            for (int i = 0; i < maxNumbers; i++) {
                available.offer(i);
            }
        }
        
        public int get() {
            Integer ret = available.poll();
            if (ret == null) {
                return -1;
            }
            used.add(ret);
            return ret;
        }
        
        public boolean check(int number) {
            if (number >= max || number < 0) {
                return false;
            }
            return !used.contains(number);
        }
        
        public void release(int number) {
            if (used.remove(number)) {
                available.offer(number);
            }
        }
    

  • 3
    B

    For method check, what if the number passed in is larger than or equal to the maxNumbers


  • 0

    @baisheng Good point! In that case, release function works properly, but check function does not. Boundary check is needed in release function.


  • 0
    D

    @mylzsd +1 for the check() function's corner case.


  • 0

    @mylzsd you only need one set. No queue is needed.

    class PhoneDirectory(object):
    
        def __init__(self, maxNumbers):
            self.available = set(range(maxNumbers))
    
        def get(self):
            return -1 if not self.available else self.available.pop()
    
        def check(self, number):
            return number in self.available
    
        def release(self, number):
            self.available.add(number)
    

  • 2

    @agave That's a different language. How would you do that in Java? With O(1) time operations like @mylzsd's.


  • 0

    @StefanPochmann sorry I thought Java had something similar to the Python set. My bad. I hate Java so I try to stay away from it.


  • 0

    @agave said in Java AC solution using queue and set:

    @StefanPochmann I hate Java

    LOL (I really did). I hate it, too. Well, it has become a little better in recent years. But still, the the hoops you have to go through to for example turn an int[] into a List<Integer>... infuriating. Bothers me even more than all the required boilerplate code.


  • 0

    @StefanPochmann said in Java AC solution using queue and set:

    But still, the the hoops you have to go through to for example turn an int[] into a List<Integer>... infuriating. Bothers me even more than all the required boilerplate code.

    Amen.


  • 1
    Q

    @StefanPochmann said in Java AC solution using queue and set:

    @agave That's a different language. How would you do that in Java? With O(1) time operations like @mylzsd's.

    @StefanPochmann I'm confused. Why can't you use one set in Java for this? Every operations looks like O(1) besides constructing it.


  • 0
    L

    What is the benefit of using Queue for available instead of HashSet like the following code?

       private Set<Integer> usedNumbers;
        private Set<Integer> unUsedNumbers;
        /** Initialize your data structure here
            @param maxNumbers - The maximum numbers that can be stored in the phone directory. */
        public PhoneDirectory(int maxNumbers) {
            usedNumbers = new HashSet<>();
            unUsedNumbers = new HashSet<>();
            for (int i = 0; i < maxNumbers; i++) {
                unUsedNumbers.add(i);
            }
        }
        
        /** Provide a number which is not assigned to anyone.
            @return - Return an available number. Return -1 if none is available. */
        public int get() {
            for (Integer num : unUsedNumbers) {
                unUsedNumbers.remove(num);
                usedNumbers.add(num);
                return num;
            }
            return -1;
        }
        
        /** Check if a number is available or not. */
        public boolean check(int number) {
            return unUsedNumbers.contains(number);
        }
        
        /** Recycle or release a number. */
        public void release(int number) {
            if (usedNumbers.contains(number)) {
                usedNumbers.remove(number);
                unUsedNumbers.add(number);
            }
        }
    

  • 0
    G

    @lubozju I also used two hashsets, but I got a TLE


  • 0
    C

    @StefanPochmann I think java HashSet can do the same. For get(), just need return the first element in available set, which is O(1).


  • 0

    @coldknight said in Java AC solution using queue and set:

    I think java HashSet can do the same. For get(), just need return the first element in available set, which is O(1).

    How do you get "the first element", and how do you know it's O(1)?


  • 0
    C

    @StefanPochmann We can use set.iterator().next() . I think it is O(1), because HashSet is implemented by HashMap, and map.keySet() is a O(1) operation. http://stackoverflow.com/questions/1850802/what-is-the-time-complexity-of-java-util-hashmap-class-keyset-method


  • 0
    K

    @StefanPochmann I actually have the same question as @coldknight , would you mind explaining why?


  • 0
    Y

    @coldknight
    https://docs.oracle.com/javase/8/docs/api/java/util/HashSet.html#iterator--
    "Returns an iterator over the elements in this set. The elements are returned in no particular order."
    The order is not guaranteed so you can't get "the first element" without a queue.


  • 0
    C

    @YetAnotherLeetCoder We don't have to get the first here. We only need to get any one of elements in this set.


  • 2

    Don't actually need a queue or 2 sets. One single set can do the work.

    EDIT: I think this method has become controversy. I thought breaking from the loop right in the first iteration is O(1), at least theoretically. But @StefanPochmann obviously has proved otherwise, as least practically. Maybe it is the implementation of the for(int n: set) loop? Meaning that, it needs to somewhat go through the entire set, before it can start iterating?

    public class PhoneDirectory {
        Set<Integer> phones; 
    
        public PhoneDirectory(int maxNumbers) {
            phones = new HashSet<>(); 
            for(int i=0; i<maxNumbers; i++) phones.add(i);    
        }    
        public int get() {
            if(phones.size()<=0) return -1; 
            else{
                int temp = 0; 
                for(int nn : phones){
                    temp = nn; 
                    break; 
                }
                phones.remove(temp);
                return temp;
            }
        }
        
        public boolean check(int number) {
            return phones.contains(number); 
        }
        
        public void release(int number) {
            phones.add(number); 
        }
    }
    
    

  • 1
    I

    @chidong Check your submission detail, your runtime is falling behind many others.

    By using a queue, we can increase the time complexity of get() method to O(1), however, the get() method in your solution needs to traverse the whole HashSet, which takes O(n).


Log in to reply
 

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