Google Interview Question for Java Developers


Country: United States




Comment hidden because of low score. Click to expand.
1
of 1 vote

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));
	}
}

- Saurabh July 06, 2018 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More