Sift Interview Questions

Create a class named LRUCache that implements the behavior expected of a Least Recently Used (LRU) Cache.

The LRUCache class implements the following methods:

• __init__(self, capacity) - initializes the object and takes in a capacity parameter specifying the maximum capacity of the cache.
• get_if_exists(self, key) -> Any|None - gets a value based on a key. If the key exists, returns the associated value. If the key has expired or did not exist in the first place, returns None.
• put(self, key, value) - places a value inside the cache. In the case wherein the cache is full, invalidates the least recently used element. When two keys collide, the older value should be invalidated in place of the new one.

Example:

cache = LRUCache(2)
cache.put("sample", 55)
cache.get_if_exists("sample")  # returns 55
cache.get_if_exists("key")  # returns None
cache.put("hello", 10) 
cache.put("sample", 9)
cache.put("world", 5)
cache.get_if_exists("hello")  # returns None

Notes:

• It is assured that the value in the put method will never receive a None value. Moreover, it is assured that the capacity will always be > 0.

• All operations must be O(1).

• Aside from Python’s standard dictionary implementation ({}), you may not use any other built-in data structures.