CareerCup

There are 3 primary requirements as I see it
1. Implementing Cache - LRU / MRU etc
2. Multi-Level Cache
3. Read Operation: constant time O(1) and Write operation: linear time O(N)

LRU cache can be quickly implemented using a LinkedHashMap and a multi-level cache can be implemented using 2 levels of LRU cache (LRU cache having value as another LRU cache).

The idea will be as follows:
=======
A multi-level cache will be an LRU cache with Key as level id (10, 20, 30 etc) and value will be another instance of an LRU cache. Value LRU cache will store user provided key and value.

Every time an add operation on the cache comes in, we check which level this key can go to. For example, say we have 3 levels, 10, 20 and 30. Any key that comes from a user, we mod that with 30 and decide which level the key value goes to.

Multi-level Cache is set up as follows
<key, Value>
<10, LRU Cache> --> any values between 0 to 9
<20, LRU Cache> --> any values between 10 to 19
<30, LRU Cache> --> any values between 20 to 29

If the input comes as key = 29 and value = 29,
Level = 29 % 30 is 29. So we add this key value to primary cache key = 10, 20 and 30

If the input comes as key = 35 and value = 35,
Level = 35 % 30 is 5. So we add this key value to primary cache key = 10 only.

Read Operation:
---------------
Read operation will always read from the lowest bucket as all the keys will eventually go to the lowest level.
Time complexity: 2 map get operations (one to get the LRU cache for the lowest level and 2nd to get the actual value from value LRU cache) so its 2 * O(1) = O(1)

Write operation:
----------------
At worst, it writes to all levels: based on the number of levels, this operation can be O(N)


Here are the code examples:

LRU Cache:
========== 
This is a LRU cache implementation

public class LRUCache<K,V> extends LinkedHashMap<K,V> {
	int size;
	LRUCache(int capacity){
		super(16, 0.75f, true); //true is for access order instead of insertion order
		this.size = capacity;
	}
	protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
		return size() > size;
	}
}


MultiLevel Cache:
=============
This is a multi level cache implementation which internally uses the above LRU cache.

public class MLCache {
	static MLCache instance;
	private static LRUCache<Integer, LRUCache<Integer, Integer>> multiCache = null;
	
	private MLCache() {}
	
	public static synchronized MLCache getInstance(){
		if(instance == null) {
			instance = new MLCache();
			multiCache = new LRUCache<Integer, LRUCache<Integer, Integer>>(3);
			multiCache.put(10, new LRUCache<Integer, Integer>(30)); //this size needs to be more so that all keys can go here without getting removed
			multiCache.put(20, new LRUCache<Integer, Integer>(3));
			multiCache.put(30, new LRUCache<Integer, Integer>(3));
		}
		return instance;
	}
	
	public int get(int key) {
		return multiCache.get(10).get(key); //we need to make sure LRU size for the lowest cache is really large so that all keys can be stored there
	}
	
	public void add(int key, int value) {
		List<Integer> levelList = getLevel(key);
		for(Integer keyList: levelList) {
			multiCache.get(keyList).put(key, value);
		}
	}
	
	private static List<Integer> getLevel(int key) {
		int modValue = key % 30;
		List<Integer> a = new ArrayList<>();
		if(modValue < 10) {a.add(10);}
		if(modValue >= 10 && modValue < 20) {a.add(20); a.add(10);}
		if(modValue >= 20 && modValue < 30) {a.add(30); a.add(20); a.add(10);}
		
		return a;
	}
}

Test Class:
=========
public class CacheTest {

	public static void main(String[] args) {
		MLCache cache = MLCache.getInstance();
		cache.add(1,1);
		cache.add(2,2);
		cache.add(3,3);
		System.out.println(cache.get(2));
		cache.add(4,4);
		cache.add(29,29);
		cache.add(35,35);
		System.out.println(cache.get(35));
	}
}

Here is the complete implementation of multi level cache

IMultiLevelCache api to client
----------------------

/**
 * Author: Nitin Gupta(nitin.gupta@walmart.com)
 * Date: 15/04/19
 * Description:
 */
public interface IMultiLevelCache<K extends CacheKey, V> {

    /**
     * this will add the element at a particular level along with from top to this level
     *
     * @param key
     * @param value
     */
    void add(K key, V value);

    Collection<V> remove(K key);

    V get(K key);

    void update(K key, V value);

    void show();
}


Cache key agreement 
---------------------

/**
 * Author: Nitin Gupta(nitin.gupta@walmart.com)
 * Date: 15/04/19
 * Description:
 */
public class CacheKey {

    private final int levelId;

    public CacheKey(int levelId) {
        this.levelId = levelId;
    }

    public int getLevelId() {
        return levelId;
    }

}

//Base cache using linkedHashMap LRU

/**
 * Author: Nitin Gupta(nitin.gupta@walmart.com)
 * Date: 15/04/19
 * Description:
 */
public class LRUCache<K, V> extends LinkedHashMap<K, V> implements Serializable {


    //Since this is lru cache, so if this cache get filed (over capacity), it will kick least recently used item.
    private int capacity;


    public LRUCache(int capacity) {
        // Call constructor of LinkedHashMap with accessOrder set to true to
        // achieve LRU Cache behavior
        super(capacity, 1.0f, true);
        this.capacity = capacity;
    }

    // Remove the eldest element whenever size of cache exceeds the capacity
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return (this.size() > capacity);
    }


}

//Multi level cache implementation 

/**
 * Author: Nitin Gupta(nitin.gupta@walmart.com)
 * Date: 15/04/19
 * Description:
 */
public final class MultiLevelCache<K extends CacheKey, V> implements IMultiLevelCache<K, V> {

    private int levels = 1;
    private int capacity;
    private Map<Integer, LRUCache<K, V>> multiLevelCache;
    private final int levelStart;
    private final int levelEnd;


    public MultiLevelCache(int levels, int capacity) {
        this.multiLevelCache = new HashMap<>(levels);
        this.levels = levels;
        this.capacity = capacity;
        this.levelStart = 10;
        this.levelEnd = levelStart * levels;
        init();
    }

    public MultiLevelCache(int capacity) {
        this.multiLevelCache = new HashMap<>(levels);
        this.levels = 1;
        this.capacity = capacity;
        this.levelStart = 10;
        this.levelEnd = levelStart * levels;
        init();
    }

    private final void init() {
        //Init all the cache at each level
        for (int i = levelStart; i <= levelEnd; i += levelStart) {
            multiLevelCache.put(i, new LRUCache<>(capacity));
        }

    }


    private final Set<Integer> getDesiredLevels(int ownLevel) {

        Set<Integer> desiredLevels = new HashSet<>();

        int expectedLevel = ownLevel % levelEnd;

        if (expectedLevel < levelStart) {
            desiredLevels.add(levelStart);
            return desiredLevels;
        }

        for (int l = levelStart; l <= levelEnd; l += levelStart) {


            if (expectedLevel > l) {
                desiredLevels.add(l);
            } else if (expectedLevel <= l) {
                desiredLevels.add(l);
                break;
            }

        }

        return desiredLevels;
    }

    @Override
    public void add(K key, V value) {
        int level = key.getLevelId();
        Set<Integer> desiredLevels = getDesiredLevels(level);

        for (Integer levelId : desiredLevels) {
            multiLevelCache.get(levelId).put(key, value);
        }


    }

    @Override
    public Collection<V> remove(K key) {
        List<V> values = new LinkedList<>();
        int level = key.getLevelId();
        Set<Integer> desiredLevels = getDesiredLevels(level);

        for (Integer levelId : desiredLevels) {
            if (multiLevelCache.get(levelId).containsKey(key)) {
                values.add(multiLevelCache.get(levelId).remove(key));
            }
        }

        return values;

    }

    @Override
    public V get(K key) {
        for (Integer levelId : multiLevelCache.keySet()) {
            if (multiLevelCache.get(levelId).containsKey(key)) {
                return multiLevelCache.get(levelId).get(key);
            }
        }

        return null;

    }

    @Override
    public void update(K key, V value) {
        for (Integer levelId : multiLevelCache.keySet()) {
            if (multiLevelCache.get(levelId).containsKey(key)) {
                multiLevelCache.get(levelId).put(key, value);
            }
        }
    }

    @Override
    public void show() {
        for (Integer levelId : multiLevelCache.keySet()) {

            System.out.println("Level:" + levelId + " value: " + multiLevelCache.get(levelId).values().stream().collect(Collectors.toList()));

        }
    }
}

Sample Test:

/**
 * Author: Nitin Gupta(nitin.gupta@walmart.com)
 * Date: 15/04/19
 * Description:
 */
public class Driver {


    static class MyCacheKey extends CacheKey {

        String key;

        public MyCacheKey(int levelId, String key) {
            super(levelId);
            this.key = key;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            MyCacheKey that = (MyCacheKey) o;
            return Objects.equals(key, that.key);
        }

        @Override
        public int hashCode() {
            return Objects.hash(key);
        }
    }

    static class MyCacheValue<T> {
        T value;

        public MyCacheValue(T value) {
            this.value = value;
        }

        @Override
        public String toString() {
            return "{" +
                    "value=" + value +
                    '}';
        }
    }

    public static void main(String args[]) {

        IMultiLevelCache<MyCacheKey, MyCacheValue<String>> multiLevelCache = new MultiLevelCache<>(3, 50);


        multiLevelCache.add(new MyCacheKey(29, "Key1"), new MyCacheValue<>("Key1Value"));
        System.out.println(multiLevelCache.get(new MyCacheKey(20, "Key1")));
        multiLevelCache.add(new MyCacheKey(80, "Key2"), new MyCacheValue<>("Key2Value"));
        System.out.println(multiLevelCache.get(new MyCacheKey(20, "Key2")));
        multiLevelCache.add(new MyCacheKey(900, "Key3"), new MyCacheValue<>("Ke31Value"));
        System.out.println(multiLevelCache.get(new MyCacheKey(20, "Key3")));
        multiLevelCache.add(new MyCacheKey(290, "Key4"), new MyCacheValue<>("Key4Value"));
        System.out.println(multiLevelCache.get(new MyCacheKey(20, "Key4")));
        multiLevelCache.add(new MyCacheKey(12, "Key5"), new MyCacheValue<>("Key5Value"));
        System.out.println(multiLevelCache.get(new MyCacheKey(20, "Key5")));
        multiLevelCache.add(new MyCacheKey(9, "Key6"), new MyCacheValue<>("Key6Value"));
        System.out.println(multiLevelCache.get(new MyCacheKey(20, "Key6")));
        multiLevelCache.add(new MyCacheKey(121, "Key7"), new MyCacheValue<>("Key7Value"));
        System.out.println(multiLevelCache.get(new MyCacheKey(20, "Key7")));


        System.out.println(multiLevelCache.remove(new MyCacheKey(20, "Key1")));

        multiLevelCache.show();

    }
}

Output:

{value=Key1Value}
{value=Key2Value}
{value=Ke31Value}
{value=Key4Value}
{value=Key5Value}
{value=Key6Value}
{value=Key7Value}
[{value=Key1Value}, {value=Key1Value}]
Level:20 value: [{value=Key2Value}, {value=Key4Value}, {value=Key5Value}]
Level:10 value: [{value=Key2Value}, {value=Ke31Value}, {value=Key4Value}, {value=Key5Value}, {value=Key6Value}, {value=Key7Value}]
Level:30 value: [{value=Key1Value}]