The AI Interview - Master AI/ML Interviews

Implement LRU-K memory eviction for agents:

LRU-K Policy:

Track last K access times for each item
Items with fewer than K accesses are candidates for eviction
Among candidates, evict least recently used
Items with K+ accesses are protected

add(item_id, data): Add item, trigger eviction if over capacity
access(item_id): Record access timestamp, return data
Eviction: Find items with < K accesses, evict oldest access time

Access Times: Store as list of timestamps (use time.time() or incremental counter)

Eviction Priority:

Items with < K accesses (candidates)
Among candidates, oldest last access time
If no candidates, evict oldest overall

Examples

Example 1:

Input: m = LRUKMemory(2, k=2); m.add('a', 1); m.add('b', 2); m.add('c', 3); 'a' in m.items

Output: False

Explanation: 'a' evicted when 'c' added (only 1 access < K=2)

Starter Code

class LRUKMemory:
    """
    LRU-K memory eviction for agent context management.
    Keeps items accessed at least K times recently.
    """
    
    def __init__(self, capacity, k=2):
        self.capacity = capacity
        self.k = k
        self.items = {}  # id -> {'data': ..., 'access_times': [...]}
    
    def add(self, item_id, data):
        """Add item, evict if necessary"""
        # Your implementation here
        pass
    
    def access(self, item_id):
        """Record access to item, return data or None"""
        # Your implementation here
        pass
    
    def _should_evict(self, item):
        """Check if item qualifies for eviction (fewer than K recent accesses)"""
        # Your implementation here
        pass
    
    def _evict_one(self):
        """Evict one item based on LRU-K policy"""
        # Your implementation here
        pass

LRU-K Memory Eviction

Examples

Starter Code