ENGG1330 Computer Programming I Assignment 1 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']]. After passing all the tests in Level 2, the interviewers proceed to ask a follow-up question to truly test your ability in programming and problem solving. They tell you that it is computationally expensive to move the most recently used item to the end of the list in order to conform to the description in the Introduction, i.e., the 1it (leftmost) item is the least recently used while the last (rightmost) item is the most recently used. It is because all the subsequent items need to be moved to the left by 1. For example, the steps of moving 2 in [1,2,3,4] to the end of the list is [1,2,3,4][1,3,3,4][1,3,4,4][1,3,4,2]. As a result, moving item to the end of a list should be avoided if possible. The follow-up question is whether you can implement a solution without the need of moving items in the cache once they are inserted. Specifically, when accessing an item, NO movement should be made to any item but you are allowed to modify the item. When adding a new item to the list, it should be added to the end of the list if the cache is not full. Otherwise, are allowed. For example, given a cache of capacity 4 : [[1,100],[2,200],[3,300]], the cache contents will be updated as follows. 1. get(2)[11,100],[2,2200],[3,300] 2. put(4,'400') [[1,100],[2,200],[3,300],[4,400]] 3. get(1)[11,100],[2,200],[3,300],[4,400]] 4. put(5,'500') [[1,100],[2,200],[5, '500'], [4,400]] As a result, there is NO limitation on how you are going to store the data. However, ONLY one list can be created and used for the cache and no other auxiliary list is allowed. Note: The test cases on VPL will be time limited. If you see timeout on VPL, it means your program is too slow and need further optimization. Nested loops are usually the most expensive operations and it is a good starting point for optimization. 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,,K Nik separated by ", , where Nk is number of keys. 3. A string of values V1,V2,,VN separated by , " where Nv is number of values. 4. A series of commands consisting of either "get, KEY" or "put, KEY,VALUE" separated by a newline character. 5. The input must be ended with "end". 5 ENGG1330 Computer Programming Assignment 1 Outputs: 1. Warning message if Nk=N2. 2. For every get operation, print the value of the key-value pair if the key exists, otherwise print "NULL". 3. Cache as a list with format [[K1,V1],[K2,V2],[Kn,Vn]] where the ordering is no longer based on recent usage but follows the specs listed in the question. Assumptions - 1C10000 or C=1 - 1Nk,Nw10000 - Input keys can be converted to integers - Input keys are unique, no duplicates - Input values are non-null string - None of the values will be equal to "NULL" - Time constraint will be imposed on VPL and timeout is possible Hints: - You may want to change the structure of how you keep the data. For example, you can store extra information alongside with each data item if you find it useful. - It is acceptable if put and/or other operations take more time to run as long as the total time is within the time constraint. Your program should be well within the time constraint unless it has multiple layers of loop. 6 ENGG1330 Computer Programming I Assignment 1