Mô tả vấn đề

Bạn được yêu cầu thiết kế và thực hiện một cấu trúc dữ liệu tuân theo quy tắc LRU (Least Recently Used) cache. Cấu trúc này bao gồm các phương thức sau:

• LRUCache(int capacity): Khởi tạo cache với dung lượng tối đa là capacity.
• int get(int key): Trả về giá trị của key nếu tồn tại, ngược lại trả về -1.
• void put(int key, int value): Nếu key đã tồn tại, cập nhật giá trị; nếu không, thêm cặp key-value. Nếu số lượng khóa vượt quá capacity, loại bỏ khóa ít sử dụng nhất.

Các hàm get và put phải hoạt động với độ phức tạp thời gian trung bình O(1).

Ví dụ

<strong>Input</strong>
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
<strong>Output</strong>
[null, null, null, 1, null, -1, null, -1, 3, 4]
<strong>Giải thích</strong>
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // Cache: {1=1}
lRUCache.put(2, 2); // Cache: {1=1, 2=2}
lRUCache.get(1);    // Trả về 1
lRUCache.put(3, 3); // Loại bỏ 2, Cache: {1=1, 3=3}
lRUCache.get(2);    // Trả về -1 (không tìm thấy)
lRUCache.put(4, 4); // Loại bỏ 1, Cache: {3=3, 4=4}
lRUCache.get(1);    // Trả về -1 (không tìm thấy)
lRUCache.get(3);    // Trả về 3
lRUCache.get(4);    // Trả về 4

Hướng dẫn giải quyết

Để giải quyết bài toán, ta có thể sử dụng bảng hash để thuận tiện cho việc tra cứu và danh sách liên kết hai chiều để theo dõi thứ tự sử dụng của các nút. Các nút mới hoặc vừa được cập nhật sẽ được đặt ở đầu, và nếu số lượng nút vượt quá capacity, nút cuối cùng sẽ bị xóa.

Phương pháp 1: Sử dụng cấu trúc dữ liệu sẵn có

Trong Python, có thể sử dụng OrderedDict, trong Java, có thể sử dụng LinkedHashMap. Tuy nhiên, cách này thường không được chấp nhận trong phỏng vấn vì nó bỏ qua điểm cần kiểm tra của bài toán.

Phương pháp 2: Bảng hash + Danh sách liên kết hai chiều

Đây là cách mà nhà tuyển dụng mong muốn. Ta sẽ tự xây dựng cấu trúc dữ liệu bằng cách kết hợp bảng hash và danh sách liên kết hai chiều. Để dễ dàng thao tác, ta sẽ tạo các nút giả head và tail.

class LRUCache {
    class Node {
        int key;
        int value;
        Node prev;
        Node next;

        Node() {}
        Node(int _key, int _value) {
            key = _key;
            value = _value;
        }
    }

    Map map = new HashMap<>();
    int size;
    int capacity;
    Node head;
    Node tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        size = 0;
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        Node node = map.get(key);
        if (node == null) {
            return -1;
        } else {
            moveToHead(node);
            return node.value;
        }
    }

    public void put(int key, int value) {
        Node node = map.get(key);
        if (node == null) {
            Node newNode = new Node(key, value);
            addNode(newNode);
            map.put(key, newNode);
            size++;
            if (size > capacity) {
                removeTail();
            }
        } else {
            node.value = value;
            moveToHead(node);
        }
    }

    private void moveToHead(Node node) {
        removeNode(node);
        addNode(node);
    }

    private void addNode(Node node) {
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
        node.prev = head;
    }

    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void removeTail() {
        Node node = tail.prev;
        removeNode(node);
        map.remove(node.key);
        size--;
    }
}