Design data structure similar to LRU cache

Google Machine Learning Engineer Approach 1 — Hash Map Paired With a Linear Recency List Two questions have to be answered on every eviction: where is the value for this key, and which key should leave next. The first is a pure lookup problem, so a hash map handles it. The second is an ordering problem, so a plain list works: keep the unpinned keys sorted from oldest to newest, oldest at the front. Pinned keys are simply removed from that list, which is exactly what makes…