Twenty Percent Knowledge: Insert Delete GetRandom O(1), with or without duplications

Design a data structure that supports all following operations in average O(1) time.

insert(val): Inserts an item val to the set if not already present.
remove(val): Removes an item val from the set if present.
getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.

Example:

// Init an empty set.
RandomizedSet randomSet = new RandomizedSet();

// Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomSet.insert(1);

// Returns false as 2 does not exist in the set.
randomSet.remove(2);

// Inserts 2 to the set, returns true. Set now contains [1,2].
randomSet.insert(2);

// getRandom should return either 1 or 2 randomly.
randomSet.getRandom();

// Removes 1 from the set, returns true. Set now contains [2].
randomSet.remove(1);

// 2 was already in the set, so return false.
randomSet.insert(2);

// Since 1 is the only number in the set, getRandom always return 1.
randomSet.getRandom();

public class RandomizedSet {
    //key is the number, value is the index in arraylist
    //appending to list to achieve O(1) overall
    Map<Integer,Integer> numIndexMap = null;
    List<Integer> nums = null;
    /** Initialize your data structure here. */
    public RandomizedSet() {
        numIndexMap = new HashMap<Integer,Integer>();
        nums = new ArrayList<Integer>();
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        if(numIndexMap.containsKey(val)){
            return false;
        }else{
            //index is 0 based, so we use its size before adding to list
            numIndexMap.put(val,nums.size());
            nums.add(val);
        }
        return true;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        if(!numIndexMap.containsKey(val)){
            return false;
        }else{
            int index = numIndexMap.remove(val);//this returns value of 
            if(index<nums.size()-1){//not last element
            //move last element to the element to be removed
                //array set operation is O(1), remove tail is O(1)
                int lastVal = nums.get(nums.size()-1);
                nums.set(index,lastVal);
                numIndexMap.put(lastVal,index);

            }                
            nums.remove(nums.size()-1);
        }
        return true;
    }
    
    /** Get a random element from the set. */
    public int getRandom() {
        if(nums.size()==0)return -1;
        if(nums.size()==1)return nums.get(0);
        Random r = new Random();
        int indexRandom = r.nextInt(nums.size());
        return nums.get(indexRandom);
    }
}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet obj = new RandomizedSet();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */

381. Insert Delete GetRandom O(1) - Duplicates allowed

https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed/

Design a data structure that supports all following operations in average O(1) time.

Note: Duplicate elements are allowed.

insert(val): Inserts an item val to the collection.
remove(val): Removes an item val from the collection if present.
getRandom: Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the collection contains.

Example:

// Init an empty collection.
RandomizedCollection collection = new RandomizedCollection();

// Inserts 1 to the collection. Returns true as the collection did not contain 1.
collection.insert(1);

// Inserts another 1 to the collection. Returns false as the collection contained 1. Collection now contains [1,1].
collection.insert(1);

// Inserts 2 to the collection, returns true. Collection now contains [1,1,2].
collection.insert(2);

// getRandom should return 1 with the probability 2/3, and returns 2 with the probability 1/3.
collection.getRandom();

// Removes 1 from the collection, returns true. Collection now contains [1,2].
collection.remove(1);

// getRandom should return 1 and 2 both equally likely.
collection.getRandom();

public class RandomizedCollection {
    Map<Integer, List<Integer>> numIndicesMap = new HashMap<Integer, List<Integer>>();
    List<Integer> nums = new ArrayList<Integer>();
    Random r = new Random();
    /** Initialize your data structure here. */
    public RandomizedCollection() {
        
    }
    
    /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
    public boolean insert(int val) {
        if(numIndicesMap.containsKey(val)){
            numIndicesMap.get(val).add(nums.size());//add a new index in numIndicesMap
            nums.add(val);//add new element to num list
            return false;
        }else{
            List<Integer> indices = new ArrayList<Integer>();
            indices.add(nums.size());
            nums.add(val);
            numIndicesMap.put(val,indices);
            return true;
        }
    }
    
    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    public boolean remove(int val) {
     if(numIndicesMap.containsKey(val)){
         //remove it from numIndicesMap
         List<Integer> indices = numIndicesMap.get(val);
         int index = indices.remove(indices.size()-1);//remove last one. index in nums should be removed
         if(indices.size()==0){//indices list is empty, remove key from map
             numIndicesMap.remove(val);
         }
         //remove from nums
         int lastIndex = nums.size()-1;
         int lastElement = nums.get(lastIndex);
         
         if(index!=lastIndex){
             //not last one
             nums.set(index,lastElement);//set last element to val's index
             //since lastElement is already in nums, it must have an index list in map
             List<Integer> indicesOfLastElement = numIndicesMap.get(lastElement);
             indicesOfLastElement.remove(new Integer(lastIndex));//remove last Index,

//this has to be object instead of prime in order to remove correct element
             indicesOfLastElement.add(index);//add new index position for last element
         }
         nums.remove(nums.size()-1);//remove last element in list
         return true;
     }
     return false;
    }
    
    /** Get a random element from the collection. */
    public int getRandom() {
        if(nums.size()==0)return -1;
        if(nums.size()==1)return nums.get(0);
        
        int randomInd = r.nextInt(nums.size());//n in nextInt is exclusive
        return nums.get(randomInd);
    }
}

/**
 * Your RandomizedCollection object will be instantiated and called as such:
 * RandomizedCollection obj = new RandomizedCollection();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */

Twenty Percent Knowledge

Friday, September 16, 2016

Insert Delete GetRandom O(1), with or without duplications

No comments: