Ebay Interview Question Software Engineer / Developers
0of 0 votesDesign LRU Cache
Team: Traffic
Country: United States
Interview Type: In-Person
Its only for Java Implementation. However, its very easy to implement it using linkedlist.
/**
* Least Recently Used Cache Implementation.
* Date: 9/19/13
* Time: 8:20 PM
*/
public class LRUCache extends LinkedHashMap {
private int maxSize;
public LRUCache(int maxSize) {
super(maxSize, 0.75F, true);
this.maxSize = maxSize;
}
public boolean removeEldestEntry(Map.Entry map) {
return super.size() > maxSize;
}
}
This is a good idea, however your code seems to lack one thing: LinkedHashMap does not change the order of the item that has already been inserted, so method put() must be @Override[n] to first remove, and then put the element if it is already in the map. Also get(K key) must be overridden.
package my.answers;
import java.util.*;
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
private int maxSize;
public LRUCache(int maxSize) {
super(maxSize, 0.75F, true);
this.maxSize = maxSize;
}
@Override
public V put(K key, V value){
remove(key);
return super.put(key, value);
}
@Override
public V get(Object key) {
if( containsKey(key) ) {
V val = super.get(key);
remove(key);
return super.put( (K) key, val);
}
return null;
}
@Override
public boolean removeEldestEntry(Map.Entry<K, V> map) {
return super.size() > maxSize;
}
}
class Node {
private int data;
private int priority;
Node next;
public Node (int data){
this.data=data;
this.priority = 0;
}
public void incrementPriority (){
priority= priority+1;
}
public int getPriority() {
return priority;
}
public int getData() {
return data;
}
}
public class LRUCache {
private Node firstNode = new Node (-1);
private Node currentNode;
public LRUCache() {
// TODO Auto-generated constructor stub
}
public static void main(String[] args) {
}
public int addNode (int data){
Node node = new Node(data);
LinkNode(node);
return node.getData();
}
public void LinkNode (Node node){
if (currentNode != null) {
currentNode.next=node;
}
else {
currentNode = firstNode;
currentNode.next = node;
}
}
public void incrementPriority (Node node){
node.incrementPriority();
RearrangeListPosition(node);
}
private void RearrangeListPosition(Node node) {
// Rearrange the position according to the priority.
}
}
package util;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentLinkedQueue;
/**
* Class Name: ConcurrentLRUCache.java
*
* Simple Cache library(LRU cache)-Generic
*
*/
public class ConcurrentLRUCache<Key, Value> {
private final int maxSize;
private ConcurrentHashMap<Key, Value> map;
private ConcurrentLinkedQueue<Key> queue;
public ConcurrentLRUCache(final int maxSize) {
this.maxSize = maxSize;
map = new ConcurrentHashMap<Key, Value>(maxSize);
queue = new ConcurrentLinkedQueue<Key>();
}
/**
* @param key
* - may not be null!
* @param value
* - may not be null!
*/
public void put(final Key key, final Value value) {
if (map.containsKey(key)) {
queue.remove(key); // remove the key from the FIFO queue
}
while (queue.size() >= maxSize) {
Key oldestKey = queue.poll();
if (oldestKey!=null) {
map.remove(oldestKey);
}
}
queue.add(key);
map.put(key, value);
}
/**
* @param key
* - may not be null!
* @return the value associated to the given key or null
*/
public Value get(final Key key) {
return map.get(key);
}
public Boolean hasKey(final Key key) {
if (map.containsKey(key))
return true;
return false;
}
public void removeOldestByTime(final Key oldestKey) {
map.remove(oldestKey);
queue.remove(oldestKey);
}
}
package util;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentLinkedQueue;
/**
* Class Name: ConcurrentLRUCache.java
*
* Simple Cache library(LRU cache)-Generic
*
*/
public class ConcurrentLRUCache<Key, Value> {
private final int maxSize;
private ConcurrentHashMap<Key, Value> map;
private ConcurrentLinkedQueue<Key> queue;
public ConcurrentLRUCache(final int maxSize) {
this.maxSize = maxSize;
map = new ConcurrentHashMap<Key, Value>(maxSize);
queue = new ConcurrentLinkedQueue<Key>();
}
/**
* @param key
* - may not be null!
* @param value
* - may not be null!
*/
public void put(final Key key, final Value value) {
if (map.containsKey(key)) {
queue.remove(key); // remove the key from the FIFO queue
}
while (queue.size() >= maxSize) {
Key oldestKey = queue.poll();
if (oldestKey!=null) {
map.remove(oldestKey);
}
}
queue.add(key);
map.put(key, value);
}
/**
* @param key
* - may not be null!
* @return the value associated to the given key or null
*/
public Value get(final Key key) {
return map.get(key);
}
public Boolean hasKey(final Key key) {
if (map.containsKey(key))
return true;
return false;
}
public void removeOldestByTime(final Key oldestKey) {
map.remove(oldestKey);
queue.remove(oldestKey);
}
}
C++ Code (Queue with DLL and Hash Map)
- R@M3$H.N January 08, 2014struct LRUCacheNode { int key; int value; LRUCacheNode* prev; LRUCacheNode* next; LRUCacheNode(): key(0),value(0),next(NULL),prev(NULL) { } ; } ; class LRUCache{ private: hash_map< int, LRUCacheNode* > Map; LRUCacheNode * Head; LRUCacheNode * Tail; int Capacity ; int Count ; public: LRUCache(int capacity) { Capacity = capacity ; Count = 0 ; Head = new LRUCacheNode; Tail = new LRUCacheNode; Head->prev = NULL; Head->next = Tail; Tail->next = NULL; Tail->prev = Head; } ~LRUCache ( ) { delete Head; delete Tail; } int get(int key) { LRUCacheNode* node = Map[key]; if(node) { DetachNode(node); AttachNodeToFront(node); return node->value; } else return -1 ; } void set(int key, int value) { LRUCacheNode* node = Map[key]; if(node) { DetachNode(node); node->value = value; AttachNodeToFront(node); } else{ LRUCacheNode* node = new LRUCacheNode ; if ( Capacity == Count ) { // If Cache is Full RemoveLRUNode ( key ) ; } node->key = key; node->value = value; Map[key] = node; AttachNodeToFront(node); Count++ ; } } private: void RemoveLRUNode ( int key ) { LRUCacheNode* node = Tail->prev; DetachNode(node); Map.erase(node->key); Count-- ; } void DetachNode(LRUCacheNode* node) { node->prev->next = node->next; node->next->prev = node->prev; } void AttachNodeToFront(LRUCacheNode* node) { node->next = Head->next; node->prev = Head; Head->next = node; node->next->prev = node; } };