9
\$\begingroup\$

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];
    }
}
\$\endgroup\$
  • \$\begingroup\$ Is this really an interview-question? What did they say? Did you pass? \$\endgroup\$ – t3chb0t Oct 13 '17 at 14:15
  • \$\begingroup\$ This is an interview question. Not my interview. I am just practicing. \$\endgroup\$ – Gilad Oct 13 '17 at 14:22
  • 2
    \$\begingroup\$ 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)? \$\endgroup\$ – Eric Lippert Oct 13 '17 at 14:34
  • 3
    \$\begingroup\$ 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? \$\endgroup\$ – Eric Lippert Oct 13 '17 at 14:37
  • \$\begingroup\$ 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?. \$\endgroup\$ – Matthew FitzGerald-Chamberlain Oct 13 '17 at 16:50
9
\$\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.


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).

\$\endgroup\$
  • \$\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 Oct 13 '17 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 Oct 13 '17 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 Oct 13 '17 at 14:13
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.