Write a class of objects named LruCache that implements a least-recently used (LRU) cache of key/value pairs.
Your cache will store key/value pairs where each key is an integer and each value is a string.
The cache will have a fixed maximum capacity that will be specified at construction.
Your cache cannot store more than this many key/value pairs.
If the client tries to add more than this many pairs, you must evict the existing pair that was least frequently used.
Each time a given key/value pair is accessed or modified through a call to get or set, it becomes the most recently used.
| member name |
description |
LruCache(capacity) |
Constructs a new empty cache that can hold up to the given number of key/value pairs. |
get(key) |
Returns the string value associated with the given key.
This key/value pair now becomes the most recently used in the cache.
Returns null if the given key is not present.
|
set(key, value) |
Stores a key/value pair in the cache; if the given key is already present, replaces its old value with the given new value.
This key/value pair now becomes the most recently used in the cache.
|
clear() |
Removes all key/value pairs from the cache. |
size() |
Returns the number of key/value pairs in the cache. |
capacity() |
Returns the maximum allowed number of key/value pairs in the cache, as passed to the constructor. |
toString() |
Returns a string representation of the cache with its key/value pairs in decreasing order by most recent usage, such as {4=a, 2=b, 3=c}. |
For example:
// most ==> least recently used
LruCache cache = new LruCache(3); // {}
cache.set(7, "seven"); // {7=seven}
cache.set(4, "four"); // {4=four, 7=seven}
cache.set(4, "fore"); // {4=fore, 7=seven}
cache.set(9, "nine"); // {9=nine, 4=fore, 7=seven}
System.out.println(cache.get(4)); // {4=fore, 9=nine, 7=seven}; prints "fore"
cache.set(2, "two"); // {2=two, 4=fore, 9=nine}; 7 falls out
System.out.println(cache.get(7)); // prints null
cache.set(9, "nein"); // {9=nein, 2=two, 4=fore}
cache.set(3, "three"); // {3=three, 9=nein, 2=two}
System.out.println(cache.get(2)); // {2=two, 3=three, 9=nein}; prints "two"
cache.clear(); // {}
Part of the challenge of this problem lies in coming up with an efficient implementation.
Can you implement both get and set with O(1) runtime?
You should define the entire class including the class heading, the private fields, and the declarations and definitions of all the public methods and constructor.
