I have implemented an LRU cache, the question is taken from: leetcode: 146. LRU Cache
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.
get(key)
- Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value)
- Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
Tests:
[TestClass]
public class LruCacheUnitTest
{
[TestMethod]
public void LruCacheTest()
{
LRUCache cache = new LRUCache(2 /* capacity */ );
cache.put(1, 1);
cache.put(2, 2);
Assert.AreEqual(1, cache.get(1)); // returns 1
cache.put(3, 3); // evicts key 2
Assert.AreEqual(-1, cache.get(2)); // returns -1 (not found)
cache.put(4, 4); // evicts key 1
Assert.AreEqual(-1, cache.get(1)); // returns -1 (not found)
Assert.AreEqual(3, cache.get(3)); // returns 3
Assert.AreEqual(4, cache.get(4)); // returns 4
}
}
Implementation:
public class LRUCache
{
private int _numOfCells;
private Dictionary<int, int> _cache;
private List<KeyValuePair<int, int>> _orderList;
public LRUCache(int numberOfCacheCells)
{
this._numOfCells = numberOfCacheCells;
_cache = new Dictionary<int, int>(_numOfCells);
_orderList = new List<KeyValuePair<int, int>>(_numOfCells);
}
public void put(int key, int value)
{
if (_cache.Count == _numOfCells) // the cache is full we need to remove 1
{
var toRemove = _orderList[0];
_cache.Remove(toRemove.Key);
_orderList.Remove(toRemove);
}
_orderList.Add(new KeyValuePair<int, int>(key, value));
_cache[key] = value;
}
public int get(int key)
{
if (!_cache.ContainsKey(key))
{
return -1;
}
//put the key and value to the back of the ordered list
var tempCacheCell = _orderList.FirstOrDefault(x=>x.Key == key);
_orderList.Remove(tempCacheCell);
_orderList.Add(tempCacheCell);
return _cache[key];
}
}
Put
returns a new LRUCache, and the old one stays the same. SimilarlyGet
returns a tuple ofint, LRUCache
. What is the maximum asymptotic order efficiency you can obtain using only immutable data structures? \$\endgroup\$get
method, which prevents intentionally storing -1 in the cache. Instead, it should return anint?
. \$\endgroup\$