Bộ Nhớ Đệm LRU

Cài đặt cấu trúc LRU Cache (Least Recently Used) với dung lượng cố định $cap$:

• get(key): Trả về giá trị tương ứng với $key$, hoặc $-1$ nếu $key$ không tồn tại. Thao tác này cũng đánh dấu $key$ là vừa được truy cập.
• put(key, value): Thêm/cập nhật cặp $(key,value)$. Nếu cache đã đầy, loại bỏ phần tử ít được dùng gần đây nhất (LRU).

Cả hai thao tác get và put đều đánh dấu $key$ là "vừa truy cập".

Hàm cần cài đặt

Đây là bài toán signature grader. Bạn chỉ cần cài đặt ba hàm sau, không cần viết main() hay đọc/ghi dữ liệu.

Ngôn ngữ hỗ trợ: C/C++, Python, và Java.

C++

void init(int cap);
int get(int key);
void put(int key, int value);

Python

def init(cap: int) -> None: ...
def get(key: int) -> int: ...
def put(key: int, value: int) -> None: ...

Java

public class Solution {
    public void init(int cap) { ... }
    public int get(int key) { ... }
    public void put(int key, int value) { ... }
}

Mô tả

• init(cap): Khởi tạo cache rỗng với dung lượng $cap$.
• get(key): Trả về giá trị nếu $key$ tồn tại, ngược lại trả về $-1$. Cập nhật $key$ thành "vừa truy cập".
• put(key, value): Thêm hoặc cập nhật. Nếu cache đầy và $key$ chưa tồn tại, loại bỏ phần tử LRU.

Ràng buộc

• $1\le cap\le {10}^5$
• $0\le key,value\le {10}^9$
• Tổng số thao tác $get$ và $put$: $\le 2·{10}^5$
• Mỗi thao tác get/put phải chạy trong $O(1)$ trung bình.

Ví dụ