Data Structures and Analysis

Design a data structure that supports the following API: class LRU LRU(N): initialize an empty LRU cache with capacity N, which is a positive integer a string. inCache(key) is the given key in the LRU cache? This method should return a Boolean value: True, if the key is in the LRU cache or false otherwise. The argument key is a string. The operations cache() and inCache() should take constant time on average under the uniform hashing assumption. For Example: 1ru=LRU(5) Give a crisp and concise English description of your data structure and how the inCache0) and cache() operation are implemented. Your answer will be graded on correctness, efficiency, and clarity. sequence of operations shown above. b) Explain how inCache(key) would be implemented c) Explain how cache(key) would be implemented