Least Recently Used (LRU) Cache, by Google

Today's Daily Coding Problem:

This problem was asked by Google.

Implement an LRU (Least Recently Used) cache. It should be able to be initialized with a cache size n, and contain the following methods:

• set(key, value): sets key to value. If there are already n items in the cache and we are adding a new item, then it should also remove the least recently used item.
• get(key): gets the value at key. If no such key exists, return null.

Each operation should run in O(1) time.

The O(1) means that both set and get operations must be performed in constant time, hence forget about using heaps or trees.
The key here is to use extra space. There is no requirements on the space utilization.
Here is the idea:

• Have a list to implement the cache. The list will be a list of <key, value>
• But also have a hash table point a key to each node in the list
• When setting, set an existing value or add a new one. Move it to the top of the list since it has been used
• If the list count is greater than N, remove the last
• On getting it, check the hash table and return that element
• Move it to the front of the list

By doing that you accomplish O(1) time for both operations with O(n) space. Hope you enjoy it, Boris.

GitHub: https://github.com/BorisVasilenko/dailycodingproblem/blob/master/DailyCodingProblem11052018.cs

Code:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Collections;

namespace DailyCodingProblem
{
 class DailyCodingProblem11052018
 {
  private LinkedList cache = null;
  private Hashtable pointerToItem = null;
  private int N = 0;

  public DailyCodingProblem11052018(int n)
  {
   this.N = n;
   cache = new LinkedList();
   pointerToItem = new Hashtable();
  }

  public void Set(string key, string value)
  {
   Console.WriteLine("Adding key = {0}, value = {1}", key, value);
   if (pointerToItem.ContainsKey(key))
   {
    //Reset the value
    LinkedListNode node = (LinkedListNode)pointerToItem[key];
    node.Value.value = value;

    //Move node up since it just got "used"
    cache.Remove(node);
    LRUCacheItem newItem = new LRUCacheItem(key, value);
    cache.AddFirst(newItem);
    pointerToItem[key] = cache.First;
   }
   else
   {
    //Add first
    LRUCacheItem newItem = new LRUCacheItem(key, value);
    cache.AddFirst(newItem);
    pointerToItem.Add(key, cache.First);

    //Remove last if needed
    if (cache.Count > N)
    {
     Console.WriteLine("Debugging: removing from cache!");
     string keyToRemove = cache.Last.Value.key;
     cache.RemoveLast();
     pointerToItem.Remove(keyToRemove);
    }
   }
  }

  public string Get(string key)
  {
   if (!pointerToItem.ContainsKey(key)) return null;

   //Get the return val
   string value = ((LinkedListNode)pointerToItem[key]).Value.value;

   //Move it up since it just got "used"
   cache.Remove((LinkedListNode)pointerToItem[key]);
   LRUCacheItem newItem = new LRUCacheItem(key, value);
   cache.AddFirst(newItem);
   pointerToItem[key] = cache.First;

   return value;
  }
 }

 public class LRUCacheItem
 {
  public string key;
  public string value;

  public LRUCacheItem(string key, string value)
  {
   this.key = key;
   this.value = value;
  }
 }
}