trjhtr

Description:

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

More details can be found here.

Code:

import java.util.Map;
import java.util.HashMap;

class Main 
 private static class LRUCache 
 private final int capacity;
 private final Map<String, Entry> map;
 private int currentCount;
 private Entry head;
 private Entry tail;

 LRUCache(int capacity) 
 if (capacity <= 0) 
 throw new IllegalArgumentException("Capacity should be greater than 0: " + capacity);
 
 this.map = new HashMap<>();
 this.capacity = capacity;
 

 /**
 * Gets the value associated with the key and
 * marks the key as most recent used.
 * 
 * @param key The cache key
 *
 * @return The value if present or null.
 */
 public Integer get(String key) 
 if (map.containsKey(key)) 
 Entry entry = map.get(key);
 remove(entry);
 addToFront(entry);
 return entry.val;
 
 return null;
 

 /**
 * Puts the value associated with the key and
 * marks the key as most recent.
 * 
 * @param key The cache key
 * @param val The cache value
 * 
 * @return The value if present or null.
 */
 public void put(String key, int val) 
 if (map.containsKey(key)) 
 Entry entry = map.get(key);
 remove(entry);
 addToFront(entry);
 else 
 currentCount++;
 Entry entry = new Entry(key, val);
 if (currentCount > capacity) 
 purge();
 
 addToFront(entry);
 map.put(key, entry);
 
 

 /**
 * Removes the entry from the list.
 */
 private void remove(Entry entry) 
 if (entry.prev != null) 
 entry.prev.next = entry.next;
 else 
 head = entry.next;
 

 if (entry.next != null) 
 entry.next.prev = entry.prev;
 else 
 tail = entry.prev;
 
 

 /**
 * Removes the last entry from the list.
 */
 private void purge() 
 if (tail == null) 
 return;
 
 Entry entry = tail;
 if (head == tail) 
 head = tail = null;
 else 
 entry.prev.next = null;
 tail = entry.prev;
 tail.next = null;
 
 map.remove(entry.key);
 

 /**
 * Adds entry to the from of the list.
 */
 private void addToFront(Entry entry) 
 entry.next = head;
 if (head != null) 
 head.prev = entry; 
 
 head = entry;
 if (tail == null) 
 tail = head;
 
 

 public String toString() 
 Entry current = head;
 StringBuilder s = new StringBuilder();
 while (current != null) 
 s.append(current + " ");
 current = current.next;
 
 return s.toString();
 
 

 private static class Entry 
 String key;
 int val;
 Entry next;
 Entry prev;

 Entry(String key, int val) 
 this.key = key;
 this.val = val;
 

 public String toString() 
 return key + ":" + val;
 
 

 public static void main(String args) 
 try 
 LRUCache cache = new LRUCache(-3);
 System.out.println("Test for -ve capacity failed");
 catch (IllegalArgumentException ex) 
 System.out.println("Test for -ve capacity passed");
 

 LRUCache cache = new LRUCache(3);
 cache.put("foo", 1);
 cache.put("bar", 2);
 cache.put("zar", 3);
 System.out.println(cache); // => zar -> bar -> foo
 cache.put("doe", 4); // => purge, i.e. remove foo
 System.out.println(cache); // => doe -> zar -> bar
 cache.get("bar");
 System.out.println(cache); // => bar -> doe -> zar
 cache.get("doe");
 System.out.println(cache); // => doe -> bar -> zar

 try 
 LRUCache c = new LRUCache(1);
 c.put("a", 1);
 c.put("b", 2);
 c.get("a");
 System.out.println("Should pass");
 catch (Exception e) 
 e.printStackTrace(System.out);
 
 

Note:

I have used the basic data structures to get more clarity for managing pointers.

Questions:

I am more interested in OOP and creating better abstractions,
any guidance in that direction would be great.