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();
    }
}