LRU Cache Design Problem

LRU Cache Design Problem — ExecCode Medium DSA Practice

Solve the LRU Cache Design problem on ExecCode. Free online medium DSA practice in Design. Write and run code in Java, C++, Python — no signup required to run.

Problem description

Description Imagine you're solving LRU Cache Design in a real system where you must be correct and efficient. Problem Design and implement an LRU (Least Recently Used) cache that supports two operations: get and put. get key: If the key exists in the cache, return its value and mark the key as most recently used. If the key does not exist, return -1. put key value: Insert or update the value for the key. If the key already exists, update its value and mark it as most recently used. If the cache is at capacity and a new key is inserted, evict the least recently used key before inserting. You will be given the cache capacity followed by a sequence of operations. For each get operation, output the returned value on its own line, in the order the get operations occur. Input Format The input is provided as a single stdin blob with the following structure: - First line: an integer C, the capacity of the LRU cache (C >= 0). Second line: an integer N, the number of subsequent operations. Next N lines: each line is either: - "put k v" — insert or update key k with value v (both integers), or - "get k" — query the value for key k. Output Format For every get operation in the order they appe…

Examples

Input 2 4 put 1 1 put 2 2 get 1 put 3 3; Output 1. Input 2 5 put 1 1 put 2 2 get 1 put 3 3 get 2; Output 1 -1

Constraints

1 <= n <= 10^5

Practice LRU Cache Design free on ExecCode. Browse DSA problems, topic map, and placement guides.