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.

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/

Xin chào các bạn, blog này thông báo rằng LCOJ sẽ tiếp tục tổ chức LCOJ Regular Contest #1.

LCOJ Regular Contest #1 sẽ diễn ra vào 20h00 ngày 26/11/2023 với thời lượng kéo dài 2 giờ 30 phút (vì một số lý do liên quan trong khâu duyệt bài nên kỳ thi sẽ kéo dài thêm 30 phút đến 23h00 ngày 26/11/2023).

Tổ chức kỳ thi

• wronganswer
• admin
• strycks, Hnhatn

Thông tin kỳ thi

• Sử dụng format ICPC.
• Kỳ thi gồm 6 task làm trong thời gian 2 giờ 30 phút.

UPD: Sau khi contest kết thúc các bạn hoàn toán có thể đóng góp editorial cho các bài tập trong contest bằng cách comment editorial của các bạn xuống dưới bài post này với tiêu đề "Editorial - Task ...". Nếu editorial của các bạn nhận được sự ủng hộ của mọi người, lời giải của các bạn sẽ được cân nhắc để được đưa làm lời giải chính thức cùng với lời giải đến từ LCOJ ! Rất mong được cùng các bạn đóng góp lời giải cho LCOJ!

Xin chào các bạn, blog này thông báo rằng LCOJ sẽ tiếp tục tổ chức LCOJ Beginner Contest #3.

LCOJ Beginner Contest #3 sẽ diễn ra vào 20h00 ngày 05/11/2023 với thời lượng kéo dài 2 giờ 30 phút.

Tổ chức kỳ thi

• wronganswer
• admin
• LCOJ rất gửi lời cảm ơn tới các bạn khiemkrkt, SaKaTa, LittleLove đã làm Testers cho LCOJ Beginner Contest #3 lần này.

Thông tin kỳ thi

• Sử dụng format ICPC.
• Kỳ thi gồm 6 task làm trong thời gian 2 giờ 30 phút.

Đặc biệt: Kỳ thi lần này sẽ tính rate cho tất cả mọi người, bao gồm các bạn không làm bài nào vì vậy hãy cân nhắc trước khi tham gia contest.

UPD: Sau khi contest kết thúc các bạn hoàn toán có thể đóng góp editorial cho các bài tập trong contest bằng cách comment editorial của các bạn xuống dưới bài post này với tiêu đề "Editorial - Task ...". Nếu editorial của các bạn nhận được sự ủng hộ của mọi người, lời giải của các bạn sẽ được cân nhắc để được đưa làm lời giải chính thức cùng với lời giải đến từ LCOJ ! Rất mong được cùng các bạn đóng góp lời giải cho LCOJ!

UPD: Xin chúc mừng top 5 của kỳ thi:

• iwannabetheguy
• Opacarophile
• PTIT_HuongTit
• ambatukam
• Vkhang

Một contest có vẻ khó hơn khi mà số lượng các bạn làm được full AC đã ít hơn, có vẻ các thí sinh gặp rất nhiều khó khăn ở Task B và Task C, editorial sẽ có trong ngày mai hoặc nhiều ngày tới.

Xin chào các bạn,

LCOJ Beginner Contest #2 đã diễn ra vào 20h00 ngày 22/10/2023 với thời lượng kéo dài 2 giờ 30 phút.

Tổ chức kỳ thi

• wronganswer
• admin

Thông tin kỳ thi

• Sử dụng format ICPC.
• Kỳ thi gồm 6 task mỗi task ~100~ điểm.

Kết quả

Contest lần này có vẻ khó hơn so với LCOJ Beginner Contest #1 vì có khá ít bạn có thể hoàn thành được cả 6 task. LCOJ xin được chúc mừng top 5 của kỳ thi:

• iwannabetheguy
• DL_DinhVuMinhHung2k8
• YugiHacker
• hungmaxx
• Vkhang

Các bài tập của kỳ thi hiện đã có mặt trong phần Danh sách bài kèm theo hướng dẫn giải (6/6).

Editorial được biên soạn bởi wronganswer và sự đóng góp của top 2 kỳ thi vừa rồi YugiHacker. Ngoài ra với task F bạn DL_DinhVuMinhHung2k8 cũng có một solution khác rất hay ở phần comment. Rất cảm ơn tất cả các bạn đã đóng góp cho Editorial của luyencode.net !

Contest tiếp theo LCOJ Beginner Contest #3 sẽ được diễn ra vào 20 giờ, ngày 5 tháng 11 năm 2023 ban tổ chức của LCOJ rất mong đông đảo các bạn người dùng LCOJ tham gia contest !

Xin chào các bạn,

Lời tựa

Luyện Code (LCOJ) lần đầu được ra mắt cộng đồng vào tháng 10/2020 tính đến nay là gần 3 năm hoạt động. Mặc dù trải qua nhiều thăng trầm, nhưng chúng tôi đã, đang và sẽ là sân chơi trí tuệ cho các bạn trẻ trau dồi kỹ năng lập trình của mình.

Để tiếp tục sứ mệnh trên, LCOJ muốn kêu gọi cộng đồng cùng tham gia xây dựng & phát triển nền tảng để sản phẩm này phát triển & giúp ích được nhiều bạn trẻ hơn nữa. Cụ thể:

Tìm kiếm Contest creator

Mặc dù LCOJ đã có kho bài tập phong phú nhưng sẽ thú vị hơn rất nhiều nêú chúng ta có các cuộc thi thường xuyên hơn. Do đó, chúng mình đang tìm kiếm những ứng viên tiềm năng cùng BQT tham gia tổ chức các kỳ thi.

Yêu cầu:

• Ham học hỏi, yêu thích lập trình & thuật toán.
• Tài khoản tại LCOJ có điểm số ~\ge 100~ hoặc tương đương.
• Có khả năng tổ chức kỳ thi (tạo đề bài, tạo testcase, ...)

Quyền lợi:

• Trau dồi kỹ năng mềm;
• Giao lưu với admin;
• Được LCOJ ghi nhận đóng góp;
• Tăng hiện diện của bản thân;
• ...

Mở rộng hợp tác

Chúng tôi sẵn sàng hợp tác với các tổ chức, cá nhân có mong muốn hợp tác liên quan tới sản phẩm này, bao gồm (không giới hạn):

• Phát triển sản phẩm
• Sử dụng các tính năng nâng cao
• Tài trợ cho LCOJ

Hãy cùng chung tay xây dựng một xã hội học tập cùng chúng tôi!

Liên hệ

Vui lòng liên hệ với LCOJ bằng một trong các kênh liên lạc tại đây

Happy coding!