Created
April 27, 2021 19:51
-
-
Save sagarr/390389b70c11b5fa730aab3efe68fbc6 to your computer and use it in GitHub Desktop.
LRUCache
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # | |
| # | |
| # Implement a LRU cache | |
| # key, value | |
| # bounded -> not more than 'n' entries | |
| # If cache is full, and you want to add another key value pair, | |
| # oldest accessed entry will be removed | |
| # | |
| # Operations like get, put, remove are constant time. | |
| # | |
| # n < 1000, 2000 | |
| # | |
| # get --> mark that entry as recently accessed | |
| # put --> mark the inserted key as recently accessed | |
| # [(1, 1), (2, 2), (3, 3)] | |
| class Node: | |
| def __init__(self, key, val): | |
| self.key = key | |
| self.val = val | |
| self.prev = None | |
| self.next = None | |
| def __repr__(self): | |
| return f"key={self.key}, val:{self.val}" | |
| class LRUCache: | |
| def __init__(self, capacity): | |
| self.cap = capacity | |
| self.cache = {} # will hold the instance of 'Node' | |
| self.left = Node(None, None) | |
| self.right = Node(None, None) | |
| self.left.next = self.right | |
| self.right.prev = self.left | |
| def _insert(self, node): | |
| temp = self.left.next | |
| self.left.next = node | |
| node.next = temp | |
| temp.prev = node | |
| def _delete(self, node): | |
| # if we are deleting the head, the prev can be none | |
| if node.prev: | |
| node.prev.next = node.next | |
| node.next.prev = node.prev | |
| def put(self, key, val): | |
| if key in self.cache: | |
| # key already present, make it recently used and update the node val | |
| node = self.cache[key] | |
| self._delete(node) | |
| node.val = val | |
| else: | |
| # put the key:val as most recently used | |
| node = Node(key, val) | |
| self._insert(node) | |
| self.cache[key] = node | |
| # check if cache is full | |
| if len(self.cache) > self.cap: | |
| # remove the oldest entry | |
| temp = self.right.prev | |
| self._delete(temp) | |
| # remove from the dict | |
| del self.cache[temp.key] | |
| def get(self, key): | |
| val = None | |
| if key in self.cache: | |
| val = self.cache[key] | |
| self._delete(val) | |
| self._insert(val) | |
| return val.val if val else -1 | |
| def remove(self, key): | |
| if key in self.cache: | |
| node = self.cache[key] | |
| # remove it from the LL | |
| self._delete(node) | |
| del self.cache[key] # if key is not present | |
| # | |
| # tests | |
| # | |
| def test_put_and_get(): | |
| lc = LRUCache(2) | |
| lc.put(1, 1) | |
| assert lc.get(1) == 1 | |
| def test_remove(): | |
| lc = LRUCache(2) | |
| lc.put(1, 1) | |
| lc.put(2, 2) | |
| lc.remove(1) | |
| assert lc.get(1) == -1 | |
| assert lc.get(2) == 2 | |
| def test_same_key_inserted_twice_will_update_the_value(): | |
| lc = LRUCache(2) | |
| lc.put(1, 1) | |
| lc.put(1, 2) | |
| lc.put(1, 3) | |
| assert lc.get(1) == 3 | |
| def test_least_recently_used_removed_when_cache_reached_to_capacity(): | |
| lc = LRUCache(2) | |
| lc.put(1, 1) | |
| lc.put(2, 2) | |
| lc.put(3, 3) # it will kick out the entry 1 | |
| assert lc.get(1) == -1 | |
| def test_recently_used_entry_removed(): | |
| lc = LRUCache(2) | |
| lc.put(1, 1) | |
| lc.put(2, 2) # 2 is recently used, now remove it | |
| lc.remove(2) | |
| assert lc.get(1) == 1 | |
| assert lc.get(2) == -1 | |
| def test_least_recently_used_entry_removed(): | |
| lc = LRUCache(2) | |
| lc.put(1, 1) | |
| lc.put(2, 2) | |
| # 1 is least recently used, lets remove it | |
| lc.remove(1) | |
| assert lc.get(1) == -1 | |
| assert lc.get(2) == 2 | |
| # run tests | |
| test_put_and_get() | |
| test_remove() | |
| test_same_key_inserted_twice_will_update_the_value() | |
| test_least_recently_used_removed_when_cache_reached_to_capacity() | |
| test_recently_used_entry_removed() | |
| test_least_recently_used_entry_removed() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment