30daychallenge (24) | LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

The cache is initialized with a positive capacity.

Follow up:
Could you do both operations in O(1) time complexity?

Đây là một bài toán cực kỳ hay và tôi đã chinh phục được nó trong một buổi tối, toàn sai mấy cái không đáng có. LRU - Least Recently Used Cache, ta sẽ loại bỏ khỏi Cache phần từ lâu chưa được dùng tới nhất. Thao tác get(key) và put(key,value), chúng ta sẽ dùng hai cấu trúc dữ liệu Doubly Linked List và HashTable theo tôi tìm hiểu là tối ưu nhất thời điểm này. Phần tử đầu list chính là phần tử lâu chưa được dùng tới nhất. Nếu có một thay đổi trên nốt, ta sẽ đẩy nó về tail đánh dấu nó vừa được cập nhật.

Dựa theo hình ảnh trên Wiki này sẽ giúp ta dễ hình dung công dụng của LRU hơn.

Mấu chốt để bài này đạt O(1) nằm ở việc sử dụng HashMap, còn nếu bạn đã cài đặt thành thạo Doubly Linked List thì bài này không thực sự khó đối với bạn.
Xin chào, cảm ơn bạn !