LRU Cache là gì?

LRU (Least Recently Used) là thuật toán loại bỏ dữ liệu ít được sử dụng gần đây nhất khi bộ nhớ cache đầy.

Use cases thực tế

1. Browser Cache

Khi bạn lướt web, trình duyệt lưu trữ các tài nguyên (JS, CSS, images). Khi cache đầy, LRU quyết định xóa resource nào không còn cần thiết.

2. Database Query Cache

MySQL và PostgreSQL dùng LRU để cache kết quả truy vấn, giúp truy vấn lặp lại nhanh hơn đáng kể.

3. Redis Memory Management

Khi maxmemory đạt giới hạn, Redis dùng LRU policy để evict keys:

maxmemory 256mb
maxmemory-policy allkeys-lru

4. Operating System Page Cache

OS dùng LRU để quyết định page nào giữ trong RAM, page nào swap ra disk.

Thuật toán đằng sau

Tại sao cần HashMap + Doubly Linked List?

Để implement LRU cache hiệu quả, chúng ta cần 2 operations chính:

1. Tìm kiếm theo key - O(1)
2. Xác định và xóa item ít dùng nhất - O(1)

Nếu chỉ dùng 1 cấu trúc dữ liệu:

=> HashMap + Doubly Linked List cho ta O(1) cho cả 2 operations!

Cách hoạt động

• HashMap: Map key -> node trong linked list (tìm kiếm nhanh)
• Doubly Linked List: Lưu thứ tự sử dụng, node gần đầu = mới dùng, gần đuôi = cũ nhất

Khi access một key:

1. HashMap tìm node trong O(1)
2. Move node lên đầu linked list (xóa khỏi vị trí cũ, thêm vào đầu)
3. Khi cache đầy, xóa node cuối cùng (tail.prev)

Implementation

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}  # key -> node
        self.head = Node()  # dummy head
        self.tail = Node()  # dummy tail
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key):
        if key in self.cache:
            node = self.cache[key]
            self._move_to_front(node)
            return node.value
        return -1

    def put(self, key, value):
        if key in self.cache:
            node = self.cache[key]
            node.value = value
            self._move_to_front(node)
        else:
            node = Node(key, value)
            self.cache[key] = node
            self._add_to_front(node)
            if len(self.cache) > self.capacity:
                lru = self.tail.prev
                self._remove(lru)
                del self.cache[lru.key]

    def _move_to_front(self, node):
        self._remove(node)
        self._add_to_front(node)

Độ phức tạp: O(1) cho cả get và put

Cách 2: Ordered Dict (Python)

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = OrderedDict()

    def get(self, key):
        if key in self.cache:
            self.cache.move_to_end(key)
            return self.cache[key]
        return -1

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)

So sánh các variant

Khi nào dùng LRU?

• Session data: User sessions, shopping cart
• API response cache: Kết quả API không thay đổi thường xuyên
• Pagination cache: Cache các trang đã duyệt
• Computation cache: Kết quả tính toán nặng

"Tôi đã lãng phí 2 năm học thuật toán"

Đó là câu mà một senior developer tại một công ty product lớn chia sẻ với tôi tuần trước.

Anh ấy nói: "Tôi ngồi giải LeetCode mỗi ngày, leo rating Codeforces lên Candidate Master, rồi vào làm — và không một lần nào tôi cần dùng đến Segment Tree hay Dijkstra trong thực tế."

Nghe có vẻ hợp lý. Nhưng bạn có chắc anh ấy đúng không?

Thực tế phũ phàng: Phần lớn code đi làm không cần thuật toán

Hãy thành thật mà nhìn nhận:

• CRUD developer? Bạn cần SQL, không cần Floyd-Warshall.
• Frontend React? Bạn cần CSS và state management, không cần cây AVL.
• DevOps/Cloud? Bạn cần Terraform và Kubernetes, không cần quy hoạch động.

Một khảo sát không chính thức trong cộng đồng developer Việt Nam cho thấy hơn 80% lập trình viên đi làm chưa bao giờ tự implement một thuật toán phức tạp trong môi trường production.

Vậy tại sao chúng ta vẫn học?

"Nhưng thuật toán dạy bạn tư duy!"

Đây là lập luận kinh điển mà người dạy thuật toán hay dùng.

Nghe có vẻ đúng. Nhưng tư duy giải quyết vấn đề có thật sự chỉ đến từ thuật toán không?

Một product manager giỏi cũng có tư duy hệ thống. Một designer UX cũng giải quyết vấn đề phức tạp. Một data analyst cũng phân tích logic. Họ không học BFS hay DFS.

Có lẽ "tư duy" mà chúng ta nói đến chỉ là tư duy của người đã chịu khó học một thứ khó — và thuật toán chỉ là một phương tiện, không phải con đường duy nhất.

Nhưng nếu bạn muốn vào Big Tech?

À, đây là chỗ mọi thứ thay đổi.

Google, Meta, Amazon, Microsoft — họ hỏi thuật toán. Không phải vì thuật toán quan trọng với công việc hàng ngày, mà vì đó là bộ lọc hiệu quả nhất họ tìm được để chọn người thông minh.

Công bằng mà nói: đây là một hệ thống không hoàn hảo. Nhiều người giỏi thuật toán nhưng làm việc nhóm tệ. Nhiều người code production xuất sắc nhưng trượt phỏng vấn thuật toán. Nhưng hệ thống vẫn tồn tại — vì nó đủ tốt cho họ.

Nếu mục tiêu của bạn là Big Tech, học thuật toán là bắt buộc, dù bạn thích hay không.

Vậy kết luận là gì?

Thật ra không có kết luận đơn giản, và đó mới là vấn đề.

Thuật toán là cần thiết nếu bạn:

• Muốn vào Big Tech / công ty product cạnh tranh cao
• Làm việc trong domain cần tối ưu thực sự (game engine, compiler, database)
• Thích competitive programming như một môn thể thao trí tuệ

Thuật toán có thể không cần thiết nếu bạn:

• Làm outsource / agency bình thường
• Build startup MVP cần ship nhanh
• Chọn con đường management / product sớm

Câu hỏi thật sự không phải "Có nên học không?"

Câu hỏi thật sự là: "Bạn muốn trở thành ai?"

Nếu bạn đang đọc bài này trên LCOJ, có nghĩa là bạn đã chọn rồi — ít nhất là phần nào.

Còn bạn nghĩ sao? Học thuật toán có thật sự xứng đáng với thời gian bỏ ra không? Hay đó là một cái bẫy mà cộng đồng competitive programming đã tạo ra cho chính mình?

Để lại ý kiến của bạn phía dưới.

Chuyên đề chặt nhị phân Bài 1:

include<bits></bits>

using namespace std; int a[100000],q,n; int chatmax(int d){ int l=1,r=n,ans=0; while (l<=r){ int mid=(l+r)/2; if (a[mid]>d) r=mid-1; else l=mid+1,ans=mid; } return(ans); } int chatmin(int d){ int l=1,r=n,ans=0; while (l<=r){ int mid=(l+r)/2; if (a[mid]>=d) r=mid-1,ans=mid; else l=mid+1; } return(ans); } int main(){ freopen("bustatq.inp","r",stdin); freopen("bustatq.out","w",stdout); cin>>n>>q; for (int i=1;i<=n;i++) cin>>a[i]; for (int i=1;i<=q;i++){ int l,r; cin>>l>>r; if (l>a[n]) cout<<"0"<<endl else cout b>

include<bits></bits>

define ll long long int

using namespace std; ll n,a[1000000],kt[1000000],f[1000000],q; ll chatmin(ll x){ ll l=1,r=n,ans=0; while (l<=r){ int mid=(l+r)/2; if (a[mid]>=x) r=mid-1,ans=mid; else if (a[mid]<x l="mid+1;" return ll chatmax x while int mid="(l+r)/2;" if r="mid-1;" else main unordered_map> mp; cin>>n>>q; for (int i=1;i<=n;i++){ cin>>a[i];mp[a[i]]++; } sort(a+1,a+n+1); if (mp[1]>0) kt[1]=1; ll j=1; for (int i=1;i<=34;i++) { j=2; if (mp[j]>0) kt[j]=1; } j=1; for (int i=1;i<=27;i++) { j=3; if (mp[j]>0) kt[j]=1; } j=1; for (int i=1;i<=25;i++) { j*=5; if (mp[j]>0) kt[j]=1; } f[0]=0;a[0]=0; for (int i=1;i<=n;i++){ f[i]=f[i-1]; if (kt[a[i]]==1) f[i]++; } for (int i=1;i<=q;i++){ ll z,x; cin>>z>>x; if (z>a[n]) cout<<"0"<<endl else int k="chatmin(z);" k1="chatmax(x);" cout b>

include<bits></bits>

using namespace std; int a[100000],b[100000],c[100000],n; int chatmax(int d){ int l=1,r=n,ans=0; while (l<=r){ int mid=(l+r)/2; if (a[mid]>d) r=mid-1; else l=mid+1; if (a[mid]==d) ans=mid; } return(ans); } int chatmin(int d){ int l=1,r=n,ans=0; while (l<=r){ int mid=(l+r)/2; if (a[mid]>=d) r=mid-1; else l=mid+1; if (a[mid]==d) ans=mid; } return(ans); } int main(){ cin>>n; for (int i=1;i<=n;i++) cin>>a[i],a[i]=a[i]a[i]; for (int i=1;i<=n;i++) cin>>b[i],b[i]=b[i]b[i]; for (int i=1;i<=n;i++) cin>>c[i],c[i]=c[i]*c[i]; sort(a+1,a+n+1);int res=0; for (int i=1;i<=n;i++){ for (int j=1;j<=n;j++){ int k=chatmax(b[i]+c[j]); int k1=chatmin(b[i]+c[j]); if (k1>0) res=res+k1-k+1; int z=chatmax(abs(b[i]-c[j])); int z1=chatmin(abs(b[i]-c[j])); if (z1>0) res=res+z1-z+1; } } cout<<res b>

include<bits></bits>

using namespace std; long long check(long long k){ long long a=k/3; long long b=k/5; long long c=k/15; return(k-(a+b-c)); } int main(){ freopen("COUNTGAM.inp","r",stdin); freopen("COUNTGAM.out","w",stdout); long long n; cin>>n; long long ans=0; long long l=1,r=1e14; while (l<r long mid="(l+r)/2;" if l="mid+1;" r="mid,ans=mid;" cout> </r>

Chào các bạn,

Luyencode.net được xây dựng với một mục tiêu rất rõ ràng: 👉 giúp người học lập trình và thuật toán rèn luyện tư duy, nâng cao kỹ năng, và tiến bộ mỗi ngày thông qua việc luyện code thực tế.

Từ những bài toán đầu tiên cho người mới bắt đầu, đến các bài nâng cao phục vụ thi cử, phỏng vấn hay luyện tập lâu dài — chúng mình luôn cố gắng làm cho Luyencode trở thành một nền tảng dễ dùng – hữu ích – và đáng tin cậy.

Tuy nhiên, không ai hiểu trải nghiệm trên Luyencode rõ hơn chính bạn – người đang sử dụng nó mỗi ngày.

🎯 Vì sao chúng mình tạo bài viết này?

Chúng mình muốn lắng nghe trực tiếp ý kiến từ cộng đồng, để có cơ sở:

• Cải thiện chất lượng bài toán
• Tối ưu trải nghiệm sử dụng website
• Bổ sung tính năng thực sự cần thiết
• Loại bỏ những thứ chưa hiệu quả hoặc gây khó chịu

Mọi góp ý của bạn đều là dữ liệu quý giá để Luyencode ngày càng tốt hơn 🚀

💬 Bạn có thể góp ý những gì?

Bạn có thể comment bất cứ điều gì bạn nghĩ, ví dụ như:

• 🧩 Bài toán

  • Độ khó có phù hợp không?
  • Mô tả đề bài đã rõ ràng chưa?
  • Test case có hợp lý không?

• 🖥️ Giao diện & trải nghiệm

  • Website có dễ sử dụng không?
  • Có điểm nào gây rối hoặc bất tiện?
  • Trên mobile / tablet trải nghiệm thế nào?

• ⚙️ Tính năng

  • Bạn đang thiếu tính năng gì?
  • Có tính năng nào bạn thấy chưa cần thiết?
  • Bạn mong muốn Luyencode hỗ trợ thêm điều gì cho việc học?

• 📈 Lộ trình học

  • Bạn có cần gợi ý học theo level / mục tiêu không?
  • Có nên có roadmap rõ ràng hơn cho người mới?

👉 Góp ý càng cụ thể thì càng giúp chúng mình cải thiện chính xác hơn.

🤝 Cam kết từ đội ngũ Luyencode

• Tất cả comment đều sẽ được đọc và ghi nhận nghiêm túc
• Những góp ý hợp lý sẽ được ưu tiên đưa vào kế hoạch cải tiến
• Luyencode sẽ tiếp tục phát triển vì cộng đồng người học lập trình Việt Nam

✍️ Hãy để lại comment ngay bên dưới bài viết này

Dù là một ý nhỏ, một khó chịu thoáng qua, hay một đề xuất lớn — chúng mình đều rất trân trọng.

Cảm ơn bạn đã đồng hành cùng Luyencode.net ❤️ Chúc bạn học tốt và code ngày càng “mượt” hơn mỗi ngày!

— Đội ngũ Luyencode

🎉 Chào Mừng Đến Với Khóa Học Python!

Bạn đang chuẩn bị bắt đầu một hành trình tuyệt vời! Khóa học này được thiết kế theo phương pháp ELI5 (Explain Like I'm 5) - giải thích mọi thứ theo cách đơn giản nhất có thể, như thể bạn mới 5 tuổi!

🎯 Khóa Học Này Dành Cho Ai?

✅ Hoàn hảo nếu bạn:

• 🆕 Chưa từng code dòng nào
• 🤷 Không biết "biến" hay "hàm" là gì
• 🇻🇳 Muốn học bằng tiếng Việt với ví dụ dễ hiểu
• 🎓 Là học sinh, sinh viên hay người muốn chuyển nghành

🗺️ Lộ Trình Học Tập

Khóa học gồm 7 phần chính được thiết kế từ dễ đến khó:

🟢 Level 1: CƠ BẢN → 🟡 Level 2: TRUNG CẤP → 🔴 Level 3: NÂNG CAO

🎮 DỰ ÁN → 💪 BÀI TẬP → 📖 TÀI LIỆU → 📚 TỪ ĐIỂN

(Xem sơ đồ chi tiết phía dưới)

🎓 Phương Pháp Học "ELI5"

Mỗi bài học bao gồm:

1. 🎨 So sánh đời thực: "Biến giống như cái hộp đựng đồ"
2. 💻 Code ví dụ: Chạy ngay, thấy kết quả liền!
3. 🎯 Bài tập thực hành: Học đi đôi với hành

✨ Sau Khóa Học, Bạn Sẽ:

• ✅ Tự tin viết code Python từ đầu
• ✅ Xây dựng được ứng dụng thực tế
• ✅ Có portfolio để xin việc/freelance
• ✅ Sẵn sàng học framework nâng cao

Bạn nhận được:

• 📝 48+ bài học chi tiết
• 🎮 6+ dự án hoàn chỉnh
• 💪 Hàng trăm bài tập có lời giải

Tham gia ngay tại behitek.com/beli5/python/intro/