pytudes._2021.leetcode.medium._146__lru_cache

https://leetcode.com/problems/lru-cache/

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Constraints:

• 1 ≤ capacity ≤ 3000

• 0 ≤ key ≤ 3000

• 0 ≤ value ≤ 104

• At most 3 * 10**4 calls will be made to get and put.

Examples:

>>> lRUCache = LRUCache(capacity=2)
>>> lRUCache.put(key=1, value=0) # cache is {1=0}
>>> lRUCache.get(key=1)
0
>>> lRUCache.put(key=1, value=1) # LRU key was 1, overwrites value at key 1, cache is {1=1}
>>> lRUCache.put(key=2, value=2) # cache is {1=1, 2=2}
>>> lRUCache.get(key=1)
1
>>> lRUCache.put(key=3, value=3) # LRU key was 2, evicts key 2, cache is {1=1, 3=3}
>>> lRUCache.get(key=2)
-1
>>> lRUCache.put(key=4, value=4) # LRU key was 1, evicts key 1, cache is {4=4, 3=3}
>>> lRUCache.get(key=1)
-1
>>> lRUCache.get(key=3)
3
>>> lRUCache.get(key=4)
4

Module Contents

Classes

DoublyLinkedListNode	Doubly-linked list node
LRUCache	Emulates an LRU cache,

Functions

_remove_from_lru_list(cache_entry)

Removes a given node from its doubly-linked list

class pytudes._2021.leetcode.medium._146__lru_cache.DoublyLinkedListNode(key, val)

Doubly-linked list node

Attributes:

key: unique key associated with a DoublyLinkedListNode instance val: value associated the key prev: [optional] predecessor node next: [optional] successor node

class pytudes._2021.leetcode.medium._146__lru_cache.LRUCache(capacity)

Emulates an LRU cache,

Internally, LRUCache uses a hashmap and doubly-linked list for efficient cache insertions, deletions, and updates.

Complexity:

n = capacity of cache Time:

get: O(1) put: O(1)

Space: O(n) (2n: n for the hash table, n (+2: dummy head and tail) for the linked list)

Attributes:

capacity:

an integer indicating how many entries the cache can store before an entry must be evicted

cache:

a dictionary mapping keys to cache Nodes

head:

a dummy DoublyLinkedListNode used as a handle to the first (MRU) cache entry

tail:

a dummy DoublyLinkedListNode used as a handle to the last (LRU) cache entry

Inits LRUCache with designated capacity

Parameters:

capacity (int) –

_make_mru(cache_entry)

Moves given cache entry to the MRU position in the LRU list

Implicitly right-shifting all other cache entries in the LRU list

Args:

cache_entry: entry which we are movign to the MRU position

Parameters:

cache_entry (DoublyLinkedListNode) –

Return type:

None

get(key)

Returns the value of the cache entry corresponding to the given key

Args:

key: key of the cache entry to retrieve

Parameters:

key (int) –

Return type:

int

put(key, value)

Inserts (key, value) item into cache

Evicting the LRU entry if the cache’s capacity will be exceeded.

Args:

key: key of item to insert value: value of item to insert

Parameters:

• key (int) –

• value (int) –

Return type:

None

pytudes._2021.leetcode.medium._146__lru_cache._remove_from_lru_list(cache_entry)

Removes a given node from its doubly-linked list

Precondition: cache_entry’s prev and next attributes are DoublyLinkedListNode instances

Module-level function following guidance from https://google.github.io/styleguide/pyguide.html#217-function-and-method-decorators Namely:

“Never use staticmethod unless forced to in order to integrate with an API defined in an existing library. Write a module level function instead.”

Args:

cache_entry: cache entry which we must excise from the LRU list

Parameters:

cache_entry (DoublyLinkedListNode) –

Return type:

None