Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Stack & Queue

LRU Cache

Hard · Stack & Queue · Asked at Amazon, Microsoft, Google, Meta, Flipkart

Implement a Least Recently Used cache with capacity c and process the operations:

Input

First line: c q. Next q lines: one operation each.

Output

One line for every get.

Constraints

A hash map from key to a node of a doubly linked list ordered by recency: move a node to the front on use, evict from the back.

Example 1

Input

2 9
put 1 1
put 2 2
get 1
put 3 3
get 2
put 4 4
get 1
get 3
get 4

Output

1
-1
-1
3
4

Example 2

Input

1 4
put 2 1
get 2
put 3 2
get 2

Output

1
-1

Hints

  1. You need O(1) lookup by key (hash map) and O(1) "move to most recent" / "remove least recent" (doubly linked list).
  2. Store list nodes in the map. On get/put, unlink the node and insert it at the front; on overflow, remove the node at the back and delete its key from the map.

Approach

A doubly linked list with sentinel head and tail keeps keys in recency order (front = most recent). The hash map stores key → node. get: if present, move its node to the front and return its value. put: if present, update and move to front; otherwise create a node at the front, and if the size exceeds the capacity, remove tail.prev and erase its key. Every step is O(1). (In Python, OrderedDict.move_to_end / popitem(last=False) implements the same structure; in Java, LinkedHashMap with access order does too.)

Complexity: O(1) per operation · O(capacity) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int cap, q;
    cin >> cap >> q;
    list<pair<long long, long long>> order; // front = most recently used
    unordered_map<long long, list<pair<long long, long long>>::iterator> pos;
    string op;
    while (q--) {
        cin >> op;
        if (op == "get") {
            long long k;
            cin >> k;
            auto it = pos.find(k);
            if (it == pos.end()) cout << -1 << "\n";
            else {
                order.splice(order.begin(), order, it->second);
                cout << it->second->second << "\n";
            }
        } else {
            long long k, v;
            cin >> k >> v;
            auto it = pos.find(k);
            if (it != pos.end()) {
                it->second->second = v;
                order.splice(order.begin(), order, it->second);
            } else {
                order.emplace_front(k, v);
                pos[k] = order.begin();
                if ((int)pos.size() > cap) {
                    pos.erase(order.back().first);
                    order.pop_back();
                }
            }
        }
    }
    return 0;
}

Python solution

import sys
from collections import OrderedDict

data = sys.stdin.read().split()
cap, q = int(data[0]), int(data[1])
cache = OrderedDict()  # last = most recently used
out, i = [], 2
for _ in range(q):
    if data[i] == "get":
        k = data[i + 1]
        i += 2
        if k in cache:
            cache.move_to_end(k)
            out.append(cache[k])
        else:
            out.append("-1")
    else:
        k, v = data[i + 1], data[i + 2]
        i += 3
        if k in cache:
            cache.move_to_end(k)
        cache[k] = v
        if len(cache) > cap:
            cache.popitem(last=False)
print("\n".join(out))

Java solution

import java.util.*;
import java.io.*;

public class Main {
    static class Node {
        long key, val;
        Node prev, next;
        Node(long k, long v) { key = k; val = v; }
    }

    static Node head = new Node(0, 0), tail = new Node(0, 0);

    static void unlink(Node x) {
        x.prev.next = x.next;
        x.next.prev = x.prev;
    }

    static void addFront(Node x) {
        x.next = head.next;
        x.prev = head;
        head.next.prev = x;
        head.next = x;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int cap = Integer.parseInt(st.nextToken()), q = Integer.parseInt(st.nextToken());
        head.next = tail;
        tail.prev = head;
        HashMap<Long, Node> map = new HashMap<>();
        StringBuilder sb = new StringBuilder();
        while (q-- > 0) {
            st = new StringTokenizer(br.readLine());
            String op = st.nextToken();
            long k = Long.parseLong(st.nextToken());
            Node x = map.get(k);
            if (op.equals("get")) {
                if (x == null) sb.append(-1).append('\n');
                else {
                    unlink(x);
                    addFront(x);
                    sb.append(x.val).append('\n');
                }
            } else {
                long v = Long.parseLong(st.nextToken());
                if (x != null) {
                    x.val = v;
                    unlink(x);
                    addFront(x);
                } else {
                    x = new Node(k, v);
                    map.put(k, x);
                    addFront(x);
                    if (map.size() > cap) {
                        Node lru = tail.prev;
                        unlink(lru);
                        map.remove(lru.key);
                    }
                }
            }
        }
        System.out.print(sb);
    }
}

Solve LRU Cache online · All practice problems