Most Recently Used Cache Your job is do design and implement a data structure called Most Recently Used (MRU) cache. This data structure supports the following operations put(key, value) - Inserts the pair passed as input into the cache. If the given key is already in the cache, its associated value is replaced with the one passed as input. If the cache is at its maximum capacity, it should invalidate the most recently used pair before inserting the new one. get(key): Returns the value associated with the given input key if the key exists in the cache, otherwise None is returned. size() Returns the number of pairs currently stored in the cache. max_capacity() Returns the maximum capacity of the cache All operations MUST run in O(1) time complexity to receive credit. You are free to use Pythons set and/or dictionary data structures. If you need to use a doubly linked list (hint), you need to code it yourself. If you find this problem too hard, contact the instructor or a TA / IA / PL. We can help with hints!

class MRUCache:

def __init__(self, max_capacity=1000):

self.max_capacity = max_capacity # maximum memory capacity

# TODO: Feel free to add more lines here

# TODO: Implement this method - Required Time Complexity: O(1)

# Gets the value of the key if the key exists

# in the cache, otherwise return None.

def get(self, key):

"""Implements 'value = self[idx]'

Raises IndexError if idx is invalid."""

raise NotImplementedError()

# TODO: Implement this method - Required Time Complexity: O(1)

# Insert or replace the value if the given key is not already in the cache.

# When the cache reaches its maximum capacity, it should invalidate the

# most recently used item before inserting a new item.

def put(self, key, value):

"""Implements 'self[idx] = value'

Raises IndexError if idx is invalid."""

raise NotImplementedError()

# TODO: Implement this method - Required Time Complexity: O(1)

# Returns the number of key/value pairs currently stored in the cache

def size(self):

"""Implements 'self[idx] = value'

Raises IndexError if idx is invalid."""

raise NotImplementedError()

# TODO: Implement this method - Required Time Complexity: O(1)

# Returns the maximum capacity of the cache

def max_capacity(self):

"""Implements 'self[idx] = value'

Raises IndexError if idx is invalid."""

raise NotImplementedError()

class MRUCache:

def __init__(self, max_capacity=1000):

self.max_capacity = max_capacity # maximum memory capacity

# TODO: Feel free to add more lines here

# TODO: Implement this method - Required Time Complexity: O(1)

# Gets the value of the key if the key exists

# in the cache, otherwise return None.

def get(self, key):

"""Implements 'value = self[idx]'

Raises IndexError if idx is invalid."""

raise NotImplementedError()

# TODO: Implement this method - Required Time Complexity: O(1)

# Insert or replace the value if the given key is not already in the cache.

# When the cache reaches its maximum capacity, it should invalidate the

# most recently used item before inserting a new item.

def put(self, key, value):

"""Implements 'self[idx] = value'

Raises IndexError if idx is invalid."""

raise NotImplementedError()

# TODO: Implement this method - Required Time Complexity: O(1)

# Returns the number of key/value pairs currently stored in the cache

def size(self):

"""Implements 'self[idx] = value'

Raises IndexError if idx is invalid."""

raise NotImplementedError()

# TODO: Implement this method - Required Time Complexity: O(1)

# Returns the maximum capacity of the cache

def max_capacity(self):

"""Implements 'self[idx] = value'

Raises IndexError if idx is invalid."""

raise NotImplementedError()

class MRUCache:

def __init__(self, max_capacity=1000):

self.max_capacity = max_capacity # maximum memory capacity

# TODO: Feel free to add more lines here

# TODO: Implement this method - Required Time Complexity: O(1)

# Gets the value of the key if the key exists

# in the cache, otherwise return None.

def get(self, key):

"""Implements 'value = self[idx]'

Raises IndexError if idx is invalid."""

raise NotImplementedError()

# TODO: Implement this method - Required Time Complexity: O(1)

# Insert or replace the value if the given key is not already in the cache.

# When the cache reaches its maximum capacity, it should invalidate the

# most recently used item before inserting a new item.

def put(self, key, value):

"""Implements 'self[idx] = value'

Raises IndexError if idx is invalid."""

raise NotImplementedError()

# TODO: Implement this method - Required Time Complexity: O(1)

# Returns the number of key/value pairs currently stored in the cache

def size(self):

"""Implements 'self[idx] = value'

Raises IndexError if idx is invalid."""

raise NotImplementedError()

# TODO: Implement this method - Required Time Complexity: O(1)

# Returns the maximum capacity of the cache

def max_capacity(self):

"""Implements 'self[idx] = value'

Raises IndexError if idx is invalid."""

raise NotImplementedError()

# Use this code cell to test the implementation of your MRUCache (test cases)

0

2

4

6

8

10

12

14

16

18