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 andget as method names don't follow C# conventions, which would bePut andGet -- although it would be even more idiomatic here to make them anindexer. 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-codingint as the type of the key and value rather than making them generic?

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

Two questions: firstly, whyKeyValuePair<int, int>? I don't see anything which uses the value. Secondly, why includeList 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).

• \$\begingroup\$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.\$\endgroup\$

  Gilad

  – Gilad

  2017-10-13 10:14:35 +00:00

  CommentedOct 13, 2017 at 10:14
• \$\begingroup\$I think OrderedDictionary could be wrapped to provide an LRU cache. There's also the cheating option of writing an LRU cache around MemoryCache.\$\endgroup\$

  Peter Taylor

  – Peter Taylor

  2017-10-13 10:23:56 +00:00

  CommentedOct 13, 2017 at 10:23
• \$\begingroup\$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 :-]\$\endgroup\$

  t3chb0t

  – t3chb0t

  2017-10-13 14:13:05 +00:00

  CommentedOct 13, 2017 at 14:13
• \$\begingroup\$Can aDictionary<int, (int data, int lastUsed)> be used here?\$\endgroup\$

  the default.

  – the default.

  2020-04-11 01:18:04 +00:00

  CommentedApr 11, 2020 at 1:18

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

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

TheDictionary<int, int> _cache operations are probably O(1) because of hashing; it's theList<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 ofList. I don't think there is such a container built-in to .NET, though you could implement one yourself. An adequate alternative isLinkedList, 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 inO(1) time complexity?

Also yourget 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. UseLinkedList 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();    }}

• c#
• programming-challenge
• interview-questions
• cache