LRU Cache

Medium Real-World Scenarios

Design a Least-Recently-Used cache with O(1)-ish get and put — the pattern behind an app's image/data cache. The example runs put/get operations on a capacity-2 cache and prints the get results.

Sample input

capacity = 2; put(1,1) put(2,2) get(1) put(3,3) get(2) put(4,4) get(1) get(3) get(4)

Sample output

1 -1 -1 3 4

Solution

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = OrderedDict()

    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)

lru = LRUCache(2)
lru.put(1, 1)
lru.put(2, 2)
out = [lru.get(1)]
lru.put(3, 3)
out.append(lru.get(2))
lru.put(4, 4)
out.append(lru.get(1))
out.append(lru.get(3))
out.append(lru.get(4))
print(*out)

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map();
  }
  get(key) {
    if (!this.cache.has(key)) return -1;
    const value = this.cache.get(key);
    this.cache.delete(key);
    this.cache.set(key, value);
    return value;
  }
  put(key, value) {
    if (this.cache.has(key)) this.cache.delete(key);
    this.cache.set(key, value);
    if (this.cache.size > this.capacity) {
      this.cache.delete(this.cache.keys().next().value);
    }
  }
}

const lru = new LRUCache(2);
lru.put(1, 1);
lru.put(2, 2);
const out = [lru.get(1)];
lru.put(3, 3);
out.push(lru.get(2));
lru.put(4, 4);
out.push(lru.get(1));
out.push(lru.get(3));
out.push(lru.get(4));
console.log(out.join(" "));

import java.util.LinkedHashMap;
import java.util.Map;

public class Main {
    static class LRUCache extends LinkedHashMap<Integer, Integer> {
        private final int capacity;
        LRUCache(int capacity) {
            super(capacity, 0.75f, true);
            this.capacity = capacity;
        }
        int getOr(int key) {
            return super.getOrDefault(key, -1);
        }
        protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
            return size() > capacity;
        }
    }

    public static void main(String[] args) {
        LRUCache lru = new LRUCache(2);
        lru.put(1, 1);
        lru.put(2, 2);
        StringBuilder sb = new StringBuilder();
        sb.append(lru.getOr(1));
        lru.put(3, 3);
        sb.append(" ").append(lru.getOr(2));
        lru.put(4, 4);
        sb.append(" ").append(lru.getOr(1));
        sb.append(" ").append(lru.getOr(3));
        sb.append(" ").append(lru.getOr(4));
        System.out.println(sb.toString());
    }
}

class LRUCache(private val capacity: Int) : LinkedHashMap<Int, Int>(capacity, 0.75f, true) {
    fun getOr(key: Int): Int = super.getOrDefault(key, -1)
    override fun removeEldestEntry(eldest: Map.Entry<Int, Int>): Boolean = size > capacity
}

fun main() {
    val lru = LRUCache(2)
    lru.put(1, 1)
    lru.put(2, 2)
    val out = StringBuilder()
    out.append(lru.getOr(1))
    lru.put(3, 3)
    out.append(" ").append(lru.getOr(2))
    lru.put(4, 4)
    out.append(" ").append(lru.getOr(1))
    out.append(" ").append(lru.getOr(3))
    out.append(" ").append(lru.getOr(4))
    println(out.toString())
}

class LRUCache {
    let capacity: Int
    var order: [Int] = []
    var map: [Int: Int] = [:]
    init(_ capacity: Int) { self.capacity = capacity }

    func get(_ key: Int) -> Int {
        guard let value = map[key] else { return -1 }
        touch(key)
        return value
    }

    func put(_ key: Int, _ value: Int) {
        map[key] = value
        touch(key)
        if map.count > capacity {
            let evict = order.removeFirst()
            map.removeValue(forKey: evict)
        }
    }

    private func touch(_ key: Int) {
        if let idx = order.firstIndex(of: key) { order.remove(at: idx) }
        order.append(key)
    }
}

let lru = LRUCache(2)
lru.put(1, 1)
lru.put(2, 2)
var out = [String]()
out.append(String(lru.get(1)))
lru.put(3, 3)
out.append(String(lru.get(2)))
lru.put(4, 4)
out.append(String(lru.get(1)))
out.append(String(lru.get(3)))
out.append(String(lru.get(4)))
print(out.joined(separator: " "))

class LRUCache {
  final int capacity;
  final Map<int, int> map = {};
  final List<int> order = [];
  LRUCache(this.capacity);

  int get(int key) {
    if (!map.containsKey(key)) return -1;
    _touch(key);
    return map[key]!;
  }

  void put(int key, int value) {
    map[key] = value;
    _touch(key);
    if (map.length > capacity) {
      final evict = order.removeAt(0);
      map.remove(evict);
    }
  }

  void _touch(int key) {
    order.remove(key);
    order.add(key);
  }
}

void main() {
  final lru = LRUCache(2);
  lru.put(1, 1);
  lru.put(2, 2);
  final out = <int>[];
  out.add(lru.get(1));
  lru.put(3, 3);
  out.add(lru.get(2));
  lru.put(4, 4);
  out.add(lru.get(1));
  out.add(lru.get(3));
  out.add(lru.get(4));
  print(out.join(' '));
}

#include <iostream>
#include <list>
#include <unordered_map>
using namespace std;

class LRUCache {
    int capacity;
    list<pair<int, int>> items;
    unordered_map<int, list<pair<int, int>>::iterator> map;
public:
    LRUCache(int cap) : capacity(cap) {}

    int get(int key) {
        auto it = map.find(key);
        if (it == map.end()) return -1;
        items.splice(items.begin(), items, it->second);
        return it->second->second;
    }

    void put(int key, int value) {
        auto it = map.find(key);
        if (it != map.end()) {
            it->second->second = value;
            items.splice(items.begin(), items, it->second);
            return;
        }
        items.push_front({key, value});
        map[key] = items.begin();
        if ((int) map.size() > capacity) {
            map.erase(items.back().first);
            items.pop_back();
        }
    }
};

int main() {
    LRUCache lru(2);
    lru.put(1, 1);
    lru.put(2, 2);
    cout << lru.get(1);
    lru.put(3, 3);
    cout << " " << lru.get(2);
    lru.put(4, 4);
    cout << " " << lru.get(1);
    cout << " " << lru.get(3);
    cout << " " << lru.get(4);
    cout << endl;
    return 0;
}

#include <stdio.h>

#define CAP 2
int keys[CAP], vals[CAP], recency[CAP];
int cacheSize = 0;

int lruGet(int key) {
    for (int i = 0; i < cacheSize; i++) {
        if (keys[i] == key) {
            int maxR = 0;
            for (int j = 0; j < cacheSize; j++) if (recency[j] > maxR) maxR = recency[j];
            recency[i] = maxR + 1;
            return vals[i];
        }
    }
    return -1;
}

void lruPut(int key, int value) {
    int maxR = 0;
    for (int j = 0; j < cacheSize; j++) if (recency[j] > maxR) maxR = recency[j];
    for (int i = 0; i < cacheSize; i++) {
        if (keys[i] == key) {
            vals[i] = value;
            recency[i] = maxR + 1;
            return;
        }
    }
    if (cacheSize == CAP) {
        int minIdx = 0;
        for (int i = 1; i < cacheSize; i++) if (recency[i] < recency[minIdx]) minIdx = i;
        keys[minIdx] = key;
        vals[minIdx] = value;
        recency[minIdx] = maxR + 1;
    } else {
        keys[cacheSize] = key;
        vals[cacheSize] = value;
        recency[cacheSize] = maxR + 1;
        cacheSize++;
    }
}

int main() {
    lruPut(1, 1);
    lruPut(2, 2);
    printf("%d", lruGet(1));
    lruPut(3, 3);
    printf(" %d", lruGet(2));
    lruPut(4, 4);
    printf(" %d", lruGet(1));
    printf(" %d", lruGet(3));
    printf(" %d", lruGet(4));
    printf("\n");
    return 0;
}