What is LRU caching and how is it implemented in different programming languages?

What is LRU caching and how does it work?

LRU stands for Least Recently Used. It's a caching algorithm that removes the least recently accessed items when the cache reaches its limit.

Can you show me how to implement LRU caching in Python?

Sure! In Python, you can use the collections.OrderedDict to maintain the order of access. Here's a simple implementation:

from collections import OrderedDict

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

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

    def put(self, key: int, value: int) -> None:
        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)

How would this be different in Java?

In Java, you can use a combination of a HashMap and a LinkedList to achieve LRU caching. Here's a basic example:

import java.util.*;

class LRUCache {
    private final Map<Integer, Integer> cache;
    private final LinkedList<Integer> order;
    private final int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
        this.order = new LinkedList<>();
    }

    public int get(int key) {
        if (!cache.containsKey(key)) return -1;
        order.remove((Integer) key);
        order.addFirst(key);
        return cache.get(key);
    }

    public void put(int key, int value) {
        if (cache.containsKey(key)) {
            order.remove((Integer) key);
        } else if (cache.size() == capacity) {
            int lruKey = order.removeLast();
            cache.remove(lruKey);
        }
        cache.put(key, value);
        order.addFirst(key);
    }
}