![]() ![]() Initially, the cache is empty, and all the elements are stored in memory. Suppose we have five elements in the main memory, A1 to A5. Let's understand the problem via an example Time required to get the least recently used element should be O(1).Access time for any item should be O(1).We want the following specifications from our LRU cache: If the number of keys exceeds the capacity of this operation, evict the least recently used key. Otherwise, add the key-value pair to the cache. void put(int key, int value): update the value of the key if the key exists.int get(int key): return the value of the key if the key exists, otherwise, return -1.LRUCache(int capacity): initialize the LRU cache with positive size capacity.We need to implement the LRUCache class with the following operations: So our goal is to design a data structure that follows the constraints of a Least Recently Used (LRU) cache. It is used to organize items in order of their use, which allows identifying items that have not been used for a long time. The Least Recently Used (LRU) is one of the popular caching strategies, which defines the policy to discard the least recently used items first from the cache and make room for new elements when the cache is full. ![]() Key takeaway: an excellent algorithm to learn data structure design and problem-solving using hash tables and doubly-linked lists. Difficulty: Hard, Asked-in: Amazon, Microsoft, Adobe, Google ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |