TikTok OA Interview Question: Cache Eviction Policies | LRU vs FIFO

Implement the Least Recently Used (LRU) and First In First Out (FIFO) cache eviction policies, respectively.

Pick ONE OR MORE options.

// LRU cache = LinkedHashMap(maxEntries)
Function put(key, value)
    if cache is full
        remove the least recently accessed entry from cache
    add the new entry to cache

// FIFO cache = Queue(maxEntries)
Function put(key, value)
    if cache is full
        remove the oldest entry from cache
    add the new entry to cache

This question tests the core difference between LRU and FIFO cache eviction. LRU should evict the least recently accessed item, which is typically implemented with an access-ordered structure such as a LinkedHashMap, while FIFO should evict the oldest inserted item, which is naturally modeled by a queue. The key idea is to match each policy with the correct eviction order.