We consider a set \(U\) of \(\) pieces of data stored in main memory. We also have a faster memory, the cache, that can hold \(k < n\) pieces of data at anyone time. We will assume that the cache initially holds some set of \(k\) items. A sequence of data items \(D = d_1,d_2,\ldots,d_m\) drawn from \(U\) is presented to us - this is the sequence of memory references we must process - and in processing them we must decide at all times which \(k\) items to keep in the cache. When item \(d_i\) is presented, we can access it very quickly if it is already in the cache; otherwise, we are required to bring it from main memory into the cache and, if the cache is full, to evict some other piece of data that is currently in the cache to make room for \(d_i\). This is called a cache miss, and we want to have as few of these as possible.

Assignment

Write a Python function òptimize(elements: list, cache: set, k: int) that receives a list of elements, a cache starting state and a number \(k\) that represents the cache size as its arguments. The function should return a list containing the evicted elements for every step element in the sequence. If there is no element evicted you should return Ǹone.

Examples

>>> optimize(['a', 'b', 'c', 'a', 'b', 'c', 'a', 'b', 'c'], {'b', 'c'}, 2)
['c', None, 'b', None, 'a', None, 'c', None, 'a']
>>> optimize(['a', 'b', 'a', 'b', 'a', 'b', 'a', 'b'], {'a'}, 1)
[None, 'a', 'b', 'a', 'b', 'a', 'b', 'a']
>>> optimize(['a', 'b', 'c', 'b', 'c', 'a', 'b'], {'a', 'b'}, 2)
[None, None, 'a', None, None, 'c', None]
>>> optimize(['a', 'b', 'c', 'd', 'a', 'd', 'e', 'a', 'd', 'b', 'c'], {'a', 'b', 'c'}, 3)
[None, None, None, 'c', None, None, 'b', None, None, 'e', 'b']
>>> optimize(['a', 'b', 'a', 'b'], {'a', 'b'}, 2)
[None, None, None, None]
>>> optimize(['a', 'b', 'c', 'd'], set(), 2)
[None,  None, 'a', 'c']