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
        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&lt;int, int&gt; _cache;
    private List&lt;KeyValuePair&lt;int, int&gt;&gt; _orderList;

    public LRUCache(int numberOfCacheCells)
    {
        this._numOfCells = numberOfCacheCells;
        _cache = new Dictionary&lt;int, int&gt;(_numOfCells);
        _orderList = new List&lt;KeyValuePair&lt;int, int&gt;&gt;(_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&lt;int, int&gt;(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=&gt;x.Key == key);
        _orderList.Remove(tempCacheCell);
        _orderList.Add(tempCacheCell);
        return _cache[key];
    }
}
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&lt;KeyValuePair&lt;int, int&gt;&gt; _orderList;



Two questions: firstly, why KeyValuePair&lt;int, int&gt;? 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=&gt;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).