LeetCode: LRU cache implementation C#

Question

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]; } } 

Answer 1

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); _orderList.Add(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).

Answer 2

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,

Follow up:
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.

Answer 3

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; private Dictionary<TKey, LinkedListNode<TKey>> nodeCache; private LinkedList<TKey> orderList; public LruCache(int capacity) { this.capacity = capacity; this.valueCache = new Dictionary<TKey, TValue>(capacity); this.nodeCache = new Dictionary<TKey, LinkedListNode<TKey>>(capacity); this.orderList = new LinkedList<TKey>(); } 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(); } this.AddFirst(key, value); } 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) { var node = new LinkedListNode<TKey>(key); this.valueCache[key] = value; this.nodeCache[key] = node; this.orderList.AddFirst(node); } private void Promote(TKey key) { LinkedListNode<TKey> node = this.nodeCache[key]; this.orderList.Remove(node); this.orderList.AddFirst(node); } private void RemoveLast() { LinkedListNode<TKey> lastNode = this.orderList.Last; this.valueCache.Remove(lastNode.Value); this.nodeCache.Remove(lastNode.Value); this.orderList.RemoveLast(); } }