# Java HsahMap and Queue solution accepted

• Explanation:
numToInd: map, use queue to store the indexes
indToNum: map, store ind to numbers
deletedInd: queue, use to store deleted indexes. This is to help the get random function. If there are a lot of indexes deleted, the get random function can be very inefficient. If we can reuse the deleted indexes, then the get random function can be slightly better. But this does make the code a slightly complicated.

public class RandomizedCollection {

``````private Map<Integer,Queue<Integer>> numToInd = new HashMap<>();
private Map<Integer,Integer> indToNum = new HashMap<>();
private Queue<Integer> deletedInd = new LinkedList<>();
private int nextInd;
private Random random = 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) {
// get the possible index
int ind = 0;
if (deletedInd.size() != 0) ind = deletedInd.poll();
else {
ind = nextInd;
nextInd ++;
}
indToNum.put(ind,val); // put ind to num in map
// add index in the index queue if num exist
if (numToInd.containsKey(val)) {
return false;
}
// create new queue if the number does not exist
numToInd.put(val,temp);
return true;
}

/** Removes a value from the collection. Returns true if the collection contained the specified element. */
public boolean remove(int val) {
if (!numToInd.containsKey(val)) return false;
Queue<Integer> inds = numToInd.get(val);
if (inds.size() == 1) numToInd.remove(val);
indToNum.remove(inds.poll());
return true;
}

/** Get a random element from the collection. */
public int getRandom() {
int ind = random.nextInt(nextInd);
while (!indToNum.containsKey(ind)) ind = random.nextInt(nextInd);
return indToNum.get(ind);
}
``````

}

• @pigabc Not sure your getRamdon() is avg O(1)..
if the nextInt is 100,000 and there is only one int left in the queue, then this getRamdon() only has 1/100,000 chance to get the only int and stuck in the while loop for a long time.

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