Skip to content

Design Problems: LRU Cache, Min Stack and Hit Counter

intermediate · 35 min · Asked often · Last reviewed 29 Oct 2026 · by TheLearningLoop Team

Key takeaways

  • A design problem asks you to build a structure whose operations are all fast. Start by listing the operations and the cost each must have.
  • An LRU cache is a hash map for O(1) lookup plus a doubly linked list for O(1) ordering. Each structure covers the weakness of the other.
  • A min stack stores the smallest value so far next to every item, so the minimum is always one lookup and a pop restores the previous minimum.
  • A hit counter keeps a queue of timestamps and drops the old ones, so memory is bounded by one window of traffic. LFU caches count uses and break ties by recency.

New to this topic? Read the overview first: Data Structures & Algorithms: The Big Picture

When to use data structure design

Use these designs when you need:

  • A cache with a size limit that keeps the useful items and drops the rest: an LRU (least recently used) or LFU (least frequently used) cache.
  • A structure that answers an extra question instantly, such as the minimum of a stack, the maximum of a window, or a random element.
  • A count over a recent period, for example hits in the last five minutes or requests per second for rate limiting.
  • An interview answer where the prompt says "all operations must be O(1)".

Use something else when:

  • A built-in structure already fits: Python's OrderedDict, Java's LinkedHashMap, or a library cache such as Caffeine or Guava. Use the library in production code.
  • The cache must be shared between many servers: use an external cache such as Redis or Memcached, and see the System Design lessons.
  • You only need the top k items: a heap is simpler.

Do not write your own cache in production unless you have a reason. Thread safety, expiry and statistics are hard to get right, and good libraries exist. These problems teach you how to combine structures, which is the real skill.

How a design problem works

A design problem asks you to build a small structure with a list of operations, each with a target cost. The method is always the same:

  1. List the operations and the cost each must have, for example get and put in O(1).
  2. Find a structure for each cost. A hash map gives O(1) lookup. A linked list gives O(1) insert and remove at a known place. A stack gives O(1) at the top. A queue gives O(1) at both ends.
  3. Combine them so each covers the other's weakness.

No single basic structure does everything. The skill is gluing two of them together so that every operation has the right cost.

The three classics:

  1. LRU cache = hash map + doubly linked list. The map finds a key in O(1) but knows nothing about order. The list keeps the keys in order of use but cannot find one quickly. The map stores key to list node, so the node is found in O(1) and moved to the front in O(1). The back of the list is the least recently used, and is evicted when the cache is full. The list must be doubly linked so a node can be removed without searching for the one before it.
  2. Min stack = a stack that remembers the minimum. Store with each value the smallest value at or below it. The minimum is the number on top. A pop removes both, and the previous minimum is already stored underneath.
  3. Hit counter = a queue of timestamps. Add each hit at the back. To count, drop timestamps from the front that are older than the window, then return the size. Each timestamp is added once and removed at most once.

An LFU cache is the next step: it evicts the key used the fewest times, and breaks ties by evicting the least recently used of those. It keeps a map from each use count to a list of keys, plus the smallest count in the cache, so it is still O(1).

Try it

Pick one of the three problems, then press Run and step through the operations.

Design problems

Step 1 of 10 · Press Space to play, arrow keys to step

Operations separated by ; for example put 1 1; get 1

Examples:

Cache, most recently used first (key:value)

The cache is empty.

Hash map keys: none

An LRU cache holds at most 2 items. A hash map finds an item in O(1), and a list keeps them in order of use so the least recently used one is easy to drop.

hits:
0
misses:
0
evictions:
0
items in cache:
0
capacity:
2

Every operation here costs constant time on average, however many items are stored.

Things to try:

  • LRU cache, "Classic": with capacity 2, the operations put 1 1; put 2 2; get 1; put 3 3; get 2; put 4 4; get 1; get 3; get 4 give 3 hits, 2 misses and 2 evictions. Reading key 1 saves it, so key 2 is evicted when key 3 arrives.
  • Min stack, "Push and pop": after push 5; push 3; push 7, min returns 3. After one pop it is still 3, and after a second pop it returns 5, with no scanning.
  • Hit counter, "Busy then quiet" with a 5-second window: three hits at seconds 1, 2 and 3 count as 3 at second 4. At second 7 only the hits at seconds 3 and 6 are inside the window, so the answer is 2. At second 20 the answer is 0.

Data structure design operations

LRU get(key).

  1. Look the key up in the hash map. If it is missing, return -1.
  2. Move its node to the front of the list, and return the value.

LRU put(key, value).

  1. If the key exists, update its value and move the node to the front.
  2. Otherwise add a new node at the front and add the key to the map.
  3. If the size is now over the capacity, remove the node at the back and delete its key from the map.

Min stack.

  1. push(v): store v and min(v, the stored minimum below).
  2. pop(): remove the top item and its stored minimum.
  3. getMin(): return the stored minimum on top.

Hit counter. hit(t) adds t at the back. count(t) removes timestamps at or before t - window from the front, then returns the number left.

Interview fact. The hash map stores the node itself, not just the value. That is the trick that makes "find it" and "move it" both O(1).

Data structure design time complexity

StructureMain operationsTimeMemory
LRU cacheget, putO(1) on averageO(capacity)
LFU cacheget, putO(1) on averageO(capacity)
Min stackpush, pop, top, getMinO(1)O(n)
Hit counter (queue)hit, countO(1) amortisedO(hits in one window)
Hit counter (one bucket per second)hit, countO(1) and O(window)O(window)

The hash map operations are O(1) on average. The hit counter is amortised because one count call may drop many old timestamps, but each timestamp is dropped only once.

Design structures vs other approaches

n is the number of stored items.

What you needCombined designHash map onlySorted structureScan every time
Look up by keyO(1)O(1)O(log n)O(n)
Know which item is least recently usedO(1)O(n)O(log n)O(n)
Minimum of a stackO(1)Not applicableO(log n)O(n)
Hits in the last windowO(1) amortisedO(n)O(log n)O(n)

The bold cells show where each wins. The combined designs match the hash map on lookup and beat everything else on the extra question. They cost more memory and more code, and they are not safe for several threads without a lock.

How to explain a design problem in an interview

  • Clarify first: capacity, what get returns on a miss, whether an update counts as a use, whether it must be thread-safe.
  • List the operations and their target costs, then say which structure gives each cost and why one is not enough.
  • For the LRU cache, say the key sentence: "the map stores the node, so I can find it and move it in O(1), and the list must be doubly linked."
  • Name the edge cases: capacity 1, updating an existing key, a miss, an empty structure.
  • State the costs: O(1) time per operation, O(capacity) memory, and name the built-in that does this for you, for example LinkedHashMap.

Where you meet these designs in real systems

Caches are everywhere in software, and the hit counter and the min stack are small versions of the same idea: a structure built so that the one question you ask often is cheap. Three examples are drawn out below, the first with code you can run, then more.

Example 1: A cache for the most recent product pages

An online shop keeps the 1,000 most recently viewed product pages in memory so it does not have to rebuild them from the database each time. When the cache is full and a new page arrives, it drops the page that has gone unviewed for the longest. That is an LRU cache, and every lookup and every eviction must be fast because it sits on the path of every request. Open the example below to see the picture and the code.

Code: an LRU cache with O(1) get and putTime O(1) per operationMemory O(capacity)
After get 112After put 331Evicted2
The cache holds two items. After put 1, put 2 and get 1, the order is 1 then 2. Adding key 3 evicts 2, the least recently used, leaving 3 then 1. Reading key 2 afterwards is a miss, because it was evicted.

Run with capacity 2 on put 1 1; put 2 2; get 1; put 3 3; get 2; put 4 4; get 1; get 3; get 4, all five versions return 1, -1, -1, 3, 4 for the five reads. Python uses OrderedDict and Java uses LinkedHashMap, which already combine a hash map and an ordered list. Go, C++ and Rust build the map and list by hand, and the Rust version stores the list in a Vec with indexes because nodes that point at each other are awkward in Rust. The C++ code builds with -std=c++17.

from collections import OrderedDict


class LRUCache:
    """A cache that keeps at most `capacity` items and drops the least recently used one.

    An OrderedDict is a hash map that also remembers the order of its keys, and it can move
    a key to the end in constant time. The end means "most recently used", the front means
    "least recently used". A plain dict could not do the "move" step in O(1).

    get(key) -> the value, or -1 if the key is not in the cache.
    put(key, value) -> stores the value, and evicts the oldest item if the cache is full.

    Time:   O(1) for get and put, on average.
    Memory: O(capacity).
    """

    def __init__(self, capacity):
        self.capacity = capacity
        self.items = OrderedDict()

    def get(self, key):
        if key not in self.items:
            return -1
        self.items.move_to_end(key)               # reading makes it the most recently used
        return self.items[key]

    def put(self, key, value):
        if key in self.items:
            self.items.move_to_end(key)           # updating also counts as a use
        self.items[key] = value
        if len(self.items) > self.capacity:
            self.items.popitem(last=False)        # drop the least recently used (the front)

Example 2: A stack that knows its minimum

A code editor or a calculator keeps a stack of values and must show the smallest one at any moment, for example the lowest price seen so far in a running list. Scanning the stack each time costs O(n). A min stack stores the minimum next to each value, so the answer is read in O(1) and popping a value restores the previous minimum automatically.

Value537Smallest so far533
Each position stores its value and the smallest value at or below it. The top is 7, but the stored minimum there is 3. After a pop the top is 3 and the minimum is still 3, and after another pop the minimum returns to 5.

Example 3: Counting requests for rate limiting

An API allows 100 requests per minute per user. For each request the server needs "how many hits in the last 60 seconds?". It keeps a queue of hit times and drops the ones older than a minute, or a circular array with one counter per second, so memory stays small however busy the user is.

hit 1droppedhit 2droppedhit 3kepthit 6keptcount 7answer 2
Hits arrive at the back of the queue. When counting at second 7, the hits at seconds 1 and 2 are older than the window and are dropped from the front. The hits at 3 and 6 remain, so the count is 2.

More real-world scenarios

4. Operating system page caches

An operating system keeps recently used disk pages in memory. Many systems use an approximation of LRU, because tracking exact order for every memory access would be too costly.

5. Database buffer pools

A database keeps recently read pages in a buffer pool and evicts the least valuable ones when it is full. Variants of LRU, such as LRU with protection against a single large scan, are common.

6. Browser and app caches

A browser keeps recently loaded images and pages, and a mobile app keeps recent thumbnails. Each has a size limit and evicts the oldest-unused entries first.

7. CDN and web caches

A content delivery network keeps popular files on servers near users. Policies such as LRU and LFU decide which files stay when disk space runs out, and frequency-based policies keep long-term favourites.

8. Rate limiting

A rate limiter counts recent requests per client with a sliding window or with buckets per second, which is the hit counter with a limit check added.

9. Undo stacks with extra information

An editor's undo stack stores state changes in order. Extra data stored per entry, such as the smallest or largest value so far, lets it answer questions about history in constant time.

10. Coding interviews

LRU cache, LFU cache, min stack, hit counter, and "design a data structure with insert, delete and get random in O(1)" are among the most common design questions, because they test whether you can combine structures.

Language standard libraries

Some languages ship an ordered map that makes an LRU cache short. Others expect you to build it.

LanguageStructure or classWhat it is under the hoodNotes
JavaLinkedHashMapHash map plus a linked list of entriesWith accessOrder true and removeEldestEntry overridden, it is an LRU cache. Caffeine is the common library for production.
C++std::list, std::unordered_mapDoubly linked list, hash tableThere is no built-in LRU. Combine them with list::splice.
C#LinkedList<T>, Dictionary<K,V>Doubly linked list, hash tableNo built-in LRU. MemoryCache offers size limits and expiry for production.
RustHashMap, VecDequeHash table, ring bufferNo LRU in the standard library. The lru crate is a common package.
Pythoncollections.OrderedDict, functools.lru_cacheOrdered hash map, a decorator that caches function resultslru_cache(maxsize=...) caches a function's results with LRU eviction.
Gocontainer/list, mapDoubly linked list, hash tableNo built-in LRU. Combine the list and map, as in the example.
JavaScriptMapHash-based map that remembers insertion orderDeleting and re-inserting a key moves it to the end, which gives a short LRU.
KotlinLinkedHashMapThe Java classThe same as Java.

The pattern: the building blocks are always a hash map and an ordered list. Languages with an ordered map give you a short LRU, and the rest need you to combine the two.

The takeaway

Whenever a system needs to keep only the most useful items within a size limit, look for a hash map plus a list, which is an LRU or LFU cache. When it needs one extra answer cheaply, such as a minimum or a recent count, it usually stores a little extra information beside each item so the answer is already there.

Interview questions

Try answering out loud before you reveal hints. Interviewers care about how you reason, not just the final answer.

  1. 1.

    Design a cache with a fixed capacity that supports get(key) and put(key, value) in O(1), and evicts the least recently used item when it is full.

    medium
  2. 2.

    Design a stack that supports push, pop, top and retrieving the minimum element, all in O(1).

    medium
  3. 3.

    Design a hit counter that records hits with a timestamp and returns the number of hits in the past 5 minutes.

    medium
  4. 4.

    How does an LFU cache differ from an LRU cache, and how can it still run in O(1)?

    hard

Finished this lesson?

Progress is saved on this device. Create a free account to keep it everywhere.

← Previous
Graphs
Topics:DesignLru cacheLfu cacheMin stackHit counterData structure designLinked hash map

↑ Back to top

Back to top