If you are preparing a coding interview for GS, this series surely helps you. I have coded the most optimized solutions of 50 LeetCode questions tagged with Goldman Sachs.

LRU Cache - LeetCode

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

leetcode.com

Goal:

  • design a cache that has a maximum capacity, which will pop out the least recently used item/key

What feature does this cache provide?

You can put a key-value pair. if the key is already present

  • update the value
  • update that this key is recently used

You can put a key-value pair. if the key is not present

  • add this key-value pair
  • and give a state to it that it is recently used
  • if the cache at its maximum size, discard the least recently used item

You can get a value using a key. if the value is present

  • update that this key is recently used
  • if the cache at its maximum size, discard the least recently used item
  • return the value

You can get a value using a key. if the value is not present

  • return -1

How you can get a value with a key using the fastest speed?

  • HashMap is a good choice with O(1) get, add, remove complexity
  • TreeMap can be another choice with O(log n) get, add, remove complexity

How can you maintain the order of the key?

if using ArrayList to store the keys

  • when you have a new item, you can add it to the end of the list, time is O(1)
  • if you pop out the first item to discard least recently used item, time is O(n)
  • if you want to update the status of a certain key, you have to remove it and put back to end of the list, time is O(n) for the removal

if using a single linked list to store the keys

  • add operation is O(1)
  • discard the least recently used item means to point the head to next item, time is O(1)
  • update the status of a key, time is O(n) to search the previous node of a key or using an extra hashmap to save pairs of node and next node

if using a double linked list to store keys

  • you can update the status of key with time O(1) as you have the previous pointer to help you remove it and then connect to next pointer to maintain the list

Performance:

  • time: put is O(1), get is O(1)
  • memory: O(n), n is no. of the key stored in the hashmap and the doubly linked list

Code Example: