LRU Cache - An Interesting LeetCode Problem

I found this problem today on LeetCode. 

LRU Cache Problem

It's not too hard, but it's not too easy either. 

It seemed interesting so I decided to solve it. 

Below is my solution (in Java). 

For more details, see this page 

LRU Cache - Wikipedia

/**

* LeetCode

*

* Problem 146

*

* LRU Cache

*

* https://leetcode.com/problems/lru-cache/description/

*/

import java.util.HashMap;

import java.util.TreeMap;

public class LRUCache {

private TreeMap<Long, Integer> mpLastUsedToKey = new TreeMap<>();

private TreeMap<Integer, Long> mpKeyToLastUsed = new TreeMap<>();

private HashMap<Integer, Integer> mpKeyToValue = new HashMap<>();

private int capacity = 0;

public LRUCache(int capacity) {

this.capacity = capacity;

this.mpLastUsedToKey = new TreeMap<>();

this.mpKeyToLastUsed = new TreeMap<>();

this.mpKeyToValue = new HashMap<>();

}

public int get(int key) {

int v = -1;

if (mpKeyToValue.containsKey(key)) {

// the key is in the cache

Long ts = mpKeyToLastUsed.get(key);

long m = System.nanoTime();

mpLastUsedToKey.remove(ts);

mpLastUsedToKey.put(m, key);

mpKeyToLastUsed.put(key, m);

v = mpKeyToValue.get(key);

} else {

// the key is not in the cache

v = -1;

}

return v;

}

public void put(int key, int value) {

if (mpKeyToValue.containsKey(key)) {

Long ts = mpKeyToLastUsed.get(key);

mpLastUsedToKey.remove(ts);

}

long m = System.nanoTime();

mpLastUsedToKey.put(m, key);

mpKeyToLastUsed.put(key, m);

mpKeyToValue.put(key, value);

if (mpKeyToValue.size() > this.capacity) {

// evict the least recently used key (kl) from the cache

Long ts = mpLastUsedToKey.firstKey();

int kl = mpLastUsedToKey.get(ts);

mpKeyToValue.remove(kl);

mpLastUsedToKey.remove(ts);

mpKeyToLastUsed.remove(kl);

}

}

public String toString() {

return this.mpKeyToValue.toString();

}

public static void main(String[] args) throws Exception {

LRUCache c = new LRUCache(2);

c.put(1, 10);

Thread.sleep(50);

c.put(2, 20);

Thread.sleep(50);

c.get(1);

c.put(3, 30);

Thread.sleep(50);

System.out.println(c);

System.out.println("DONE!");

}

}