1. Introduction

An LRU (Least Recently Used) cache is a type of cache in which the least recently used entries are removed when the cache reaches its size limit. The main idea behind an LRU cache is to prioritize the most recently accessed items and discard the least recently accessed ones. In this post, we will implement a simple LRU cache using an array.

2. Program Steps

1. Define the LRUCache class.

2. Initialize an array to store the cache items and another array to track the usage of items.

3. Create methods access, get, and put to manage the cache.

4. Implement an algorithm to determine which item to evict when the cache reaches its limit.

3. Code Program

class LRUCache {
    private int[] cache;
    private int[] usage;
    private int capacity;
    private int count;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.count = 0;
        this.cache = new int[capacity];
        this.usage = new int[capacity];
        for (int i = 0; i < capacity; i++) {
            this.cache[i] = -1;
            this.usage[i] = 0;
        }
    }

    // Increase the usage count of an item
    private void access(int index) {
        for (int i = 0; i < count; i++) {
            if (i == index) {
                usage[i] = count;
            } else {
                usage[i]--;
            }
        }
    }

    public int get(int key) {
        for (int i = 0; i < count; i++) {
            if (cache[i] == key) {
                access(i);
                return key;
            }
        }
        return -1;  // Key not found
    }

    public void put(int key) {
        int index = get(key);
        if (index == -1) { // Key not in cache
            if (count < capacity) {
                cache[count] = key;
                access(count);
                count++;
            } else {
                // Evict least recently used item
                int minIndex = 0;
                for (int i = 1; i < count; i++) {
                    if (usage[i] < usage[minIndex]) {
                        minIndex = i;
                    }
                }
                cache[minIndex] = key;
                access(minIndex);
            }
        }
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(3); // Capacity of 3

        cache.put(1);
        cache.put(2);
        cache.put(3);
        cache.get(1);
        cache.put(4);

        // Print the cache
        for (int i = 0; i < cache.count; i++) {
            System.out.print(cache.cache[i] + " ");
        }
    }
}

Output:

1 2 4

4. Step By Step Explanation

1. The LRUCache class is designed to store integers in an LRU fashion using an array called cache to store the values and another array called usage to track the usage count of each item.

2. The access method is used internally to increment the usage count of an accessed item and decrement the usage count of other items.

3. The get method retrieves an item from the cache if present and updates its usage count.

4. The put method adds a new item to the cache or updates an existing one. If the cache is full, it evicts the least recently used item before adding the new item.

5. In the main method, a new cache of capacity 3 is created. Items 1, 2, and 3 are added, then item 1 is accessed, and finally item 4 is added. As a result, the least recently used item 3 is evicted from the cache, and the final cache contains items 1, 2, and 4.

Note: This is a basic implementation of an LRU cache using arrays. Real-world implementations might use more advanced data structures like linked lists or hash maps to achieve better performance.