Oracle Interview Question
Software Engineer / DevelopersCountry: United States
If you know Java good and it is allowed to be lazy, we can reuse LinkedHashMap to achieve the desired behavior.
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.function.Function;
/**
* Created by sis on 6/4/15.
*/
public class CareerCup_5735022524891136 {
public static void main(String[] args) {
LRU<Integer, Integer> cache = new LRU<>(2, s -> {
System.out.println(s);
return s;
});
// new value
cache.apply(1);
// use cache
cache.apply(1);
// new value
cache.apply(2);
// new value, 1 is pushed from cache
cache.apply(3);
// use cache
cache.apply(2);
// new value because we removed 1 previously
cache.apply(1);
}
/**
* LRU implementation as a pattern 'Proxy'.
* @param <K> key type
* @param <V> value type
*/
public static final class LRU<K, V> implements Function<K, V> {
private final LinkedHashMap<K, V> map;
private final Function<K, V> realSubject;
public LRU(final int size, Function<K, V> realSubject) {
this.realSubject = realSubject;
this.map = new LinkedHashMap(16, 0.75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return this.size() == size + 1;
}
};
}
@Override
public V apply(K k) {
V v = map.get(k);
if (v == null) {
v = realSubject.apply(k);
map.put(k, v);
}
return v;
}
}
}
Use two data structures in tandem:
1) A "move to front" doubly linked list (that is, every time an element is accessed, it gets moved to front of the list.... each node of list represents a page in this case)
2) hash table mapping page identifiers of some sort to references in the double linked list
So here is how things work.
Assume only M pages can exist in the cache.
Now whenever a page is accessed, check to see if it's in the hash table.
Case 1: Cache Miss
----------------------------
If it is NOT, check if number of elements in the LIST is < M.
If it is < M, simply add the element to head of the list, and add corresponding entry in hash table, and move the page into cache.
If we already have M elements in the LIST, we must remove the LRU page.
Use tail pointer to the list and remove the last element there (i.e., delete it from the list, delete it from hash table AND delete the page from the cache itself).
Case 2: Cache hit
-------------------------
Page does exist in hash table. Follow the hash table ("value" is reference to node in doubly linked list) to get the node pointer. Now do some pointer magic to move the node to head of the list.
Everything is O(1).
Email me for opportunities in the Waterloo/Toronto, Ontario area.
- Ajeet June 05, 2015