ENGG1330 Computer Programming I (22-23 Sem 2) Assignment 1 Least Recently Used (LRU) Cache Due date: noon, 17-MAR-2023 (Friday) Late submission: 20% deduction per day Coverage: Only Python libraries/features covered in this course up to and including Array (List). Using other libraries, non-built-in functions, and features (e.g., dictionary, set) is not allowed and you will be given zero marks. If you are unsure, feel free to contact us for clarification. Grading: Evaluated against a set of private test cases on VPLs. While programming style is not. graded, you are highly recommended to use function to factor your program and write clear and tidy codes, e.g., appropriate comments, concise and clear naming, appropriate spacing. Introduction You are having a technical interview for a software engineer internship at EEE Limited. You are asked to implement a least recently used (LRU) cache in Python. The interviewers know that you may be unfamiliar with LRU cache, so they also give you a description of LRU cache as follows. A cache in programming is used to store data so that future requests for the data can be served faster. A data item in cache is stored as a key-value pair [key, value], where key is a unique identifier that identifies the data item and value is the data item to be stored. For example, after computing total marks of students, a cache can be used to store the total marks by using student ID as the key and his/her total mark as the value. As a result, a request for a student's total mark can be directly retrieved from the cache instead of re-computing it to reduce the computational time. However, since the cache also occupies storage/memory, its capacity is limited. When the cache is full, an existing item must be swapped out when a new item needs to be stored. A LRU cache is a special kind of cache that defines the way of evicting item from the cache when it is full. Its policy is to evict the least recently used item. For example, a cache having capacity of 4 and is currently storing [[1, '101'], [2, '102'], [3, '103'], [4, '104']], where the 1st (leftmost) item [1, '101'] is the least recently used and the last (rightmost) item [4, '104'] is the most recently used. When the item [2, '102'] is accessed, the cache becomes [[1, '101'], [3, '103'], [4, '104'], [2, '102']] as the item [2, '102'] becomes the most recently used. When another item [10, '110'] is pushed into the cache, the cache cannot hold all of the items and must evict the least recently used item which is [1, "101'] and the cache becomes [[3, '103'], [4, '104'], [2, '102'], [10, '110']]. Your program will receive the capacity of the cache, a list of keys and a list of values as the inputs. You are then required to combine the keys and values to initialize a cache as a list of key-value pairs as follows and each key-value pair is stored as a sub-list of length 2. [[K1,V1],[K2,V2],[Kn,Vn]], where n is the number of data itens Requirements: 1. Keys must be stored as integers. 2. Values must be stored as strings. 3. If the numbers of keys and values are different, prints Warning: number of keys and values are not the same" and outputs an empty cache. 4. If the cache capacity is larger than or equal to the number of data items, stores all the data items in the cache. The order of data items stored in the cache must be the same as the order of the input key-value pairs. 5. If the cache capacity is smaller than the number of data items, keeps only those that are near the end of the inputs (right) up to the capacity. For example, if capacity is 3 , keys=[1,2,3,4,5] and values =[1,2,3,4,5], cache =[13,"3],[4,4],[5,"5]]. Inputs: 1. Capacity of the cache C (integer). C=1 means that the cache has unlimited capacity- 2. A string of integral keys K1,K2,,KMk separated by ," where Nk is number of keys. 3. A string of values V1,V2,,VNu separated by " where Nv is number of values. Outputs: 1. Warning message if Nk=Nv. 2. Cache as a list with format [[K1,V1],[K2,V2],[Kn,Vn]]. Assumptions: - 1C1000 or C=1 - 1Nk,Nv1000 - Input keys can be coriverted to integers - Input keys are unique, no duplicates. - Input values are non-null string. Hints: - You can use "A_STRUGG" split(", ") to split a string separated by a comma "," into a https://docs.pvthon.org/3/librarv/stdtypes.htmiAstr.split ENGG1330 Computer Programming I Assignment 1