Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
import java.util.LinkedHashMap;
import java.util.Map;
public class LRUCacheUsingLinkedHashMap {
private static int CACHE_SIZE = 4;
public static void main(String[] args) {
// accessOrder is true, so whenever any page gets changed or accessed, // its order will change in the map,
LinkedHashMap<Integer,String> lruCache = new LinkedHashMap<Integer,String>(CACHE_SIZE, .75F, true) {
private static final long serialVersionUID = 1L;
protected boolean removeEldestEntry(Map.Entry<Integer,String> eldest) {
return size() > CACHE_SIZE;
}
};
lruCache.put(0, "0");
lruCache.put(1, "1");
lruCache.put(2, "2");
System.out.println(lruCache);
System.out.println("Read 1 from the cache, after reading 1 will moved to the end of cache");
lruCache.get(1);
System.out.println(lruCache);
lruCache.put(3, "3");
System.out.println(lruCache + " , After first 4");
lruCache.put(4, "4");
System.out.println(lruCache);
System.out.println("Read 2 from the cache, after reading 2 will moved to the end of cache");
lruCache.get(2);
System.out.println(lruCache);
lruCache.put(5, "5");
System.out.println(lruCache);
lruCache.put(6, "6");
System.out.println(lruCache);
}
}
{0=0, 1=1, 2=2}
Read 1 from the cache, after reading 1 will moved to the end of cache
{0=0, 2=2, 1=1}
{0=0, 2=2, 1=1, 3=3} , After first 4
{2=2, 1=1, 3=3, 4=4}
Read 2 from the cache, after reading 2 will moved to the end of cache
{1=1, 3=3, 4=4, 2=2}
{3=3, 4=4, 2=2, 5=5}
{4=4, 2=2, 5=5, 6=6}
Use a queue of length 10. And a hash table with key value
The hash will have the key and the corresponding element number in the queue
The value will be stored at the element number in the queue.
Put will check if key exists will remove that element from queue and add it to last. If length 10 the will remove first element remove its key from hash and add that element in the last
Linked Hashmap will, apart from doing its basic work i.e, storing key value pairs, also keep track of insertion order of they keys.
LinkedHashmap knows the order in which keys were added.
So if you know firstLink and lastLink of the map then,
both your get and put operations will have O(1) complexity.
get(key, value)
- Return the map.get(key) - O(1),
- Remove it from map (link.previous = link.next) and put it back in the map making it the first element of the map.
put(key, value)
- if the list is full, then lastElement.previous.next = null; (making the second last element as the last element of the map)
- add the new element and make it the firstElement of the map.
Using priorityQueue for caching. HashMap to maintain keyset and perform faster put and get operation. setting priority based on the time of use.
package com.amazon.practice;
import java.util.Calendar;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
class LRU<K,V> implements Comparable<LRU<K,V>>{
private long recentUseTime = Calendar.getInstance().getTimeInMillis();
private K key;
private V value;
@Override
public int compareTo(LRU<K, V> arg0) {
// TODO Auto-generated method stub
return Double.compare(this.recentUseTime, arg0.recentUseTime);
}
public void setPriority(long p){
this.recentUseTime = p;
}
public LRU(K key, V value){
this.key = key;
this.value = value;
}
public V getValue(){
return this.value;
}
public K getKey(){
return this.key;
}
public void setValue(V v){
this.value = v;
}
public void setKey(K k){
this.key = k;
}
public String toString(){
return "[ "+this.key+" - "+this.value+" ]";
}
}
class LRUCache<K,V>{
private Queue<LRU<K,V>> cache = new PriorityQueue<LRU<K,V>>();
private Map<K,LRU<K,V>> keySet = new HashMap<K,LRU<K,V>>();
public void put(K key,V value){
if(this.keySet.containsKey(key)){
(this.keySet.get(key)).setPriority(Calendar.getInstance().getTimeInMillis());
this.cache.remove(this.keySet.get(key));
this.cache.add(this.keySet.get(key));
}else{
LRU<K,V> lruNode = null;
if(this.cache.size()==10){
lruNode = this.cache.peek();
}
if(lruNode!=null){
keySet.remove(lruNode.getKey());
lruNode.setPriority(0);
lruNode.setKey(key);
lruNode.setValue(value);
}else{
lruNode = new LRU<K,V>(key,value);
this.cache.add(lruNode);
}
this.keySet.put(key, lruNode);
}
}
public V get(K key){
return (this.keySet.get(key)).getValue();
}
public void printCache(){
Iterator<LRU<K,V>> it = cache.iterator();
System.out.println();
while(it.hasNext())
System.out.print(it.next().toString());
System.out.println();
}
}
public class LRUCacheTest {
public static void main(String[] arg){
LRUCache<String,String> cache= new LRUCache<String,String>();
cache.put("one", "one");
cache.put("two", "two");
cache.put("three", "three");
cache.put("four", "four");
cache.put("five", "five");
cache.put("six", "six");
cache.put("seven", "seven");
cache.put("eight", "eight");
cache.put("nine", "nine");
cache.put("ten", "ten");
cache.printCache();
cache.put("eleven", "eleven");
cache.printCache();
cache.put("seven", "seven");
cache.printCache();
cache.put("eleven", "eleven");
cache.printCache();
}
}
User unordered_map only..whenever size is greater than 10 then remove the first element and insert it in last . if element already exists then remove it and insert it into last.
std::unordered_map<std::string,int> mymap;
void addData(std::string &key, int value)
{
std::unordered_map<std::string,int>::const_iterator got = mymap.find (key);
if ( got == mymap.end() )
{
std::cout << "not found";
if( mymap.size() >= 10)
{
mymap.erase ( mymap.begin() );
mymap.insert( key,value);
}
}
else
{
mymap.erase(key);
mymap.insert( key,value);
}
}
import java.util.LinkedHashMap;
import java.util.Map;
public class LRUCa<K, V> {
private final int CACHE_SIZE;
private final int initialCapacity = 16;
private final float loadFactor = 0.75F;
public LRUCa(int size) {
this.CACHE_SIZE = size;
}
public LinkedHashMap<K, V> cache = new LinkedHashMap<K, V>(initialCapacity, loadFactor, true) {
private static final long serialVersionUID = 1L;
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
boolean ifRemove = this.size() > CACHE_SIZE;
return ifRemove;
}
};
public synchronized void put(K key, V value) {
if (value == null)
return;
else
cache.put(key, value);
}
public synchronized V get(K key) {
return cache.get(key);
}
public synchronized void clear() {
cache.clear();
}
public static void main(String[] args) {
LRUCache<String, String> c = new LRUCache<String, String>(3);
c.put("1", "one"); // 1
c.put("2", "two"); // 2 1
c.put("3", "three"); // 3 2 1
c.put("4", "four"); // 4 3 2
c.get("3");
for (Map.Entry<String, String> e : c.cache.entrySet()) {
System.out.println(e.getKey() + " : " + e.getValue());
}
}
}
Here is compact implementation using LinkedHashMap ... hope this helps ...
public class LRUCache<String, Integer> extends LinkedHashMap<String, Integer> {
int capacity ;
public void setCapacity(int cap){
this.capacity = cap;
}
public LRUCache(int cap) {
super(cap, 1f, true);
setCapacity(cap);
}
public boolean addToCache(String key, Integer val){
if(super.size() < this.capacity)
this.put(key,val);
else{
super.remove(getLeastAccessedEntryKey());
this.put(key,val);
}
System.out.println(this);
return true;
}
public Integer getElement(String key){
if(this.get(key) == null)
return null;
return (Integer)this.get(key);
}
public String getLeastAccessedEntryKey()
{
String key = null;
Set<String> keySet= this.keySet();
Iterator< String> itr = keySet.iterator();
if(itr.hasNext()){
key = itr.next();
}
return key;
}
void printMap(){
System.out.println(this);
}
}
public interface LRUCache<K,V> {
V get(K key);
void put(K key, V value);
}
public class LRUCacheImpl<K,V> implements LRUCache<K, V> {
HashMap<K,V> hm;
LinkedList<K> order;
private static final int CAPACITY = 10;
public LRUCacheImpl(){
hm = new HashMap<K,V>(CAPACITY);
order = new LinkedList<>();
}
@Override
public V get(K key) {
V val = hm.get(key);
if(val != null){
promote(key);
}
return val;
}
@Override
public void put(K key, V value) {
if(hm.containsKey(key)){
hm.put(key, value);
promote(key);
} else {
if(hm.size() >= CAPACITY){
hm.remove(order.removeLast());
}
hm.put(key, value);
order.addFirst(key);
}
}
private void promote(K key){
order.removeFirstOccurrence(key);
order.addFirst(key);
}
}
public class LRUCacheTest {
LRUCache<Integer, String> cut;
private final static String ZERO = "ZERO";
private final static String ONE = "ONE";
private final static String TWO = "TWO";
private final static String THREE = "THREE";
private final static String FOUR = "FOUR";
private final static String FIVE = "FIVE";
private final static String SIX = "SIX";
private final static String SEVEN = "SEVEN";
private final static String EIGHT = "EIGHT";
private final static String NINE = "NINE";
private final static String TEN = "TEN";
@Before
public void initialize(){
cut = new LRUCacheImpl<Integer, String>();
}
@Test
public void shouldPut() {
cut.put(0, ZERO);
assertEquals(cut.get(0), ZERO);
}
@Test
public void shouldGet() {
cut.put(0, ZERO);
cut.put(1, ONE);
cut.put(2, TWO);
cut.put(3, THREE);
cut.put(4, FOUR);
assertEquals(cut.get(3), THREE);
assertEquals(cut.get(2), TWO);
assertEquals(cut.get(1), ONE);
assertEquals(cut.get(4), FOUR);
}
@Test
public void shouldRemoveLeastRecent() {
cut.put(0, ZERO);
cut.put(1, ONE);
cut.put(2, TWO);
cut.put(3, THREE);
cut.put(4, FOUR);
cut.put(5, FIVE);
cut.put(6, SIX);
cut.put(7, SEVEN);
cut.put(8, EIGHT);
cut.put(9, NINE);
cut.put(10, TEN);
assertNull(cut.get(0));
assertEquals(cut.get(10), TEN);
}
@Test
public void shouldMarkLastRecentWhenRead() {
cut.put(0, ZERO);
cut.put(1, ONE);
cut.put(2, TWO);
cut.put(3, THREE);
cut.put(4, FOUR);
cut.put(5, FIVE);
cut.put(6, SIX);
cut.put(7, SEVEN);
cut.put(8, EIGHT);
cut.put(9, NINE);
cut.get(0);
cut.put(10, TEN);
assertNotNull(cut.get(0));
assertNull(cut.get(1));
assertEquals(cut.get(10), TEN);
}
@Test
public void shouldMarkLastRecentWhenOverridden() {
cut.put(0, ZERO);
cut.put(1, ONE);
cut.put(2, TWO);
cut.put(3, THREE);
cut.put(4, FOUR);
cut.put(5, FIVE);
cut.put(6, SIX);
cut.put(7, SEVEN);
cut.put(8, EIGHT);
cut.put(9, NINE);
cut.put(0, NINE);
cut.put(10, TEN);
assertNotNull(cut.get(0));
assertNull(cut.get(1));
assertEquals(cut.get(10), TEN);
}
}
Using a struct and a list:
{
struct element
{
int key;
int value;
};
class LRUcache
{
private:
int max_size;
int current_size;
list<element*> l;
public:
LRUcache()
{
max_size = 10;
current_size = 0;
}
int get(int key)
{
int value = -INT32_MAX;
for(list<element*>::iterator it = l.begin(); it != l.end(); it++)
{
if((*it)->key == key)
{
value = (*it)->value;
list<element*>::iterator aux = it;
l.erase(it);
l.push_front(*aux);
return value;
}
}
return value;
}
void put(int key, int value)
{
element * e = new element;
e->key = key;
e->value = value;
if(current_size == max_size)
{
cout << "replacing oldest value: " << l.back()->key << " " << l.back()->value << endl;
delete l.back();
l.pop_back();
current_size--;
}
l.push_front(e);
current_size++;
}
};
}
The problem requires us to maintain a searchable queue since I not only have to access the LRU, but also search for a key value in the queue optimally.
One way to attain O(log(n)) search with a well ordered queue is to assign a running number to every item in the queue, which is stored against the hash value of the key.
Let us say for cache size of 3, my input is A, B, C, B.
My queue at the end of 4th input will look like: A, C, B
Searching for B linearly is very expensive. One way to get O(log n) is to add ordered numbering to this queue. One way to do is by assigning every item that is added to the queue a number +1 of the number assigned to MRU.
Thus for this queue, I will have: A1, B2, C3, B4
My queue at the end of 4th input will look like: A1, C3, B4. My hash will look like:
A(1):A Value
B(4): B Value
C(3); C Value
Thus while accessing any key value, I will know the number assigned to it in the queue, and since the way numbering is assigned is in incremental order, I will be able to located that in O(log n) to be able to put it at the end of the queue. The item will then get a new number and the hash key will be updated with that number as well.
import java.util.Map;
import java.util.TreeMap;
public class LRU {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Map<Integer,Integer> lruMap = new TreeMap<Integer, Integer>();
// By Default all element has 1 occurance in map.
lruMap.put(0, 1);
lruMap.put(3, 1);
lruMap.put(4, 1);
lruMap.put(6, 1);
lruMap.put(9, 1);
lruMap.put(8, 1);
lruMap.put(7, 1);
lruMap.put(2, 1);
lruMap.put(5, 1);
lruMap.put(1, 1);
// new entry to Map (here I am making 15 as new entry
int addNew = 15;
Boolean flag = true;
Map.Entry<Integer, Integer> min = null;
// Checking if map has same key entry then I am incrementing the value in Map.
for(Map.Entry<Integer, Integer> entry : lruMap.entrySet()){
if(entry.getKey().equals(addNew)){
lruMap.put(addNew, entry.getValue()+1);
flag = false;
}
}
// If Map has new entry then I am removing element having minimum value.
if(flag){
for(Map.Entry<Integer, Integer> entry : lruMap.entrySet()){
if(min == null || min.getValue() > entry.getValue()){
min = entry;
}
}
lruMap.remove(min.getKey());
lruMap.put(addNew, 1);
}
for(Map.Entry<Integer, Integer> entry : lruMap.entrySet()){
System.out.println("Key "+ entry.getKey() +" Value "+ entry.getValue());
}
}
}
Apparently, the simplest possible implementation is,
public class LRUCache extends LinkedHashMap<Integer, String>{
private int cacheSize;
public LRUCache(int size) {
super(size, 0.75f, true);
this.cacheSize = size;
}
@Override
protected boolean removeEldestEntry(
java.util.Map.Entry<Integer, String> eldest) {
// remove the oldest element when size limit is reached
return size() > cacheSize;
}
}
package zhang.juanyong.interview.amazon;
import java.util.Collections;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.TreeMap;
import org.apache.commons.lang.math.RandomUtils;
/**
*
* @author Juanyong
*
* Implement LRU cache of size 10 which can store Key, Value pair.
* (get(key) & put(key,value) methods) - If we try to add 11th element,
* the least recently used element should get removed. - If key already
* present, overwrite it and mark it as most recently used.
*/
public class LRUCache2<V> {
private final int capacity;
private Map<V, Long> cache = new LinkedHashMap<V, Long>() {
private static final long serialVersionUID = 5592193692539799835L;
protected boolean removeEldestEntry(Map.Entry<V, Long> eldest) {
return size() > capacity;
}
};
public LRUCache2(int size) {
super();
this.capacity = size;
}
public void put(V obj) {
try {
Thread.sleep(1);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
Long timestamp = System.currentTimeMillis();
cache.put(obj, timestamp);
}
public void printCache() {
TreeMap<Long, V> sortedMap = new TreeMap<Long, V>();
for (V key : cache.keySet()) {
sortedMap.put(cache.get(key), key);
}
for (Long key : sortedMap.descendingKeySet()) {
System.out.println(key + " = " + sortedMap.get(key));
}
}
public static void main(String[] args) {
int[] arr = new int[20];
LRUCache2<Integer> lruCache = new LRUCache2<Integer>(10);
PriorityQueue<Integer> pQ = new PriorityQueue<Integer>(5,
Collections.reverseOrder());
for (int i = 0; i < arr.length; i++) {
int value = RandomUtils.nextInt(10000);
arr[i] = value;
lruCache.put(value);
pQ.add(value);
}
lruCache.printCache();
System.out.println(pQ);
}
}
The best solution would be :
import java.util.LinkedHashMap;
import java.util.Map;
public LRUCache<K, V> extends LinkedHashMap<K, V> {
private int cacheSize;
public LRUCache(int cacheSize) {
super(16, 0.75, true);
this.cacheSize = cacheSize;
}
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() >= cacheSize;
}
}
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
@SuppressWarnings("serial")
class LRUCacheImplement<K, V> extends LinkedHashMap<K, V> {
private int cacheSize;
public LRUCacheImplement(int cacheSize) {
super(16, (float) 0.75, true);
this.cacheSize = cacheSize;
}
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > cacheSize;
}
public void displayEntries(){
Iterator itr=this.entrySet().iterator();
while(itr.hasNext())
{
System.out.println(itr.next());
}
}
}
C++ Code (Queue with DLL and Hash Map)
- R@M3$H.N May 07, 2014