Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Lập trình Web & Backend] LRU Cache đầy đủ: GET/PUT

    LRU Cache với GET/PUT

    Hiện thực LRU cache lưu cặp key→value, sức chứa C:

    • PUT k v: ghi/ghi đè. Nếu key mới làm vượt sức chứa, loại key ít dùng gần đây nhất. PUT (kể cả ghi đè) tính là "vừa dùng".
    • GET k: nếu có, in v và đánh dấu "vừa dùng"; nếu không, in -1.

    Yêu cầu

    Dòng 1: C. Dòng 2: số thao tác N. N dòng: PUT k v hoặc GET k. In kết quả mỗi GET (mỗi dòng).

    Ví dụ

    Input:

    2
5
PUT a 1
PUT b 2
GET a
PUT c 3
GET b

    GET a→1 (đẩy a thành mới nhất). PUT c loại b. GET b→-1.

    • Định dạng đầu vào:

      Dòng 1: C. Dòng 2: N. N dòng thao tác: PUT k v | GET k.

    • Ràng buộc đầu vào:

      1 ≤ C ≤ 1000, 1 ≤ N ≤ 10000. key, v là chuỗi không khoảng trắng.

    • Định dạng đầu ra:

      Mỗi GET in một dòng: value hoặc -1.

    Ví dụ:

    Đầu vào:

    2
5
PUT a 1
PUT b 2
GET a
PUT c 3
GET b

    Đầu ra:

    1
-1

    Giải thích:

    GET a trả 1 và làm a mới nhất; PUT c loại b; GET b trả -1.

    Đang tải editor...