Cache eviction policies (LRU, LFU, TTL) in HLD - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding LRU Cache Behavior

Consider a cache with a capacity of 3 items using the Least Recently Used (LRU) eviction policy. The cache is initially empty. The following keys are accessed in order: 1, 2, 3, 1, 4.

After these accesses, which keys remain in the cache?

A [2, 3, 4]

B [1, 3, 4]

C [1, 2, 4]

D [2, 3, 1]

💡 Hint

Remember that LRU removes the least recently used item when the cache is full.

Initially, keys 1, 2, 3 fill the cache. Accessing key 1 makes it most recently used. When key 4 is accessed, the least recently used key (2) is evicted. Remaining keys are 1, 3, and 4.

❓ Architecture

intermediate

Choosing Cache Eviction Policy for Read-Heavy Workload

You are designing a caching layer for a read-heavy web application where some items are accessed very frequently, and others rarely. Which cache eviction policy is most suitable to maximize cache hit rate?

A Least Frequently Used (LFU)

B Random eviction

C Time To Live (TTL) based eviction

D Least Recently Used (LRU)

💡 Hint

Consider which policy favors items accessed many times over time.

LFU keeps items accessed most frequently, which suits read-heavy workloads with hot items. LRU favors recent access but may evict frequently accessed older items. TTL evicts based on time, not usage frequency.

❓ scaling

advanced

Scaling Cache with TTL Eviction in Distributed Systems

You have a distributed cache system with TTL-based eviction. What is a major challenge when scaling this system across multiple nodes?

A Randomly evicting items to balance load

B Handling cache misses due to LRU eviction

C Tracking frequency counts for LFU eviction

D Ensuring consistent TTL expiration times across nodes

💡 Hint

Think about time synchronization and expiration consistency.

In distributed caches with TTL, nodes must agree on expiration times. Clock skew or delays can cause inconsistent evictions, leading to stale or missing data. LRU and LFU challenges differ and are unrelated to TTL expiration.

❓ tradeoff

advanced

Tradeoffs Between LRU and LFU Cache Policies

Which statement best describes a key tradeoff between LRU and LFU cache eviction policies?

A LRU requires tracking access frequency, LFU only tracks recency

B LFU is simpler to implement than LRU and uses less memory

C LRU adapts quickly to changing access patterns, while LFU may retain stale popular items longer

D Both LRU and LFU evict items randomly when full

💡 Hint

Consider how each policy responds to changes in item popularity over time.

LRU evicts least recently used items, adapting quickly if access patterns change. LFU evicts least frequently used items, which can cause it to keep items that were popular in the past but are no longer accessed.

❓ estimation

expert

Estimating Cache Size for TTL Eviction

A cache stores items with a TTL of 10 minutes. On average, 1000 new items are added per minute. Assuming steady state and no evictions other than TTL expiration, approximately how many items will the cache hold?

A 10,000 items

B 1000 items

C 100 items

D 1,000,000 items

💡 Hint

Think about how many items accumulate over the TTL duration.

With 1000 items added per minute and a TTL of 10 minutes, the cache holds items added in the last 10 minutes: 1000 * 10 = 10,000 items.

Practice

1. Which cache eviction policy removes the data that was used the longest time ago?

easy

A. Random Replacement

B. Least Frequently Used (LFU)

C. Time To Live (TTL)

D. Least Recently Used (LRU)

Solution

1. Step 1: Understand LRU policy

   LRU removes the cache entry that was accessed the longest time ago, prioritizing recent usage.

2. Step 2: Compare with other policies

   LFU removes least used items by frequency, TTL removes expired items by time, Random Replacement is arbitrary.

3. Final Answer:

   Least Recently Used (LRU) -> Option D

4. Quick Check:

   Oldest access time = LRU [OK]

Hint: LRU = remove oldest used data [OK]

Common Mistakes:

• Confusing LRU with LFU
• Thinking TTL removes based on usage
• Assuming random removal is LRU

2. Which of the following is a correct description of the TTL cache eviction policy?

easy

A. Removes data after a fixed expiration time

B. Removes the least recently used data

C. Removes the least frequently used data

D. Removes data randomly when cache is full

Solution

1. Step 1: Define TTL policy

   TTL (Time To Live) removes cache entries after their set expiration time passes.

2. Step 2: Contrast with other policies

   LRU removes oldest used, LFU removes least used by frequency, random is arbitrary.

3. Final Answer:

   Removes data after a fixed expiration time -> Option A

4. Quick Check:

   TTL = expiration time removal [OK]

Hint: TTL means data expires after set time [OK]

Common Mistakes:

• Mixing TTL with LRU or LFU
• Thinking TTL depends on usage frequency
• Assuming TTL removes randomly

3. Consider a cache with the following access pattern: keys A, B, A, C, B, A. Using LFU eviction, which key will be evicted when the cache is full and a new key D is added?

medium

A. Key C

B. Key A

C. Key B

D. Key D

Solution

1. Step 1: Count frequency of each key

   Key A accessed 3 times, B accessed 2 times, C accessed 1 time.

2. Step 2: Identify LFU eviction candidate

   LFU removes the least frequently used key, which is C with frequency 1.

3. Final Answer:

   Key C -> Option A

4. Quick Check:

   Lowest frequency = C [OK]

Hint: LFU evicts lowest frequency key [OK]

Common Mistakes:

• Evicting most recent key instead of least frequent
• Confusing frequency with recency
• Evicting key D which is new

4. A cache using TTL eviction is not removing expired entries as expected. Which of the following is the most likely cause?

medium

A. The TTL value is set too low

B. The cache uses LRU instead of TTL

C. The cache does not check expiration before access

D. The cache size is too large

Solution

1. Step 1: Understand TTL eviction mechanism

   TTL eviction requires checking if entries have expired before returning or during cleanup.

2. Step 2: Identify why expired entries remain

   If cache does not check expiration on access or cleanup, expired entries stay indefinitely.

3. Final Answer:

   The cache does not check expiration before access -> Option C

4. Quick Check:

   Expiration check missing = no TTL eviction [OK]

Hint: TTL needs expiration checks to remove entries [OK]

Common Mistakes:

• Assuming low TTL causes no eviction
• Confusing TTL with LRU behavior
• Thinking cache size affects TTL eviction

5. You are designing a cache for a news website where articles are frequently accessed shortly after publishing but rarely after a few days. Which eviction policy is best suited to keep fresh content while removing stale data efficiently?

hard

A. Least Recently Used (LRU)

B. Time To Live (TTL)

C. Random Replacement

D. Least Frequently Used (LFU)

Solution

1. Step 1: Analyze data usage pattern

   Articles are popular shortly after publishing, then become stale after days.

2. Step 2: Match eviction policy to pattern

   TTL removes data after expiration time, ideal for removing stale articles automatically.

3. Step 3: Compare with other policies

   LRU and LFU focus on usage, but TTL ensures freshness by time. Random is inefficient.

4. Final Answer:

   Time To Live (TTL) -> Option B

5. Quick Check:

   Freshness by expiration time = TTL [OK]

Hint: Use TTL for time-based freshness eviction [OK]

Common Mistakes:

• Choosing LRU or LFU ignoring data staleness
• Assuming random eviction is efficient
• Not considering time-based expiration