# LeetCode: LRU cache implementation C#

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
cache.put(4, 4);    // evicts key 1
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);
}
_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);
return _cache[key];
}
}

• Is this really an interview-question? What did they say? Did you pass? Oct 13 '17 at 14:15
• This is an interview question. Not my interview. I am just practicing. Oct 13 '17 at 14:22
• As noted in answers: your solution is not O(1). But you are on the right track. Hint: instead of an array-backed list of pairs, use a doubly-linked list of pairs, and instead of a dictionary of key to value, make a dictionary of key to doubly-linked-list-node. Now do you see how to do it in O(1)? Oct 13 '17 at 14:34
• Next challenge: Can you write an efficient immutable LRU key-value store? That is, Put returns a new LRUCache, and the old one stays the same. Similarly Get returns a tuple of int, LRUCache. What is the maximum asymptotic order efficiency you can obtain using only immutable data structures? Oct 13 '17 at 14:37
• It's unfortunate that the question as written returns -1 from the get method, which prevents intentionally storing -1 in the cache. Instead, it should return an int?. Oct 13 '17 at 16:50

The indentation is inconsistent: the test class has its {} indented the same as the class declaration, but the main class has them indented one level more.

It's good that you've included a unit test, but it's only testing half of the functionality. What about the getter?

put and get as method names don't follow C# conventions, which would be Put and Get -- although it would be even more idiomatic here to make them an indexer. The original task is phrased in terms which are as language-agnostic as possible, but in an interview you should aim to show language knowledge where you have it as well as general knowledge and skill.

Is there any reason for hard-coding int as the type of the key and value rather than making them generic?

private List<KeyValuePair<int, int>> _orderList;


Two questions: firstly, why KeyValuePair<int, int>? I don't see anything which uses the value. Secondly, why include List in the name? The type says that already.

                _orderList.Remove(toRemove);

            var tempCacheCell = _orderList.FirstOrDefault(x=>x.Key == key);
_orderList.Remove(tempCacheCell);


What's the asymptotic complexity of adding or fetching an element? It can certainly be improved. Hint: one approach would be to manually implement a different type of list. Alternative hint: there's some quite powerful collections in .Net Framework (I haven't checked which of them made it into .Net Standard).

• Great feedback thanks. I understand what you mean about storing the same object for linked list and dictionary and creating my own linked list. But what do you mean about collections. There is nothing like linkedlist with dictionary in c#. The closest is orderdictionary. But it doesn't support the functionaltly needed for cache. Oct 13 '17 at 10:14
• I think OrderedDictionary could be wrapped to provide an LRU cache. There's also the cheating option of writing an LRU cache around MemoryCache. Oct 13 '17 at 10:23
• The indentation is inconsistent: the test class has its {} indented the same as the class declaration, but the main class has them indented one level more. well, this is a copy/paste error, I don't think it's intentionally indented... so I've fixed it... as I always do :-] Oct 13 '17 at 14:13
• Can a Dictionary<int, (int data, int lastUsed)> be used here? Apr 11 '20 at 1:18

This is a simple implementation but its performance wouldn't scale well for large numberOfCacheCells values.

In particular, _orderList.Remove(toRemove); looks like it's O(n) rather than O(1).

The Dictionary<int, int> _cache operations are probably O(1) because of hashing; it's the List<KeyValuePair<int, int>> _orderList operations that are problematic.

There are never "holes" in the LRU list because you only ever remove the oldest item (the class doesn't support removing arbitrary items). So a "circular list buffer" or double-ended queue is possibly the container that you want to use instead of List. I don't think there is such a container built-in to .NET, though you could implement one yourself. An adequate alternative is LinkedList, adequate because its operations are O(1).

I wouldn't normally fuss, except that "cache" sounds like it might be performance-sensitive; and, yes, reading the question you linked to, it does say,

Could you do both operations in O(1) time complexity?

Also your get implementation could be slightly faster using _cache.TryGetValue so that it only has to access _cache once.

List is internally backed by an array, so item-removal won't be efficient. Use LinkedList instead which is a doubly linked list and allows efficient removal.

[TestClass]
public class LruCacheUnitTest
{
[TestMethod]
public void LruCacheTest()
{
var cache = new LruCache<int, string>(2);

cache.Put(1, "One");
cache.Put(2, "Two");
Assert.AreEqual("One", cache.Get(1));
cache.Put(3, "Three");
Assert.IsNull(cache.Get(2));
cache.Put(4, "Four");
Assert.IsNull(cache.Get(1));
Assert.AreEqual("Three", cache.Get(3));
Assert.AreEqual("Four", cache.Get(4));
}
}

public class LruCache<TKey, TValue>
{
private int capacity;
private Dictionary<TKey, TValue> valueCache;

public LruCache(int capacity)
{
this.capacity = capacity;
this.valueCache = new Dictionary<TKey, TValue>(capacity);
}

public void Put(TKey key, TValue value)
{
if (this.valueCache.ContainsKey(key)) // Key already exists.
{
this.Promote(key);
this.valueCache[key] = value;
return;
}

if (this.valueCache.Count == capacity) // Cache full.
{
this.RemoveLast();
}

}

public TValue Get(TKey key)
{
if (!this.valueCache.ContainsKey(key))
{
return default;
}

this.Promote(key);
return this.valueCache[key];
}

private void AddFirst(TKey key, TValue value)
{
this.valueCache[key] = value;
this.nodeCache[key] = node;
}

private void Promote(TKey key)
{