Get startedGet started for free

Implementing an LRU cache

You're developing a web application that frequently retrieves user profile information as strings. To improve performance, you want to implement a simple cache that stores these profile strings and can identify which entries were least recently used.

This exercise is part of the course

Optimizing Code in Java

View Course

Exercise instructions

  • In the get() method, retrieve the entry for the specified key.
  • After retrieving the key, update its access time.
  • After putting an entry in the cache, if the capacity has been exceeded, remove the least recently used entry.

Hands-on interactive exercise

Have a go at this exercise by completing this sample code.

import java.util.*;

public class StringCache {
    private final int capacity = 100;
    private final Map cache = new HashMap<>();
    
    public String get(String key) {
        // Get the entry for the specified key
        CacheEntry entry = ____
        if (entry == null) return null;
        // Since that entry was accessed, update its access time
        entry.____
        return entry.value;
    }
    
    public void put(String key, String value) {
        cache.put(key, new CacheEntry(value));
        if (cache.size() > capacity) {
            // If cache exceeds capacity, remove least recently used
            ____
        }
    }

    void removeLeastRecentlyUsed() {
        String lruKey = null;
        long oldest = Long.MAX_VALUE;
        for (Map.Entry e : cache.entrySet()) {
            if (e.getValue().lastAccessed < oldest) {
                oldest = e.getValue().lastAccessed;
                lruKey = e.getKey();
            }
        }
        if (lruKey != null) { cache.remove(lruKey); }
    }

    static class CacheEntry {
        String value;
        long lastAccessed;
        CacheEntry(String value) {
            this.value = value;
            updateAccessTime();
        }
        void updateAccessTime() {
            lastAccessed = System.currentTimeMillis();
        }
    }

    public static void main(String[] args) {}
}
Edit and Run Code