Design a key-value store (Phone Interview)


  • 1
    J

    Design a key-value store to support methods like get, put and getRandom.

    getRandom -> Should generate a random number and return the key-value stored at this random number


  • 1
    M

    Use a HashMap for storing the key-value pair, but have a wrapper on top of value to store an index pointing to the index of a list where the key is stored. To implement getRandom, use the ArrayList to keep track of available keys. getRandom would return a random key (using a random index using Random nextInt() function)

    public class RandomDataStructure {
    
    	private static class Value {
    		private int value, index;
    
    		public Value(int value, int index) {
    			this.value = value;
    			this.index = index;
    		}
    	}
    
    	private HashMap<Integer, Value> internalMap;
    	private ArrayList<Integer> availableKeys;
    	private Random rand;
    
    	public RandomDataStructure() {
    		this(10);
    	}
    
    	public RandomDataStructure(int size) {
    		if (size < 1)
    			throw new IllegalArgumentException("Illegal Capacity: " + size);
    		internalMap = new HashMap<Integer, Value>(size);
    		availableKeys = new ArrayList<Integer>(size);
    		rand = new Random();
    	}
    
    	public int size() {
    		return internalMap.size();
    	}
    
    	public void insert(int key, int value) {
    		Value v = internalMap.get(key);
    		if (v == null) {
    			availableKeys.add(key);
    			internalMap.put(key, new Value(value, availableKeys.size() - 1));
    		} else {
    			internalMap.put(key, new Value(value, v.index));
    		}
    	}
    
    	public void delete(int key) {
    		Value v = internalMap.remove(key);
    		if (v != null) {
    			if (v.index != availableKeys.size() - 1)
    				availableKeys.set(v.index, availableKeys.get(availableKeys.size() - 1));
    			availableKeys.remove(availableKeys.size() - 1);
    		}
    	}
    
    	public int get(int key) {
    		Value v = internalMap.get(key);
    		if (v == null)
    			throw new NoSuchElementException(String.format("ERROR: Key %1$d does not exist!", key));
    		return v.value;
    	}
    
    	public int getRandomKey() {
    		if (internalMap.size() == 0)
    			throw new NoSuchElementException("ERROR: Data Structure is empty!");
    		return availableKeys.get(rand.nextInt(availableKeys.size()));
    	}
    
    }
    

Log in to reply
 

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