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
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.
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)
- Why are the counters atomic and not plain int?
- When is a read-write lock better than a plain lock?