{"id":"a22b710a-61d6-4024-947e-78898f3b946e","name":"Design Lru Chache","description":"1. Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.\r\n\r\n2. Discards the least recently used items first. This algorithm requires keeping track of what \r\n was used when, which is expensive if one wants to make sure the algorithm always discards \r\n the least recently used item. General implementations of this technique require keeping \r\n \"age bits\" for cache-lines and track the \"Least Recently Used\" cache-line based on age-bits. \r\n In such an implementation, every time a cache-line is used, the age of all other cache-lines changes\r\n \r\n3. mplement the LRUCache class: \r\n 3.1 LRUCache(int capacity) Initialize the LRU cache with positive size capacity.\r\n 3.2 int get(int key) Return the value of the key if the key exists, otherwise return -1.\r\n 3.3 void put(int key, int value) Update the value of the key if the key exists. Otherwise, \r\n add the key-value pair to the cache. If the number of keys exceeds the capacity from this \r\n operation, evict the least recently used key.\r\n\r\n4. Could you do get and put in O(1) time complexity? \r\n\r\nNote -> Use the code snippet and follow the algorithm discussed in question video. The judge can't \r\n force you but the intention is to teach a concept. Play in spirit of the question.\r\n","inputFormat":"input in managed for you.","outputFormat":"output in managed for you.","constraints":"1 &lt;= N &lt;= 10^6\r\n1 &lt;= capacity &lt;= 10^3","sampleCode":{"cpp":{"code":"#include <iostream>\r\n#include <unordered_map>\r\nusing namespace std;\r\n\r\nclass LRUCache\r\n{\r\npublic:\r\n LRUCache(int capacity)\r\n {\r\n }\r\n\r\n int get(int key)\r\n {\r\n return 0;\r\n }\r\n\r\n void put(int key, int value)\r\n {\r\n }\r\n};\r\n\r\nint main()\r\n{\r\n int n, size; // no of operations\r\n cin >> n >> size;\r\n // 0 stand for put, 1 stand for get\r\n LRUCache lru(size);\r\n\r\n while (n-- > 0)\r\n {\r\n int op, val, key;\r\n cin >> op;\r\n if (op == 0)\r\n {\r\n cin >> val;\r\n cin >> key;\r\n lru.put(val, key);\r\n }\r\n else\r\n {\r\n cin >> val;\r\n cout << lru.get(val) << endl;\r\n }\r\n }\r\n\r\n return 0;\r\n}"},"java":{"code":"import java.util.*;\r\n\r\nclass Main {\r\n public static class LRUCache {\r\n public LRUCache(int capacity) {\r\n\r\n }\r\n\r\n public int get(int key) {\r\n return 0;\r\n }\r\n\r\n // app name, app state\r\n public void put(int key, int value) {\r\n }\r\n\r\n }\r\n\r\n public static void main(String[] args) {\r\n Scanner scn = new Scanner(System.in);\r\n\r\n int n = scn.nextInt(); // no of operations\r\n // 0 stand for put, 1 stand for get\r\n int size = scn.nextInt();\r\n LRUCache lru = new LRUCache(size);\r\n\r\n while (n-- > 0) {\r\n int op = scn.nextInt();\r\n if (op == 0)\r\n lru.put(scn.nextInt(), scn.nextInt());\r\n else\r\n System.out.println(lru.get(scn.nextInt()));\r\n }\r\n }\r\n}"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"5 2\r\n0 5 2\r\n0 6 8\r\n0 5 3\r\n0 4 7\r\n1 5","sampleOutput":"3\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"1e4c8949-5890-4d15-be5b-6601c7e2029a","name":"Linked List For Intermediate","slug":"linked-list-for-intermediate-637","type":0},{"id":"6ed5a412-e59b-47df-951e-5eedf466005c","name":"Design Lru Chache","slug":"design-lru-chache","type":1}],"next":{"id":"65df21da-fd65-4296-8a07-688b9d249877","name":"Design LRU cache MCQ","type":0,"slug":"design-lru-cache-mcq"},"prev":{"id":"2bf64c68-0dc5-47a3-97d6-ac5752e2936f","name":"Display Forward and Backward in doubly linked list","type":3,"slug":"display-forward-and-backward-in-doubly-linked-list"}}}

Design Lru Chache

1. Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. 2. Discards the least recently used items first. This algorithm requires keeping track of what was used when, which is expensive if one wants to make sure the algorithm always discards the least recently used item. General implementations of this technique require keeping "age bits" for cache-lines and track the "Least Recently Used" cache-line based on age-bits. In such an implementation, every time a cache-line is used, the age of all other cache-lines changes 3. mplement the LRUCache class: 3.1 LRUCache(int capacity) Initialize the LRU cache with positive size capacity. 3.2 int get(int key) Return the value of the key if the key exists, otherwise return -1. 3.3 void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key. 4. Could you do get and put in O(1) time complexity? Note -> Use the code snippet and follow the algorithm discussed in question video. The judge can't force you but the intention is to teach a concept. Play in spirit of the question.

{"id":"a22b710a-61d6-4024-947e-78898f3b946e","name":"Design Lru Chache","description":"1. Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.\r\n\r\n2. Discards the least recently used items first. This algorithm requires keeping track of what \r\n was used when, which is expensive if one wants to make sure the algorithm always discards \r\n the least recently used item. General implementations of this technique require keeping \r\n \"age bits\" for cache-lines and track the \"Least Recently Used\" cache-line based on age-bits. \r\n In such an implementation, every time a cache-line is used, the age of all other cache-lines changes\r\n \r\n3. mplement the LRUCache class: \r\n 3.1 LRUCache(int capacity) Initialize the LRU cache with positive size capacity.\r\n 3.2 int get(int key) Return the value of the key if the key exists, otherwise return -1.\r\n 3.3 void put(int key, int value) Update the value of the key if the key exists. Otherwise, \r\n add the key-value pair to the cache. If the number of keys exceeds the capacity from this \r\n operation, evict the least recently used key.\r\n\r\n4. Could you do get and put in O(1) time complexity? \r\n\r\nNote -> Use the code snippet and follow the algorithm discussed in question video. The judge can't \r\n force you but the intention is to teach a concept. Play in spirit of the question.\r\n","inputFormat":"input in managed for you.","outputFormat":"output in managed for you.","constraints":"1 &lt;= N &lt;= 10^6\r\n1 &lt;= capacity &lt;= 10^3","sampleCode":{"cpp":{"code":"#include <iostream>\r\n#include <unordered_map>\r\nusing namespace std;\r\n\r\nclass LRUCache\r\n{\r\npublic:\r\n LRUCache(int capacity)\r\n {\r\n }\r\n\r\n int get(int key)\r\n {\r\n return 0;\r\n }\r\n\r\n void put(int key, int value)\r\n {\r\n }\r\n};\r\n\r\nint main()\r\n{\r\n int n, size; // no of operations\r\n cin >> n >> size;\r\n // 0 stand for put, 1 stand for get\r\n LRUCache lru(size);\r\n\r\n while (n-- > 0)\r\n {\r\n int op, val, key;\r\n cin >> op;\r\n if (op == 0)\r\n {\r\n cin >> val;\r\n cin >> key;\r\n lru.put(val, key);\r\n }\r\n else\r\n {\r\n cin >> val;\r\n cout << lru.get(val) << endl;\r\n }\r\n }\r\n\r\n return 0;\r\n}"},"java":{"code":"import java.util.*;\r\n\r\nclass Main {\r\n public static class LRUCache {\r\n public LRUCache(int capacity) {\r\n\r\n }\r\n\r\n public int get(int key) {\r\n return 0;\r\n }\r\n\r\n // app name, app state\r\n public void put(int key, int value) {\r\n }\r\n\r\n }\r\n\r\n public static void main(String[] args) {\r\n Scanner scn = new Scanner(System.in);\r\n\r\n int n = scn.nextInt(); // no of operations\r\n // 0 stand for put, 1 stand for get\r\n int size = scn.nextInt();\r\n LRUCache lru = new LRUCache(size);\r\n\r\n while (n-- > 0) {\r\n int op = scn.nextInt();\r\n if (op == 0)\r\n lru.put(scn.nextInt(), scn.nextInt());\r\n else\r\n System.out.println(lru.get(scn.nextInt()));\r\n }\r\n }\r\n}"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"5 2\r\n0 5 2\r\n0 6 8\r\n0 5 3\r\n0 4 7\r\n1 5","sampleOutput":"3\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"1e4c8949-5890-4d15-be5b-6601c7e2029a","name":"Linked List For Intermediate","slug":"linked-list-for-intermediate-637","type":0},{"id":"6ed5a412-e59b-47df-951e-5eedf466005c","name":"Design Lru Chache","slug":"design-lru-chache","type":1}],"next":{"id":"65df21da-fd65-4296-8a07-688b9d249877","name":"Design LRU cache MCQ","type":0,"slug":"design-lru-cache-mcq"},"prev":{"id":"2bf64c68-0dc5-47a3-97d6-ac5752e2936f","name":"Display Forward and Backward in doubly linked list","type":3,"slug":"display-forward-and-backward-in-doubly-linked-list"}}}
plane

Editor


Loading...

Design Lru Chache

medium

1. Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. 2. Discards the least recently used items first. This algorithm requires keeping track of what was used when, which is expensive if one wants to make sure the algorithm always discards the least recently used item. General implementations of this technique require keeping "age bits" for cache-lines and track the "Least Recently Used" cache-line based on age-bits. In such an implementation, every time a cache-line is used, the age of all other cache-lines changes 3. mplement the LRUCache class: 3.1 LRUCache(int capacity) Initialize the LRU cache with positive size capacity. 3.2 int get(int key) Return the value of the key if the key exists, otherwise return -1. 3.3 void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key. 4. Could you do get and put in O(1) time complexity? Note -> Use the code snippet and follow the algorithm discussed in question video. The judge can't force you but the intention is to teach a concept. Play in spirit of the question.

Constraints

1 <= N <= 10^6 1 <= capacity <= 10^3

Format

Input

input in managed for you.

Output

output in managed for you.

Example

Sample Input

5 2 0 5 2 0 6 8 0 5 3 0 4 7 1 5

Sample Output

3

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode