Skip to content
intermediate Phase · Caching

LRU

Implement Least Recently Used eviction for efficient cache management.

35m
0 problems
Topic Progress 0%

LRU Cache

LRU Implementation (LinkedHashMap)

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    public LRUCache(int capacity) {
        super(capacity, 0.75f, true); // accessOrder=true
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}

LRU Properties

  • Access: O(1) get/put
  • Eviction: least recently used item
  • Data structure: HashMap + Doubly Linked List

Cache Best Practices

Strategies

  • Cache-Aside: Application manages cache
  • Write-Through: Sync write to cache and DB
  • Write-Behind: Async write to DB
  • Read-Through: Cache loads from DB

Invalidation

  • Time-based TTL
  • Event-based invalidation
  • Version-based keys
  • Tag-based grouping

Monitoring

  • Hit rate > 80% is good
  • Monitor eviction rates
  • Track cache size
  • Alert on anomalies

Key Points

  • Understanding LRU Cache is essential for production systems
  • Always consider scalability and maintainability
  • Test thoroughly before deploying to production
  • Monitor performance and set up alerting

Common Patterns

  1. Validation: Always validate input at the boundary
  2. Error Handling: Use structured error responses
  3. Logging: Log key events for debugging
  4. Testing: Unit, integration, and load tests
  5. Documentation: Keep docs updated with code changes

Practice Problems

0 / 3 solved
Implement LRU Cache

Design and implement a solution for LRU Cache in a backend system. Consider scalability, error handling, and production readiness.

Solution 
// LRU Cache implementation
// Key aspects: validation, error handling, logging, testing

public class LRUCache {
    // Production-ready implementation
}
LRU Cache Edge Cases

Identify and handle edge cases for LRU Cache. What happens under high load, with invalid input, or during failures?

Solution 
// Edge case handling:
// 1. Null/empty input -> validation
// 2. High load -> rate limiting, queuing
// 3. Failures -> retries, circuit breaker
// 4. Concurrent access -> locks, idempotency
LRU Cache Testing Strategy

Write a testing strategy for LRU Cache. Include unit tests, integration tests, and performance tests.

Solution 
// Test plan:
// - Unit: 80% coverage target
// - Integration: API contracts
// - Performance: latency, throughput
// - Chaos: failure injection

Quiz

1. LRU stands for?

Question 1 options

2. LRU time complexity?

Question 2 options

3. What is a common mistake when implementing LRU Cache?

Question 3 options

Flashcards

Question

LRU?

Click to reveal answer

Answer

Least Recently Used

Question

LRU complexity?

Click to reveal answer

Answer

O(1) get/put

Question

LRU Cache best practices

Click to reveal answer

Answer

Follow SOLID principles, write clean code, test thoroughly, document decisions, and monitor in production.

Revision Notes

Key Takeaways

  • 1. LRU evicts least recently accessed item
  • 2. Implementation: HashMap + Doubly Linked List
  • 3. O(1) for get and put operations

Interview Tips

  • • Implement LRU cache
  • • Know data structure

Cheat Sheet

LRU Cache

  • Least Recently Used
  • Data structure: HashMap + Doubly Linked List
  • O(1) get/put
  • Access order: most recent at end