کش LRU
LRU CacheLRU Cache وقتی ظرفیت پر شود آیتمی را حذف می‌کند که از همه بیشتر زمان است استفاده نشده. طراحی کلاسیک O(1) از Hash Map + Doubly Linked List استفاده می‌کند.
اول این مفهوم را در ذهن نگه دار
LRU Cache وقتی ظرفیت پر شود آیتمی را حذف می‌کند که از همه بیشتر زمان است استفاده نشده. طراحی کلاسیک O(1) از Hash Map + Doubly Linked List استفاده می‌کند.
چطور کار می‌کند؟ ساده و مرحله‌ای
Hash Map پیدا کردن key را O(1) می‌کند.
Doubly Linked List ترتیب تازگی را نگه می‌دارد تا آیتم استفاده‌شده سریع به اول منتقل و قدیمی‌ترین آیتم از انتها حذف شود.
الگوریتم را به شکل تصمیم‌های پشت سر هم بخوان
Invariant اصلی ساختار را مشخص کن.
مسیر read/update را در ساختار دنبال کن.
بعد از mutation قبل از return invariant را دوباره برقرار کن.
یک ورودی خیلی کوچک را دستی اجرا کن و بعد از هر عملیات مهم state را بنویس. برای کش LRU هدف این است که invariant را ببینی، نه اینکه کد را حفظ کنی.
get/put O(1)
این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرض‌های preprocessing نتیجه بگیر.
موارد مناسب
- وقتی عملیات غالب برنامه با نقاط قوت این ساختار هماهنگ است از آن استفاده کن.
- علاوه بر Big-O، هزینه حافظه را هم مقایسه کن.
کجا معمولاً اشتباه می‌کنیم؟
- پیچیدگی را بدون فهم representation حفظ نکن.
- بدترین شکل ساختار یا هزینه resize/rebalance را نادیده نگیر.
مدل یک پاسخ حرفه‌ای
نکته کلیدی مصاحبه دلیل ترکیب دو ساختار است: Map برای lookup و Doubly Linked List برای update ترتیب و eviction در O(1).
کش LRU چه مسئله‌ای را حل می‌کند؟
LRU Cache وقتی ظرفیت پر شود آیتمی را حذف می‌کند که از همه بیشتر زمان است استفاده نشده. طراحی کلاسیک O(1) از Hash Map + Doubly Linked List استفاده می‌کند.
درباره Complexity چه چیزی باید بگویم؟
پیچیدگی معمول اینجا get/put O(1) است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.
رایج‌ترین اشتباه چیست؟
پیچیدگی را بدون فهم representation حفظ نکن.