Java LRU Cache: Use Access Order in LinkedHashMap

An LRU cache evicts the entry that has gone longest without access. In Java, an access-ordered LinkedHashMap moves accessed entries to the recent end, letting you calculate hits and costs in request order.

The Programmers cache exercise compares English city names without case sensitivity and assigns cost 1 to a hit and 5 to a miss. Capacity ranges from 0 to 30, with at most 100,000 requests. These are exercise costs, not measured database response times.

Processing flow

Capacity zero returns immediately. Otherwise get/put refresh recency, and an overflow evicts the least recently accessed key.

Update order on access

Save this complete class as Solution.java. It targets Java 11 or later; local execution compiled for Java 11 using JDK 17. The method assumes inputs satisfy the exercise constraints.

import java.util.LinkedHashMap;
import java.util.Locale;

public class Solution {
    public int solution(int cacheSize, String[] cities) {
        if (cacheSize == 0) return 5 * cities.length;
        var cache = new LinkedHashMap<String, Boolean>(16, 0.75f, true);
        int cost = 0;
        for (String city : cities) {
            String key = city.toLowerCase(Locale.ROOT);
            cost += cache.get(key) == null ? 5 : 1;
            cache.put(key, Boolean.TRUE);
            if (cache.size() > cacheSize) {
                String oldest = cache.keySet().iterator().next();
                cache.remove(oldest);
            }
        }
        return cost;
    }
}

The constructor’s final true argument matters. Unlike the default insertion order, an access-ordered LinkedHashMap updates order for accesses including get and put. Because this implementation never stores null values, get(key) == null can identify a miss.

When capacity is exceeded, remove the first key in iteration order: the least recently accessed entry. This differs from LFU, which chooses by access frequency. Locale.ROOT avoids making English case normalization depend on the machine’s default locale.

Why a hit changes eviction

With capacity 2, these requests cost 21 in total. Cache contents are shown oldest first.

Request	Result	Cache after request	Total cost
Jeju	miss	jeju	5
Pangyo	miss	jeju, pangyo	10
Jeju	hit	pangyo, jeju	11
Seoul	miss	jeju, seoul	16
Pangyo	miss	seoul, pangyo	21

If the third request does not refresh Jeju’s position, the next eviction changes. Capacity 0 cannot retain an entry, so the method returns 5 * cities.length immediately. Jeju and JEJU must also normalize to the same key.

Assuming average constant-time hash operations, M requests with name length L and capacity C take O(M×L) time including normalization and O(C×L) storage. Remember the exercise’s bounds on L and C. This implementation does not establish concurrent-access behavior or measured cache performance.

Continue with Java dot products and int bounds for numeric limits, or ID normalization for ordered string transformations.