Design a Systems Component

Understanding the round

When VMware runs a design round, "system design" is a trap if you read it the way a consumer-web loop means it. The center of gravity here is a systems component. That's a single piece of infrastructure you model in clean classes, back with the right data structures, and defend as the interviewer grows the requirements. The recurring prompts are things like an in-memory cache, a thread pool, a rate limiter, a connection pool or a bounded queue. Nobody is measuring whether you can serve a billion users. The interviewer watches how you reason about a component a platform team would own for years. You start from the data structures, then work through concurrency, a fixed memory budget, and the moment it crashes and has to come back.

An in-memory key-value cache is the ideal vehicle, because it forces every layer of the skill to show up. There's data-structure reasoning. A lookup has to be constant time and so does eviction. That's why one structure isn't enough, and a hash map has to work alongside a recency list. There's concurrency. A cache is the most contended thing in a service. A single lock around it is correct and also a bottleneck, and the choice of how to shard the locking is graded. There's resource pressure. A cache lives inside a memory budget it can't exceed, so what it drops when it's full is a real decision. And there's failure. Entries expire on a clock, and a process restart must not corrupt what was on disk. Get these layers right and the design reads like an infrastructure engineer's work. A plain dictionary with no eviction and no locking reads like a cache from a single-threaded script.

The VMware angle

VMware is an infrastructure company. The component you design in this round stands in for the components it ships. Think of a cache in a management server, a metadata store, a buffer under a hypervisor, or a config store a dozen services read on their hot path. That code outlives the person who writes it. So the round rewards the instincts that keep long-lived systems software healthy. Derive the structure from first principles instead of reciting the answer. The interviewer will change the requirements, and a memorized cache falls apart once the eviction policy isn't the one you rehearsed. Reason about the machine, with no infinite fleet to lean on. The platform runs on a fixed memory budget, and a cache that grows without bound is a resource leak with a friendly name. And treat concurrency and crash recovery as part of the problem from the start. On a real server, a burst of threads and an unplanned restart are the normal operating condition.

Pinning the requirements first

Resist naming a data structure in the first sentence. A minute spent bounding the problem keeps a component coherent instead of sprawling. State the functional surface plainly. The cache maps a key to a value. A read returns the value if it's present and still valid, and reports a miss otherwise. A write stores a value, optionally with a time to live after which the entry is no longer valid. The cache holds at most a fixed number of entries, its budget. When it's full and a new key arrives, it must make room by evicting an existing entry under a stated rule. That's the whole core, and it's enough to build something real.

Then separate what you handle now from what you name and defer. The interviewer will push on exactly this. Say eviction starts as least-recently-used and lives behind an interface. It can grow into least-frequently-used or a scan-resistant policy by swapping one class, with no rewrite of the read path. Say that persistence starts as an append-only log with periodic snapshots. Durability is then a component you can strengthen, never a promise baked into every method. Say the value can be opaque bytes now and get a size accounting later. Then the budget can move from a count of entries to a count of bytes without disturbing the structure. In a good design, each of those upgrades replaces one collaborator. If any of them means rewriting the read path, the design needs work. Naming the deferral is the reliability instinct the round looks for.

• What the round grades: a component, not a fleet. Clean class responsibilities, the right data structures, concurrency, and behavior under a fixed budget and a crash. Sharding a database across regions and capacity math for a viral spike don't belong here. If you're drawing load balancers, you've misread the prompt, which asks for one component on one machine.
• Lookup and eviction: both must be constant time. A read has to be O(1), and so does making room when the cache is full. No single common structure gives you both a keyed lookup and an ordered eviction victim. So the design pairs a hash map with a recency list instead of reaching for one container.
• It lives in a budget: bounded, with an eviction rule. The cache exists because memory is finite. An unbounded map leaks memory, however simple it looks. The graded decision is which entry to drop when the budget is reached, stated as an invariant instead of left to chance.
• Threads and crashes are normal: design for both up front. A cache is the most contended object in a service, and the process will restart at the worst possible moment. Concurrency and recovery belong in the requirements. Name the locking discipline and what a restart reads back before the interviewer asks.

The data structures underneath

Spend the first real minutes on the data structures. Once the mechanism is straight, the classes fall out cleanly. Two requirements pull against each other. Reads must find a key in constant time, which asks for a hash map. Eviction must find and remove the right victim in constant time, which a hash map can't do because it has no order. The whole design rests on one resolution: keep both structures and let them point at the same entries. A hash map gives constant-time lookup from a key to a node. A doubly linked list keeps those same nodes in recency order, freshest at the front and the eviction victim at the back. Reads find the node through the map and splice it to the front. An eviction reads the node at the back and removes it from both. Every operation stays constant time because neither structure ever has to scan.

Time to live adds a second axis, and the honest first answer is to expire lazily. Store an absolute deadline on each entry instead of a countdown, so no background clock has to touch every entry as it ages. A read checks the deadline. If the entry has passed it, treat the read as a miss and remove the dead entry right away, so nothing stale lingers on the hot path. That keeps the common case cheap and correct. Say out loud where it falls short, because the interviewer will find it. Lazy expiry alone lets a key that's never read again sit in the map, holding memory after it has died. A real cache adds an occasional sweep or a deadline-ordered structure to reclaim those. Naming the limit and its fix beats pretending lazy expiry is complete.

Underline the nouns that survive and the classes are already visible. An Entry is the unit of storage: a key, a value, an expiry deadline, and a handle to its own node in the recency list. The index is the hash map from key to entry. The recency list is the intrusive doubly linked list that orders entries by last use. Eviction policy is the one decision of which entry to drop when the budget is reached, kept behind its own interface. And the cache itself is the facade that owns all of them and routes every read and write through one consistent discipline. Give each a single responsibility and check that no two are secretly doing the same job.

// An Entry is the unit the cache stores: the value, when it expires, and its
// slot in the recency list. expiry == kNever means the entry has no TTL. The
// node handle is what makes eviction O(1): the map jumps to the entry, and the
// entry already knows where it sits in the recency order.
struct Entry {
    Key        key;
    Value      value;
    TimePoint  expiry;     // absolute deadline; kNever if there is no TTL
    ListNode*  node;       // this entry's position in the recency list
};
// The Cache is the facade. It owns the index and the recency list, and the
// eviction rule lives BEHIND an interface so least-recently-used today can
// become least-frequently-used or a scan-resistant policy later WITHOUT
// touching get() or put(). That seam is the extensibility the round grades.
class Cache {
    std::unordered_map<Key, Entry>  index_;      // O(1) lookup: key -> entry
    RecencyList                     order_;       // intrusive doubly linked list
    std::unique_ptr<EvictionPolicy> policy_;      // strategy: which victim to drop
    size_t                          capacity_;    // the hard budget, in entries
public:
    std::optional<Value> get(const Key& k, TimePoint now);
    void                 put(const Key& k, Value v, TimePoint now, Duration ttl);
};

This modeling buys a lot. The map and the list share nodes instead of copying entries, so the two structures can never disagree about what the cache holds. The eviction policy is a collaborator the cache calls, kept out of the write path. Swapping least-recently-used for something smarter changes one class. And the expiry lives as a deadline on the Entry. Checking whether a value is still valid is a comparison in one place, never a special case scattered through every read. The read and write methods end up short because each piece already knows its own job.

Finding the classes

With the structures fixed, the read and the write are short enough to write on the board. Writing them proves every class is pulling its weight. The order inside each one is the design. A read is a lookup, a validity check and a recency bump, in that order. A hit that has passed its deadline becomes a miss and is removed, never returned. A write inserts or refreshes, then enforces the budget. When the cache is full and the key is new, the policy names a victim before the new slot is allocated. Get the order right and no rule is homeless.

// get is a lookup, an expiry check, and a recency bump. An entry that has
// passed its deadline is treated as a miss AND evicted on the spot, so a dead
// value never lingers on the hot path.
std::optional<Value> Cache::get(const Key& k, TimePoint now) {
    auto it = index_.find(k);
    if (it == index_.end()) return std::nullopt;          // clean miss
    Entry& e = it->second;
    if (e.expiry != kNever && now >= e.expiry) {           // expired: evict lazily
        order_.erase(e.node);
        index_.erase(it);
        return std::nullopt;
    }
    order_.move_to_front(e.node);                          // now most-recently-used
    return e.value;
}
// put inserts or refreshes, THEN enforces the budget. When the cache is full
// and the key is new, the policy names the victim BEFORE the new slot exists,
// so the cache is never one entry over budget, not even for an instant.
void Cache::put(const Key& k, Value v, TimePoint now, Duration ttl) {
    TimePoint exp = (ttl > Duration::zero()) ? now + ttl : kNever;
    auto it = index_.find(k);
    if (it != index_.end()) {                              // refresh in place
        it->second.value  = v;
        it->second.expiry = exp;
        order_.move_to_front(it->second.node);
        return;
    }
    if (index_.size() >= capacity_) {                      // full: make room first
        Key victim = policy_->evict(order_);               // e.g. least-recently-used
        order_.erase(index_[victim].node);
        index_.erase(victim);
    }
    ListNode* n = order_.push_front(k);
    index_.emplace(k, Entry{k, v, exp, n});
}

Say two things about these methods to the interviewer directly. First, eviction runs before the insert, never after, so the cache is never even momentarily over its budget. On a machine with a hard memory ceiling, being one entry over for one instant is the allocation that trips the limit. Second, the cache calls the policy instead of inlining it. That seam lets the module survive the mid-round change. Say the interviewer adds a full scan that pollutes the cache and asks you to protect the hot keys. You replace the policy with a frequency-aware or scan-resistant one. Eviction is isolated, so that upgrade touches nothing in the read or write path. Point at the seam before they ask, and you've shown the extensibility instinct the round is built to detect.

The class relationships

With the classes named, the design is the wiring between them and the path of one operation, so draw it. Read the diagram by role. Blue is the caller from outside. Violet is the cache facade that owns the discipline. Indigo is the two services it drives, the lock that guards a shard and the policy that names a victim. Green is the state the design owns: the index, the recency list, and the durable log and snapshot underneath. Follow the numbered edges to read one write in order. Lock the shard and find the node through the index. Apply the eviction or expiry policy against the recency list. Then append the change to the log that periodically folds into a snapshot.

Concurrency and locking

A cache that's correct single-threaded and wrong under load is a failing answer at VMware. A cache is the most contended object in a service, and the interviewers are systems engineers who'll push on exactly this. Start from the honest baseline: a single mutex around every read and write. It's correct, and it's a bottleneck. Every thread that touches any key now waits behind every other. The structure you built for constant-time operations spends its life blocked. Worse, the read path isn't read-only. A get moves its entry to the front of the recency list, which mutates shared state. So you can't wave it through with a shared read lock and call it safe. Say out loud that even reads write here. That observation shows you've built a concurrent cache, beyond reading about one.

To buy real concurrency, shard the key space into stripes, each an independent cache with its own lock, and route a key to its stripe by hash. Now two threads working on different keys never contend. Only keys that collide in the same stripe serialize, which is rare when the stripe count comfortably exceeds the thread count. State the cost. Any operation that spans the whole cache no longer sits behind one lock: an exact size, a clean shutdown, a global flush. A total size becomes an approximation, and a full sweep has to walk the stripes. That's the classic infrastructure trade, more parallelism for a weaker global view. The round grades you on naming which side you chose and why, far more than on the diagram.

// A single global mutex is correct but serializes every operation, so the
// cache becomes a bottleneck the moment many threads use it. Sharding the key
// space into independently locked stripes keeps operations on DIFFERENT keys
// from waiting on each other. The price is an honest one: a global size is now
// approximate, because no single lock covers the whole cache at once.
size_t ShardedCache::shard_for(const Key& k) const {
    return std::hash<Key>{}(k) % shards_.size();
}
std::optional<Value> ShardedCache::get(const Key& k, TimePoint now) {
    Shard& s = shards_[shard_for(k)];
    std::lock_guard<std::mutex> guard(s.mutex);   // lock ONE stripe, not all of them
    return s.cache.get(k, now);                    // note: get mutates recency, so it
}                                                  // needs exclusion, not a shared lock

The VMware angle

A VMware loop probes concurrency hardest. The platform it builds is thread-dense by nature, and the interviewers came up writing this kind of code. Two habits land. First, be precise about what your lock protects and for how long. Hold the stripe lock across the whole read-modify cycle. A get that reads the node, then splices it to the front in two unguarded steps, is a data race that corrupts the list under contention. Second, be ready to reason one level below the mutex, because these interviewers will ask. Know why a lock-free or sharded design beats a global lock under contention. Know where a spinlock is right and where it wastes a core. And know what a reader-writer lock can't buy you when the read path mutates recency. You don't have to implement the lock-free version on the board. Show you know the ladder from a coarse global lock to striped locks to finer-grained or lock-free structures, and what each rung costs. The bar is set to find that systems fluency.

Memory, eviction, and persistence

A cache exists because memory is finite. So the budget and what happens at its edge are the heart of the design. Start with the budget itself. Counting entries is the easy version and a fine place to begin. But say plainly that a real cache on a fixed memory ceiling budgets by bytes. A thousand tiny values and a thousand large ones put different loads on the machine. Moving from an entry count to a byte count changes the accounting inside the cache. It adds a size to each entry and tracks a running total, without disturbing the map, the list or the read path. The budget can change units without a rewrite. That's the payoff of keeping the accounting in one place.

Eviction is the rule at the edge of the budget. Least-recently-used is the honest default. It's cheap, and it matches the common case where a key used lately is likely to be used again. Name its failure mode before the interviewer does. A workload that reads a large set of keys once, a scan, walks straight through the cache. It evicts the genuinely hot keys to make room for keys it will never touch again. That case motivates a frequency-aware or scan-resistant policy. Since eviction lives behind an interface, you can name the upgrade as a one-class change. The graded signal is knowing which workload breaks the default and where the fix plugs in. Implementing every policy is beside the point.

Then handle the two failures that are constant on a real server. The first is time. Entries expire on their deadline, handled lazily on read for the common case. An occasional sweep backs that up, so a key that's never read again doesn't hold its memory forever after it has died. The second is a restart. The process will go down at the worst moment. A cache expected to survive that appends every write to a log and periodically folds the log into a snapshot. On startup it loads the latest snapshot and replays only the log written since. Whether the cache needs durability at all is itself a requirement to pin, and a clean thing to ask the interviewer. A read-through cache in front of a database can rebuild itself cold and skip persistence entirely. A cache that's the source of truth for its keys can't. The answer changes the whole lower half of the design.

• Budget by bytes over entries: the machine counts bytes. Counting entries is the starter version. A cache on a fixed memory ceiling budgets by size, because uneven value sizes make an entry count a poor proxy for real pressure. The switch adds a size to each entry and a running total, and touches nothing in the read path.
• LRU has a known blind spot: a scan evicts the hot keys. Least-recently-used is a cheap, sound default until a one-pass scan over many cold keys walks through the cache and pushes out the keys that matter. That specific workload is what justifies a frequency-aware or scan-resistant policy, dropped in behind the eviction interface.
• Expiry is lazy plus a sweep: do not let dead keys linger. Check the deadline on read and evict an expired entry immediately, which keeps the hot path cheap. Back it with an occasional sweep, so a key that's never read again still gives its memory back after it has died.
• Durability is a requirement to pin: ask before you build it. A read-through cache can rebuild cold from its source and skip persistence. A cache that owns its keys needs a log plus periodic snapshots, so a restart replays only recent writes. Which one you're building changes the lower half of the design, so clarify it early.

The VMware angle

The instinct that reads as a VMware hire is designing for the machine and the bad day, beyond the clean demo. Say out loud that the cache is bounded because it runs inside a fixed memory budget. An unbounded map is a resource leak the platform can't afford. Eviction is a stated invariant, never whatever the container happens to drop. A scan is a real workload the default policy handles badly. And a restart is an event the component plans for, more than an accident it hopes to dodge. The same infrastructure thesis runs through everything VMware ships. Get the most out of the hardware you have, and stay correct when the day goes wrong. Reason about the cache under memory pressure, under a hostile scan and mid-crash, beyond the warm single-threaded hit. That's the judgment the bar is set to find. It's the same judgment whether the component is a cache, a thread pool or a connection pool.

The runnable core: a Premium question with TTL

The interviewer often compresses the whole design into one implementable class. For a cache, that's the cache itself at its core: a fixed-capacity store that reads in constant time and refreshes recency on every touch. It evicts the least-recently-used entry when full and expires entries on a deadline. It's the full design in miniature. The whole posture lives in that one class: constant-time operations, a hard budget, a defined eviction rule and a strict expiry boundary. It's where a candidate either states clean invariants or hand-waves.

The problem below keeps the mechanism and drops the distributed concerns, because that's what runs. Time is passed in explicitly as a parameter instead of read from a clock. That makes the TTL behavior deterministic and testable, the same way a real test harness injects time. The work is handling three things cleanly: the recency update on every read, the eviction victim when the budget is full, and the exact expiry boundary. Those edges carry the exercise, the way the duplicate case does in a min-stack.

1

In-memory cache: fixed capacity with LRU eviction and TTL

Medium

Problem

Implement an in-memory key-value cache that holds at most a fixed number of entries, evicts the least-recently-used entry when it is full, and expires entries after a time to live. Time is passed in explicitly so the behavior is deterministic.

- Cache(capacity) creates a cache that holds at most capacity entries.
- put(key, value, now, ttl) stores value under key. The entry expires at now + ttl when ttl > 0; when ttl == 0 the entry never expires. Writing counts as using the key, so it becomes the most-recently-used. If the key is new and the cache is already full, evict the least-recently-used entry first, then insert. If the key already exists, refresh its value and expiry in place.
- get(key, now) returns the value for key if it is present and not expired, and marks it most-recently-used. If the key is absent, return -1. If the key is present but has expired (meaning now >= expiry), remove it and return -1.

The recency update on every touch, the eviction victim, and the expiry boundary are the whole exercise. A full cache must drop the right entry, and a read must count as a use. An entry sitting exactly at its deadline counts as expired.

Input encoding. A test case is a JSON array of operations. The first entry is ["Cache", [capacity]]; each later entry is [method, [args]]. The expected array holds each operation's return, with null for the constructor and for put.

Input: Cache(2); put(1,10,0,0); put(2,20,0,0); get(1,0); put(3,30,0,0); get(2,0)

Output: get(1,0) returns 10; get(2,0) returns -1

The read of key 1 makes it most-recently-used, so key 2 is now the least-recently-used. When key 3 arrives the cache is full, so key 2 is evicted and a later read of it misses.

Input: Cache(3); put(5,50,10,100); get(5,50); get(5,110)

Output: get(5,50) returns 50; get(5,110) returns -1

Key 5 expires at now+ttl = 110. A read at now=50 is before the deadline and hits; a read at now=110 is at the deadline, so the entry is expired, removed, and reported as a miss.

How this uses the pattern

Keep a hash map from key to a node in a doubly linked list ordered by recency, so lookup and moving a node to the front are both constant time. Store an absolute expiry on each node. get checks the deadline and removes on expiry. Otherwise it moves the node to the front. put refreshes or inserts, evicting the tail node first when full.

In-memory cache: fixed capacity with LRU eviction and TTL

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Test Cases

Input: [["Cache",[2]],["put",[1,10,0,0]],["put",[2,20,0,0]],["get",[1,0]],["put",[3,30,0,0]],["get",[2,0]],["get",[3,0]],["get",[1,0]]]Expected: [null,null,null,10,null,-1,30,10]

Input: [["Cache",[2]],["put",[1,10,0,0]],["put",[2,20,0,0]],["put",[1,15,0,0]],["put",[3,30,0,0]],["get",[2,0]],["get",[1,0]],["get",[3,0]]]Expected: [null,null,null,null,null,-1,15,30]

Input: [["Cache",[3]],["put",[5,50,10,100]],["get",[5,50]],["get",[5,110]],["get",[5,120]]]Expected: [null,null,50,-1,-1]

Input: [["Cache",[1]],["put",[1,10,0,20]],["get",[1,25]],["put",[2,20,25,0]],["get",[2,25]]]Expected: [null,null,-1,null,20]

Input: [["Cache",[2]],["put",[9,90,5,0]],["get",[9,1000000]],["put",[7,70,0,50]],["get",[7,49]],["get",[7,50]]]Expected: [null,null,90,null,70,-1]

Need a hint? (3 available)

The VMware angle

This is the real-time core of the cache design, reduced to what runs. VMware cares that the cache is bounded and that eviction and expiry are defined precisely. On a fixed memory budget, an unbounded map is a resource leak and a fuzzy expiry rule is a correctness bug. The interviewer watches three things survive contact with the tests. A read counts as a use and reorders recency. Eviction drops the true least-recently-used entry. And the expiry boundary is handled as now >= expiry instead of a strict greater-than. State those invariants before you code, and drive the boundary cases yourself. Try a full cache, a read that changes who gets evicted, and an entry read at exactly its deadline.

Take it further

A natural VMware extension puts the systems concerns back. Make it thread-safe without turning it into a bottleneck. Shard the key space into independently locked stripes instead of wrapping one global lock around everything. Be ready to say why a get still needs exclusive access even though it looks like a read. Moving a node to the front mutates the shared list. Then make eviction pluggable behind an interface, so least-recently-used can become least-frequently-used or a scan-resistant policy. Say what a one-pass scan does to plain LRU. Finally, budget by bytes instead of entry count. That adds a size per entry and a running total but leaves the read path untouched.

Show solution & walkthrough

What the round rewards

The bar on this round is a clean systems component reasoned from the ground up. Whichever component you draw, a cache, a thread pool, a rate limiter or a connection pool, the moves are the same. Pin the requirements and the deferrals out loud before you build, so scope is agreed and the interviewer knows which upgrades have a home. Derive the data structures from those requirements. The hash-map-plus-recency-list pairing should arrive because constant-time lookup and constant-time eviction demanded it. Keep the coordinator thin and hide the eviction policy and the persistence behind their own seams, so a mid-round change to either lands in one class. Treat concurrency as a first-class requirement, from a global lock to striped locks to finer structures, and say what each rung costs. And design for the machine and the bad day: a fixed budget with a stated eviction rule, expiry that reclaims memory, and a restart the component plans for. Show that judgment and you read like an engineer who could own a piece of a real platform.