Amazon Interview Question Interns
Country: India
As bob said, use a min heap to cache the Jobs.
1. When new Job is added into the cache,
If Heap size is max cache size, remove root and replace with newly added Job. Use current timestamp as node value for comparison. With that new node will move down to leaf node.
2. When an item is accessed from the cache, update it's time stamp to the current time and that will cause it to move down.
However this will not solve the problem of searching an element with O(1) from cache. Therefore an additional Map might be required to point into Heap for efficient retrieval
#include <queue>
#include <stdexcept>
#include <unordered_map>
using namespace std;
class LRU
{
public:
LRU(int c = 0) : cap(c), size(0), time(0) {}
int get(int key)
{
if (vlist.cunt(key) == 0) throw logic_error("can't find key");
return vlist[key];
}
void set(int key, int val)
{
if (vlist.count(key) == 0)
{
if (size == cap)
{
while (true)
{
P p = que.top(); que.pop(); int t = p.first, k = p.second;
if (t == tlist[k])
{
tlist.erase(key); vlist.erase(key); break;
}
}
}
else ++size;
}
vlist[key] = val;
tlist[key] = ++time;
que.push(P(time, key));
}
private:
typedef pair<int, int> P;
int time, size, cap;
proority_queue<P> que;
unordered_map<int, int> tlist, vlist;
};
#include <queue>
#include <stdexcept>
#include <unordered_map>
using namespace std;
class LRU
{
public:
LRU(int c = 0) : cap(c), size(0), time(0) {}
int get(int key)
{
if (vlist.cunt(key) == 0) throw logic_error("can't find key");
return vlist[key];
}
void set(int key, int val)
{
if (vlist.count(key) == 0)
{
if (size == cap)
{
while (true)
{
P p = que.top(); que.pop(); int t = p.first, k = p.second;
if (t == tlist[k])
{
tlist.erase(key); vlist.erase(key); break;
}
}
}
else ++size;
}
vlist[key] = val;
tlist[key] = ++time;
que.push(P(time, key));
}
private:
typedef pair<int, int> P;
int time, size, cap;
proority_queue<P> que;
unordered_map<int, int> tlist, vlist;
};
#include <queue>
#include <stdexcept>
#include <unordered_map>
using namespace std;
class LRU
{
public:
LRU(int c = 0) : cap(c), size(0), time(0) {}
int get(int key)
{
if (vlist.cunt(key) == 0) throw logic_error("can't find key");
return vlist[key];
}
void set(int key, int val)
{
if (vlist.count(key) == 0)
{
if (size == cap)
{
while (true)
{
P p = que.top(); que.pop(); int t = p.first, k = p.second;
if (t == tlist[k])
{
tlist.erase(key); vlist.erase(key); break;
}
}
}
else ++size;
}
vlist[key] = val;
tlist[key] = ++time;
que.push(P(time, key));
}
private:
typedef pair<int, int> P;
int time, size, cap;
proority_queue<P> que;
unordered_map<int, int> tlist, vlist;
};
public class LRUCache<K,V> {
int capacity;
LRUCache( int capacity ) {
this.capacity = capacity;
}
static class Element<K,V> implements Comparable<Element<K,V>>{
Element(K k, V v) {
this.k = k;
this.v = v;
timestamp = System.currentTimeMillis();
}
long timestamp;
K k;
V v;
public int compareTo(Element<K,V> other) {
return Long.compare(this.timestamp, other.timestamp);
}
public boolean equals(Object obj ) {
if ( !( obj instanceof Element ) ) return false;
Element<K,V> other =(Element<K,V>)obj;
return other.k.equals(this.k);
}
public int hashCode() {
return k.hashCode();
}
}
PriorityQueue<Element<K,V>> queue = new PriorityQueue<Element<K,V>>();
Map<K,Element<K,V>> elements = new HashMap<K,Element<K,V>>();
public V get(K k) {
if (elements.containsKey(k)) {
Element<K, V> e = elements.get(k);
queue.remove(e);
e.timestamp = System.currentTimeMillis();
queue.add(e);
return e.v;
} else {
return null;
}
}
void set(K k, V v) {
if (elements.containsKey(k)) {
Element<K, V> e = elements.get(k);
queue.remove(e);
e.v = v;
e.timestamp = System.currentTimeMillis();
queue.add(e);
}
else if ( queue.size() + 1 > capacity ) {
Element<K,V> e = queue.remove();
elements.remove(e.k);
Element<K,V> newE = new Element<K,V>(k,v);
queue.add(newE);
elements.put(k, newE);
}
else {
Element<K,V> newE = new Element<K,V>(k,v);
queue.add(newE);
elements.put(k, newE);
}
}
void remove (K k) {
if (elements.containsKey(k)) {
Element<K, V> e = elements.get(k);
queue.remove(e);
elements.remove(k);
}
}
public static void main(String[] args) {
}
}
Use min-heap to store the least recently used element at the top. When a new element arrives, replace the topmost element with it and sift it down.
- bob22 June 13, 2015class LRUCache(object): def __init__(self, size): self._size = size self._key_to_index = {} self._index_to_key = [None] * self._size self._heap = [] self._key_to_value = {} self._access_counter = 0 def has(self, key): """Just check if cache has key without accessing it""" return key in self._key_to_value def _get_access_counter(self): self._access_counter += 1 return self._access_counter def _protect_counter_overflow(self): if self._access_counter >= (1 << 31) - 1: min_value = max_value = self._heap[0] for i in xrange(self._size): self._heap[i] -= min_value max_value = max(self._heap[i], max_value) self._access_counter = max_value def get(self, key): key_index = self._key_to_index.get(key) if key_index is None: raise KeyError(key) self._heap[key_index] = self._get_access_counter() self._sift_down(key_index) self._protect_counter_overflow() return self._key_to_value[key] def set(self, key, value): key_index = self._key_to_index.get(key) if len(self._heap) < self._size: if key_index is None: self._key_to_index[key] = len(self._heap) self._index_to_key[len(self._heap)] = key self._key_to_value[key] = value self._heap.append(self._get_access_counter()) if len(self._heap) == self._size: self._heapify() else: self._heap[key_index] = self._get_access_counter() else: if key_index is None: # Replace least recently used key pop_key = self._index_to_key[0] self._key_to_value.pop(pop_key) self._key_to_index.pop(pop_key) self._index_to_key[0] = key self._heap[0] = self._get_access_counter() self._key_to_value[key] = value self._key_to_index[key] = self._size self._sift_down(0) else: self._heap[key_index] = self._get_access_counter() self._sift_down(key_index) self._protect_counter_overflow() def _heapify(self): for i in xrange(1, self._size): self._sift_up(i) def _sift_down(self, index): while True: left_index = index * 2 + 1 right_index = index * 2 + 2 value = self._heap[index] swap_with_index = None if left_index < self._size: if self._heap[left_index] < value: value = self._heap[left_index] swap_with_index = left_index if right_index < self._size: if self._heap[right_index] < value: swap_with_index = right_index if swap_with_index is None: break self._swap_index(index, swap_with_index) index = swap_with_index def _sift_up(self, index): while index != 0: parent_index = int((index - 1) / 2) value = self._heap[index] parent_value = self._heap[parent_index] if value >= parent_value: break self._swap_index(index, parent_index) index = parent_index def _swap_index(self, left_index, right_index): self._heap[left_index], self._heap[right_index] = self._heap[right_index], self._heap[left_index] left_key = self._index_to_key[left_index] right_key = self._index_to_key[right_index] self._index_to_key[left_index] = right_key self._index_to_key[right_index] = left_key self._key_to_index[left_key] = right_index self._key_to_index[right_key] = left_index if __name__ == '__main__': cache = LRUCache(3) cache.set('a', 1) cache.set('b', 2) cache.set('c', 3) assert cache.get('a') == 1 cache.set('d', 'hello') assert not cache.has('b') cache.set('e', 'world') assert not cache.has('c') assert cache.get('a') == 1 cache.get('d') == 'hello' cache.set('f', 'another') assert not cache.has('e') cache = LRUCache(50) for i in xrange(100): cache.set(i, i) for i in xrange(50, 100): assert cache.has(i) for i in xrange(25, 75): cache.set(i, i) for i in xrange(25): cache.set(i, i) for i in xrange(75): if i < 25: assert cache.has(i), i if 25 <= i < 50: assert not cache.has(i), i if 50 <= i: assert cache.has(i)