Amazon | Phone | Map implementation with equal probability randomizer
Prazhant
964
AmazonHash TableInterview

Implement the following APIs

public Object get(key)
public void put(key, object)
public void delete(key)
public Object random()

The first three are straight forward implementation of hashmap while the last one had a tricky condition to it. The random method should return a random object from the map with equal probability amongst the values in the map.

My Solution:

public class RandomMap{

private Map<int, Object> map = new HashMap();
private List<int> keyList = new ArrayList<>();
private int size=0;

public Object get(int key){
	return map.get(key);
}

public void put(int key,Object value){
	if(! map.containsKey(key)){
		keyList.add(key);
	}
	map.put(key,value);
}


public void delete(int key){
	map.remove(key);
	keyList.remove(key);
}

public Object random(){

	int size = keyList.size();
	int randomIndex=getRandomIndex(0,size);
	int key = keyList.get(randomIndex);
	return map.get(key);
}
 public int getRandomIndex(int min, int max)
    {
        if (min > max || (max - min + 1 > Integer.MAX_VALUE)) {
            throw new IllegalArgumentException("Invalid range");
        }
 
        return new Random().nextInt(max - min + 1) + min;
    }

Please let me know if there are better ways to handle this problem.

Comments (2)