1e:I[344796,["/_next/static/chunks/0whdtqcc5h8md.js","/_next/static/chunks/1qo17jq3o72yb.js","/_next/static/chunks/00mfjk9z2ewie.js","/_next/static/chunks/3_0kqrj9zuodm.js","/_next/static/chunks/2q9x6spyz4qxv.js","/_next/static/chunks/2cxhk-z7t3ztw.js","/_next/static/chunks/35kg0tmkl08ow.js","/_next/static/chunks/09hukzrse-ioj.js","/_next/static/chunks/3-qfh2-yexhl7.js","/_next/static/chunks/0_-iwh06bu1or.js"],"default"] 1f:T735,#include #include #include #include #include #include using namespace std; class LRUCache { public: LRUCache(int capacity) { // Initialize your data structure here } int get(int key) { // Your code here return -1; } void put(int key, int value) { // Your code here } }; int main() { // Example input parsing for local testing // Format: // Line 1: List of methods ["LRUCache", "put", "get", ...] // Line 2: List of arguments [[2], [1, 1], [1], ...] string line1, line2; if (!getline(cin, line1) || !getline(cin, line2)) return 0; // Simple parser to handle the array-like input strings auto parseStr = [](string s) { vector res; string cur; for (char c : s) { if (c == '"' || c == '[' || c == ']' || c == ',' || c == ' ') continue; cur += c; if (cur.length() > 0 && (s.find(cur + ",") != string::npos || s.find(cur + "]") != string::npos)) { // simplified parsing logic, robust parsing is complex in pure C++ without libraries } } // For competitive programming, manual parsing of JSON-like strings is tedious. // Assuming standard input redirection or simpler token-based input for local runs. return res; }; // NOTE: Implementing a full JSON-like parser for C++ boilerplate is excessive. // Instead, we will assume standard token-based input for simplicity or hardcode a test. // Example usage: // LRUCache* obj = new LRUCache(capacity); // int param_1 = obj->get(key); // obj->put(key,value); cout << "Boilerplate ready. Implement the class and instantiate in main for testing." << endl; return 0; }20:T520,import sys class LRUCache: def __init__(self, capacity: int): pass def get(self, key: int) -> int: return -1 def put(self, key: int, value: int) -> None: pass # Driver code to handle input/output if __name__ == "__main__": # Reading input from stdin # Expected format: Two lines. # Line 1: List of operation names (e.g., ["LRUCache","put","get"]) # Line 2: List of argument lists (e.g., [[2],[1,1],[1]]) input_ops = sys.stdin.readline().strip() input_params = sys.stdin.readline().strip() # Basic parsing (using eval for simplicity in Python contexts) # CAUTION: eval is dangerous in production, but standard for CP boilerplate parsing ops = eval(input_ops) params = eval(input_params) obj = None results = [] for i, op in enumerate(ops): if op == "LRUCache": obj = LRUCache(params[i][0]) results.append(None) elif op == "get": res = obj.get(params[i][0]) results.append(res) elif op == "put": obj.put(params[i][0], params[i][1]) results.append(None) # Format output to match standard null/value format print("[" + ",".join("null" if x is None else str(x) for x in results) + "]")21:Tb2c,import java.util.*; import java.io.*; class LRUCache { public LRUCache(int capacity) { } public int get(int key) { return -1; } public void put(int key, int value) { } } public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // Reading input lines String opsLine = br.readLine(); String paramsLine = br.readLine(); if (opsLine == null || paramsLine == null) return; // Basic parsing to remove brackets and quotes String[] ops = opsLine.replace("[", "").replace("]", "").replace("\"", "").split(","); // Parsing nested arrays for params is tricky with simple split. // We will use a simple character-based parser for params. List> params = parseParams(paramsLine); LRUCache obj = null; StringBuilder output = new StringBuilder(); output.append("["); for (int i = 0; i < ops.length; i++) { String op = ops[i].trim(); List argsList = params.get(i); if (op.equals("LRUCache")) { obj = new LRUCache(argsList.get(0)); output.append("null"); } else if (op.equals("get")) { int res = obj.get(argsList.get(0)); output.append(res); } else if (op.equals("put")) { obj.put(argsList.get(0), argsList.get(1)); output.append("null"); } if (i < ops.length - 1) output.append(","); } output.append("]"); System.out.println(output.toString()); } // Helper to parse string like [[2],[1,1],[1]] into Lists private static List> parseParams(String s) { List> res = new ArrayList<>(); s = s.trim(); if (s.length() < 2) return res; // Remove outer brackets s = s.substring(1, s.length() - 1); int balance = 0; StringBuilder sb = new StringBuilder(); for (char c : s.toCharArray()) { if (c == '[') { balance++; } else if (c == ']') { balance--; String inner = sb.toString(); List currentArgs = new ArrayList<>(); if (!inner.isEmpty()) { String[] parts = inner.split(","); for (String p : parts) currentArgs.add(Integer.parseInt(p.trim())); } res.add(currentArgs); sb.setLength(0); } else if (balance > 0) { sb.append(c); } } return res; } }22:T9bc,# LRU Cache ## Problem Design a data structure that follows the constraints of a **Least Recently Used (LRU) Cache**. Implement the `LRUCache` class: - `LRUCache(int capacity)` Initialize the LRU cache with **positive** size `capacity`. - `int get(int key)` Return the value of the `key` if the key exists, otherwise return `-1`. - `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. The functions `get` and `put` must each run in `O(1)` average time complexity. ## Interface (Typical LeetCode Serialization Format) Input is given as two parallel arrays: `operations` and `args`. - `operations[i]` is the method name: `"LRUCache"`, `"put"`, or `"get"`. - `args[i]` are the arguments for that operation (as a list). The function calls are executed in order, and the output is an array of return values (`null` for `LRUCache` and `put`, `int` for `get`). ## Examples ### Example 1 ``` Input: ["LRUCache","put","put","get","put","get","put","get"] [[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1]] Output: [null,null,null,1,null,-1,null,-1] ``` ### Example 2 ``` Input: ["LRUCache","put","get","put","get","get"] [[1],[2,1],[2],[3,2],[2],[3]] Output: [null,null,1,null,-1,2] ``` ### Example 3 ``` Input: ["LRUCache","put","put","get","put","get","get"] [[2],[2,1],[2,2],[2],[1,1],[1],[2]] Output: [null,null,null,2,null,1,2] ``` ### Example 4 ``` Input: ["LRUCache","put","put","get","put","get","get","get"] [[2],[1,1],[2,2],[1],[3,3],[1],[2],[3]] Output: [null,null,null,1,null,1,-1,3] ``` ### Example 5 ``` Input: ["LRUCache","put","put","put","put","get","get","get","get","put","get","get"] [[3],[1,1],[2,2],[3,3],[4,4],[4],[3],[2],[1],[5,5],[1],[2]] Output: [null,null,null,null,null,4,3,2,-1,null,-1,2] ``` ### Example 6 ``` Input: ["LRUCache","put","put","put","get","put","get"] [[2],[1,1],[1,2],[1,3],[1],[2,2],[1]] Output: [null,null,null,null,3,null,3] ``` ## Constraints - **Not provided in the source material.** Typical constraints for this LeetCode problem: `1 <= capacity <= 3000`, `0 <= key, value <= 10^4`, at most `2 * 10^5` calls. The provided editorial assumes capacity is positive and integer. ## Notes - The problem requires `O(1)` time for both operations. - The official solutions use a hash map combined with a doubly linked list (Solution 1) or a built-in ordered map (Solution 2).23:T38e7,# LRU Cache ## Solution 1: Hash Map with Doubly Linked List ### Intuition * The goal is to maintain a fixed-size collection where we can quickly find items and also quickly identify which item was used least recently. * A hash map is the natural choice for looking up values by key in constant time. * However, a hash map alone does not track the order of access. * To track order, we can use a list where the most recently used items are at the front and the least recently used are at the back. * By using a doubly linked list, we can remove any node in constant time if we have a pointer to it, and move it to the front. * Combining these two, the hash map will store keys and pointers to the corresponding nodes in the doubly linked list, allowing us to achieve all operations in constant time. ### Approach * Create a doubly linked list node structure that stores both the key and the value. * Maintain a hash map that maps keys to their corresponding node addresses in the list. * When a key is requested via a search operation, find the node in the map, move it to the head of the list, and return its value. * When a new key-value pair is added, first check if the key already exists to update it and move it to the head. * If the key is new and the cache is at capacity, remove the tail node of the list and its entry from the map. * Insert the new pair as a new node at the head of the list and record it in the map. ### Pseudocode ```pseudocode /* Define a node for the doubly linked list */ class Node { key value prev next } class LRUCache { /* Initialize the cache with a specific capacity */ LRUCache(capacity) { this.capacity = capacity this.map = new HashMap() /* Use dummy head and tail nodes to simplify edge cases */ this.head = new Node() this.tail = new Node() this.head.next = this.tail this.tail.prev = this.head } /* Helper function to add a node right after the head */ addNode(node) { node.prev = head node.next = head.next head.next.prev = node head.next = node } /* Helper function to remove an existing node from the list */ removeNode(node) { prevNode = node.prev nextNode = node.next prevNode.next = nextNode nextNode.prev = prevNode } /* Helper function to move a node to the most recent position */ moveToHead(node) { removeNode(node) addNode(node) } /* Retrieve a value from the cache */ get(key) { /* Check if key exists in the map */ if (map.contains(key)) { node = map.get(key) /* Mark as recently used */ moveToHead(node) return node.value } /* Key not found */ return -1 } /* Insert or update a value in the cache */ put(key, value) { /* If key already exists, update value and refresh position */ if (map.contains(key)) { node = map.get(key) node.value = value moveToHead(node) } else { /* Check if capacity is reached */ if (map.size() == capacity) { /* Identify the least recently used node */ lru = tail.prev /* Remove it from map and list */ map.remove(lru.key) removeNode(lru) } /* Create and add new node */ newNode = new Node(key, value) map.put(key, newNode) addNode(newNode) } } } ``` ### Code Implementation #### C++ ```cpp #include #include #include #include using namespace std; struct Node { int key; int val; Node* prev; Node* next; Node() : key(0), val(0), prev(nullptr), next(nullptr) {} Node(int k, int v) : key(k), val(v), prev(nullptr), next(nullptr) {} }; class solution { private: int capacity; unordered_map cache; Node* head; Node* tail; void addNode(Node* node) { node->prev = head; node->next = head->next; head->next->prev = node; head->next = node; } void removeNode(Node* node) { Node* prev = node->prev; Node* next = node->next; prev->next = next; next->prev = prev; } void moveToHead(Node* node) { removeNode(node); addNode(node); } Node* popTail() { Node* res = tail->prev; removeNode(res); return res; } public: solution(int cap) : capacity(cap) { head = new Node(); tail = new Node(); head->next = tail; tail->prev = head; } int get(int key) { if (cache.find(key) == cache.end()) { return -1; } Node* node = cache[key]; moveToHead(node); return node->val; } void put(int key, int value) { if (cache.find(key) != cache.end()) { Node* node = cache[key]; node->val = value; moveToHead(node); } else { Node* newNode = new Node(key, value); cache[key] = newNode; addNode(newNode); if (cache.size() > capacity) { Node* tail = popTail(); cache.erase(tail->key); delete tail; } } } }; ``` #### Python ```python class Node: def __init__(self, key=0, value=0): self.key = key self.value = value self.prev = None self.next = None class solution: def __init__(self, capacity: int): self.capacity = capacity self.cache = {} self.head = Node() self.tail = Node() self.head.next = self.tail self.tail.prev = self.head def _add_node(self, node): node.prev = self.head node.next = self.head.next self.head.next.prev = node self.head.next = node def _remove_node(self, node): prev_node = node.prev next_node = node.next prev_node.next = next_node next_node.prev = prev_node def _move_to_head(self, node): self._remove_node(node) self._add_node(node) def _pop_tail(self): res = self.tail.prev self._remove_node(res) return res def get(self, key: int) -> int: if key in self.cache: node = self.cache[key] self._move_to_head(node) return node.value return -1 def put(self, key: int, value: int) -> None: if key in self.cache: node = self.cache[key] node.value = value self._move_to_head(node) else: new_node = Node(key, value) self.cache[key] = new_node self._add_node(new_node) if len(self.cache) > self.capacity: lru = self._pop_tail() del self.cache[lru.key] ``` #### Java ```java import java.util.*; class Node { int key; int value; Node prev; Node next; Node() {} Node(int key, int value) { this.key = key; this.value = value; } } class Solution { private Map cache = new HashMap<>(); private int capacity; private Node head, tail; public Solution(int capacity) { this.capacity = capacity; head = new Node(); tail = new Node(); head.next = tail; tail.prev = head; } private void addNode(Node node) { node.prev = head; node.next = head.next; head.next.prev = node; head.next = node; } private void removeNode(Node node) { Node prev = node.prev; Node next = node.next; prev.next = next; next.prev = prev; } private void moveToHead(Node node) { removeNode(node); addNode(node); } private Node popTail() { Node res = tail.prev; removeNode(res); return res; } public int get(int key) { Node node = cache.get(key); if (node == null) return -1; moveToHead(node); return node.value; } public void put(int key, int value) { Node node = cache.get(key); if (node == null) { Node newNode = new Node(key, value); cache.put(key, newNode); addNode(newNode); if (cache.size() > capacity) { Node lru = popTail(); cache.remove(lru.key); } } else { node.value = value; moveToHead(node); } } } ``` #### JavaScript ```javascript class Node { constructor(key = 0, value = 0) { this.key = key; this.value = value; this.prev = null; this.next = null; } } class Solution { constructor(capacity) { this.capacity = capacity; this.cache = new Map(); this.head = new Node(); this.tail = new Node(); this.head.next = this.tail; this.tail.prev = this.head; } _addNode(node) { node.prev = this.head; node.next = this.head.next; this.head.next.prev = node; this.head.next = node; } _removeNode(node) { let prev = node.prev; let next = node.next; prev.next = next; next.prev = prev; } _moveToHead(node) { this._removeNode(node); this._addNode(node); } _popTail() { let res = this.tail.prev; this._removeNode(res); return res; } get(key) { if (!this.cache.has(key)) return -1; let node = this.cache.get(key); this._moveToHead(node); return node.value; } put(key, value) { if (this.cache.has(key)) { let node = this.cache.get(key); node.value = value; this._moveToHead(node); } else { let newNode = new Node(key, value); this.cache.set(key, newNode); this._addNode(newNode); if (this.cache.size > this.capacity) { let tail = this._popTail(); this.cache.delete(tail.key); } } } } ``` ### Complexity Analysis - **Time Complexity:** `O(1)` for both `get` and `put`. - **Space Complexity:** `O(capacity)` for the hash map and doubly linked list. ## Solution 2: Built-in Ordered Hash Map ### Intuition * Some programming languages provide built-in data structures that combine a hash map with a list to preserve insertion order. * Python's `OrderedDict` or JavaScript's `Map` automatically track order. By deleting and re-inserting a key, we mark it as most recently used. * The least recently used item is always the first in order. ### Approach * Use an ordered mapping structure. * In `get`, if key exists, retrieve value and move key to end. * In `put`, if key exists, update value and move to end. If new and at capacity, remove the first key. ### Pseudocode ```pseudocode class LRUCache { LRUCache(capacity) { this.capacity = capacity this.orderMap = new OrderedMap() } get(key) { if (orderMap.contains(key)) { val = orderMap.get(key) orderMap.move_to_end(key) return val } return -1 } put(key, value) { if (orderMap.contains(key)) { orderMap.set(key, value) orderMap.move_to_end(key) } else { if (orderMap.size() == capacity) { orderMap.pop_first() } orderMap.set(key, value) } } } ``` ### Code Implementation #### C++ (manual simulation) ```cpp #include #include #include #include #include using namespace std; class solution { private: int capacity; list> items; unordered_map>::iterator> cache; public: solution(int cap) : capacity(cap) {} int get(int key) { if (cache.find(key) == cache.end()) return -1; items.splice(items.begin(), items, cache[key]); return cache[key]->second; } void put(int key, int value) { if (cache.find(key) != cache.end()) { items.splice(items.begin(), items, cache[key]); cache[key]->second = value; return; } if (items.size() == capacity) { int lruKey = items.back().first; items.pop_back(); cache.erase(lruKey); } items.emplace_front(key, value); cache[key] = items.begin(); } }; ``` #### Python ```python from collections import OrderedDict class solution(OrderedDict): def __init__(self, capacity: int): self.capacity = capacity def get(self, key: int) -> int: if key not in self: return -1 self.move_to_end(key) return self[key] def put(self, key: int, value: int) -> None: if key in self: self.move_to_end(key) self[key] = value if len(self) > self.capacity: self.popitem(last=False) ``` #### Java (`LinkedHashMap` with access order) ```java import java.util.LinkedHashMap; import java.util.Map; class Solution extends LinkedHashMap { private int capacity; public Solution(int capacity) { super(capacity, 0.75f, true); this.capacity = capacity; } public int get(int key) { return super.getOrDefault(key, -1); } public void put(int key, int value) { super.put(key, value); } @Override protected boolean removeEldestEntry(Map.Entry eldest) { return size() > capacity; } } ``` #### JavaScript (`Map`) ```javascript class Solution { constructor(capacity) { this.capacity = capacity; this.cache = new Map(); } get(key) { if (!this.cache.has(key)) return -1; const val = this.cache.get(key); this.cache.delete(key); this.cache.set(key, val); return val; } put(key, value) { if (this.cache.has(key)) { this.cache.delete(key); } else if (this.cache.size >= this.capacity) { this.cache.delete(this.cache.keys().next().value); } this.cache.set(key, value); } } ``` ### Complexity Analysis - **Time Complexity:** `O(1)` average per operation. - **Space Complexity:** `O(capacity)`.16:[["$","script",null,{"type":"application/ld+json","dangerouslySetInnerHTML":{"__html":"{\"@context\":\"https://schema.org\",\"@type\":\"LearningResource\",\"learningResourceType\":\"Coding Question\",\"name\":\"LRU Cache\",\"description\":\"LRU Cache\",\"educationalLevel\":\"medium\",\"about\":{\"@type\":\"Organization\",\"name\":\"Media.net IIT BHU\"},\"provider\":{\"@type\":\"Organization\",\"name\":\"OAHelper\",\"url\":\"https://www.oahelper.in\"},\"isPartOf\":{\"@type\":\"WebSite\",\"name\":\"OAHelper\",\"url\":\"https://www.oahelper.in\"},\"url\":\"https://www.oahelper.in/problems/MjQzOHww/lru-cache\"}"}}],["$","script",null,{"type":"application/ld+json","dangerouslySetInnerHTML":{"__html":"{\"@context\":\"https://schema.org\",\"@type\":\"BreadcrumbList\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https://www.oahelper.in/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Problems\",\"item\":\"https://www.oahelper.in/problems\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"LRU Cache\",\"item\":\"https://www.oahelper.in/problems/MjQzOHww/lru-cache\"}]}"}}],["$","$L1e",null,{"fallback":["$","section",null,{"className":"mx-auto max-w-5xl px-6 py-24 text-white","children":[["$","h1",null,{"className":"mb-5 text-3xl font-bold","children":"LRU Cache"}],["$","p",null,{"children":["Company: ","Media.net IIT BHU"]}],["$","p",null,{"children":["Difficulty: ","medium"]}],false,["$","div",null,{"children":[["$","h2",null,{"children":"Problem Statement"}],["$","p",null,{"children":"LRU Cache"}]]}],false,["$","nav",null,{"aria-label":"Related company pages","children":[["$","$L9",null,{"href":"/company-questions/medianet-iit-bhu","children":["More ","Media.net IIT BHU"," OA questions"]}],["$","$L9",null,{"href":"/interview-experiences","children":"Interview experiences"}]]}]]}],"id":"MjQzOHww","initialQuestion":{"id":"MjQzOHww","title":"LRU Cache","google_doc_link":null,"problem_statement":"

LRU Cache

","solution_cpp":"#include \n#include \n#include \n\nclass LRUCache {\nprivate:\n int capacity;\n std::list> items;\n std::unordered_map>::iterator> cache;\n\npublic:\n LRUCache(int capacity) : capacity(capacity) {}\n\n int get(int key) {\n if (cache.find(key) == cache.end()) {\n return -1;\n }\n items.splice(items.begin(), items, cache[key]);\n return cache[key]->second;\n }\n\n void put(int key, int value) {\n if (cache.find(key) != cache.end()) {\n items.splice(items.begin(), items, cache[key]);\n cache[key]->second = value;\n return;\n }\n if (items.size() == capacity) {\n int lruKey = items.back().first;\n items.pop_back();\n cache.erase(lruKey);\n }\n items.emplace_front(key, value);\n cache[key] = items.begin();\n }\n};","solution_python":null,"solution_java":null,"pregiven_code_cpp":"$1f","pregiven_code_python":"$20","pregiven_code_java":"$21","difficulty":"medium","question_type":"coding","premium_required":0,"created_at":"2025-11-05T12:39:42+00:00","updated_at":"2026-08-09T22:19:04.937636+00:00","solution_code":null,"solution":null,"pregiven_code":null,"input_test_case":"[\"[\\\"LRUCache\\\",\\\"put\\\",\\\"put\\\",\\\"get\\\",\\\"put\\\",\\\"get\\\",\\\"put\\\",\\\"get\\\"]\\n[[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1]]\", \"[\\\"LRUCache\\\",\\\"put\\\",\\\"get\\\",\\\"put\\\",\\\"get\\\",\\\"get\\\"]\\n[[1],[2,1],[2],[3,2],[2],[3]]\"]","output_test_case":"[\"[null,null,null,1,null,-1,null,-1]\", \"[null,null,1,null,-1,2]\"]","lc_tags":"[\"Hash Table\", \"Linked List\", \"Design\", \"Doubly-Linked List\"]","visual_animation":null,"difficulty_score":60,"md_problem_statement":"$22","unique_company_name":"medianet","sql_solution":null,"bash_solution":null,"js_solution":null,"editorial":"$23","hidden_test_cases_blob_count":null,"youtube_tutorial":null,"prompt_solution":null,"campus_type":"on_campus","college_name":"IIT BHU","role":null,"hidden_test_cases_ref":null,"is_mock_oa":false,"publication_status":"published","has_image":true,"company_name":"Media.net IIT BHU","is_first_in_company":true,"company_ref":"ODQ3fDA","total_test_cases":6,"hidden_test_cases_count":4},"isQotdToday":false,"qotdReward":5}]]