package advanced.datastructure.random.lc381_insertdeletegetrandomo1duplicatesallowed;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Design a data structure that supports all following operations in average O(1) time.
 * Note: Duplicate elements are allowed.
 */
public class RandomizedCollection {

    private Map<Integer,Integer> data;

    private List<Integer> index;

    private java.util.Random rand;

    /** Initialize your data structure here. */
    public RandomizedCollection() {
        this.data = new HashMap<>();
        this.index = new ArrayList<>();
        this.rand = new java.util.Random();
    }

    /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
    public boolean insert(int val) {
        Integer cnt = data.get(val);
        if (cnt == null) {
            cnt = 0;
        }
        data.put(val, cnt + 1);
        index.add(val);
        return cnt == 0;
    }

    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    public boolean remove(int val) {
        Integer cnt = data.get(val);
        if (cnt == null) {
            return false;
        }
        if (cnt == 1) {
            data.remove(val);
        } else {
            data.put(val, cnt - 1);
        }
        index.remove((Integer) val);
        return true;
    }

    /** Get a random element from the collection. */
    public int getRandom() {
        return index.get(rand.nextInt(index.size()));
    }
}

/**
 * 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();
 */

@@ -155,34 +155,107 @@
 til.
-List;%0Aimport java.util.Map
+HashSet;%0Aimport java.util.List;%0Aimport java.util.Map;%0Aimport java.util.Random;%0Aimport java.util.Set
 ;%0A%0A/
@@ -426,17 +426,16 @@
 ction %7B%0A
-%0A
     priv
@@ -442,603 +442,580 @@
 ate 
-Map%3CInteger,Integer%3E data;%0A%0A    private List%3CInteger%3E index;%0A%0A    private java.util.Random rand;%0A%0A    /** Initialize your data structure here. */%0A    public RandomizedCollection() %7B%0A        this.data = new HashMap%3C%3E();%0A        this.index = new ArrayList%3C%3E();%0A        this.rand = new java.util.Random();%0A    %7D%0A%0A    /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */%0A    public boolean insert(int val) %7B%0A        Integer cnt = data.get(val);%0A        if (cnt == null) %7B%0A            cnt = 0;%0A        %7D%0A        data.put(val, cnt + 1
+Random rand = new Random();%0A    private List%3CInteger%3E list = new ArrayList%3C%3E();%0A    private Map%3CInteger,Set%3CInteger%3E%3E bag = new HashMap%3C%3E();%0A%0A    /** Initialize your data structure here. */%0A    public RandomizedCollection() %7B%7D%0A%0A    /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */%0A    public boolean insert(int val) %7B%0A        boolean isNew = false;%0A        if (!bag.containsKey(val)) %7B%0A            bag.put(val, new HashSet%3C%3E());%0A            isNew = true;%0A        %7D%0A        bag.get(val).add(list.size()
 );%0A 
@@ -1021,21 +1021,20 @@
         
-index
+list
 .add(val
@@ -1055,16 +1055,13 @@
 urn 
-cnt == 0
+isNew
 ;%0A  
@@ -1226,89 +1226,217 @@
     
-Integer cnt = data.get(val);%0A        if (cnt == null) %7B%0A            return false;
+if (bag.containsKey(val)) %7B%0A            int idx = bag.get(val).iterator().next();%0A            bag.get(val).remove(idx);%0A            // Copy last one to deleted position%0A            if (idx %3C list.size() - 1) %7B
 %0A   
@@ -1432,34 +1432,32 @@
  - 1) %7B%0A        
-%7D%0A
         if (cnt 
@@ -1453,22 +1453,47 @@
    i
-f (cnt == 1) %7B
+nt lastval = list.get(list.size() - 1);
 %0A   
@@ -1505,144 +1505,367 @@
     
-data.remove(val);%0A        %7D else %7B%0A            data.put(val, cnt - 1);%0A        %7D%0A        index.remove((Integer) val);%0A        return tru
+    bag.get(lastval).remove(list.size() - 1);%0A                bag.get(lastval).add(idx);%0A                list.set(idx, lastval);%0A            %7D%0A            // Delete last one%0A            list.remove(list.size() - 1);%0A            if (bag.get(val).isEmpty()) %7B%0A                bag.remove(val);%0A            %7D%0A            return true;%0A        %7D%0A        return fals
 e;%0A 
@@ -1967,21 +1967,20 @@
  return 
-index
+list
 .get(ran
@@ -1993,13 +1993,12 @@
 Int(
-index
+list
 .siz

insert delete get random O(1) duplicates allowed