Google Interview Question
Java DevelopersCountry: United States
Nice write up !! Few things I would like to point out :
+ if you are reading from one cache and writing to all 3 is not a real world scenario. It doesnt give you anything, whats the point of maintaining 3 cache then.
+ Multilevel cache has to be same as hierarchical means small capacity cache -> then bigger cache and then biggest cache
+ First cache should be faster since its close. and then second and then third.
+ writing and reading should happen at all 3 cache level.
Great write up, i feel there are multiple follow up questions;
1. is it possible that top level cache gets full and spill over to next level cache ?
if so then we need to check the key in all below level cache until we find it or we don't find till end
2. What happen when duplicate key comes, should we update the cache at all level where this key is present (since in q 1 it can spill over)
3. do we need to provide any remove from cache method ?
and many more
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}]
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:
- Saurabh July 06, 2018