CodingGyan

LRU Cache

hard Java Collections

Problem

Simulate a Least Recently Used (LRU) cache. The first line is the capacity. Each next line is put K V or get K. put stores the value (and replaces an old value). If the cache has more than capacity keys after a put, the least recently used key is removed. A put or a successful get makes the key the most recently used. For every get print the value, or -1 if the key is not in the cache.

Constraints

  • 1 <= capacity <= 1000
  • 1 <= commands <= 10^4

Examples

Input

2
put 1 1
put 2 2
get 1
put 3 3
get 2

Output

1
-1

Solutions

Best approachTime O(1) per operationSpace O(capacity)

An LRU cache throws away the key that was used longest ago. A map that remembers the order of use does this in O(1): move a key to the end when it is used, and remove from the front when the cache is full.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Process commands line by line.
 * Input   : Several lines of commands.
 * Output  : The answers of the get commands.
 * Approach: Keep keys in order of use.
 * Time    : O(1) per operation
 * Space   : O(capacity)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
        // Step 1: LinkedHashMap with accessOrder = true keeps keys from least recently used to most recently used.
        // removeEldestEntry is called after each put. We remove the oldest entry when the size is above the capacity.
        static class LruCache extends java.util.LinkedHashMap<Integer, Integer> {
            private final int capacity;

            LruCache(int capacity) {
                super(16, 0.75f, true);
                this.capacity = capacity;
            }

            @Override
            protected boolean removeEldestEntry(java.util.Map.Entry<Integer, Integer> eldest) {
                return size() > capacity;
            }
        }

    // This method solves the task. It receives the input and returns the answer.
    static String[] solve(String[] lines) {
        LruCache cache = new LruCache(Integer.parseInt(lines[0]));
        java.util.List<String> output = new java.util.ArrayList<>();

        for (int i = 1; i < lines.length; i++) {
            String[] parts = lines[i].split(" ");

            // Step 2: put stores the value. The map removes the oldest entry by itself when it is too big.
            if (parts[0].equals("put")) {
                cache.put(Integer.parseInt(parts[1]), Integer.parseInt(parts[2]));
            } else {
                // Step 3: get returns -1 for a missing key. A successful get also marks the key as recently used.
                Integer value = cache.get(Integer.parseInt(parts[1]));
                output.add(value == null ? "-1" : String.valueOf(value));
            }
        }
        return output.toArray(new String[0]);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        java.util.List<String> all = new java.util.ArrayList<>();
        while (scanner.hasNextLine()) {
            String line = scanner.nextLine().trim();
            if (!line.isEmpty()) {
                all.add(line);
            }
        }
        String[] lines = all.toArray(new String[0]);
        System.out.println(String.join("\n", solve(lines)));
    }
}
Hints (2)
  1. Which key is removed when the cache is full?
  2. What happens to a key after a get?

Try these next