DEV Community: Ritesh Gupta

Caching Is Easy. Cache Invalidation Is the Hard Part.

Ritesh Gupta — Fri, 16 Oct 2026 12:32:03 +0000

Imagine you're building an e-commerce application.

A user opens a product page. Instead of querying the database every time, you store the product details in Redis. The page loads faster, and your database has less work to do.

Everything looks great. Then someone updates the product price from ₹999 to ₹1,199. The database has the correct price. But your application keeps showing ₹999.

Nothing is broken in the database. Your API is responding. Redis is working exactly as expected.

Yet the user is seeing the wrong information.

This is the tricky part of caching. Making data faster to access is relatively straightforward. Keeping that cached data accurate is where things get interesting.

Let's understand why cache invalidation is such an important problem in system design.

1. Why Do We Need Caching in the First Place?

Consider a simple application where every request goes directly to the database.

User Request
     |
     v
 Application Server
     |
     v
   Database
     |
     v
    Response

This approach works perfectly well for small applications. But as traffic increases, the database may receive thousands of repeated queries for the same information.

For example, imagine a popular product page receives 10,000 requests in a short period. If every request queries the database for the same product details, we're doing a lot of repetitive work.

Instead, we can store frequently accessed data in a cache.

User Request
     |
     v
 Application Server
     |
     v
    Cache
     |
     |-- Cache HIT --> Return cached data
     |
     |-- Cache MISS --> Query database
                           |
                           v
                      Store in cache
                           |
                           v
                       Return data

A cache is a fast storage layer that keeps copies of data so the application can retrieve them without repeatedly accessing the original data source.

Redis is a popular choice, although caches can also exist inside an application, in a browser, or at a CDN edge.

The benefits are straightforward:

Lower response latency
Fewer database queries
Reduced load on backend services
Better performance during periods of high traffic

But there's one important detail: a cache stores a copy of the data, not the original source of truth.

That distinction explains the problem we're about to explore.

2. What Exactly Is Cache Invalidation?

Cache invalidation means making cached data unusable when it is no longer valid, so that the application can fetch or generate a correct replacement.

Let's continue with our e-commerce example.

Initially, the database contains:

{
  "product_id": 101,
  "name": "Wireless Headphones",
  "price": 999
}

The application fetches this record and caches it.

A few minutes later, an administrator updates the price:

{
  "product_id": 101,
  "name": "Wireless Headphones",
  "price": 1199
}

The database now contains ₹1,199, but the cache still contains ₹999.

If the application returns the cached record, the customer sees an outdated price.

This is called stale data.

The challenge is deciding when cached data should be removed, refreshed, or treated as invalid.

And the difficulty increases when multiple application servers, caches, and services are involved.

3. Three Common Approaches to Cache Invalidation

There isn't one universal solution. The right approach depends on how frequently the data changes and how much staleness the application can tolerate.

Approach 1: TTL-Based Expiration

TTL stands for Time to Live.

It defines how long an entry can remain in the cache before it expires.

For example, we might cache product details for five minutes.

cache.set(
    "product:101",
    product_data,
    ex=300
)

Here, ex=300 represents a 300-second expiration when using the Redis Python client.

After the TTL expires, Redis treats the entry as expired. The next cache lookup will need to retrieve the data again if no valid entry exists.

Advantages:

Simple to implement
Automatically limits how long old entries remain cached
Useful for data that doesn't require immediate updates

Disadvantages:

Data may remain stale until the TTL expires
Frequently accessed entries may still need to be recomputed after expiration
Short TTLs increase cache misses and database load

One important point: TTL does not guarantee that data stays fresh for the entire time window. It only limits how long an entry remains valid according to its expiration.

For example, if a product price changes one second after the cache is populated, users could still see the old price for almost five minutes.

TTL is useful when a little staleness is acceptable. It isn't sufficient by itself when updates must become visible quickly.

Approach 2: Cache-Aside Pattern

Cache-aside is one of the most common caching patterns in backend applications.

The application checks the cache first. If the data isn't there, it reads from the database and stores the result in the cache.

Here's a simplified Python example using a Redis client and a database access function:

import json

def get_product(product_id, redis, db):
    cache_key = f"product:{product_id}"

    cached = redis.get(cache_key)

    if cached is not None:
        return json.loads(cached)

    product = db.get_product(product_id)

    if product is None:
        return None

    redis.set(
        cache_key,
        json.dumps(product),
        ex=300
    )

    return product

The flow is:

Check Redis for the product.
If the entry exists, return it.
Otherwise, query the database.
Store the result in Redis with a TTL.
Return the result to the caller.

This approach keeps the application in control of when data is loaded into the cache.

But notice something important: cache-aside describes how data is read and populated. It doesn't automatically solve invalidation after an update.

We need to handle writes separately.

Approach 3: Explicit Invalidation After a Write

Suppose an administrator updates a product price.

A common strategy is to update the database first and then delete the corresponding cache entry.

def update_product_price(
    product_id,
    new_price,
    db,
    redis
):
    db.update_price(product_id, new_price)

    redis.delete(f"product:{product_id}")

The next request won't find the old cache entry. It can read the updated product from the database and populate the cache again.

This is a simple and effective strategy for many applications.

However, there's a subtle issue.

What happens if the database update succeeds but the cache deletion fails?

The application could continue serving stale data until the cache entry expires or another mechanism removes it.

Distributed systems also introduce race conditions. For example, a request that started reading the old database value before the update might write that old value into the cache after the invalidation occurs.

So even explicit deletion isn't a complete guarantee of consistency under every possible failure or concurrency scenario.

For systems where stale data is especially costly, engineers may need retries, reliable event processing, versioning, or other coordination mechanisms.

4. Cache Invalidation vs. Cache Refresh

These terms are related, but they aren't identical.

Invalidation makes an existing cache entry unusable. The next request may fetch fresh data from the source of truth.

Refresh updates the cached value with newer data, either when a request arrives or in the background.

For example, after a product price changes:

Invalidation: Delete product:101 from Redis.
Refresh: Fetch the updated product and overwrite product:101.

Invalidation is often simpler because the application doesn't have to immediately rebuild every cached value.

Refreshing can be useful when an entry is expensive to regenerate and likely to be requested again soon.

The trade-off is that refresh logic introduces additional work and failure cases. A refresh can fail, or it can overwrite newer data with an older result if concurrency isn't handled carefully.

5. What Happens When Multiple Servers Are Involved?

So far, we've considered one application and one cache.

Now imagine your application has ten server instances, all reading and writing product data.

If each server maintains its own in-memory cache, invalidating data on one server won't automatically invalidate it on the others.

                 Load Balancer
                       |
          +------------+------------+
          |            |            |
          v            v            v
       Server A     Server B     Server C
          |            |            |
       Cache A      Cache B      Cache C
          |            |            |
          +------------+------------+
                       |
                    Database

This is one reason shared caching systems such as Redis are useful: multiple application instances can access the same cache.

But a shared cache doesn't eliminate every consistency problem.

There can still be concurrent requests, delayed invalidation, failed operations, replica lag, and stale values already held by other layers, such as application memory or a CDN.

For larger systems, engineers may use mechanisms such as:

Event-driven invalidation: Publish an event when data changes and have relevant services invalidate their caches.
Versioned cache keys: Include a version in the key so old entries are no longer selected after an update.
TTL as a fallback: Ensure that entries eventually expire even if an invalidation event is missed.
Reliable event delivery: Use durable messaging or an outbox pattern when losing invalidation events would be unacceptable.

These approaches have their own trade-offs. Event-driven invalidation, for example, can reduce stale-data windows, but it doesn't automatically provide immediate consistency because events may be delayed or retried.

The important lesson is that cache invalidation becomes a coordination problem as a system grows.

6. A Related Problem: Cache Stampede

There's another issue worth understanding.

Imagine a popular cached item expires just as thousands of users request it.

Many requests miss the cache at approximately the same time. They all query the database and try to repopulate the same entry.

This sudden burst of work is commonly called a cache stampede.

Instead of reducing database load, the cache expiration creates a spike in database traffic.

Some ways to mitigate this include:

Request coalescing: Let one request load the missing value while other requests wait for its result.
TTL jitter: Add a small random variation to expiration times to avoid many entries expiring simultaneously.
Background refresh: Refresh frequently accessed data before it expires.
Stale-while-revalidate: Serve an older value temporarily while refreshing it in the background, when the application can safely tolerate that staleness.

These techniques solve a different problem from invalidation itself, but they matter when designing a reliable caching strategy.

7. How Do You Choose the Right Strategy?

There is no need to use the most complicated solution everywhere.

Start by asking a few questions:

How frequently does the data change?

For mostly static content, a longer TTL may be enough. For frequently updated records, explicit invalidation may be more appropriate.

How much staleness is acceptable?

A slightly outdated recommendation might be acceptable. An outdated account balance or incorrect price at checkout can have much more serious consequences.

What happens if invalidation fails?

If stale data can cause significant harm, think beyond a simple cache deletion. Consider retries, durable events, versioning, and a clear consistency guarantee.

How expensive is recomputing the data?

If regenerating a value is costly, refreshing it before expiration or coalescing concurrent misses may help.

The goal isn't to eliminate every possible stale read at any cost. It's to choose a strategy whose performance, complexity, and consistency guarantees fit the requirements.

8. The Biggest Lesson I Took From This

Before exploring caching in depth, it's easy to think of it as a simple optimization: put frequently accessed data into Redis and let the application read it faster.

But caching introduces another copy of the data, and now the system has to manage the relationship between that copy and the source of truth.

That changes the problem.

You're no longer thinking only about how quickly a request can return a response. You're also thinking about what happens when data changes, requests overlap, network calls fail, and multiple services disagree temporarily.

A fast system isn't necessarily a correct system. And a good system design has to account for both.

Caching is powerful, but it works best when you understand what you're trading away, how stale data is handled, and what guarantees your application actually needs.

The next time you add a cache to a project, don't stop at asking, "How can I make this faster?"

Also ask:

"When this data changes, how will the rest of my system find out?"

That question can make a much bigger difference than adding another layer of caching.

Want to Practice System Design Beyond Theory?

Understanding concepts like caching, cache invalidation, and distributed systems is a great start. But the real learning happens when you try to apply them to actual system design problems.

That's one reason I've been exploring ScaleDojo — a platform for learning and practicing system design through interactive challenges.

Instead of only reading about architectures, you can work through design problems, think about trade-offs, and improve your understanding of how real-world systems are put together.

If you're learning system design for backend engineering interviews or want to get better at designing scalable applications, it's worth checking out.

Explore ScaleDojo: https://scaledojo.dev/

My takeaway: don't just memorize how distributed systems work. Practice making the decisions that make them work.

The Celebrity Problem: From Brute Force to O(n)

Ritesh Gupta — Sun, 11 Oct 2026 05:49:18 +0000

Imagine you walk into a party with a few hundred guests. You don't know who anyone is, but you're told that one person there might be a celebrity. You can only ask questions of the form:

"Hey, do you know that person over there?"

How many questions do you need to ask to find the celebrity, or to prove there isn't one?

My first instinct when I met this problem was "just ask everyone about everyone." It works, but it's slow. By the end of this post you'll see how to do it with one pass and no extra memory.

Grab a coffee. We'll build this up step by step.

What exactly is a celebrity?

In this problem, a celebrity is someone who satisfies both of these rules:

Everyone knows them.
They know nobody.

That's it. Two rules, and both must hold.

You're given a square matrix M of size n x n:

M[i][j] = 1 means person i knows person j
M[i][j] = 0 means person i does not know person j

Your job: return the celebrity's index, or -1 if there isn't one.

A tiny example

M = [
    [0, 0, 1, 0],   # person 0 knows only person 2
    [0, 0, 1, 0],   # person 1 knows only person 2
    [0, 0, 0, 0],   # person 2 knows nobody
    [0, 1, 1, 0],   # person 3 knows persons 1 and 2
]

Here is the same thing as a picture. An arrow A -> B means "A knows B":

    0 -----+
           |
           v
    1 ---> 2 <--- 3
           ^       |
           |       |
           +-------+
     (3 also knows 1)

Everyone points at person 2, and person 2 points at nobody. So the answer is 2.

💡 Quick sanity check: can there ever be two celebrities? Think about it for a second before reading on.

Answer
No. If A and B were both celebrities, then A would have to know B (because everyone knows a celebrity). But a celebrity knows nobody. That's a contradiction, so there is at most one celebrity. This fact is the secret ingredient of the fast solution later.

Attempt 1: Brute force

The most natural idea is to test every person one by one.

For each person c:

Check that c knows nobody (their entire row is 0, apart from themselves).
Check that everyone knows c (their entire column is 1, apart from themselves).

def find_celebrity_brute(M):
    n = len(M)

    for c in range(n):
        is_celebrity = True

        for i in range(n):
            if i == c:
                continue
            # c must not know i, and i must know c
            if M[c][i] == 1 or M[i][c] == 0:
                is_celebrity = False
                break

        if is_celebrity:
            return c

    return -1

How slow is it?

We have an outer loop over n people and an inner loop over n people.

Time: O(n²), Space: O(1)

For 1,000 people that's about a million checks. For 100,000 people it's ten billion. That's the point where your laptop fan starts to sound like a jet engine.

Can we do better? Let's look for wasted work.

The key insight: every question kills someone

Here's the idea that changes everything. Pick any two people, A and B, and ask just one question: "Does A know B?"

There are only two possible answers, and both of them eliminate somebody.

Answer	What it tells us	Who is eliminated?
Yes, A knows B	A knows someone, but a celebrity knows nobody	A can't be the celebrity
No, A doesn't know B	B isn't known by everyone, but a celebrity must be	B can't be the celebrity

Read that table once more. It's the entire trick.

One question, one person eliminated. Always. No matter what.

So if we start with n people, after n - 1 questions we're left with exactly one candidate. Not the celebrity yet, just the only person who hasn't been ruled out.

Attempt 2: Eliminate with a stack

Let's turn that insight into an algorithm. A stack is a nice way to picture it:

Push everyone onto the stack.
Pop two people, a and b.
If a knows b, then a is out, so push b back. Otherwise b is out, so push a back.
Repeat until one person is left.
Verify that person (more on this soon).

def find_celebrity_stack(M):
    n = len(M)
    stack = list(range(n))

    while len(stack) > 1:
        a = stack.pop()
        b = stack.pop()

        if M[a][b] == 1:      # a knows b, so a is not a celebrity
            stack.append(b)
        else:                 # a doesn't know b, so b is not a celebrity
            stack.append(a)

    candidate = stack.pop()

    # Verification step
    for i in range(n):
        if i == candidate:
            continue
        if M[candidate][i] == 1 or M[i][candidate] == 0:
            return -1

    return candidate

Time: O(n), Space: O(n) for the stack.

We got linear time. But storing everyone in a stack feels like overkill. Can we get rid of it?

Attempt 3: Two pointers, no extra memory

Why keep a stack when we only ever hold one survivor at a time? We can just remember a single variable called candidate.

The idea:

Start by assuming person 0 is the celebrity.
Walk through everyone else, one at a time.
If the current candidate knows person i, the candidate is out and i becomes the new candidate.
Otherwise i is out, and we keep our candidate.

def find_celebrity(M):
    n = len(M)

    # Phase 1: find a possible candidate
    candidate = 0
    for i in range(1, n):
        if M[candidate][i] == 1:
            candidate = i

    # Phase 2: verify the candidate
    for i in range(n):
        if i == candidate:
            continue
        if M[candidate][i] == 1 or M[i][candidate] == 0:
            return -1

    return candidate

That's the whole solution. Two small loops.

Time: O(n), Space: O(1)

Let's trace it by hand

Using our earlier matrix:

M = [
    [0, 0, 1, 0],
    [0, 0, 1, 0],
    [0, 0, 0, 0],
    [0, 1, 1, 0],
]

Phase 1: find the candidate

Step	candidate	i	`M[candidate][i]`	Decision
start	0	-	-	Assume 0
1	0	1	0	0 doesn't know 1, so 1 is out. Keep 0
2	0	2	1	0 knows 2, so 0 is out. Candidate becomes 2
3	2	3	0	2 doesn't know 3, so 3 is out. Keep 2

Candidate after phase 1: 2.

Phase 2: verify

Person	Does 2 know them? (must be 0)	Do they know 2? (must be 1)	OK?
0	`M[2][0] = 0`	`M[0][2] = 1`	✅
1	`M[2][1] = 0`	`M[1][2] = 1`	✅
3	`M[2][3] = 0`	`M[3][2] = 1`	✅

All checks pass, so the celebrity is person 2. 🎉

Wait, why do we need Phase 2?

This is the part most beginners (including me, the first time) skip.

Phase 1 only tells us: "everyone else has been ruled out." It does not tell us the survivor is actually a celebrity. Maybe there is no celebrity at all!

Try this matrix where nobody knows anybody:

M = [
    [0, 0, 0],
    [0, 0, 0],
    [0, 0, 0],
]

Phase 1 hands us person 0 as the candidate (nobody ever knew anyone, so the candidate never changed). But person 0 is not a celebrity, because nobody knows them. Phase 2 catches this and correctly returns -1.

Rule of thumb: elimination finds the only possible answer. Verification confirms it's a real answer.

Comparing all approaches

Approach	Time	Space	Idea
Brute force	O(n²)	O(1)	Test every person fully
Stack elimination	O(n)	O(n)	Eliminate one person per question
Two pointer candidate	O(n)	O(1)	Same idea, no stack needed

And here's how the number of questions grows as n grows:

n (people)	Brute force (about n²)	Optimized (about 3n)
10	100	30
1,000	1,000,000	3,000
100,000	10,000,000,000	300,000

The optimized version needs about n - 1 questions to find a candidate, plus about 2(n - 1) to verify. That is roughly 3n, which is still O(n).

Common mistakes to avoid

Forgetting the verification phase. The most common bug. See the all zeros matrix above.
Checking M[i][i]. A person knowing themselves is usually 0 or ignored. Always skip i == candidate.
Mixing up the direction. M[a][b] means "a knows b", not the other way around. Read it out loud while coding.
Using the wrong elimination rule. If a knows b, eliminate a (not b). I've flipped this more than once at 1 AM.

The interview version

In interviews you often don't get the matrix. You get a function instead:

def knows(a, b) -> bool: ...

The goal is the same, and the number of calls to knows is what gets measured. The same algorithm drops right in:

def findCelebrity(n):
    candidate = 0
    for i in range(1, n):
        if knows(candidate, i):
            candidate = i

    for i in range(n):
        if i == candidate:
            continue
        if knows(candidate, i) or not knows(i, candidate):
            return -1

    return candidate

A small optimization worth mentioning to your interviewer: you can cache results of knows so you never ask the same question twice.

Quick quiz

Test yourself before looking at the answers.

Q1. In Phase 1, candidate = 4 and M[4][7] = 0. What happens?

Answer
Person 4 doesn't know person 7, so 7 cannot be the celebrity (a celebrity must be known by everyone). We keep 4 as the candidate and move on.

Q2. Can the algorithm return a wrong answer without Phase 2?

Answer
Yes. Phase 1 always produces a candidate, even when no celebrity exists. Phase 2 is what confirms it.

Q3. What would the time complexity be if we verified every person instead of only the final candidate?

Answer
That's just the brute force approach again, so O(n²). The whole point of elimination is that we only fully verify one person.

Key takeaways

A celebrity is known by everyone and knows no one.
There can be at most one celebrity.
Every question knows(a, b) rules out exactly one of the two people.
Eliminate first, verify second.
Brute force is O(n²). The elimination approach is O(n) time and O(1) space.

The bigger lesson isn't about celebrities. It's this question:

"Can each step of my algorithm throw away part of the problem?"

That mindset shows up in binary search, two pointers, monotonic stacks, and many other patterns. Once you start looking for it, you'll see it everywhere.

🥋 Want to practice problems like this?

Understanding the solution is one thing.

Being able to solve a new problem on your own is another.

That's why I've been exploring ScaleDojo, a hands-on platform for practicing system design, LLD, API design, and algorithmic problem-solving.

Instead of only reading the solution, you can practice concepts through interactive challenges and get feedback on your approach.

If you're preparing for technical interviews or simply trying to become better at problem-solving, it's worth checking out:

👉 Try ScaleDojo

Your turn

Did you solve this with the stack, two pointers, or something even cleverer? Drop your approach (or your favorite language) in the comments. I'd love to see a Rust or Go version!

And one more question for you: what's the first thing you'd check if your app slowed down after hitting 10x traffic? I'm curious what everyone's instinct is.

If this post helped you, a ❤️ or 🦄 helps more beginners find it, and following me means you won't miss the next one in this series. Thanks for reading, and happy coding!

The Celebrity Problem: From Brute Force to O(n)

Ritesh Gupta — Sun, 11 Oct 2026 05:46:12 +0000

Imagine you walk into a party with a few hundred guests. You don't know who anyone is, but you're told that one person there might be a celebrity. You can only ask questions of the form:

"Hey, do you know that person over there?"

How many questions do you need to ask to find the celebrity, or to prove there isn't one?

My first instinct when I met this problem was "just ask everyone about everyone." It works, but it's slow. By the end of this post you'll see how to do it with one pass and no extra memory.

Grab a coffee. We'll build this up step by step.

What exactly is a celebrity?

In this problem, a celebrity is someone who satisfies both of these rules:

Everyone knows them.
They know nobody.

That's it. Two rules, and both must hold.

You're given a square matrix M of size n x n:

M[i][j] = 1 means person i knows person j
M[i][j] = 0 means person i does not know person j

Your job: return the celebrity's index, or -1 if there isn't one.

A tiny example

M = [
    [0, 0, 1, 0],   # person 0 knows only person 2
    [0, 0, 1, 0],   # person 1 knows only person 2
    [0, 0, 0, 0],   # person 2 knows nobody
    [0, 1, 1, 0],   # person 3 knows persons 1 and 2
]

Here is the same thing as a picture. An arrow A -> B means "A knows B":

    0 -----+
           |
           v
    1 ---> 2 <--- 3
           ^       |
           |       |
           +-------+
     (3 also knows 1)

Everyone points at person 2, and person 2 points at nobody. So the answer is 2.

💡 Quick sanity check: can there ever be two celebrities? Think about it for a second before reading on.

Attempt 1: Brute force

The most natural idea is to test every person one by one.

For each person c:

Check that c knows nobody (their entire row is 0, apart from themselves).
Check that everyone knows c (their entire column is 1, apart from themselves).

def find_celebrity_brute(M):
    n = len(M)

    for c in range(n):
        is_celebrity = True

        for i in range(n):
            if i == c:
                continue
            # c must not know i, and i must know c
            if M[c][i] == 1 or M[i][c] == 0:
                is_celebrity = False
                break

        if is_celebrity:
            return c

    return -1

How slow is it?

We have an outer loop over n people and an inner loop over n people.

Time: O(n²), Space: O(1)

For 1,000 people that's about a million checks. For 100,000 people it's ten billion. That's the point where your laptop fan starts to sound like a jet engine.

Can we do better? Let's look for wasted work.

The key insight: every question kills someone

Here's the idea that changes everything. Pick any two people, A and B, and ask just one question: "Does A know B?"

There are only two possible answers, and both of them eliminate somebody.

Answer	What it tells us	Who is eliminated?
Yes, A knows B	A knows someone, but a celebrity knows nobody	A can't be the celebrity
No, A doesn't know B	B isn't known by everyone, but a celebrity must be	B can't be the celebrity

Read that table once more. It's the entire trick.

One question, one person eliminated. Always. No matter what.

So if we start with n people, after n - 1 questions we're left with exactly one candidate. Not the celebrity yet, just the only person who hasn't been ruled out.

Attempt 2: Eliminate with a stack

Let's turn that insight into an algorithm. A stack is a nice way to picture it:

Push everyone onto the stack.
Pop two people, a and b.
If a knows b, then a is out, so push b back. Otherwise b is out, so push a back.
Repeat until one person is left.
Verify that person (more on this soon).

def find_celebrity_stack(M):
    n = len(M)
    stack = list(range(n))

    while len(stack) > 1:
        a = stack.pop()
        b = stack.pop()

        if M[a][b] == 1:      # a knows b, so a is not a celebrity
            stack.append(b)
        else:                 # a doesn't know b, so b is not a celebrity
            stack.append(a)

    candidate = stack.pop()

    # Verification step
    for i in range(n):
        if i == candidate:
            continue
        if M[candidate][i] == 1 or M[i][candidate] == 0:
            return -1

    return candidate

Time: O(n), Space: O(n) for the stack.

We got linear time. But storing everyone in a stack feels like overkill. Can we get rid of it?

Attempt 3: Two pointers, no extra memory

Why keep a stack when we only ever hold one survivor at a time? We can just remember a single variable called candidate.

The idea:

Start by assuming person 0 is the celebrity.
Walk through everyone else, one at a time.
If the current candidate knows person i, the candidate is out and i becomes the new candidate.
Otherwise i is out, and we keep our candidate.

def find_celebrity(M):
    n = len(M)

    # Phase 1: find a possible candidate
    candidate = 0
    for i in range(1, n):
        if M[candidate][i] == 1:
            candidate = i

    # Phase 2: verify the candidate
    for i in range(n):
        if i == candidate:
            continue
        if M[candidate][i] == 1 or M[i][candidate] == 0:
            return -1

    return candidate

That's the whole solution. Two small loops.

Time: O(n), Space: O(1)

Let's trace it by hand

Using our earlier matrix:

M = [
    [0, 0, 1, 0],
    [0, 0, 1, 0],
    [0, 0, 0, 0],
    [0, 1, 1, 0],
]

Phase 1: find the candidate

Step	candidate	i	`M[candidate][i]`	Decision
start	0	-	-	Assume 0
1	0	1	0	0 doesn't know 1, so 1 is out. Keep 0
2	0	2	1	0 knows 2, so 0 is out. Candidate becomes 2
3	2	3	0	2 doesn't know 3, so 3 is out. Keep 2

Candidate after phase 1: 2.

Phase 2: verify

Person	Does 2 know them? (must be 0)	Do they know 2? (must be 1)	OK?
0	`M[2][0] = 0`	`M[0][2] = 1`	✅
1	`M[2][1] = 0`	`M[1][2] = 1`	✅
3	`M[2][3] = 0`	`M[3][2] = 1`	✅

All checks pass, so the celebrity is person 2. 🎉

Wait, why do we need Phase 2?

This is the part most beginners (including me, the first time) skip.

Phase 1 only tells us: "everyone else has been ruled out." It does not tell us the survivor is actually a celebrity. Maybe there is no celebrity at all!

Try this matrix where nobody knows anybody:

M = [
    [0, 0, 0],
    [0, 0, 0],
    [0, 0, 0],
]

Rule of thumb: elimination finds the only possible answer. Verification confirms it's a real answer.

Comparing all approaches

Approach	Time	Space	Idea
Brute force	O(n²)	O(1)	Test every person fully
Stack elimination	O(n)	O(n)	Eliminate one person per question
Two pointer candidate	O(n)	O(1)	Same idea, no stack needed

And here's how the number of questions grows as n grows:

n (people)	Brute force (about n²)	Optimized (about 3n)
10	100	30
1,000	1,000,000	3,000
100,000	10,000,000,000	300,000

The optimized version needs about n - 1 questions to find a candidate, plus about 2(n - 1) to verify. That is roughly 3n, which is still O(n).

Common mistakes to avoid

Forgetting the verification phase. The most common bug. See the all zeros matrix above.
Checking M[i][i]. A person knowing themselves is usually 0 or ignored. Always skip i == candidate.
Mixing up the direction. M[a][b] means "a knows b", not the other way around. Read it out loud while coding.
Using the wrong elimination rule. If a knows b, eliminate a (not b). I've flipped this more than once at 1 AM.

The interview version

In interviews you often don't get the matrix. You get a function instead:

def knows(a, b) -> bool: ...

The goal is the same, and the number of calls to knows is what gets measured. The same algorithm drops right in:

def findCelebrity(n):
    candidate = 0
    for i in range(1, n):
        if knows(candidate, i):
            candidate = i

    for i in range(n):
        if i == candidate:
            continue
        if knows(candidate, i) or not knows(i, candidate):
            return -1

    return candidate

A small optimization worth mentioning to your interviewer: you can cache results of knows so you never ask the same question twice.

Quick quiz

Test yourself before looking at the answers.

Q1. In Phase 1, candidate = 4 and M[4][7] = 0. What happens?

Answer
Person 4 doesn't know person 7, so 7 cannot be the celebrity (a celebrity must be known by everyone). We keep 4 as the candidate and move on.

Q2. Can the algorithm return a wrong answer without Phase 2?

Answer
Yes. Phase 1 always produces a candidate, even when no celebrity exists. Phase 2 is what confirms it.

Q3. What would the time complexity be if we verified every person instead of only the final candidate?

Answer
That's just the brute force approach again, so O(n²). The whole point of elimination is that we only fully verify one person.

Key takeaways

A celebrity is known by everyone and knows no one.
There can be at most one celebrity.
Every question knows(a, b) rules out exactly one of the two people.
Eliminate first, verify second.
Brute force is O(n²). The elimination approach is O(n) time and O(1) space.

The bigger lesson isn't about celebrities. It's this question:

"Can each step of my algorithm throw away part of the problem?"

That mindset shows up in binary search, two pointers, monotonic stacks, and many other patterns. Once you start looking for it, you'll see it everywhere.

🥋 Want to practice problems like this?

Understanding the solution is one thing.

Being able to solve a new problem on your own is another.

That's why I've been exploring ScaleDojo, a hands-on platform for practicing system design, LLD, API design, and algorithmic problem-solving.

Instead of only reading the solution, you can practice concepts through interactive challenges and get feedback on your approach.

If you're preparing for technical interviews or simply trying to become better at problem-solving, it's worth checking out:

👉 Try ScaleDojo

Your turn 👇

Did you solve this with the stack, two pointers, or something even cleverer? Drop your approach (or your favorite language) in the comments. I'd love to see a Rust or Go version!

And one more question for you: what's the first thing you'd check if your app slowed down after hitting 10x traffic? I'm curious what everyone's instinct is.

If this post helped you, a ❤️ or 🦄 helps more beginners find it, and following me means you won't miss the next one in this series. Thanks for reading, and happy coding!

[Boost]

Ritesh Gupta — Tue, 15 Sep 2026 14:42:05 +0000

What Is System Design? A Practical Guide for Developers Who Just Want to "Get It" - DEV Community

The first time someone said "design a system like Twitter" to me, my brain did this weird glitchy...

dev.to

What Is System Design? A Practical Guide for Developers Who Just Want to "Get It"

Ritesh Gupta — Tue, 15 Sep 2026 14:40:11 +0000

The first time someone said "design a system like Twitter" to me, my brain did this weird glitchy thing where it just... stopped. I could build a to-do app. I could write a REST API. I could center a div (okay, that one took longer). But "design a system"? That felt like being asked to build a car when I'd only ever changed a tire.

If that sounds familiar, you're exactly who this post is for.

This is my first post on dev.to, so let's make it count no dry textbook definitions, no 40-page whitepaper energy. Just a straight-up, developer-to-developer walkthrough of what system design actually is, why it matters, and how to start thinking like someone who can design systems not just write code that runs.

Grab your coffee ☕. Let's go.

First, Let's Kill the Scary Myth

Here's the biggest misconception: system design is not about knowing fancy buzzwords.

You don't need to memorize "CAP theorem," "eventual consistency," and "consistent hashing" like flashcards to be good at this. Those are tools. System design is really just one thing:

Figuring out how to structure software so it actually works reliably, at scale, and without falling over when real users show up.

That's it. Everything else load balancers, databases, caching, queues exists to solve that one problem.

Writing code answers the question "how do I make this work?"
System design answers the question "how do I make this work when 10 people become 10 million people?"

Why Should You, a Regular Developer, Care?

Maybe you're not applying to Google. Maybe you just build stuff for your startup, your client, or your side project. So why bother?

Because system design thinking shows up everywhere, even in small projects:

Your app is slow under load → that's a system design problem.
Your database keeps timing out → system design.
Your server crashes when a blog post goes viral → yep, system design.
You want your app to survive a server restart without losing data → still system design.

Understanding these concepts doesn't just help you pass interviews (though it absolutely does that too). It helps you build things that don't fall apart the moment they get popular.

The Building Blocks: What You're Actually Juggling

Let's break down system design into the core ingredients. Think of these as the "food groups" of a healthy, scalable system.

1. Scalability: Handling More Without Breaking

Scalability is your system's ability to handle growth. There are two classic ways to scale:

Type	What it means	Analogy
Vertical Scaling	Add more power (CPU, RAM) to one machine	Hiring a stronger worker
Horizontal Scaling	Add more machines to share the load	Hiring more workers

Vertical scaling is easy but has a ceiling there's only so much RAM you can cram into one box. Horizontal scaling is how the big players (Netflix, Amazon, etc.) handle massive traffic spreading the load across hundreds or thousands of servers.

2. Load Balancers: The Traffic Cops

Imagine one cashier trying to serve an entire mall on Black Friday. Chaos, right?

A load balancer sits in front of your servers and distributes incoming requests across them, so no single server gets overwhelmed. It's the reason your favorite app doesn't collapse when everyone opens it at once.

3. Caching: Stop Doing the Same Work Twice

If your database gets asked "what's the weather in Lucknow?" ten thousand times a second, that's ten thousand unnecessary trips to the database.

Caching stores frequently accessed data somewhere fast (like Redis or Memcached) so your system can say "oh, I already know that" instead of doing the expensive lookup every single time.

Rule of thumb: if data doesn't change often but is read a LOT, cache it.

4. Databases: SQL vs NoSQL (and Why It's Not a Fight)

This isn't a "which one is better" debate it's "which one fits your problem."

SQL (Postgres, MySQL) great when your data has clear relationships and you need strong consistency (think: banking transactions).
NoSQL (MongoDB, Cassandra, DynamoDB) great when you need flexibility and massive horizontal scale (think: social media feeds, logs, sensor data).

As systems grow, you'll also hear about:

Replication copying your database across multiple servers for reliability.
Sharding splitting one giant database into smaller pieces so no single machine is overloaded.

5. The CAP Theorem (Said Simply)

You'll hear this term thrown around a lot, so here's the plain-English version:

In a distributed system, you can only reliably guarantee two of these three at the same time:

Consistency everyone sees the same data at the same time
Availability the system always responds, even during failures
Partition Tolerance the system keeps working even if parts of it can't talk to each other

Since network failures will happen eventually, you're really choosing between Consistency and Availability when things go wrong. That single decision shapes a huge chunk of real-world architecture.

6. Message Queues: Let Tasks Wait Their Turn

Not everything needs to happen instantly. If a user uploads a video, do you really need to process it right now, blocking their entire request?

Nope. You drop the task into a message queue (like Kafka, RabbitMQ, or SQS), and a separate worker processes it in the background. This keeps your app responsive and decouples "slow work" from "user-facing work."

7. CDNs: Serving Content Closer to Users

A Content Delivery Network caches your static content (images, videos, JS files) on servers around the world, so a user in Mumbai isn't waiting on a server sitting in Virginia. Faster load times, happier users.

Let's Actually Design Something: A URL Shortener 🔗

Theory is nice, but let's get our hands dirty. A classic beginner-friendly system design problem: build something like bit.ly.

The ask: User pastes a long URL, gets back a short one. When someone visits the short URL, they get redirected to the original.

Here's a simplified way to think through it:

API Layer a simple endpoint like POST /shorten takes the long URL.
ID Generation generate a short, unique code (e.g., base62 encoding of an auto-incrementing ID, or a hash).
Database store the mapping: short_code → original_url.
Redirect Endpoint GET /:short_code looks up the original URL and issues a redirect (HTTP 301/302).
Caching since popular short links get hit a LOT, cache the hot ones in Redis instead of hitting the database every time.
Scale it up add a load balancer in front of multiple API servers, and shard the database once you outgrow a single instance.

User → Load Balancer → API Servers → Cache (Redis) → Database
                                   ↳ if cache miss, fallback to DB

See? It's not magic. It's just asking "what happens at each step, and what breaks first as this grows?"

Mistakes Almost Every Beginner Makes (I Made All of These)

Jumping straight to "microservices" for a project with 10 users. You don't need Kubernetes for your todo app. Start simple, scale when you actually need to.
Ignoring the database until it's a fire. Data modeling decisions made on day one haunt you on day 300.
Designing for infinite scale nobody asked for. Over-engineering is just as bad as under-engineering.
Forgetting about failure. Ask "what happens if this server dies right now?" more often than you think you need to.

How to Actually Get Good at This

You don't learn system design by reading one article (yes, even this one). You learn it by:

Studying real architectures Read engineering blogs from companies like Uber, Netflix, and Discord. They openly explain how they solved massive scale problems.
Practicing real system-design problems Platforms like ScaleDojo can help you move from simply reading system-design concepts to actually applying them through hands-on challenges.
Building small versions yourself Add caching to a side project. Try horizontal scaling with Docker Compose. Break things on purpose and see what happens.
Asking "what if this fails?" constantly This single question separates junior thinking from senior thinking.

Wrapping Up

System design isn't some elite skill reserved for senior engineers with 10 years of experience. It's a mindset one where you zoom out from "does this code work" to "does this system survive contact with the real world."

Start small. Ask good questions. Break your own toy projects on purpose and figure out how to fix them. That's genuinely how this skill is built one curious "wait, what happens if..." at a time.

If this helped untangle system design even a little, I'd love to hear about the first "big" system you ever tried to design drop it in the comments. And if you want, I can turn this into a series: caching deep-dive, database scaling, real interview walkthroughs just say the word. 👇

This is my first post on dev.to feedback (gentle or brutal) is very welcome! 🙌

DEV Community: Ritesh Gupta

Caching Is Easy. Cache Invalidation Is the Hard Part.

1. Why Do We Need Caching in the First Place?

2. What Exactly Is Cache Invalidation?

3. Three Common Approaches to Cache Invalidation

Approach 1: TTL-Based Expiration

Approach 2: Cache-Aside Pattern

Approach 3: Explicit Invalidation After a Write

4. Cache Invalidation vs. Cache Refresh

5. What Happens When Multiple Servers Are Involved?

6. A Related Problem: Cache Stampede

7. How Do You Choose the Right Strategy?

8. The Biggest Lesson I Took From This

Want to Practice System Design Beyond Theory?

The Celebrity Problem: From Brute Force to O(n)

What exactly is a celebrity?

A tiny example

Attempt 1: Brute force

How slow is it?

The key insight: every question kills someone

Attempt 2: Eliminate with a stack

Attempt 3: Two pointers, no extra memory

Let's trace it by hand

Phase 1: find the candidate

Phase 2: verify

Wait, why do we need Phase 2?

Comparing all approaches

Common mistakes to avoid

The interview version

Quick quiz

Key takeaways

🥋 Want to practice problems like this?

More practice problems

Your turn

The Celebrity Problem: From Brute Force to O(n)

What exactly is a celebrity?

A tiny example

Attempt 1: Brute force

How slow is it?

The key insight: every question kills someone

Attempt 2: Eliminate with a stack

Attempt 3: Two pointers, no extra memory

Let's trace it by hand

Phase 1: find the candidate

Phase 2: verify

Wait, why do we need Phase 2?

Comparing all approaches

Common mistakes to avoid

The interview version

Quick quiz

Key takeaways

🥋 Want to practice problems like this?

More practice problems

Your turn 👇

[Boost]

What Is System Design? A Practical Guide for Developers Who Just Want to "Get It" - DEV Community

What Is System Design? A Practical Guide for Developers Who Just Want to "Get It"

First, Let's Kill the Scary Myth

Why Should You, a Regular Developer, Care?

The Building Blocks: What You're Actually Juggling

1. Scalability: Handling More Without Breaking

2. Load Balancers: The Traffic Cops

3. Caching: Stop Doing the Same Work Twice

4. Databases: SQL vs NoSQL (and Why It's Not a Fight)

5. The CAP Theorem (Said Simply)

6. Message Queues: Let Tasks Wait Their Turn

7. CDNs: Serving Content Closer to Users

Let's Actually Design Something: A URL Shortener 🔗

Mistakes Almost Every Beginner Makes (I Made All of These)

How to Actually Get Good at This

Wrapping Up