Cache with a Read-Write Lock

Problem

A cache is shared by many threads. Many readers may read at the same time, but a writer must be alone. Build it with a read-write lock, and count the hits and misses. Commands: put KEY VALUE (store, replace if present), get KEY (print the value, or miss), stats (print hits and misses, as two numbers separated by a space).

Constraints

  • 1 <= commands <= 100

Examples

Input

put a 1
get a
get b
stats

Output

1
miss
1 1

Solutions

Best approachTime O(n)Space O(n)

In Java, the read lock lets many readers work together, and the write lock keeps a writer alone. The counters are atomic because several readers update them at the same moment. The commands here run one by one so the output is fixed.

Same code works in Java810172125Basic features only, so nothing changes between versions.

Only Java has a read-write lock. Python uses one plain lock, and JavaScript and TypeScript run one task at a time.

/*
 * Problem : Run the commands.
 * Input   : Command lines.
 * Output  : One line per answer.
 * Approach: Cache class
 * Time    : O(n)
 * Space   : O(n)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
        // Step 1: A read-write lock gives two locks. The read lock can be held by many threads, the write lock by one.
        static class Cache {
            private final java.util.Map<String, Long> data = new java.util.HashMap<String, Long>();
            private final java.util.concurrent.locks.ReadWriteLock lock = new java.util.concurrent.locks.ReentrantReadWriteLock();
            // Step 2: Readers change the counters at the same time, so the counters must be atomic.
            private final java.util.concurrent.atomic.AtomicInteger hits = new java.util.concurrent.atomic.AtomicInteger();
            private final java.util.concurrent.atomic.AtomicInteger misses = new java.util.concurrent.atomic.AtomicInteger();

            void put(String key, long value) {
                lock.writeLock().lock();
                try {
                    data.put(key, value);
                } finally {
                    lock.writeLock().unlock();
                }
            }

            // Step 3: get only reads the map, so it takes the shared read lock.
            Long get(String key) {
                lock.readLock().lock();
                try {
                    Long value = data.get(key);
                    if (value == null) {
                        misses.incrementAndGet();
                    } else {
                        hits.incrementAndGet();
                    }
                    return value;
                } finally {
                    lock.readLock().unlock();
                }
            }

            String stats() {
                return hits.get() + " " + misses.get();
            }
        }

    // This method solves the task. It receives the input and returns the answer.
    static String[] solve(String[] lines) {
        Cache cache = new Cache();
        java.util.List<String> out = new java.util.ArrayList<String>();
        for (String line : lines) {
            String[] part = line.split(" ");
            if (part[0].equals("put")) {
                cache.put(part[1], Long.parseLong(part[2]));
            } else if (part[0].equals("get")) {
                Long value = cache.get(part[1]);
                out.add(value == null ? "miss" : String.valueOf(value));
            } else {
                out.add(cache.stats());
            }
        }
        return out.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. Why are the counters atomic and not plain int?
  2. When is a read-write lock better than a plain lock?