CareerCup

LinkedHashMap. Cannot post link, so you can google it.

impletement LRU class which extends LinkedHashMap and override removeEldestEntry like this:

class LRULinkedHashMap<K,V> extends LinkedHashMap<K,V>{  
    private int capacity;  

    LRULinkedHashMap(int capacity){  
        super(16,0.75f,true);  
        this.capacity=capacity;  
    }  

    @Override  
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest){   
        return size() > capacity;  
    }    
}

Keep a linked list in the node for each entry. In Swift:

class CacheEntry {
    var next : CacheEntry?
    let value : String
    let key : String
    
    init(key : String, value : String) {
        self.value = value
        self.key = key // only used for deletion
    }
}

class Cache {
    var entries : [String: CacheEntry] = [:]
    var head : CacheEntry? = nil
    let cacheMax : Int
    var cacheCount = 0
    
    init(maxSize : Int) {
        self.cacheMax = maxSize
    }
    
    func findKey(key : String) -> String? {
        return entries[key]?.value
    }
    
    func insert(key : String, value : String) {
        let newEntry = CacheEntry(key: key, value: value)
        entries[key] = newEntry
        newEntry.next = head
        head = newEntry
        if cacheCount > cacheMax {
            let (prev, last) = findLast()
            if let last = last {
                if let prev = prev {
                    prev.next = nil
                }
                entries[last.key] = nil
            }
        }
        cacheCount++
        printLinkedList()
    }
    
    func findLast() -> (CacheEntry?, CacheEntry?) {
        var prev : CacheEntry? = nil
        var element: CacheEntry? = head
        repeat {
            prev = element
            element = element?.next
        } while element?.next != nil
        return (prev, element)
    }
    
    func printLinkedList() {
        print("start")
        var element : CacheEntry? = head
        repeat {
            print("\(element?.value)")
            element = element?.next
        } while element?.next != nil
        print("end")
    }
}
let cache = Cache(maxSize: 5)
cache.insert("A", value: "AV")
cache.insert("B", value: "BV")
cache.insert("C", value: "CV")
cache.insert("D", value: "DV")
cache.insert("E", value: "EV")
cache.insert("F", value: "FV")
cache.insert("G", value: "GV")

Not particularly efficient or clean, but simple. Keeps a counter of "age" (in terms of number of operations on the cache), and simply evicts the entry with the minimal age when inserting into a full cache.

# implement a LRU cache with only a single container

class LRU:
    size = 3
    cache = {}
    counter = 0
    def __init__(self, size=3):
        self.size = size
        
    def find(self, key):
        if key not in self.cache:
            return None
        entry = self.cache[key]
        entry[1] = self.counter
        self.counter += 1
        self.cache[key] = entry
        return self.cache[key][0]
        
    def insert(self, key, val):
        if len(self.cache) >= self.size: # find the oldest, to evict
            lruK = None
            lruAge = None
            for k in self.cache.keys():
                entry = self.cache[k]
                if lruK == None:
                    lruK = k
                    lruAge = entry[1]
                else:
                    if entry[1] < lruAge:
                        lruK = k
                        lruAge = entry[1]
            del self.cache[lruK]
        self.cache[key] = [val, self.counter]
        self.counter += 1

/*
I read it from here once : Java Generics and collections --> page 229

We can use make a class that extends class LinkedHashMap, it has a function removeEldestEntry which we can override.
The Idea behind implementation is to have a map and let it grow till it reaches its capacity. Then we can remove the oldest element from the map which is exactly like removing the least recenty element from cache.

Following is the implementation:

*/

class LRUCache<K,V> extends LinkedHashMap<K,V>{
		private int maxEntries;
			
		public LRUCache(int maxEntries){
			super(16,0.75f,true); // 16 is initial capacity and 0.75f is load factor
			this.maxEntries = maxEntries;
		}
		protected boolean removeEldestEntry(Map.Entry<K,V> eldest){
			return size() > maxEntries; 
		}
	}