Expert · Data structures · 261 of 264
Cache hits
A cache holds at most k items. When a requested item is in the cache it is a hit (and becomes the most recently used); otherwise it is a miss and is added, and if the cache is full the least recently used item is removed. Count the hits and misses. Tip: collections.OrderedDict.
Input: k, then the requests on one line. Output: Hits: <h> Misses: <m>
Examples
2 a b a c b a
Hits: 1 Misses: 5
1 x x x
Hits: 2 Misses: 1
3 1 2 3 4 1 2 5 1 2 3 4 5
Hits: 2 Misses: 10
One more test checks other inputs when you press Check.
Stuck? The idea behind data structures
Choose the structure for what you do most: a heap (heapq) gives the smallest item fast, a deque adds and removes at both ends, a dictionary finds by key.
Two heaps, one for each half, keep the middle value of a stream of numbers.
import heapq
h = []
for x in [5, 1, 8, 3]:
heapq.heappush(h, x)
print(heapq.heappop(h), heapq.heappop(h)) # 1 3Watch for: heapq keeps the smallest first: for the largest, push -x and turn it back when you pop.