A random approach using HashMap and PriorityQueue is not random enough. Need Help!!!


  • 0
    M

    My approach is a bit different. I am using a PriorityQueue and HashMap. When insert is called, I generate a random number and insert it into the priority queue along with the value. The priority queue is sorted based on the random number that is generated.
    When we delete a value, we only delete the value from the HashMap and not from the PriorityQueue. When getRandom is called we compare the top element with the values in the map. If the value doesn't exist in the map we ignore it and then go to the next value. If not we get the value, generate a new random number and insert it back into the priority queue. I understand that the priority queue takes O(log n) for insert.
    But the issue I am having is that the numbers are not random enough.

    public class RandomizedSet {
        class Number{
            int val;
            int random;
            Number(int v, int r){
                val=v;
                random = r;
            }
        }
        HashMap<Integer,Integer> map; 
        Queue<Number> q;
        Random rd;
        /** Initialize your data structure here. */
        public RandomizedSet() {
            map = new HashMap<>();
            q = new PriorityQueue<Number>(new Comparator<Number>(){
               public int compare(Number n1, Number n2){
                   if(n1.random<n2.random){
                       return 1;
                   }else if(n1.random>n2.random){
                       return -1;
                   }else{
                       return 0;
                   }
               } 
            });
            rd=new Random();
        }
        
        /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
        public boolean insert(int val) {
            if(!map.containsKey(val)){
                map.put(val,1);
                int r=rd.nextInt(map.size())+200;     //Added 200 so that when we insert values the map size will be insignificant and thus one value will not be burried for ever. 
                Number n = new Number(val,r);
                q.add(n);    
                
                return true;
            }else{
                return false;
            }
            
            
        }
        
        /** Removes a value from the set. Returns true if the set contained the specified element. */
        public boolean remove(int val) {
            if(map.containsKey(val)){
                map.remove(val);
                return true;
            }else{
                return false;
            }
        }
        
        /** Get a random element from the set. */
        public int getRandom() {
            while(!q.isEmpty()){
                Number n=q.poll();
                if(!map.containsKey(n.val)){
                    continue;
                }else{
                    int val=n.val;
                    int r=rd.nextInt(map.size());
                    n.random=r;
                    q.add(n);
                    return val;
                }
            }
            return -1;
            
        }
    }
    
    

  • 0
    Y

    Your random numbers are not the same when inserting and reinserting. Change these lines int r=rd.nextInt(map.size()); int r=rd.nextInt(map.size())+200; to something more random like int r=rd.nextInt(Integer.MAX_VALUE);


Log in to reply
 

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