Cache Hit Ratio for a News Feed
Problem
A news feed service keeps recently viewed posts in an LRU cache in front of its database. Given the sequence of post ids that readers request and the cache capacity in posts, replay the requests: a request for a cached post is a hit and makes it the most recently used; a miss loads the post into the cache, evicting the least recently used post if the cache is over capacity. Return the hit ratio as a percentage rounded to 1 decimal. Call it for several capacities to see how much each extra slot buys. There are up to 1,000,000 requests.
Examples
Input: feed = ["p1", "p2", "p1", "p3", "p1", "p2", "p4", "p1", "p5", "p2", "p1", "p3"],
capacities 1, 2, 3 and 4
Output: [0.0, 16.7, 41.7, 50.0]
Why: the third slot adds the most, because it is enough to keep both hot posts, p1 and p2Input: feed = ["a", "b", "c", "a", "b", "c"], capacity = 2
Output: 0.0
Why: a loop one post longer than the cache evicts each post just before it is needed againInput: feed = ["x", "x", "x"], capacity = 1
Output: 66.7
Why: edge case, only the very first request for a post can missHints
0 / 3
An LRU cache needs two operations to be fast: look up a post, and find the least recently used one to evict.
Python's OrderedDict keeps insertion order and can move a key to the end. Treat the end as most recently used and the front as the next to evict.
On a hit, count it and move the post to the end. On a miss, insert it, and if the cache is now over capacity, pop the first item. Divide hits by requests at the end.
Solution
Feed traffic is skewed, a few posts get most of the views, and that skew is what makes a small cache worth having. The simulation is an LRU cache on an OrderedDict: a hit moves the post to the most recently used end, and a miss inserts it and evicts from the other end when the cache overflows. Running the same trace against several capacities gives the hit-ratio curve an interview answer should reason about: the first example jumps once the cache can hold both hot posts and then flattens. The second example is LRU's known weak spot, a cyclic scan slightly larger than the cache, where the hit ratio drops to zero. Each request is O(1), so time is O(n) per capacity and space is O(c) for c cached posts.
from collections import OrderedDict
def hit_ratio(requests, capacity):
cache, hits = OrderedDict(), 0 # front = least recently used
for post in requests:
if post in cache:
hits += 1
cache.move_to_end(post) # now the most recently used
else:
cache[post] = True
if len(cache) > capacity:
cache.popitem(last=False) # evict the least recently used
return round(100 * hits / len(requests), 1)
feed = ["p1", "p2", "p1", "p3", "p1", "p2", "p4", "p1", "p5", "p2", "p1", "p3"]
print([hit_ratio(feed, c) for c in (1, 2, 3, 4)]) # -> [0.0, 16.7, 41.7, 50.0]
print(hit_ratio(["a", "b", "c", "a", "b", "c"], 2)) # -> 0.0
print(hit_ratio(["x", "x", "x"], 1)) # -> 66.7Stuck on the idea rather than the code? Design a Distributed Cache covers it.