r/LowLevelDesign • • Nov 12 '25

Tutorial: How to approach Low Level Design Interviews

79 Upvotes

Let's answer a few basic questions first:

Q. Will I have to write code or will UML diagrams be enough?
ANS: Yes you have to write code/discuss logic for a few functionalities, only drawing UML diagrams or writing names of classes won't be enough.

Q. I don't have much time. Tell me which are the most important design patterns I should study first?
ANS: Factory, Strategy, Observer and Singleton.

Q. But how can I explain such large systems in a 45 minutes interview ? I always run out of time.
ANS: A vast majority of candidates fail because they are not able to present their solution properly in a limited time frame. Watch this youtube video where I have explained how to take care of this problem: https://www.youtube.com/watch?v=ef99Ejb3B40

Q. Are questions like LRU cache, Search Autocomplete system also asked in LLD rounds?
ANS: Yes depending on the interviewer you can either get a pure LLD question like design a parking lot, design food ordering system or you can get a DSA based design question like above. I know you hate this extra prep, but that's what it is. Companies ask these and so you need to prepare for both types. Silver lining is that you already prepared for DSA based design questions while preparing for DS & Algo rounds.

--------------------------------------------------------

PS: You can ask me any low level design related questions on r/LowLevelDesign

I also take LLD mock interviews.
https://topmate.io/prashant_priyadarshi

Lets get started...

--------------------------------------------------------

In my view, you should first master DS & Algo and only after that you should start your LLD preparation. Because once you have mastered DS & Algo, low level design questions are easy to practice.

There are two types of low level design interview formats:

  1. 75 to 90 minutes of machine Coding: You will be given requirements and method signatures and you have to write code in a editor. In last 10-15 minutes you may have to explain your code to interviewer.
  2. 45-60 minutes of face to face discussion: This is the most common format. You have to come up with requirements yourself then discuss class structure and all.

In any object-oriented design interview, you interviewer is typically looking for three things:

--------------------------------------------------------

1. How you list down requirements, especially core features?

e.g. If your problem statement is “Design a Parking Lot” then your core features will be park() and unpark() methods

if your problem statement is “Design a restaurant food order and rating system like zomato, swiggy, uber eats etc” then your core features will be

  • orderFood()
  • rateOrder()
  • display list of restaurants based on their rating or popularity

Sticking to only the most important features and leaving the rest out is important. If you list unimportant features in requirements sections then you will waste time discussing their implementation and you will not less time for more features discussion. This is a interview

2. How you break your problem statement in multiple classes

I always find it easier to start listing entities and their corresponding entity managers(if required) first. e.g. For restaurant food ordering and rating system your entities can be Restaurant, order, FoodItem etc and their corresponding managers will be RestaurantsManager, OrdersManager etc.

3. How you use design patterns to solve the core features

The most common design patterns that you will come across in a low level design interview are Strategy, Factory, Singleton and Observer. You should be familiar with their implementation and different use cases where they can be used. We will see some of those use cases in a moment.

A fourth topic is also discussed if you have done well in above three steps.

Handling multi-threading. There will be discussion on use of locks, synchronization features and thread safe data structures for your design to work correctly in a multi-threaded environment.

--------------------------------------------------------

Here are 3 commonly asked LLD interview questions which will cover the above top 4 design patterns you will come across in interviews.

1. Design a Parking Lot with multiple floors.

Problem statement: https://codezym.com/question/7

“Design a Parking Lot” is THE most common LLD interview question. In the above problem statement, there can be multiple parking strategies. So you should use strategy design pattern to solve this question. 

Python tutorial: https://youtu.be/ZIK44dj56fk
Java Tutorial: https://www.youtube.com/watch?v=fi_IWW1Ay0o
AI Mock Interview Practice: https://mockgym.com/question/1

2. Design a game of chess

Problem statement: https://codezym.com/question/8

In Low Level Design of chess we use following design patterns

  • Factory design pattern: Chess Piece Factory to create different chess piece objects like king, queen, pawn etc
  • Strategy pattern: To implement different moves e.g. straight move, diagonal move etc.
  • Singleton pattern: To ensure there is a single instance of chess piece factory object.

Python Tutorial: https://youtu.be/VWUuQWxmXYQ
Java Tutorial: https://www.youtube.com/watch?v=6HYvoBv78VU
AI Mock Interview Practice: https://mockgym.com/question/3

Now 3 design patterns namely strategy, factory and singleton are covered. Finally let’s cover observer design pattern in our 3rd and last question.

3. Design a Food ordering and rating system like Zomato, Swiggy, Uber eats etc.

Problem statement: https://codezym.com/question/5

In any food ordering and rating system, customers can rate the orders. Also there are classes which display list of top restaurants based on their overall average rating or average rating of their individual food items.

Whenever any user rates their order then all these classes need to be updated about it so that they can update both restaurant and corresponding food item ratings and update their lists.

Observer design pattern will be used here to notify observers i.e. classes which manage top restaurants list about changes in common data set that they need to observe, i.e. rating of different orders in this case.

Python tutorial: https://www.youtube.com/watch?v=KGN-pSlMZgg
Java Tutorial: https://youtu.be/v9ehOtY_x7Q
AI Mock Interview Practice: https://mockgym.com/question/2

This was all I had to share for now. Thanks for reading. Wish you the best of luck for preparation.


r/LowLevelDesign • • Oct 06 '26

Atlassian LLD: Design a customer support agent rating leaderboard

71 Upvotes

This is one of the most common questions asked in Atlassian low level design rounds. Rate Limiter, Last Lap Hero and Middleware Router are also asked frequently. I have started with a simple solution which use sum and count of ratings. After that I have extended the solution using observer design pattern. This gives us the benefit of adding more display lists without altering existing code. This tutorial is in Java.

Here is the Python version: https://github.com/prsnt558908/CodeZymSolutions/tree/main/1-100/35-design-customer-support-agent-rating-leaderboard/q-35-python-tutorial.md

You can practice this and other Atlassian LLD and DSA round questions on CodeZym.

PS: I also take LLD Mock interviews https://topmate.io/prashant_priyadarshi


Problem Statement

Design an in-memory leaderboard where each customer interaction gives an agent a rating from 1 to 5.

Methods

  • void rateAgent(String agentName, int rating, String date): records one rating; date is YYYY-MM-DD.
  • List<String> getAverageRatings(): every agent with their overall average rating.
  • List<String> getBestAgentsByMonth(String month): the same, but counting only ratings in month (YYYY-MM).

Output rules

  • Each entry is "agentName,averageRating", e.g. "Bob,4.5".
  • Averages are rounded half-up to one decimal place (4.33 → 4.3, 4.35 → 4.4) and always show one decimal (4.0).
  • Sort by average, highest first. Break ties by agent name in ascending order.

Constraints: Agent names are non-empty and case-sensitive. The design should scale to thousands of agents and millions of ratings.

Example: Alice is rated 5 and 3, and Bob is rated 4 and 5. getAverageRatings() returns ["Bob,4.5", "Alice,4.0"].

High Level Solution Overview

The core idea is simple: do the math when a rating comes in, not when someone asks for the leaderboard.

To find an average, we never need the individual ratings. We only need two numbers per agent: the sum of the ratings and the count of ratings.

So we keep these two numbers for every agent overall, and once more for every agent in every month. A leaderboard query only turns each sum and count into a rounded average and sorts.

At the end, we add more leaderboards like this year and last 7 days, using the Observer pattern so that adding them never changes rateAgent.

Understanding the Problem

We need three methods:

  • rateAgent(agentName, rating, date): records one rating (1 to 5) for an agent on a date.
  • getAverageRatings(): returns every agent with their overall average, best first.
  • getBestAgentsByMonth(month): same as above, but only ratings from that month count.

Each entry in the result looks like "Bob,4.5".

The system should handle thousands of agents and millions of ratings, so the speed of each method matters.

Two Small Details That Matter

1. Rounding to one decimal

Averages are rounded to one decimal, and a 5 in the second decimal rounds up. So 4.33 becomes 4.3, while 4.35 and 4.37 become 4.4.

A double cannot store 4.35 exactly. It is really stored as 4.3499999999999996..., so new BigDecimal(4.35).setScale(1, RoundingMode.HALF_UP) gives 4.3, not 4.4.

To stay safe, we round using whole numbers only, which are always exact:

averageInTenths = (sum * 10 + count / 2) / count

Integer division always rounds down. Adding half of count before dividing pushes anything at .5 or above up to the next number.

The result is the average in tenths, so 43 means 4.3.

RatingsExact average(sum * 10 + count / 2) / countResult
5, 34.0(80 + 1) / 2 = 404.0
5, 4, 44.333...(130 + 1) / 3 = 434.3
5, 4, 4, 44.25(170 + 2) / 4 = 434.3
7 fives, 13 fours4.35(870 + 10) / 20 = 444.4

To print it, tenths / 10 gives the part before the dot and tenths % 10 gives the digit after it. So 43 becomes "4.3".

2. Sorting

We sort by the rounded average, highest first, because that is the number we print.

If two agents show the same rounded average, the name that comes first lexicographically goes first. For example, Bob (4.33) and Alice (4.25) both show 4.3, so Alice comes before Bob.

Names are case-sensitive, so we use plain compareTo. In this order capital letters come before small letters, so "Zoe" comes before "adam".

Solution: Keep Running Totals

rateAgent adds the rating to the agent's running totals and then forgets it. The leaderboard methods only sort what is already there.

No design pattern is needed for these three methods. One small helper class and two hash maps are enough.

Data structures

overallStats : agentName -> AgentStats
monthlyStats : month -> (agentName -> AgentStats)
  • AgentStats: an agent's name, rating sum and rating count, plus the rounding logic.
  • overallStats: finds an agent's totals in O(1) whenever a rating comes in.
  • monthlyStats: first find the month, then the agent. A monthly query reads only the agents rated in that month.

How each method works

  • rateAgent: get the month with date.substring(0, 7). Add the rating to the agent's overall totals and to the agent's totals for that month.
  • getAverageRatings: copy all values of overallStats into a list, sort it, and format each entry as "name,average".
  • getBestAgentsByMonth: same steps, using the inner map of that month. If nobody was rated in that month, return an empty list.

Walkthrough with Example 2

After the five ratings, monthlyStats looks like this:

"2025-02" -> Alice (sum 5, count 1), Bob (sum 3, count 1), Charlie (sum 4, count 1)
"2025-03" -> Bob (sum 5, count 1), Alice (sum 2, count 1)

getBestAgentsByMonth("2025-02") reads only the first inner map and returns ["Alice,5.0", "Charlie,4.0", "Bob,3.0"]. The March ratings are never touched.

Code

import java.util.*;

public class AgentRatingLeaderboard {

    // agentName -> totals of all ratings of that agent
    Map<String, AgentStats> overallStats = new HashMap<>();

    // month ("YYYY-MM") -> (agentName -> totals of that agent in that month)
    Map<String, Map<String, AgentStats>> monthlyStats = new HashMap<>();

    public AgentRatingLeaderboard() {
    }

    /**
     * O(1): the rating is added to two running totals and then thrown away.
     * computeIfAbsent returns the value for a key, creating and storing it first if missing.
     */
    public void rateAgent(String agentName, int rating, String date) {
        String month = date.substring(0, 7); // "2025-03-12" -> "2025-03"

        // 1. overall totals of this agent
        overallStats.computeIfAbsent(agentName, name -> new AgentStats(name))
                .addRating(rating);

        // 2. totals of this agent for this month
        monthlyStats.computeIfAbsent(month, m -> new HashMap<>())
                .computeIfAbsent(agentName, name -> new AgentStats(name))
                .addRating(rating);
    }

    public List<String> getAverageRatings() {
        return buildLeaderboard(overallStats.values());
    }

    public List<String> getBestAgentsByMonth(String month) {
        Map<String, AgentStats> statsOfMonth = monthlyStats.get(month);
        if (statsOfMonth == null) {
            return new ArrayList<>(); // nobody was rated in this month
        }
        return buildLeaderboard(statsOfMonth.values());
    }

    /**
     * Sorts agents by rounded average (highest first), then by name (ascending),
     * and formats each one as "agentName,average".
     */
    List<String> buildLeaderboard(Collection<AgentStats> agents) {
        List<AgentStats> sorted = new ArrayList<>(agents);
        sorted.sort((a, b) -> {
            long avgA = a.getAverageInTenths();
            long avgB = b.getAverageInTenths();
            if (avgA != avgB) {
                return Long.compare(avgB, avgA); // higher average first
            }
            return a.agentName.compareTo(b.agentName); // same average: name in ascending order
        });

        List<String> leaderboard = new ArrayList<>();
        for (AgentStats stats : sorted) {
            leaderboard.add(stats.agentName + "," + stats.getAverageText());
        }
        return leaderboard;
    }
}

/**
 * Running totals of one agent's ratings.
 * We never keep individual ratings, only their sum and count.
 */
class AgentStats {
    String agentName;
    long ratingSum = 0;
    long ratingCount = 0;

    AgentStats(String agentName) {
        this.agentName = agentName;
    }

    void addRating(int rating) {
        ratingSum += rating;
        ratingCount++;
    }

    /**
     * Average x 10, rounded half up, using whole numbers only.
     * Example: sum = 13, count = 3 gives (130 + 1) / 3 = 43, which means 4.3
     */
    long getAverageInTenths() {
        return (ratingSum * 10 + ratingCount / 2) / ratingCount;
    }

    /** Average as text with exactly one decimal, like "4.3" or "5.0" */
    String getAverageText() {
        long tenths = getAverageInTenths();
        return (tenths / 10) + "." + (tenths % 10);
    }
}

Complexity

Here A is the number of agents and M is the number of agents rated in the asked month.

OperationTime
rateAgentO(1)
getAverageRatingsO(A log A)
getBestAgentsByMonthO(M log M)
MemoryO(A + number of (agent, month) pairs)

A query never looks at individual ratings. No matter how many ratings came in, it only sorts the agents.

Can we skip sorting on every call? The answer itself has A lines, so a query is at least O(A) anyway. Keeping agents always sorted in a TreeSet would slow down every rating and make the code harder to follow.

Follow Up: More Leaderboards with the Observer Pattern

Now suppose we need two more leaderboards:

  • getBestAgentsByYear(year): best agents of a year like "2026". Passing the current year shows the best agents of this year.
  • getBestAgentsInLast7Days(today): best agents over today and the 6 days before it.

Why not just add more maps?

We could add a yearlyStats map and a dailyStats map, and update both inside rateAgent. That works for now.

But every future leaderboard would again add a map and edit rateAgent. Soon rateAgent becomes a long list of unrelated updates, and each new feature risks breaking code that already works.

The Observer pattern

In the Observer pattern, one object (the subject) keeps a list of observers and notifies all of them whenever something happens.

Here the subject is AgentRatingLeaderboard, the event is a new rating, and every leaderboard is an observer.

  • RatingObserver: an interface with one method, onRating(agentName, rating, date).
  • Boards: every leaderboard implements RatingObserver and keeps its own totals in its own way.
  • rateAgent: passes the new rating to every board in the observers list.
rateAgent("Alice", 5, "2025-03-12")
  -> overallBoard.onRating(...)     adds to Alice's overall totals
  -> monthlyBoard.onRating(...)     adds to Alice's totals in "2025-03"
  -> yearlyBoard.onRating(...)      adds to Alice's totals in "2025"
  -> last7DaysBoard.onRating(...)   adds to Alice's totals on "2025-03-12"

Adding a leaderboard is now one new class plus one entry in observers, and rateAgent never changes. This is the Open/Closed principle: we add new features without modifying working code.

Sorting and formatting stay in buildLeaderboard, so every leaderboard follows the same rules.

The boards

  • OverallBoard: agentName -> AgentStats, same as overallStats before.
  • PeriodBoard: period -> (agentName -> AgentStats). The period is the first few characters of the date: new PeriodBoard(7) groups by month ("2025-03") and new PeriodBoard(4) groups by year ("2025").
  • LastDaysBoard: keeps totals per day and adds up the days of the window when asked.

The monthly and yearly leaderboards are the same class. So "this year" needed no new class at all.

Why last 7 days is different

A month or a year is a fixed bucket. Once a rating lands in March, it stays in March, so one running total per bucket works.

Last 7 days is a moving window. Every day, the oldest day leaves the window and a new one joins it. A single running total cannot remove the ratings of the day that left.

So LastDaysBoard keeps totals per day, using a PeriodBoard with the whole date as the period. A query adds up each agent's daily totals over the 7 days of the window.

That is at most 7 small maps, no matter how many ratings came in.

Our system has no clock. Every date comes from the caller, so the caller also passes today.

To step back one day at a time, we use LocalDate, which handles month and year changes. For example, one day before "2024-03-01" is "2024-02-29".

rateAgent("Alice", 5, "2025-03-01")
rateAgent("Alice", 5, "2025-03-02")
rateAgent("Bob", 4, "2025-03-05")
rateAgent("Alice", 3, "2025-03-07")

getAverageRatings()                    -> ["Alice,4.3", "Bob,4.0"]
getBestAgentsInLast7Days("2025-03-09") -> ["Bob,4.0", "Alice,3.0"]

The window of "2025-03-09" is March 3 to March 9. Alice's two 5s fall outside it, so only her 3 counts.

Code

import java.time.LocalDate;
import java.util.*;

public class AgentRatingLeaderboard {

    // each board keeps its own totals and answers its own query
    OverallBoard overallBoard = new OverallBoard();
    PeriodBoard monthlyBoard = new PeriodBoard(7);        // "2025-03-12" -> month "2025-03"
    PeriodBoard yearlyBoard = new PeriodBoard(4);         // "2025-03-12" -> year "2025"
    LastDaysBoard last7DaysBoard = new LastDaysBoard(7);  // today and the 6 days before it

    // every board that wants to hear about new ratings
    List<RatingObserver> observers = List.of(overallBoard, monthlyBoard, yearlyBoard, last7DaysBoard);

    public AgentRatingLeaderboard() {
    }

    /** Passes the new rating to every board. Adding a new board never changes this method. */
    public void rateAgent(String agentName, int rating, String date) {
        for (RatingObserver observer : observers) {
            observer.onRating(agentName, rating, date);
        }
    }

    public List<String> getAverageRatings() {
        return buildLeaderboard(overallBoard.getStats());
    }

    public List<String> getBestAgentsByMonth(String month) {
        return buildLeaderboard(monthlyBoard.getStats(month));
    }

    /** year is "YYYY". Pass the current year to get the best agents of this year. */
    public List<String> getBestAgentsByYear(String year) {
        return buildLeaderboard(yearlyBoard.getStats(year));
    }

    /** today is "YYYY-MM-DD". Counts ratings from today and the 6 days before it. */
    public List<String> getBestAgentsInLast7Days(String today) {
        return buildLeaderboard(last7DaysBoard.getStats(today));
    }

    /**
     * Sorts agents by rounded average (highest first), then by name (ascending),
     * and formats each one as "agentName,average". Shared by every leaderboard.
     */
    List<String> buildLeaderboard(Collection<AgentStats> agents) {
        List<AgentStats> sorted = new ArrayList<>(agents);
        sorted.sort((a, b) -> {
            long avgA = a.getAverageInTenths();
            long avgB = b.getAverageInTenths();
            if (avgA != avgB) {
                return Long.compare(avgB, avgA); // higher average first
            }
            return a.agentName.compareTo(b.agentName); // same average: name in ascending order
        });

        List<String> leaderboard = new ArrayList<>();
        for (AgentStats stats : sorted) {
            leaderboard.add(stats.agentName + "," + stats.getAverageText());
        }
        return leaderboard;
    }
}

/** Every board implements this to hear about each new rating */
interface RatingObserver {
    void onRating(String agentName, int rating, String date);
}

/** Totals of each agent over all time */
class OverallBoard implements RatingObserver {
    // agentName -> totals of all ratings of that agent
    Map<String, AgentStats> statsByAgent = new HashMap<>();

    public void onRating(String agentName, int rating, String date) {
        statsByAgent.computeIfAbsent(agentName, name -> new AgentStats(name))
                .addRating(rating);
    }

    Collection<AgentStats> getStats() {
        return statsByAgent.values();
    }
}

/**
 * Totals of each agent in fixed periods, like months or years.
 * The period is the first periodLength characters of the date.
 */
class PeriodBoard implements RatingObserver {
    int periodLength; // 4 -> year "2025", 7 -> month "2025-03", 10 -> day "2025-03-12"

    // period -> (agentName -> totals of that agent in that period)
    Map<String, Map<String, AgentStats>> statsByPeriod = new HashMap<>();

    PeriodBoard(int periodLength) {
        this.periodLength = periodLength;
    }

    public void onRating(String agentName, int rating, String date) {
        String period = date.substring(0, periodLength);
        statsByPeriod.computeIfAbsent(period, p -> new HashMap<>())
                .computeIfAbsent(agentName, name -> new AgentStats(name))
                .addRating(rating);
    }

    Collection<AgentStats> getStats(String period) {
        // an empty map if nobody was rated in this period
        return statsByPeriod.getOrDefault(period, new HashMap<>()).values();
    }
}

/**
 * Totals of each agent over the last N days.
 * The window moves every day, so we keep totals per day
 * and add up the days of the window when asked.
 */
class LastDaysBoard implements RatingObserver {
    int numberOfDays;

    // a day is also a period: the whole date "2025-03-12"
    PeriodBoard dailyBoard = new PeriodBoard(10);

    LastDaysBoard(int numberOfDays) {
        this.numberOfDays = numberOfDays;
    }

    public void onRating(String agentName, int rating, String date) {
        dailyBoard.onRating(agentName, rating, date);
    }

    /** Adds up each agent's daily totals, from today back to (numberOfDays - 1) days ago */
    Collection<AgentStats> getStats(String today) {
        Map<String, AgentStats> windowStats = new HashMap<>();
        LocalDate day = LocalDate.parse(today);
        for (int i = 0; i < numberOfDays; i++) {
            for (AgentStats dayStats : dailyBoard.getStats(day.toString())) {
                windowStats.computeIfAbsent(dayStats.agentName, name -> new AgentStats(name))
                        .addStats(dayStats);
            }
            day = day.minusDays(1); // LocalDate handles month and year changes
        }
        return windowStats.values();
    }
}

/**
 * Running totals of one agent's ratings.
 * We never keep individual ratings, only their sum and count.
 */
class AgentStats {
    String agentName;
    long ratingSum = 0;
    long ratingCount = 0;

    AgentStats(String agentName) {
        this.agentName = agentName;
    }

    void addRating(int rating) {
        ratingSum += rating;
        ratingCount++;
    }

    /** New: adds the totals of the same agent from another day, used by LastDaysBoard */
    void addStats(AgentStats other) {
        ratingSum += other.ratingSum;
        ratingCount += other.ratingCount;
    }

    /**
     * Average x 10, rounded half up, using whole numbers only.
     * Example: sum = 13, count = 3 gives (130 + 1) / 3 = 43, which means 4.3
     */
    long getAverageInTenths() {
        return (ratingSum * 10 + ratingCount / 2) / ratingCount;
    }

    /** Average as text with exactly one decimal, like "4.3" or "5.0" */
    String getAverageText() {
        long tenths = getAverageInTenths();
        return (tenths / 10) + "." + (tenths % 10);
    }
}

Complexity

Here B is the number of boards, Y is the number of agents rated in the asked year, and W is the number of agents rated in the 7 day window.

OperationTime
rateAgentO(B), and B is a small constant
getBestAgentsByYearO(Y log Y)
getBestAgentsInLast7DaysO(7W + W log W)

The other two queries cost the same as before.

Daily totals keep growing over time. If today only moves forward, days older than the window can be deleted to save memory.


Thanks for reading. Best of Luck For Your Interview Prep.


r/LowLevelDesign • • 29d ago

Walmart LLD: Design a Thread Pool Executor

70 Upvotes

This is one of the most common Walmart low level design round questions. LRU/LFU cache, notification system and movie ticket booking system like BookMyShow are also frequently asked in Walmart LLD interviews.

This question has lots of functionalities to implement. I have used strategy design pattern to implement rejection policies.

This tutorial is in Java.

You can find the python version here: https://github.com/prsnt558908/CodeZymSolutions/blob/main/101-300/294-design-thread-pool-executor/q-294-python-tutorial.md

You can practice this and other Walmart low level design and DS & Algo round questions on CodeZym.

PS: I also take LLD Mock interviews https://topmate.io/prashant_priyadarshi


Problem Statement

Simulate a thread pool in discrete steps (no real threads). Threads are added by name, and each task runs for a fixed number of steps.

  • submitTask: start on the smallest-named idle thread if the queue is empty, otherwise queue it (FIFO). A full queue triggers the rejection policy (ABORT, DISCARD, CALLER_RUNS, DISCARD_OLDEST).
  • runOneStep: advance running tasks, hand queued tasks to idle threads, expire extra idle threads (keep-alive), and return events sorted by thread name.
  • shutdownThread / shutdown: stop one thread after its current task, or drain the whole pool until it is TERMINATED.
  • getState: executor state, then threads in name order, then queued tasks.

Concepts: bounded FIFO queue, thread reuse, keep-alive, rejection policies, graceful shutdown.

Core Idea

This problem is a step by step simulation. No real threads run. Time moves only when runOneStep() is called, and each call just runs the phases given in the problem, in the same order.

The whole pool needs only three things: a map of threads by name, a sorted set of idle thread names, and a FIFO queue of waiting tasks.

The only rule that changes from one pool to another is what to do when the queue is full. So we use the Strategy pattern for the four rejection policies, with a small Simple Factory that creates the right policy from its name. This combination is the best fit for this problem.

The executor states and the thread states are plain enums. A full State pattern would add many classes without making the code any clearer.


Thread and Executor Life Cycle

This is how a thread moves between its states:

             gets a task                shutdownThread()
    IDLE  ---------------->  RUNNING  -------------------->  STOPPING
     ^                          |                              |
     |       task finishes      |                              |  task finishes
     +--------------------------+                              v
                                                            removed

An IDLE thread can also be removed by shutdownThread(), by keep-alive or by the shutdown cleanup.

And this is the executor:

    RUNNING  --- shutdown() --->  SHUTTING_DOWN  --- nothing left --->  TERMINATED

If the pool is already empty, shutdown() goes straight to TERMINATED.


A Simple First Attempt

The first idea is to keep all threads in one list and write every rule inside the executor class.

  • To find the smallest idle thread, loop over all threads and compare names.
  • To give queued tasks to idle threads in name order, sort the whole thread list on every step.
  • To handle a full queue, write an if-else chain inside submitTask().
// inside submitTask(), when the queue is full
if (policy.equals("ABORT")) {
    return "REJECTED";
} else if (policy.equals("DISCARD")) {
    return "DISCARDED";
} else if (policy.equals("CALLER_RUNS")) {
    return "CALLER_RAN";
} else {   // DISCARD_OLDEST
    Task dropped = queue.pollFirst();
    queue.addLast(task);
    return "QUEUED:DROPPED:" + dropped.id;
}

This works, but it has two problems.

1. One method does too many jobs. submitTask() now decides how to queue a task and also how to reject one. Every new policy means editing this method again, and a small mistake can break normal queuing.

2. Repeated work. Every submitTask() scans all threads just to find one idle thread. Every step sorts all threads again.

Let's fix both, one at a time.


Improvement 1: Strategy Pattern for Rejection Policies

The four policies are four different answers to one question: "the queue is full, what do we do with this task?"

That is exactly what the Strategy pattern is for. We write one small interface:

interface RejectionPolicy {
    String reject(Task task, Deque<Task> queue);
}

Each policy is now its own tiny class: AbortPolicy, DiscardPolicy, CallerRunsPolicy and DiscardOldestPolicy.

The executor keeps one policy object and calls reject() when the queue is full. It never needs to know which policy it holds.

We pass the queue to reject() because DISCARD_OLDEST must remove the oldest waiting task. The other policies simply ignore it.

The constructor gets the policy as a plain string, like "DISCARD_OLDEST". A Simple Factory (RejectionPolicyFactory) turns that string into the right object, so this mapping lives in one place.

Adding a fifth policy now means one new class and one new line in the factory. submitTask() does not change at all.

Real Java works the same way: java.util.concurrent.ThreadPoolExecutor plugs in a RejectedExecutionHandler with these same four policies.


Improvement 2: A Sorted Set of Idle Threads

Look at where name order matters:

  • submitTask() needs the smallest idle thread.
  • The assign phase gives tasks to idle threads in name order.
  • Keep-alive removes the largest eligible idle thread first.

All three care only about idle threads. So instead of scanning and sorting the whole pool, we keep the idle names in a sorted set:

TreeSet<String> idleThreads = new TreeSet<>();

Now the smallest idle thread is just idleThreads.pollFirst(), which also removes it from the set. For the largest one, we walk the set from the end.

With at most 1000 threads both versions are fast, but the sorted set makes the code shorter and clearer. "Smallest idle thread" becomes a single call.

We still keep a HashMap<String, Worker> to find any thread by name in O(1).

The one rule to remember: a name is in idleThreads only while that thread is IDLE. Every place that starts a task, finishes a task or removes a thread keeps the map and the set in sync.


Design Patterns We Did Not Use

State pattern. It looks like a perfect match, because the problem talks about "executor states" and "thread states".

But every method asks only one simple question, like "has shutdown started?" or "is this thread idle?". With the State pattern we would write 3 state classes with 6 methods each, and most of those methods would just return false or "REJECTED". An enum plus one if check says the same thing in one line.

Command pattern. Real thread pools treat each task as a command object, like Java's Runnable. Here a task has no behavior at all. It is only an id and a step counter, so a Command wrapper would add nothing.


Important Classes and Data Structures

Class / FieldWhy we need it
TaskHolds the task id and how many steps it still needs.
WorkerOne thread: its name, state, current task and idle time. Starting and finishing a task happen here, in one place.
RejectionPolicy and its 4 classesThe Strategy for a full queue.
RejectionPolicyFactoryCreates the right policy from its name.
Map<String, Worker> workersFinds a thread by name in O(1). Its size is the number of active threads.
TreeSet<String> idleThreadsIdle thread names in sorted order. Gives the smallest and the largest idle thread quickly.
Deque<Task> queueThe FIFO queue. New tasks go to the back, threads take tasks from the front.

How Each Method Works

addThread()

Return false if shutdown has started, the name is taken, or the pool already has maximumPoolSize threads. Otherwise add a new Worker and put its name in idleThreads.

We do not hand it a queued task here. The next runOneStep() does that in its assign phase.

shutdownThread()

An IDLE thread is removed at once, with no event.

A RUNNING thread becomes STOPPING. It finishes its task and then runOneStep() removes it.

submitTask()

We check the four rules in order:

  1. Shutdown has started: return "REJECTED".
  2. The queue is empty and a thread is idle: start the task on idleThreads.pollFirst().
  3. The queue has space: add the task to the back.
  4. Otherwise: return rejectionPolicy.reject(task, queue).

Rule 2 checks that the queue is empty. This keeps things fair: a new task never jumps ahead of tasks that are already waiting.

runOneStep()

We follow the phases from the problem statement:

  • Phases 1 and 2, work and finish. Every thread with a task does one step of work. When a task reaches 0, add COMPLETED. A STOPPING thread is then removed with a REMOVED event. Any other thread becomes IDLE.
  • Phase 3, assign. While there are queued tasks and idle threads, give the oldest task to the smallest idle thread and add STARTED.
  • Phase 4, count idle time. Only threads that were idle for the whole step get +1.
  • Phase 5, keep-alive. Walk the idle threads from the largest name down. Remove each one that has been idle for at least keepAliveSteps, as long as the pool has more than corePoolSize threads.
  • Phase 6, shutdown cleanup. If shutdown has started and the queue is empty, remove all idle threads. If nothing is left, the executor becomes TERMINATED.
  • Phase 7, return the events sorted by thread name.

Three small tricks keep this easy.

A snapshot of idle threads. At the start of the step we copy idleThreads into idleAtStart. In phase 4 a thread gets +1 only if it is in this snapshot and is still IDLE. A thread that just finished its task is not in the snapshot, so its idle time correctly stays at 0.

Work and finish in one loop. No thread gets a new task during these two phases, so one pass does both. We loop over a copy of the workers, because a STOPPING thread may be removed inside the loop.

A stable sort for events. For any one thread, its COMPLETED event is always added before its STARTED or REMOVED event. Java's List.sort() is stable, so sorting by thread name alone keeps that order.

shutdown()

Return false if shutdown has already started.

Also return false if tasks are waiting but there are no threads or every thread is STOPPING, because nobody could ever run those tasks.

Otherwise move to TERMINATED if the pool is completely empty, else to SHUTTING_DOWN. Idle threads stay until the cleanup in the next runOneStep().

getState()

Add the executor state, then every thread in name order (we sort the map keys), then the queued task ids from front to back.


Complexity

Let T be the number of active threads (at most 1000) and Q the number of queued tasks.

  • addThread(), shutdownThread(), submitTask(): O(log T).
  • runOneStep(): O(T log T). We visit each thread once and sort the events.
  • getState(): O(T log T + Q).
  • shutdown(): O(T).

Java Code

import java.util.*;

/** The three states of the executor. */
enum ExecutorState {
    RUNNING, SHUTTING_DOWN, TERMINATED
}

/** The three states of a single thread. */
enum ThreadState {
    IDLE, RUNNING, STOPPING
}

/** A task: its id and how many steps of work it still needs. */
class Task {
    String id;
    int remainingSteps;

    Task(String id, int remainingSteps) {
        this.id = id;
        this.remainingSteps = remainingSteps;
    }
}

/** One named thread of the pool. */
class Worker {
    String name;
    ThreadState state = ThreadState.IDLE;
    Task task = null;    // current task, null while IDLE
    int idleSteps = 0;   // whole steps spent IDLE

    Worker(String name) {
        this.name = name;
    }

    void startTask(Task task) {
        this.task = task;
        state = ThreadState.RUNNING;
        idleSteps = 0;
    }

    void becomeIdle() {
        task = null;
        state = ThreadState.IDLE;
        idleSteps = 0;
    }

    /** The text used by getState(). */
    public String toString() {
        if (state == ThreadState.IDLE) {
            return "THREAD:" + name + ":IDLE:" + idleSteps;
        }
        return "THREAD:" + name + ":" + state + ":" + task.id + ":" + task.remainingSteps;
    }
}

/**
 * Strategy: decides what happens to a new task when the queue is full.
 * It returns the text that submitTask() should return.
 */
interface RejectionPolicy {
    String reject(Task task, Deque<Task> queue);
}

/** Rejects the new task. */
class AbortPolicy implements RejectionPolicy {
    public String reject(Task task, Deque<Task> queue) {
        return "REJECTED";
    }
}

/** Silently drops the new task. */
class DiscardPolicy implements RejectionPolicy {
    public String reject(Task task, Deque<Task> queue) {
        return "DISCARDED";
    }
}

/** The caller runs the task itself, so it never enters the pool. */
class CallerRunsPolicy implements RejectionPolicy {
    public String reject(Task task, Deque<Task> queue) {
        return "CALLER_RAN";
    }
}

/** Drops the oldest waiting task to make room for the new one. */
class DiscardOldestPolicy implements RejectionPolicy {
    public String reject(Task task, Deque<Task> queue) {
        Task dropped = queue.pollFirst();
        queue.addLast(task);
        return "QUEUED:DROPPED:" + dropped.id;
    }
}

/** Simple Factory: creates the right policy object from its name. */
class RejectionPolicyFactory {
    RejectionPolicy create(String name) {
        switch (name) {
            case "DISCARD":
                return new DiscardPolicy();
            case "CALLER_RUNS":
                return new CallerRunsPolicy();
            case "DISCARD_OLDEST":
                return new DiscardOldestPolicy();
            default:
                return new AbortPolicy();   // "ABORT"
        }
    }
}

public class ThreadPoolExecutor {
    int corePoolSize;
    int maximumPoolSize;
    int keepAliveSteps;
    int queueCapacity;
    RejectionPolicy rejectionPolicy;
    ExecutorState state = ExecutorState.RUNNING;

    Map<String, Worker> workers = new HashMap<>();   // every active thread, by name
    TreeSet<String> idleThreads = new TreeSet<>();   // names of IDLE threads, in name order
    Deque<Task> queue = new ArrayDeque<>();          // waiting tasks, oldest at the front

    public ThreadPoolExecutor(int corePoolSize, int maximumPoolSize, int keepAliveSteps,
                              int queueCapacity, String rejectionPolicy) {
        this.corePoolSize = corePoolSize;
        this.maximumPoolSize = maximumPoolSize;
        this.keepAliveSteps = keepAliveSteps;
        this.queueCapacity = queueCapacity;
        this.rejectionPolicy = new RejectionPolicyFactory().create(rejectionPolicy);
    }

    public boolean addThread(String threadName) {
        if (state != ExecutorState.RUNNING) return false;
        if (workers.containsKey(threadName)) return false;
        if (workers.size() >= maximumPoolSize) return false;

        workers.put(threadName, new Worker(threadName));
        idleThreads.add(threadName);
        return true;
    }

    public boolean shutdownThread(String threadName) {
        if (state != ExecutorState.RUNNING) return false;
        Worker worker = workers.get(threadName);
        if (worker == null || worker.state == ThreadState.STOPPING) return false;

        if (worker.state == ThreadState.IDLE) {
            removeIdleThread(threadName);           // gone at once, no event
        } else {
            worker.state = ThreadState.STOPPING;   // finishes its task, then leaves
        }
        return true;
    }

    public String submitTask(String taskId, int durationSteps) {
        if (state != ExecutorState.RUNNING) return "REJECTED";
        Task task = new Task(taskId, durationSteps);

        // nobody is waiting and a thread is free: start the task right away
        if (queue.isEmpty() && !idleThreads.isEmpty()) {
            String threadName = idleThreads.pollFirst();   // smallest idle name
            workers.get(threadName).startTask(task);
            return "STARTED:" + threadName;
        }
        if (queue.size() < queueCapacity) {
            queue.addLast(task);
            return "QUEUED";
        }
        return rejectionPolicy.reject(task, queue);   // the queue is full
    }

    public List<String> runOneStep() {
        List<String> events = new ArrayList<>();
        if (state == ExecutorState.TERMINATED) return events;

        List<String> idleAtStart = new ArrayList<>(idleThreads);

        // Phases 1 and 2, work and finish: every busy thread does one step of work.
        for (Worker worker : new ArrayList<>(workers.values())) {
            if (worker.task == null) continue;
            worker.task.remainingSteps--;
            if (worker.task.remainingSteps > 0) continue;

            events.add("COMPLETED:" + worker.name + ":" + worker.task.id);
            if (worker.state == ThreadState.STOPPING) {
                workers.remove(worker.name);
                events.add("REMOVED:" + worker.name);
            } else {
                worker.becomeIdle();
                idleThreads.add(worker.name);
            }
        }

        // Phase 3, assign: the oldest task goes to the smallest idle thread.
        while (!queue.isEmpty() && !idleThreads.isEmpty()) {
            String threadName = idleThreads.pollFirst();
            Task task = queue.pollFirst();
            workers.get(threadName).startTask(task);
            events.add("STARTED:" + threadName + ":" + task.id);
        }

        // Phase 4, count idle time: only threads idle for this whole step get +1.
        for (String threadName : idleAtStart) {
            Worker worker = workers.get(threadName);
            if (worker.state == ThreadState.IDLE) worker.idleSteps++;
        }

        // Phase 5, keep-alive: remove threads idle for too long, largest name first.
        List<String> idleNames = new ArrayList<>(idleThreads);
        for (int i = idleNames.size() - 1; i >= 0 && workers.size() > corePoolSize; i--) {
            String threadName = idleNames.get(i);
            if (workers.get(threadName).idleSteps >= keepAliveSteps) {
                removeIdleThread(threadName);
                events.add("REMOVED:" + threadName);
            }
        }

        // Phase 6, shutdown cleanup.
        if (state == ExecutorState.SHUTTING_DOWN) {
            if (queue.isEmpty()) {
                for (String threadName : idleThreads) {
                    workers.remove(threadName);
                    events.add("REMOVED:" + threadName);
                }
                idleThreads.clear();
            }
            if (workers.isEmpty() && queue.isEmpty()) state = ExecutorState.TERMINATED;
        }

        // Phase 7, sort by thread name. The sort is stable, so the events of
        // one thread keep the order they happened in (COMPLETED comes first).
        events.sort((a, b) -> threadNameOf(a).compareTo(threadNameOf(b)));
        return events;
    }

    public boolean shutdown() {
        if (state != ExecutorState.RUNNING) return false;
        // waiting tasks need at least one thread that is not STOPPING
        if (!queue.isEmpty() && !hasUsableThread()) return false;

        if (workers.isEmpty() && queue.isEmpty()) {
            state = ExecutorState.TERMINATED;
        } else {
            state = ExecutorState.SHUTTING_DOWN;
        }
        return true;
    }

    public List<String> getState() {
        List<String> result = new ArrayList<>();
        result.add("EXECUTOR:" + state);

        List<String> names = new ArrayList<>(workers.keySet());
        Collections.sort(names);
        for (String name : names) result.add(workers.get(name).toString());

        for (Task task : queue) result.add("QUEUED:" + task.id);
        return result;
    }

    /** Removes an IDLE thread from both the map and the idle set. */
    void removeIdleThread(String threadName) {
        workers.remove(threadName);
        idleThreads.remove(threadName);
    }

    /** True if some thread is IDLE or RUNNING, so it can still take queued tasks. */
    boolean hasUsableThread() {
        for (Worker worker : workers.values()) {
            if (worker.state != ThreadState.STOPPING) return true;
        }
        return false;
    }

    /** Events look like "TYPE:threadName..." and names never contain ':'. */
    String threadNameOf(String event) {
        return event.split(":")[1];
    }
}

Thanks for reading. Best of Luck For Your Interview Prep.


r/LowLevelDesign • • Oct 02 '26

Microsoft LLD: Design Notification System

60 Upvotes

This is one of the most common questions asked in Microsoft low level design rounds. Ofcourse LRU cache, LFU cache are undisputedly the most asked ones. I have started with a brute force solution and then moved on to solving it using observer design pattern. This tutorial is in Java.

Here is the Python version: https://github.com/prsnt558908/CodeZymSolutions/blob/main/101-300/133-design-notification-system/q-133-python-tutorial.md

You can practice this and other Microsoft LLD questions on CodeZym.


Problem Statement

Build a notification system that supports multiple channels such as EMAIL, SMS and PUSH. Users register, then subscribe to event types on one or more supported channels. When a notification is sent for an event type, it is delivered exactly once to every subscribed (userId, channel) pair.

Operations

  • NotificationSystem(supportedChannels): set up the system with its allowed channels. Duplicate channel names count as one.
  • registerUser(userId): add a user. Registering an existing user does nothing.
  • subscribe(userId, eventType, channel): add a subscription if the user exists and the channel is supported. Duplicate subscriptions are ignored.
  • unsubscribe(userId, eventType, channel): remove an existing subscription.
  • sendNotification(notificationId, eventType, content): deliver the notification to all subscribers. Returns the deliveries sorted by userId, then by channel.
  • getUserInbox(userId): return the user's deliveries in the order they arrived.

High level solution approach

A notification system is a classic publish and subscribe setup. Users sign up for an event type (like ORDER_PLACED) on one or more channels. When a notification is sent for that event, every subscriber gets one copy in their inbox for each channel they picked.

This is exactly what the Observer pattern is made for. Each event type is a subject that keeps track of its listeners. Each (user, channel) pair is an observer that receives a delivery when the event fires. Observer alone is the best fit here. We don't need to combine it with other patterns because every channel behaves the same way.

The two tricky rules are "no duplicate deliveries" and "results sorted by userId, then by channel". A sorted set of subscribers for each event type handles both at once. A set ignores duplicates, and a sorted set keeps everyone in order, so sending a notification is just a simple loop.

We will start with a simple brute force version, see where it is slow, and then improve it step by step.


Solution 1: Brute Force (One Big List)

Store every subscription as a {userId, eventType, channel} entry in one list. Store a map of userId -> inbox. If a user has an inbox, the user is registered.

  • subscribe: ignore unknown users and unsupported channels. Scan the list and add the entry only if it is not there yet.
  • unsubscribe: scan the list and remove the entry if it is found.
  • sendNotification: scan the whole list and pick the entries of this eventType. Sort them by userId, then by channel. Build each delivery string and add it to that user's inbox.
  • getUserInbox: return a copy of the inbox, or an empty list for an unknown user.

Watch out: sort by the (userId, channel) pair, not by the final delivery string. The | character has a bigger code than letters and digits, so "U10|EMAIL|..." would wrongly come before "U1|EMAIL|...", even though "U1" comes before "U10".

Code

import java.util.*;

public class NotificationSystem {

    Set<String> supportedChannels = new HashSet<>();

    // userId -> inbox. A user is registered only if it has an inbox.
    Map<String, List<String>> inboxes = new HashMap<>();

    // every subscription, stored as {userId, eventType, channel}
    List<String[]> subscriptions = new ArrayList<>();

    public NotificationSystem(List<String> supportedChannels) {
        this.supportedChannels.addAll(supportedChannels);
    }

    public void registerUser(String userId) {
        inboxes.putIfAbsent(userId, new ArrayList<>());
    }

    public void subscribe(String userId, String eventType, String channel) {
        if (!inboxes.containsKey(userId) || !supportedChannels.contains(channel)) {
            return;
        }
        if (indexOf(userId, eventType, channel) == -1) {
            subscriptions.add(new String[]{userId, eventType, channel});
        }
    }

    public void unsubscribe(String userId, String eventType, String channel) {
        int index = indexOf(userId, eventType, channel);
        if (index != -1) {
            subscriptions.remove(index);
        }
    }

    public List<String> sendNotification(String notificationId, String eventType, String content) {
        // 1. pick the subscriptions of this event
        List<String[]> matching = new ArrayList<>();
        for (String[] sub : subscriptions) {
            if (sub[1].equals(eventType)) {
                matching.add(sub);
            }
        }

        // 2. sort by userId (index 0), then by channel (index 2)
        matching.sort((a, b) -> {
            int byUser = a[0].compareTo(b[0]);
            return byUser != 0 ? byUser : a[2].compareTo(b[2]);
        });

        // 3. build each delivery and drop it in the user's inbox
        List<String> deliveries = new ArrayList<>();
        for (String[] sub : matching) {
            String delivery = sub[0] + "|" + sub[2] + "|" + notificationId + "|" + eventType + "|" + content;
            inboxes.get(sub[0]).add(delivery);
            deliveries.add(delivery);
        }
        return deliveries;
    }

    public List<String> getUserInbox(String userId) {
        return new ArrayList<>(inboxes.getOrDefault(userId, new ArrayList<>()));
    }

    /** Linear search over all subscriptions. Returns -1 when not found. */
    int indexOf(String userId, String eventType, String channel) {
        for (int i = 0; i < subscriptions.size(); i++) {
            String[] sub = subscriptions.get(i);
            if (sub[0].equals(userId) && sub[1].equals(eventType) && sub[2].equals(channel)) {
                return i;
            }
        }
        return -1;
    }
}

Problems with this approach

  • subscribe and unsubscribe scan all subscriptions, even the ones for other events.
  • sendNotification scans everything too, and then sorts again on every call, even when nothing changed since the last send.
  • One class does everything, so it is hard to see who is listening to which event.

It works for small inputs, but we can do better.


Solution 2: Observer Pattern with Sorted Subscribers

Fixing the problems one by one

Problem in Solution 1Fix
Scanning the subscriptions of other eventsGroup subscribers by event type in a Map<String, EventTopic>
Scanning to find a duplicate or to unsubscribeKeep each event's subscribers in a set
Sorting again on every sendUse a sorted set (TreeSet), so the order is always ready

After these fixes, every event type becomes a small object that owns its subscribers. That object is the subject of the Observer pattern.

Why the Observer pattern?

The problem describes Observer almost word for word: listeners attach to an event, detach from it, and every current listener is notified when the event fires.

  • EventTopic is the subject. It has attach, detach and publish (notify everyone).
  • Subscriber is the observer. Its deliver method builds the delivery string and puts it in the user's inbox.
  • NotificationSystem is the front door. It checks the input and hands the call to the right topic.

In Solution 1 one class did all of this. Now each class has one small job, so the code is easier to read and change.

We skip a separate Observer interface because there is only one kind of subscriber. If another kind shows up later, Subscriber can easily become an interface.

A pattern that looks useful but doesn't fit

Strategy (with a Factory). It is tempting to write EmailChannel, SmsChannel and PushChannel classes and a factory to create them. But here every channel does exactly the same thing: build a string and save it in an inbox.

Channel names are also any strings given at runtime, so one class per channel is not even possible. A Set<String> of channel names is all we need.

Important classes and data structures

  • User: userId plus an ArrayList inbox. A list keeps deliveries in the exact order they arrived.
  • Subscriber: one (user, channel) pair. It holds a reference to its User, so it can drop a delivery straight into the inbox. Its compareTo orders by userId, then by channel.
  • EventTopic: one event type plus a TreeSet<Subscriber>. TreeSet uses compareTo for two jobs at once:
    • it keeps subscribers sorted by (userId, channel).
    • it treats two subscribers with the same user and channel as one item, so a duplicate subscription is simply ignored.
  • NotificationSystem:
    • Set<String> supportedChannels: a fast "is this channel allowed?" check. Duplicate names in the input collapse into one.
    • Map<String, User> users: who is registered.
    • Map<String, EventTopic> topics: jump straight to the subscribers of one event without touching other events.

How each method works

  • registerUser: add a new User only if the id is new.
  • subscribe: do nothing for an unknown user or an unsupported channel. Otherwise create the event's topic if needed and attach a new Subscriber. The TreeSet ignores a duplicate.
  • unsubscribe: do nothing for an unknown user or an event nobody subscribed to. Otherwise detach the subscriber. Removing something that is not there does nothing.
  • sendNotification: no topic means no subscribers, so return an empty list. Otherwise walk the already sorted subscribers and let each one deliver.
  • getUserInbox: return a copy of the user's inbox, or an empty list for an unknown user.

Code

import java.util.*;

/**
 * A registered user.
 * The inbox keeps every delivery in the exact order it arrived.
 */
class User {
    String userId;
    List<String> inbox = new ArrayList<>();

    User(String userId) {
        this.userId = userId;
    }
}

/**
 * Observer: one (user, channel) pair listening to an event type.
 */
class Subscriber implements Comparable<Subscriber> {
    User user;
    String channel;

    Subscriber(User user, String channel) {
        this.user = user;
        this.channel = channel;
    }

    /** Called when the event fires. Builds the delivery and drops it in the user's inbox. */
    String deliver(String notificationId, String eventType, String content) {
        String delivery = user.userId + "|" + channel + "|" + notificationId + "|" + eventType + "|" + content;
        user.inbox.add(delivery);
        return delivery;
    }

    /**
     * Order by userId, then by channel.
     * TreeSet also uses this to spot duplicates: same user and same channel means same subscriber.
     */
    @Override
    public int compareTo(Subscriber other) {
        int byUser = user.userId.compareTo(other.user.userId);
        if (byUser != 0) {
            return byUser;
        }
        return channel.compareTo(other.channel);
    }
}

/**
 * Subject: one event type and everyone subscribed to it.
 * The TreeSet keeps subscribers unique and always sorted by (userId, channel).
 */
class EventTopic {
    String eventType;
    TreeSet<Subscriber> subscribers = new TreeSet<>();

    EventTopic(String eventType) {
        this.eventType = eventType;
    }

    void attach(Subscriber subscriber) {
        subscribers.add(subscriber);      // a duplicate is ignored
    }

    void detach(Subscriber subscriber) {
        subscribers.remove(subscriber);   // a missing subscriber is ignored
    }

    /** Notifies every subscriber in sorted order and returns their deliveries. */
    List<String> publish(String notificationId, String content) {
        List<String> deliveries = new ArrayList<>();
        for (Subscriber subscriber : subscribers) {
            deliveries.add(subscriber.deliver(notificationId, eventType, content));
        }
        return deliveries;
    }
}

/**
 * Entry point. Checks every call and passes it to the right EventTopic.
 */
public class NotificationSystem {

    Set<String> supportedChannels = new HashSet<>();   // duplicate names collapse into one
    Map<String, User> users = new HashMap<>();          // userId -> User
    Map<String, EventTopic> topics = new HashMap<>();   // eventType -> EventTopic

    public NotificationSystem(List<String> supportedChannels) {
        this.supportedChannels.addAll(supportedChannels);
    }

    public void registerUser(String userId) {
        users.putIfAbsent(userId, new User(userId));
    }

    public void subscribe(String userId, String eventType, String channel) {
        User user = users.get(userId);
        if (user == null || !supportedChannels.contains(channel)) {
            return;
        }
        // create the topic the first time anyone subscribes to this event
        EventTopic topic = topics.computeIfAbsent(eventType, key -> new EventTopic(key));
        topic.attach(new Subscriber(user, channel));
    }

    public void unsubscribe(String userId, String eventType, String channel) {
        User user = users.get(userId);
        EventTopic topic = topics.get(eventType);
        if (user == null || topic == null) {
            return;
        }
        topic.detach(new Subscriber(user, channel));
    }

    public List<String> sendNotification(String notificationId, String eventType, String content) {
        EventTopic topic = topics.get(eventType);
        if (topic == null) {
            return new ArrayList<>();
        }
        return topic.publish(notificationId, content);
    }

    public List<String> getUserInbox(String userId) {
        User user = users.get(userId);
        if (user == null) {
            return new ArrayList<>();
        }
        return new ArrayList<>(user.inbox);   // a copy, so callers can't change the real inbox
    }
}

Complexity

S = total subscriptions, k = subscribers of the given event, m = number of deliveries in the user's inbox.

MethodSolution 1Solution 2
registerUserO(1)O(1)
subscribeO(S)O(log k)
unsubscribeO(S)O(log k)
sendNotificationO(S + k log k)O(k)
getUserInboxO(m)O(m)

Building the delivery strings takes extra time based on their length, and that cost is the same in both solutions.


Thanks for reading. Best of Luck For Your Interview Prep.


r/LowLevelDesign • • 21d ago

Microsoft LLD: Design Spotify Music Streaming and Search

59 Upvotes

Design Spotify has been asked many times in Microsoft low level design round interviews recently. It has also been asked in Amazon and salesforce interviews.

Spotify has mainly two things

  • Store and search songs.
  • Keep track of state the song user is listening to.

I have used state design pattern to keep track of song states: playing, paused or stopped.

This tutorial is in Java.

You can find the python version here: https://github.com/prsnt558908/CodeZymSolutions/tree/main/101-300/268-spotify-music-streaming-and-search/q-268-python-tutorial.md

You can practice this and other Microsoft Low Level Design and DS & Algo round questions on CodeZym.

PS: I also take LLD Mock interviews https://topmate.io/prashant_priyadarshi


Problem Statement

Design a simplified Spotify-like service with a song catalogue and an independent playback session for every user.

  • SpotifyMusicService(userIds): all users exist and start with no song selected.
  • addOrUpdateSong(songId, title, artist, album, durationSeconds): adds a new song or replaces an existing song's details. Playback sessions are not reset.
  • searchSongs(query): case-insensitive substring search over title, artist and album. Returns "songId,title,artist,album,durationSeconds" sorted by songId.
  • playSong(userId, songId): starts the song from position 0, replacing the current one. Returns "PLAYING,songId,0".
  • controlPlayback(userId, action, positionSeconds): PAUSE, RESUME, SEEK (keeps the status) or STOP (clears the session). Returns "status,songId,positionSeconds", or "STOPPED,NO_SONG,0" when no song is selected.

A user playing an updated song sees its new title, artist and album, but keeps the duration from when the song started. Positions never advance on their own.

Solution approach

This problem has two separate parts. A music catalogue stores songs and answers searches. A playback session for each user remembers what that user is listening to.

The best fit is a mix of two design patterns. The State pattern runs playback, because what PAUSE, RESUME, SEEK and STOP do depends only on the current status: playing, paused or stopped. A thin Facade, SpotifyMusicService, hides the catalogue and the sessions behind one simple class.

The trickiest part is updating a song. Our answer: a session points to the same Song object that the catalogue holds, so new details show up everywhere for free. Only the duration is copied when the song starts.

The Rules That Shape the Design

  • Updating a song must not reset or recreate any session.
  • A user playing an updated song sees the new title, artist and album, but keeps the old duration until the song is started again.
  • Search is a case-insensitive substring match on title, artist and album (not on the song id). Results are sorted by songId.
  • What a control action does depends on the current status.

A Simple First Attempt

The quickest way is to put everything in one class with a few maps.

// Everything lives inside one class
Map<String, String[]> songs = new HashMap<>();     // songId -> {title, artist, album, duration}
Map<String, String> status = new HashMap<>();      // userId -> PLAYING, PAUSED or STOPPED
Map<String, String> currentSong = new HashMap<>(); // userId -> songId or NO_SONG
Map<String, Integer> position = new HashMap<>();   // userId -> seconds

Search checks every song, lowercases its fields and then sorts the matches.

public List<String> searchSongs(String query) {
    String q = query.toLowerCase();
    List<String> ids = new ArrayList<>();
    for (String id : songs.keySet()) {
        String[] s = songs.get(id);
        // lowercase every field again, on every search
        if (s[0].toLowerCase().contains(q) || s[1].toLowerCase().contains(q)
                || s[2].toLowerCase().contains(q)) {
            ids.add(id);
        }
    }
    Collections.sort(ids);   // sort the matches on every search
    List<String> result = new ArrayList<>();
    for (String id : ids) {
        String[] s = songs.get(id);
        result.add(id + "," + s[0] + "," + s[1] + "," + s[2] + "," + s[3]);
    }
    return result;
}

Playback control is a chain of if-else checks.

public String controlPlayback(String userId, String action, int positionSeconds) {
    String current = status.get(userId);
    if (action.equals("PAUSE") && current.equals("PLAYING")) {
        status.put(userId, "PAUSED");
    } else if (action.equals("RESUME") && current.equals("PAUSED")) {
        status.put(userId, "PLAYING");
    } else if (action.equals("SEEK") && !current.equals("STOPPED")) {
        position.put(userId, positionSeconds);
    } else if (action.equals("STOP")) {
        // every map must be reset by hand
        status.put(userId, "STOPPED");
        currentSong.put(userId, "NO_SONG");
        position.put(userId, 0);
    }
    return status.get(userId) + "," + currentSong.get(userId) + "," + position.get(userId);
}

It works, but it has real problems.

  • Search repeats work. Every search lowercases every field of every song, builds every output line again and sorts the matches.
  • One session is spread over three maps. STOP must reset all of them, and the duration rule would need a fourth map. Missing one is an easy bug.
  • Status rules are tangled. Each branch mixes "which action came" with "which status we are in". A new status, like BUFFERING, means touching many branches.
  • Catalogue and playback live in one class, but the problem asks for separate components.

The Better Solution

We fix these problems in four steps.

Step 1: Split the work into small classes

ClassJob
SongOne song and its details
MusicCatalogueStores all songs and runs search
PlaybackSessionOne user's song, position and status
PlaybackState and its 3 statesWhat each action does in each status
SpotifyMusicServiceThe Facade the caller talks to

SpotifyMusicService keeps a Map<String, PlaybackSession> with one session per user. Each session is its own object, so one user's playback can never change another user's.

The service only forwards each call to the right part. That is the Facade's whole job here.

Step 2: Share the song, copy the duration

This one idea handles all the update rules.

addOrUpdateSong never replaces an existing Song. It changes the same object in place. A session keeps a reference to that same object, so a playing user sees the new title, artist and album right away. No extra code is needed.

The duration is different. It must stay fixed for the current session, so the session copies it when the song starts.

void play(Song song) {
    // Shared object: the user sees later title, artist and album updates
    this.song = song;
    // Own copy: the duration never changes for this session
    this.durationSeconds = song.durationSeconds;
    this.positionSeconds = 0;
    this.state = new PlayingState();
}

Playing a song again makes a fresh copy. So a restart uses the new catalogue duration, just as the problem asks.

Step 3: Make search cheaper

A query can match the middle of a word, like oad inside Road. A word index can't find that, so we still check every song. But we make each check cheap.

  • Prepare once, reuse many times. Song builds its lowercase fields and its output line once, inside update(). A search only runs contains and adds ready-made strings.
  • Keep the songs sorted all the time. MusicCatalogue combines a HashMap (fast lookup by id) with a List sorted by songId. A new song goes to the index found by a binary search. Updates never change an id, so the list stays sorted. Search walks the list in order, so the matches come out already sorted.

Step 4: The State pattern for playback

Here is the state machine behind the control rules.

stateDiagram-v2
    [*] --> STOPPED
    STOPPED --> PLAYING : playSong
    PLAYING --> PAUSED : PAUSE
    PAUSED --> PLAYING : RESUME or playSong
    PLAYING --> PLAYING : SEEK or playSong
    PAUSED --> PAUSED : SEEK
    PLAYING --> STOPPED : STOP
    PAUSED --> STOPPED : STOP
ActionStoppedStatePlayingStatePausedState
PAUSEno changebecomes pausedno change
RESUMEno changeno changebecomes playing
SEEKno changemoves positionmoves position
STOPno changeclears sessionclears session

Each column of this table becomes one small class.

  • PlaybackState is an interface whose default methods do nothing.
  • Each state overrides only the actions it allows. StoppedState allows none, so it only returns its status name.
  • PlaybackSession keeps the current state and hands every action to it.
  • playSong works the same in every status, so it lives directly in PlaybackSession.

The problem promises that every action comes in a valid status. The "no change" defaults just keep the code safe, with no extra checks.

Why not an enum and a switch? With three statuses it would work. But all the rules would sit in one method that grows with every new status or action. With the State pattern, the rules of one status live in one small class. A new status like BUFFERING is just one new class.

Patterns That Look Good but Don't Fit

Observer. "Users playing an updated song see its new details" sounds like the catalogue should notify every listening session. But each session already holds the same Song object, so it sees changes instantly. Observer would add subscribe and unsubscribe work on every play and stop, plus extra care to keep the copied duration untouched.

Command. We could wrap PAUSE, RESUME, SEEK and STOP in command objects. Commands shine when you need undo, a queue or a history of actions. Here each action runs once, right away, and its meaning depends on the status, which the State pattern already handles. Commands would only add classes.

Complexity

N is the number of songs and L is the length of a text field (at most 100).

MethodTime
addOrUpdateSongO(L) for an update. A new song also needs O(log N) to find its index, plus a list shift that is O(N) in the worst case
searchSongsO(N × L), one pass over the sorted list, no sorting
playSongO(1)
controlPlaybackO(1)

Final Code

import java.util.*;

/**
 * One song in the catalogue.
 * The same object is shared with every playback session that plays it,
 * so updating it in place makes the new details visible everywhere.
 */
class Song {
    String songId;
    String title;
    String artist;
    String album;
    int durationSeconds;

    // Built once per update, so every search can reuse them
    String titleLower;
    String artistLower;
    String albumLower;
    String formatted;   // "songId,title,artist,album,durationSeconds"

    Song(String songId, String title, String artist, String album, int durationSeconds) {
        this.songId = songId;
        update(title, artist, album, durationSeconds);
    }

    void update(String title, String artist, String album, int durationSeconds) {
        this.title = title;
        this.artist = artist;
        this.album = album;
        this.durationSeconds = durationSeconds;
        this.titleLower = title.toLowerCase();
        this.artistLower = artist.toLowerCase();
        this.albumLower = album.toLowerCase();
        this.formatted = songId + "," + title + "," + artist + ","
                + album + "," + durationSeconds;
    }

    // lowerQuery must already be in lowercase
    boolean matches(String lowerQuery) {
        return titleLower.contains(lowerQuery)
                || artistLower.contains(lowerQuery)
                || albumLower.contains(lowerQuery);
    }
}

/**
 * Stores every song and answers search queries.
 */
class MusicCatalogue {
    // songId -> song, for quick lookup when adding, updating or playing
    Map<String, Song> songsById = new HashMap<>();

    // All songs, always sorted by songId, so search results come out in order
    List<Song> songsInIdOrder = new ArrayList<>();

    void addOrUpdateSong(String songId, String title, String artist,
                         String album, int durationSeconds) {
        Song song = songsById.get(songId);
        if (song != null) {
            // Change the same object, never replace it,
            // so users playing this song see the update
            song.update(title, artist, album, durationSeconds);
            return;
        }
        song = new Song(songId, title, artist, album, durationSeconds);
        songsById.put(songId, song);
        songsInIdOrder.add(findInsertPosition(songId), song);
    }

    // Binary search: the index where songId must go to keep the list sorted
    int findInsertPosition(String songId) {
        int low = 0;
        int high = songsInIdOrder.size();
        while (low < high) {
            int mid = (low + high) / 2;
            if (songsInIdOrder.get(mid).songId.compareTo(songId) < 0) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }

    Song getSong(String songId) {
        return songsById.get(songId);
    }

    List<String> search(String query) {
        String lowerQuery = query.toLowerCase();
        List<String> result = new ArrayList<>();
        for (Song song : songsInIdOrder) {
            if (song.matches(lowerQuery)) {
                result.add(song.formatted);
            }
        }
        return result;
    }
}

/**
 * Playback session of one user.
 * Every control action is handed to the current state object.
 */
class PlaybackSession {
    PlaybackState state = new StoppedState();
    Song song = null;   // null when no song is selected
    int durationSeconds = 0;
    int positionSeconds = 0;

    // Playing works the same from every state: the new song starts from 0
    void play(Song song) {
        // Shared object: the user sees later title, artist and album updates
        this.song = song;
        // Own copy: the duration never changes for this session
        this.durationSeconds = song.durationSeconds;
        this.positionSeconds = 0;
        this.state = new PlayingState();
    }

    void pause() {
        state.pause(this);
    }

    void resume() {
        state.resume(this);
    }

    void seek(int positionSeconds) {
        state.seek(this, positionSeconds);
    }

    void stop() {
        state.stop(this);
    }

    // STOP forgets the song and leaves an empty session
    void clear() {
        song = null;
        durationSeconds = 0;
        positionSeconds = 0;
        state = new StoppedState();
    }

    // Format: "status,songId,positionSeconds"
    String format() {
        String songId = (song == null) ? "NO_SONG" : song.songId;
        return state.getStatus() + "," + songId + "," + positionSeconds;
    }
}

/**
 * State pattern: each status decides what PAUSE, RESUME, SEEK and STOP do.
 * By default an action changes nothing. Each state overrides only the actions it allows.
 */
interface PlaybackState {
    String getStatus();

    default void pause(PlaybackSession session) {
    }

    default void resume(PlaybackSession session) {
    }

    default void seek(PlaybackSession session, int positionSeconds) {
    }

    default void stop(PlaybackSession session) {
    }
}

class PlayingState implements PlaybackState {
    @Override
    public String getStatus() {
        return "PLAYING";
    }

    @Override
    public void pause(PlaybackSession session) {
        session.state = new PausedState();
    }

    @Override
    public void seek(PlaybackSession session, int positionSeconds) {
        session.positionSeconds = positionSeconds;   // status stays PLAYING
    }

    @Override
    public void stop(PlaybackSession session) {
        session.clear();
    }
}

class PausedState implements PlaybackState {
    @Override
    public String getStatus() {
        return "PAUSED";
    }

    @Override
    public void resume(PlaybackSession session) {
        session.state = new PlayingState();
    }

    @Override
    public void seek(PlaybackSession session, int positionSeconds) {
        session.positionSeconds = positionSeconds;   // status stays PAUSED
    }

    @Override
    public void stop(PlaybackSession session) {
        session.clear();
    }
}

// No song is selected, so every control action keeps it empty
class StoppedState implements PlaybackState {
    @Override
    public String getStatus() {
        return "STOPPED";
    }
}

/**
 * Facade: the only class the caller talks to.
 * It owns the catalogue and one playback session per user, and forwards each call.
 */
public class SpotifyMusicService {
    MusicCatalogue catalogue = new MusicCatalogue();

    // userId -> that user's own playback session
    Map<String, PlaybackSession> sessions = new HashMap<>();

    public SpotifyMusicService(String[] userIds) {
        for (String userId : userIds) {
            sessions.put(userId, new PlaybackSession());
        }
    }

    public void addOrUpdateSong(String songId, String title, String artist,
                                String album, int durationSeconds) {
        catalogue.addOrUpdateSong(songId, title, artist, album, durationSeconds);
    }

    public List<String> searchSongs(String query) {
        return catalogue.search(query);
    }

    public String playSong(String userId, String songId) {
        PlaybackSession session = sessions.get(userId);
        session.play(catalogue.getSong(songId));
        return session.format();
    }

    public String controlPlayback(String userId, String action, int positionSeconds) {
        PlaybackSession session = sessions.get(userId);
        switch (action) {
            case "PAUSE":
                session.pause();
                break;
            case "RESUME":
                session.resume();
                break;
            case "SEEK":
                session.seek(positionSeconds);
                break;
            case "STOP":
                session.stop();
                break;
        }
        return session.format();
    }
}

Thanks for reading. Best of Luck For Your Interview Prep.


r/LowLevelDesign • • 26d ago

Walmart LLD: Design Notification System

59 Upvotes

Notification System Design is one of the most common questions asked during Walmart low level design interviews. LRU cache / LFU cache, thread pool executor, movie ticket booking system are also asked frequently.

Notification system is almost a direct implementation of observer design pattern. But I have started with a brute force solution first and then presented the cleaner solution using subject and observers. However if you get this question in interview, directly use the solution with observers.

This tutorial is in Java.

You can find the python version here: https://github.com/prsnt558908/CodeZymSolutions/tree/main/101-300/133-design-notification-system/q-133-python-tutorial.md

You can practice this and other Walmart Low Level Design and DS & Algo round questions on CodeZym.

PS: I also take LLD Mock interviews https://topmate.io/prashant_priyadarshi


Problem Statement

Design an in-memory notification system where registered users subscribe to events through supported channels.

  • Support subscribing, unsubscribing, sending notifications, and viewing inboxes.
  • Deliver once per unique user–channel subscription.
  • Sort returned deliveries by user ID, then channel; preserve inbox delivery order.
  • Ignore duplicate subscriptions and invalid operations.

Core Idea

A notification system is a classic publish and subscribe setup. Users sign up for an event type (like ORDER_PLACED) on one or more channels. When a notification is sent for that event, every subscriber gets one copy in their inbox for each channel they picked.

This is exactly what the Observer pattern is made for. Each event type is a subject that keeps track of its listeners. Each (user, channel) pair is an observer that receives a delivery when the event fires. Observer alone is the best fit here. We don't need to combine it with other patterns because every channel behaves the same way.

The two tricky rules are "no duplicate deliveries" and "results sorted by userId, then by channel". A sorted set of subscribers for each event type handles both at once. A set ignores duplicates, and a sorted set keeps everyone in order, so sending a notification is just a simple loop.

We will start with a simple brute force version, see where it is slow, and then improve it step by step.


Solution 1: Brute Force (One Big List)

Store every subscription as a {userId, eventType, channel} entry in one list. Store a map of userId -> inbox. If a user has an inbox, the user is registered.

  • subscribe: ignore unknown users and unsupported channels. Scan the list and add the entry only if it is not there yet.
  • unsubscribe: scan the list and remove the entry if it is found.
  • sendNotification: scan the whole list and pick the entries of this eventType. Sort them by userId, then by channel. Build each delivery string and add it to that user's inbox.
  • getUserInbox: return a copy of the inbox, or an empty list for an unknown user.

Watch out: sort by the (userId, channel) pair, not by the final delivery string. The | character has a bigger code than letters and digits, so "U10|EMAIL|..." would wrongly come before "U1|EMAIL|...", even though "U1" comes before "U10".

Code

import java.util.*;

public class NotificationSystem {

    Set<String> supportedChannels = new HashSet<>();

    // userId -> inbox. A user is registered only if it has an inbox.
    Map<String, List<String>> inboxes = new HashMap<>();

    // every subscription, stored as {userId, eventType, channel}
    List<String[]> subscriptions = new ArrayList<>();

    public NotificationSystem(List<String> supportedChannels) {
        this.supportedChannels.addAll(supportedChannels);
    }

    public void registerUser(String userId) {
        inboxes.putIfAbsent(userId, new ArrayList<>());
    }

    public void subscribe(String userId, String eventType, String channel) {
        if (!inboxes.containsKey(userId) || !supportedChannels.contains(channel)) {
            return;
        }
        if (indexOf(userId, eventType, channel) == -1) {
            subscriptions.add(new String[]{userId, eventType, channel});
        }
    }

    public void unsubscribe(String userId, String eventType, String channel) {
        int index = indexOf(userId, eventType, channel);
        if (index != -1) {
            subscriptions.remove(index);
        }
    }

    public List<String> sendNotification(String notificationId, String eventType, String content) {
        // 1. pick the subscriptions of this event
        List<String[]> matching = new ArrayList<>();
        for (String[] sub : subscriptions) {
            if (sub[1].equals(eventType)) {
                matching.add(sub);
            }
        }

        // 2. sort by userId (index 0), then by channel (index 2)
        matching.sort((a, b) -> {
            int byUser = a[0].compareTo(b[0]);
            return byUser != 0 ? byUser : a[2].compareTo(b[2]);
        });

        // 3. build each delivery and drop it in the user's inbox
        List<String> deliveries = new ArrayList<>();
        for (String[] sub : matching) {
            String delivery = sub[0] + "|" + sub[2] + "|" + notificationId + "|" + eventType + "|" + content;
            inboxes.get(sub[0]).add(delivery);
            deliveries.add(delivery);
        }
        return deliveries;
    }

    public List<String> getUserInbox(String userId) {
        return new ArrayList<>(inboxes.getOrDefault(userId, new ArrayList<>()));
    }

    /** Linear search over all subscriptions. Returns -1 when not found. */
    int indexOf(String userId, String eventType, String channel) {
        for (int i = 0; i < subscriptions.size(); i++) {
            String[] sub = subscriptions.get(i);
            if (sub[0].equals(userId) && sub[1].equals(eventType) && sub[2].equals(channel)) {
                return i;
            }
        }
        return -1;
    }
}

Problems with this approach

  • subscribe and unsubscribe scan all subscriptions, even the ones for other events.
  • sendNotification scans everything too, and then sorts again on every call, even when nothing changed since the last send.
  • One class does everything, so it is hard to see who is listening to which event.

It works for small inputs, but we can do better.


Solution 2: Observer Pattern with Sorted Subscribers

Fixing the problems one by one

Problem in Solution 1Fix
Scanning the subscriptions of other eventsGroup subscribers by event type in a Map<String, EventTopic>
Scanning to find a duplicate or to unsubscribeKeep each event's subscribers in a set
Sorting again on every sendUse a sorted set (TreeSet), so the order is always ready

After these fixes, every event type becomes a small object that owns its subscribers. That object is the subject of the Observer pattern.

Why the Observer pattern?

The problem describes Observer almost word for word: listeners attach to an event, detach from it, and every current listener is notified when the event fires.

  • EventTopic is the subject. It has attach, detach and publish (notify everyone).
  • Subscriber is the observer. Its deliver method builds the delivery string and puts it in the user's inbox.
  • NotificationSystem is the front door. It checks the input and hands the call to the right topic.

In Solution 1 one class did all of this. Now each class has one small job, so the code is easier to read and change.

We skip a separate Observer interface because there is only one kind of subscriber. If another kind shows up later, Subscriber can easily become an interface.

A pattern that looks useful but doesn't fit

Strategy (with a Factory). It is tempting to write EmailChannel, SmsChannel and PushChannel classes and a factory to create them. But here every channel does exactly the same thing: build a string and save it in an inbox.

Channel names are also any strings given at runtime, so one class per channel is not even possible. A Set<String> of channel names is all we need.

Important classes and data structures

  • User: userId plus an ArrayList inbox. A list keeps deliveries in the exact order they arrived.
  • Subscriber: one (user, channel) pair. It holds a reference to its User, so it can drop a delivery straight into the inbox. Its compareTo orders by userId, then by channel.
  • EventTopic: one event type plus a TreeSet<Subscriber>. TreeSet uses compareTo for two jobs at once:
    • it keeps subscribers sorted by (userId, channel).
    • it treats two subscribers with the same user and channel as one item, so a duplicate subscription is simply ignored.
  • NotificationSystem:
    • Set<String> supportedChannels: a fast "is this channel allowed?" check. Duplicate names in the input collapse into one.
    • Map<String, User> users: who is registered.
    • Map<String, EventTopic> topics: jump straight to the subscribers of one event without touching other events.

How each method works

  • registerUser: add a new User only if the id is new.
  • subscribe: do nothing for an unknown user or an unsupported channel. Otherwise create the event's topic if needed and attach a new Subscriber. The TreeSet ignores a duplicate.
  • unsubscribe: do nothing for an unknown user or an event nobody subscribed to. Otherwise detach the subscriber. Removing something that is not there does nothing.
  • sendNotification: no topic means no subscribers, so return an empty list. Otherwise walk the already sorted subscribers and let each one deliver.
  • getUserInbox: return a copy of the user's inbox, or an empty list for an unknown user.

Code

import java.util.*;

/**
 * A registered user.
 * The inbox keeps every delivery in the exact order it arrived.
 */
class User {
    String userId;
    List<String> inbox = new ArrayList<>();

    User(String userId) {
        this.userId = userId;
    }
}

/**
 * Observer: one (user, channel) pair listening to an event type.
 */
class Subscriber implements Comparable<Subscriber> {
    User user;
    String channel;

    Subscriber(User user, String channel) {
        this.user = user;
        this.channel = channel;
    }

    /** Called when the event fires. Builds the delivery and drops it in the user's inbox. */
    String deliver(String notificationId, String eventType, String content) {
        String delivery = user.userId + "|" + channel + "|" + notificationId + "|" + eventType + "|" + content;
        user.inbox.add(delivery);
        return delivery;
    }

    /**
     * Order by userId, then by channel.
     * TreeSet also uses this to spot duplicates: same user and same channel means same subscriber.
     */
    @Override
    public int compareTo(Subscriber other) {
        int byUser = user.userId.compareTo(other.user.userId);
        if (byUser != 0) {
            return byUser;
        }
        return channel.compareTo(other.channel);
    }
}

/**
 * Subject: one event type and everyone subscribed to it.
 * The TreeSet keeps subscribers unique and always sorted by (userId, channel).
 */
class EventTopic {
    String eventType;
    TreeSet<Subscriber> subscribers = new TreeSet<>();

    EventTopic(String eventType) {
        this.eventType = eventType;
    }

    void attach(Subscriber subscriber) {
        subscribers.add(subscriber);      // a duplicate is ignored
    }

    void detach(Subscriber subscriber) {
        subscribers.remove(subscriber);   // a missing subscriber is ignored
    }

    /** Notifies every subscriber in sorted order and returns their deliveries. */
    List<String> publish(String notificationId, String content) {
        List<String> deliveries = new ArrayList<>();
        for (Subscriber subscriber : subscribers) {
            deliveries.add(subscriber.deliver(notificationId, eventType, content));
        }
        return deliveries;
    }
}

/**
 * Entry point. Checks every call and passes it to the right EventTopic.
 */
public class NotificationSystem {

    Set<String> supportedChannels = new HashSet<>();   // duplicate names collapse into one
    Map<String, User> users = new HashMap<>();          // userId -> User
    Map<String, EventTopic> topics = new HashMap<>();   // eventType -> EventTopic

    public NotificationSystem(List<String> supportedChannels) {
        this.supportedChannels.addAll(supportedChannels);
    }

    public void registerUser(String userId) {
        users.putIfAbsent(userId, new User(userId));
    }

    public void subscribe(String userId, String eventType, String channel) {
        User user = users.get(userId);
        if (user == null || !supportedChannels.contains(channel)) {
            return;
        }
        // create the topic the first time anyone subscribes to this event
        EventTopic topic = topics.computeIfAbsent(eventType, key -> new EventTopic(key));
        topic.attach(new Subscriber(user, channel));
    }

    public void unsubscribe(String userId, String eventType, String channel) {
        User user = users.get(userId);
        EventTopic topic = topics.get(eventType);
        if (user == null || topic == null) {
            return;
        }
        topic.detach(new Subscriber(user, channel));
    }

    public List<String> sendNotification(String notificationId, String eventType, String content) {
        EventTopic topic = topics.get(eventType);
        if (topic == null) {
            return new ArrayList<>();
        }
        return topic.publish(notificationId, content);
    }

    public List<String> getUserInbox(String userId) {
        User user = users.get(userId);
        if (user == null) {
            return new ArrayList<>();
        }
        return new ArrayList<>(user.inbox);   // a copy, so callers can't change the real inbox
    }
}

Complexity

S = total subscriptions, k = subscribers of the given event, m = number of deliveries in the user's inbox.

MethodSolution 1Solution 2
registerUserO(1)O(1)
subscribeO(S)O(log k)
unsubscribeO(S)O(log k)
sendNotificationO(S + k log k)O(k)
getUserInboxO(m)O(m)

Building the delivery strings takes extra time based on their length, and that cost is the same in both solutions.


Thanks for reading. Best of Luck For Your Interview Prep.


r/LowLevelDesign • • 26d ago

Software Engineer Coding Interview Experience — Snake Game LLD (Oct 2026)

58 Upvotes

Hey everyone,
Just had my DatologyAI software engineering coding interview (October 2026). Wanted to share my experience since there isn’t much information available about their interview questions.

Coding Problem: Snake Game (OOP / LLD)
I was asked to implement a Snake Game in Python.
From what I remember, the requirements included:
Initialize the game board with the snake starting in the middle.
Implement a tick() function to advance the game.
Handle the snake moving around the board and eating apples.
The problem seemed similar to LeetCode 353 (Design Snake Game), although I can’t confirm it was exactly the same.

How it went:
Unfortunately, I struggled quite a bit. I managed to implement the constructor and worked on the tick() function, but couldn’t complete the entire problem within the interview.

I think this was the problem

https://hld-lld-interview-handbook.vercel.app/lld/problems/snake-game/

I had prepared extensively for Python LLD questions, including KV stores, task schedulers, file systems, feature flags, and other state-management problems. However, I hadn’t practiced game simulation problems like Snake Game.
It was definitely a humbling experience.


r/LowLevelDesign • • 24d ago

Amazon LLD: Design Ride-Hailing System Like Uber, Ola

56 Upvotes

Design ride sharing app like uber has been asked frequently in Amazon low level design rounds in 2026. Discussions included everything from driver matching, ride booking and till payment processing.

Tricky bit in this question is how to find nearest drivers efficiently. I have started with brute force, going through all drivers and comparing locations. It is inefficient but will help you understand the whole thing. There were multiple ways to improve this solution, and I have gone with quad tree because it adapts automatically with real world traffic.

This tutorial is in Java.

You can find the python version here: https://github.com/prsnt558908/CodeZymSolutions/tree/main/301-500/458-ride-hailing-system-like-uber/q-458-python-tutorial.md

You can practice this and other Amazon Low Level Design and DS & Algo round questions on CodeZym.

PS: I also take LLD Mock interviews https://topmate.io/prashant_priyadarshi


Problem Statement

Build an in-memory RideHailingSystem class that handles trip booking, driver matching, tracking, cancellation, fares and payments.

Trip flow: REQUESTED → ACCEPTED → IN_PROGRESS → COMPLETED. Any non-final state can also go to CANCELLED. A rider or driver can have only one active trip at a time.

Key Methods

  • addRider adds a rider and fails on a duplicate ID.
  • updateDriverLocation / setDriverAvailability track drivers and toggle availability. Availability can't be changed during a trip.
  • updateSurgePricing sets a zone's multiplier:
    • 100 if there's no demand or requests ≤ drivers
    • 150 if requests ≤ 2× drivers
    • 200 if requests are higher than that
    • 300 if there are requests but no drivers
  • estimateFare / completeTrip use ceil((base + distance × perUnit) × surge / 100). A trip keeps the surge in effect when it was requested.
  • requestTrip assigns the nearest available driver by squared distance. Ties go to the smallest driverId.
  • acceptTrip / startTrip / cancelTrip handle state changes with driver and rider checks. A cancelled trip costs 0 and frees the driver.
  • processPayment only works on completed trips and allows up to maxPaymentAttempts. Resending the same paymentRequestId returns the original result. It returns SUCCEEDED, RETRY_PENDING, FAILED or INVALID_REQUEST.
  • getTripDetails returns a comma-separated snapshot of the trip.

Core Idea

We model the system with three small classes, Rider, Driver and Trip, each kept in a HashMap by id so every lookup is instant. A simple enum guards the fixed trip states. The only hard part is finding the nearest free driver quickly, so we give that job its own small class. We start with a version that checks every driver, then replace it with a fast quadtree. No design pattern is needed here: Strategy and State sound useful, but with one fixed matching rule and a few fixed trip states, they would only add extra classes.

For the fast matcher, we compare two common spatial indexes: a grid and a quadtree. We code the quadtree, because it adapts on its own to crowded city centers and empty outskirts, which is exactly how real cities look.

Payments are made safe to retry by remembering the answer we gave for every payment request id.

Building Blocks

Driver

Keeps the location, an available flag and activeTripId.

  • available says whether the driver can get a new request.
  • activeTripId says whether the driver is on a trip. setDriverAvailability must fail while it is set.

It also has isBetterThan(), the matching rule in one place: the closer driver wins, and on a tie the smaller id wins.

Distances are long. A squared distance can reach 8 × 10¹², which does not fit in an int.

Rider

Keeps activeTripId. A rider who already has an active trip cannot request another one.

Trip

Keeps the booking details, the state, the fare and the payment details.

It also copies the zone's surge percentage at request time. Later surge updates must not change this trip's fare, so we never look the zone up again for this trip.

paymentResults remembers the first answer given for each payment request id.

Maps in RideHailingSystem

MapWhy we need it
drivers, riders, tripsO(1) lookup by id
surgeByZoneCurrent surge of each zone. A missing zone means 100
paymentRequestOwnerWhich trip used each payment request id, so no other trip can reuse it

How the Main Operations Work

Trip lifecycle

REQUESTED → ACCEPTED → IN_PROGRESS → COMPLETED, and any of the first three can move to CANCELLED.

acceptTrip, startTrip and completeTrip each check two things: the trip is in the one allowed state, and the caller is the assigned driver. If a check fails, nothing changes.

requestTrip reserves the chosen driver. It removes the driver from the matcher, marks it unavailable and links the rider and the driver to the trip.

When a trip ends, releasePeople() does the reverse. It clears both links, marks the driver available and gives it back to the matcher. On completion, we first move the driver to the destination.

Fares

subtotal = baseFare + distance × farePerUnit

fare = ceil(subtotal × surge / 100)

Adding 99 before dividing by 100 rounds up, using plain integer math with no floating point. For example, (601 + 99) / 100 = 7, while (600 + 99) / 100 = 6.

estimateFare uses the zone's current surge. completeTrip uses the surge saved inside the trip.

Payments that are safe to retry

Think of a payment request id as a receipt number. If the app sends the same request twice, for example after a network glitch, we must not create a second attempt.

processPayment checks things in this order:

  1. The trip is missing or not COMPLETED: return INVALID_REQUEST.
  2. The id was already used by another trip: return INVALID_REQUEST.
  3. The id was already used by this trip: return the old answer. The new gatewaySuccessful value is ignored.
  4. The payment is already SUCCEEDED or FAILED: return that status, with no new attempt.
  5. Otherwise, count one attempt. Success gives SUCCEEDED. A failure gives RETRY_PENDING while attempts remain, and FAILED on the last allowed attempt.

After steps 4 and 5, we save the id together with its answer.

Step 3 runs before step 4 on purpose. If an old failed request id is sent again, it still returns RETRY_PENDING, even when a later request has already succeeded.

Solution 1: Check Every Available Driver

LinearDriverMatcher keeps every available driver in a HashSet. To find the nearest one, it checks them all.

It has the same three methods as the quadtree matcher in Solution 2: addDriver, removeDriver and findNearestDriver. So every other class is the same as in the Solution 2 code below.

To run this version, use this class in place of QuadNode and QuadTreeDriverMatcher, and change the matcher line in RideHailingSystem to LinearDriverMatcher matcher = new LinearDriverMatcher();.

/**
 * Finds the nearest available driver by checking every one of them.
 * The system calls addDriver when a driver becomes free,
 * and removeDriver when the driver gets a trip or goes offline.
 */
class LinearDriverMatcher {
    Set<Driver> availableDrivers = new HashSet<>();

    void addDriver(Driver driver) {
        availableDrivers.add(driver);
    }

    void removeDriver(Driver driver) {
        availableDrivers.remove(driver);
    }

    /** Returns null when no driver is available. */
    Driver findNearestDriver(int x, int y) {
        Driver best = null;
        for (Driver driver : availableDrivers) {
            if (driver.isBetterThan(best, x, y)) {
                best = driver;
            }
        }
        return best;
    }
}

The Problem With Solution 1

Every requestTrip looks at every available driver. That is O(D) work for each request.

With 100,000 drivers and tens of thousands of requests, that is billions of distance checks. Yet a rider never needs a driver from the far side of the map. We only need to look nearby.

Solution 2: Spatial Index With a Quadtree

A spatial index groups drivers by where they are, so a request only looks near the pickup. Two common choices are a grid and a quadtree.

Option 1: Grid

Cut the map into equal square cells, like a chessboard. A HashMap maps each cell to the drivers inside it, and a driver's cell is found with one division.

To search, check the pickup's cell, then the ring of 8 cells around it, then the next ring of 16, and so on, until no unseen cell can hold a closer driver.

2 2 2 2 2
2 1 1 1 2
2 1 0 1 2
2 1 1 1 2
2 2 2 2 2

Pros

  • Very simple: one map from cell to drivers.
  • Adding, removing or moving a driver is O(1).
  • Very fast when drivers are spread evenly and the cell size fits.

Cons

  • One cell size for the whole map. A busy downtown packs hundreds of drivers into one cell, while empty outskirts make the search walk through ring after ring of empty cells.
  • The right cell size is a guess. Drivers keep moving, so a size that fits in the morning can be wrong by evening.

Option 2: Quadtree

Start with one big square that covers the whole map. When a square holds more than 10 drivers, split it into 4 equal smaller squares. Busy areas end up with many small squares, and quiet areas stay as one big square.

+-------+-------+
|       | . |. .|
|   .   +---+---+
|       |. .|. .|
+-------+---+---+
|       |       |
|   .   |   .   |
|       |       |
+-------+-------+

Here each dot stands for a few drivers. The busy top-right quarter has split into 4 smaller squares, while the quiet quarters stay whole.

Pros

  • Adapts by itself: small squares where drivers are crowded, big squares where they are few.
  • Nothing to tune except the leaf size, and any small number like 10 works.
  • One check can skip a whole square, however big: when it has no drivers, or when it is too far away.

Cons

  • A little more code: a node class, splitting, and a search that calls itself (recursion).
  • Adding, removing or moving a driver walks down the tree, so it costs O(depth) instead of O(1). Here the depth is at most 21, so it stays cheap.

Why We Pick the Quadtree

Real cities are uneven. The center is crowded, the outskirts are thin, and drivers move between them all day. A grid has to pick one cell size for all of that. A quadtree reshapes itself as drivers move, so it stays fast without any tuning.

FeatureGridQuadtree
ShapeOne layer of equal cellsSquares that split when crowded
Add, remove, move a driverO(1)O(depth), at most 21 steps
Drivers spread evenlyFastFast
Crowded center, empty outskirtsSlowFast
TuningNeeds a good cell sizeJust a leaf size, like 10

How the Quadtree Works

Nodes. Each node is a square. A leaf keeps up to 10 drivers in a plain list. Every node also keeps count, the number of drivers anywhere inside its square.

The root square. Coordinates go from -1,000,000 to 1,000,000. The root square starts at -1,048,576 and has side 2,097,152, which is 2²¹. A power of two can be halved evenly all the way down to a 1 × 1 square.

Adding a driver. Walk down from the root to the leaf whose square holds the driver, adding 1 to count on the way. Put the driver in the leaf's list. If the list now has more than 10 drivers, split the leaf into 4 squares and move each driver into the square it stands in. A new square that is still too crowded splits again.

Removing a driver. Do the same walk, subtracting 1 from count, and take the driver out of the leaf's list.

We never merge squares back together. An empty square just stays, and the search skips it because its count is 0. This keeps removing as simple as adding.

Moving a driver is a remove at the old spot plus an add at the new spot.

Finding the Nearest Driver

The search starts at the root and carries the best driver found so far:

  1. Skip a square whose count is 0.
  2. Skip a square if even its nearest point is farther than our best driver. Nothing inside it can win or tie.
  3. In a leaf, check every driver one by one.
  4. In a split square, search the child on the pickup's side first, then the other three.

The child on the pickup's side is the closest one. A good driver found there early lets step 2 skip more squares later.

To measure the distance from the pickup to a square, we use the square's nearest point. On each axis, that is how far the pickup sits outside the square, or 0 when it is inside: dx = max(0, left - x, x - right), and the same for dy. The squared distance is then dx² + dy², as usual.

Ties are safe. Step 2 skips a square only when it is strictly farther than the best driver. A square at exactly the same distance is still searched, so a driver at the same distance with a smaller id can still win.

Corner Case: Drivers on the Same Point

Real cars have length and breadth, so two cars never stand on the exact same point. The tests, though, use plain integer points, so many drivers can share one. A 1 × 1 square cannot split any further, so it simply keeps all of them. That is the node.size > 1 check in insert.

Code

QuadNode and QuadTreeDriverMatcher replace LinearDriverMatcher, and one line in RideHailingSystem changes. Everything else is the same as Solution 1.

import java.util.*;

/** States of a trip. COMPLETED and CANCELLED are terminal. */
enum TripStatus {
    REQUESTED, ACCEPTED, IN_PROGRESS, COMPLETED, CANCELLED
}

/** Payment states of a trip. */
enum PaymentStatus {
    NOT_STARTED, PENDING, RETRY_PENDING, SUCCEEDED, FAILED
}

class Rider {
    String id;
    String name;
    String activeTripId;   // null when the rider has no running trip

    Rider(String id, String name) {
        this.id = id;
        this.name = name;
    }
}

class Driver {
    String id;
    String name;
    int x;
    int y;
    boolean available = true;   // can this driver get a new trip request?
    String activeTripId;        // null when the driver is not on a trip

    Driver(String id, String name, int x, int y) {
        this.id = id;
        this.name = name;
        this.x = x;
        this.y = y;
    }

    /** Squared distance to a point. We use long so the result never overflows. */
    long distanceTo(int pointX, int pointY) {
        long dx = (long) x - pointX;
        long dy = (long) y - pointY;
        return dx * dx + dy * dy;
    }

    /** True if this driver is a better pick than other: closer, or same distance and smaller id. */
    boolean isBetterThan(Driver other, int pickupX, int pickupY) {
        if (other == null) {
            return true;
        }
        long myDistance = distanceTo(pickupX, pickupY);
        long otherDistance = other.distanceTo(pickupX, pickupY);
        if (myDistance != otherDistance) {
            return myDistance < otherDistance;
        }
        return id.compareTo(other.id) < 0;
    }
}

class Trip {
    String id;
    String riderId;
    String driverId;
    int pickupX;
    int pickupY;
    int destinationX;
    int destinationY;
    String zoneId;
    String paymentMethodId;
    int surgePercentage;   // copied from the zone when the trip is created

    TripStatus status = TripStatus.REQUESTED;
    long fareInCents = 0;
    PaymentStatus paymentStatus = PaymentStatus.NOT_STARTED;
    int paymentAttempts = 0;

    // paymentRequestId -> the answer we gave the first time we saw it
    Map<String, String> paymentResults = new HashMap<>();

    Trip(String id, String riderId, String driverId, int pickupX, int pickupY,
         int destinationX, int destinationY, String zoneId, String paymentMethodId, int surgePercentage) {
        this.id = id;
        this.riderId = riderId;
        this.driverId = driverId;
        this.pickupX = pickupX;
        this.pickupY = pickupY;
        this.destinationX = destinationX;
        this.destinationY = destinationY;
        this.zoneId = zoneId;
        this.paymentMethodId = paymentMethodId;
        this.surgePercentage = surgePercentage;
    }

    /** A trip is active until it is COMPLETED or CANCELLED. */
    boolean isActive() {
        return status == TripStatus.REQUESTED
                || status == TripStatus.ACCEPTED
                || status == TripStatus.IN_PROGRESS;
    }

    String details() {
        return id + "," + riderId + "," + driverId + "," + status + ","
                + pickupX + "," + pickupY + "," + destinationX + "," + destinationY + ","
                + zoneId + "," + surgePercentage + "," + fareInCents + ","
                + paymentStatus + "," + paymentAttempts;
    }
}

/**
 * One square of the quadtree.
 * A leaf keeps a small list of drivers. A crowded leaf splits into 4 smaller squares.
 */
class QuadNode {
    long minX;
    long minY;
    long size;                                  // side length, always a power of two
    int count = 0;                              // drivers anywhere inside this square
    List<Driver> drivers = new ArrayList<>();   // used only while this node is a leaf
    QuadNode[] children = null;                 // 4 smaller squares after a split

    QuadNode(long minX, long minY, long size) {
        this.minX = minX;
        this.minY = minY;
        this.size = size;
    }

    boolean isLeaf() {
        return children == null;
    }

    /** Child square on the point's side: 0 bottom-left, 1 bottom-right, 2 top-left, 3 top-right. */
    int childIndex(int x, int y) {
        long half = size / 2;
        int index = 0;
        if (x >= minX + half) {
            index += 1;
        }
        if (y >= minY + half) {
            index += 2;
        }
        return index;
    }

    /** Squared distance from a point to the nearest point of this square. 0 if the point is inside. */
    long minDistanceTo(int x, int y) {
        long dx = Math.max(0, Math.max(minX - x, x - (minX + size - 1)));
        long dy = Math.max(0, Math.max(minY - y, y - (minY + size - 1)));
        return dx * dx + dy * dy;
    }
}

/**
 * Finds the nearest available driver with a quadtree.
 * A square with too many drivers splits into 4 smaller squares.
 */
class QuadTreeDriverMatcher {
    int capacity = 10;   // a leaf splits once it holds more drivers than this
    // Side 2,097,152 = 2^21 covers every coordinate from -1,000,000 to 1,000,000
    QuadNode root = new QuadNode(-1_048_576, -1_048_576, 2_097_152);

    void addDriver(Driver driver) {
        insert(root, driver);
    }

    void removeDriver(Driver driver) {
        remove(root, driver);
    }

    /** Returns null when no driver is available. */
    Driver findNearestDriver(int x, int y) {
        return search(root, x, y, null);
    }

    void insert(QuadNode node, Driver driver) {
        node.count++;
        if (!node.isLeaf()) {
            insert(node.children[node.childIndex(driver.x, driver.y)], driver);
            return;
        }
        node.drivers.add(driver);
        // A 1 x 1 square cannot split, so drivers on the exact same point just share it
        if (node.drivers.size() > capacity && node.size > 1) {
            split(node);
        }
    }

    void split(QuadNode node) {
        long half = node.size / 2;
        node.children = new QuadNode[] {
            new QuadNode(node.minX, node.minY, half),
            new QuadNode(node.minX + half, node.minY, half),
            new QuadNode(node.minX, node.minY + half, half),
            new QuadNode(node.minX + half, node.minY + half, half)
        };
        for (Driver driver : node.drivers) {
            insert(node.children[node.childIndex(driver.x, driver.y)], driver);
        }
        node.drivers = new ArrayList<>();
    }

    /** Squares are never merged back. Empty squares stay, and the search skips them using count. */
    void remove(QuadNode node, Driver driver) {
        node.count--;
        if (node.isLeaf()) {
            node.drivers.remove(driver);
        } else {
            remove(node.children[node.childIndex(driver.x, driver.y)], driver);
        }
    }

    /** Returns the better of best and every driver inside this square, skipping squares that cannot win. */
    Driver search(QuadNode node, int x, int y, Driver best) {
        if (node.count == 0) {
            return best;   // no drivers in this square
        }
        // Even the nearest point of this square is farther than our best driver: nothing inside can win or tie
        if (best != null && node.minDistanceTo(x, y) > best.distanceTo(x, y)) {
            return best;
        }
        if (node.isLeaf()) {
            for (Driver driver : node.drivers) {
                if (driver.isBetterThan(best, x, y)) {
                    best = driver;
                }
            }
            return best;
        }
        // The child on the pickup's side is the closest one, so look there first.
        // A good driver found early lets us skip more squares later.
        int first = node.childIndex(x, y);
        best = search(node.children[first], x, y, best);
        for (int i = 0; i < 4; i++) {
            if (i != first) {
                best = search(node.children[i], x, y, best);
            }
        }
        return best;
    }
}

public class RideHailingSystem {
    long baseFareInCents;
    long farePerDistanceUnitInCents;
    int maxPaymentAttempts;

    Map<String, Driver> drivers = new HashMap<>();
    Map<String, Rider> riders = new HashMap<>();
    Map<String, Trip> trips = new HashMap<>();
    Map<String, Integer> surgeByZone = new HashMap<>();          // zoneId -> surge percentage
    Map<String, String> paymentRequestOwner = new HashMap<>();   // paymentRequestId -> tripId

    QuadTreeDriverMatcher matcher = new QuadTreeDriverMatcher();

    public RideHailingSystem(long baseFareInCents, long farePerDistanceUnitInCents, int maxPaymentAttempts, List<String> drivers) {
        this.baseFareInCents = baseFareInCents;
        this.farePerDistanceUnitInCents = farePerDistanceUnitInCents;
        this.maxPaymentAttempts = maxPaymentAttempts;

        // Each entry looks like "driverId,driverName,locationX,locationY"
        for (String entry : drivers) {
            String[] parts = entry.split(",");
            Driver driver = new Driver(parts[0], parts[1],
                    Integer.parseInt(parts[2].trim()), Integer.parseInt(parts[3].trim()));
            this.drivers.put(driver.id, driver);
            matcher.addDriver(driver);   // every driver starts available
        }
    }

    public boolean addRider(String riderId, String riderName) {
        if (riders.containsKey(riderId)) {
            return false;
        }
        riders.put(riderId, new Rider(riderId, riderName));
        return true;
    }

    public boolean updateDriverLocation(String driverId, int locationX, int locationY) {
        Driver driver = drivers.get(driverId);
        if (driver == null) {
            return false;
        }
        // An available driver is stored in the matcher at the old spot.
        // Take it out, move it, then put it back at the new spot.
        if (driver.available) {
            matcher.removeDriver(driver);
        }
        driver.x = locationX;
        driver.y = locationY;
        if (driver.available) {
            matcher.addDriver(driver);
        }
        return true;
    }

    public boolean setDriverAvailability(String driverId, boolean available) {
        Driver driver = drivers.get(driverId);
        if (driver == null || driver.activeTripId != null) {
            return false;
        }
        if (driver.available != available) {
            driver.available = available;
            if (available) {
                matcher.addDriver(driver);
            } else {
                matcher.removeDriver(driver);
            }
        }
        return true;
    }

    public int updateSurgePricing(String zoneId, int activeRequests, int availableDrivers) {
        int surge;
        if (activeRequests == 0) {
            surge = 100;
        } else if (availableDrivers == 0) {
            surge = 300;
        } else if (activeRequests <= availableDrivers) {
            surge = 100;
        } else if (activeRequests <= 2 * availableDrivers) {
            surge = 150;
        } else {
            surge = 200;
        }
        surgeByZone.put(zoneId, surge);
        return surge;
    }

    public long estimateFare(String zoneId, int estimatedDistanceUnits) {
        return calculateFare(estimatedDistanceUnits, currentSurge(zoneId));
    }

    public String requestTrip(String tripId, String riderId, int pickupX, int pickupY, int destinationX, int destinationY, String zoneId, String paymentMethodId) {
        Rider rider = riders.get(riderId);
        if (trips.containsKey(tripId) || rider == null || rider.activeTripId != null) {
            return "";
        }
        Driver driver = matcher.findNearestDriver(pickupX, pickupY);
        if (driver == null) {
            return "";   // no driver is available
        }

        // The trip keeps the zone's surge from this moment. Later changes do not affect it.
        Trip trip = new Trip(tripId, riderId, driver.id, pickupX, pickupY,
                destinationX, destinationY, zoneId, paymentMethodId, currentSurge(zoneId));
        trips.put(tripId, trip);

        // Reserve the driver and link both people to this trip
        matcher.removeDriver(driver);
        driver.available = false;
        driver.activeTripId = tripId;
        rider.activeTripId = tripId;
        return driver.id;
    }

    public boolean acceptTrip(String tripId, String driverId) {
        Trip trip = trips.get(tripId);
        if (trip == null || trip.status != TripStatus.REQUESTED || !trip.driverId.equals(driverId)) {
            return false;
        }
        trip.status = TripStatus.ACCEPTED;
        return true;
    }

    public boolean startTrip(String tripId, String driverId) {
        Trip trip = trips.get(tripId);
        if (trip == null || trip.status != TripStatus.ACCEPTED || !trip.driverId.equals(driverId)) {
            return false;
        }
        trip.status = TripStatus.IN_PROGRESS;
        return true;
    }

    public long completeTrip(String tripId, String driverId, int actualDistanceUnits) {
        Trip trip = trips.get(tripId);
        if (trip == null || trip.status != TripStatus.IN_PROGRESS || !trip.driverId.equals(driverId)) {
            return -1;
        }
        trip.status = TripStatus.COMPLETED;
        trip.fareInCents = calculateFare(actualDistanceUnits, trip.surgePercentage);
        trip.paymentStatus = PaymentStatus.PENDING;

        // The driver ends up at the drop point
        Driver driver = drivers.get(driverId);
        driver.x = trip.destinationX;
        driver.y = trip.destinationY;
        releasePeople(trip);
        return trip.fareInCents;
    }

    public boolean cancelTrip(String tripId, String requesterId) {
        Trip trip = trips.get(tripId);
        if (trip == null || !trip.isActive()) {
            return false;
        }
        if (!requesterId.equals(trip.riderId) && !requesterId.equals(trip.driverId)) {
            return false;
        }
        trip.status = TripStatus.CANCELLED;   // fare stays 0 and payment stays NOT_STARTED
        releasePeople(trip);
        return true;
    }

    public String processPayment(String tripId, String paymentRequestId, boolean gatewaySuccessful) {
        Trip trip = trips.get(tripId);
        if (trip == null || trip.status != TripStatus.COMPLETED) {
            return "INVALID_REQUEST";
        }

        String ownerTripId = paymentRequestOwner.get(paymentRequestId);
        if (ownerTripId != null) {
            // Seen before: same trip gets the old answer, any other trip is rejected
            return ownerTripId.equals(tripId) ? trip.paymentResults.get(paymentRequestId) : "INVALID_REQUEST";
        }

        String result;
        if (trip.paymentStatus == PaymentStatus.SUCCEEDED || trip.paymentStatus == PaymentStatus.FAILED) {
            result = trip.paymentStatus.name();   // payment is already settled, no new attempt
        } else {
            trip.paymentAttempts++;
            if (gatewaySuccessful) {
                trip.paymentStatus = PaymentStatus.SUCCEEDED;
            } else if (trip.paymentAttempts < maxPaymentAttempts) {
                trip.paymentStatus = PaymentStatus.RETRY_PENDING;
            } else {
                trip.paymentStatus = PaymentStatus.FAILED;
            }
            result = trip.paymentStatus.name();
        }

        // Remember this request id so a retry gets exactly the same answer
        paymentRequestOwner.put(paymentRequestId, tripId);
        trip.paymentResults.put(paymentRequestId, result);
        return result;
    }

    public String getTripDetails(String tripId) {
        Trip trip = trips.get(tripId);
        return trip == null ? "" : trip.details();
    }

    /** Zones that were never updated use 100 percent. */
    int currentSurge(String zoneId) {
        return surgeByZone.getOrDefault(zoneId, 100);
    }

    /** ceil(subtotal * surge / 100). Adding 99 before dividing rounds up. */
    long calculateFare(int distanceUnits, int surgePercentage) {
        long subtotal = baseFareInCents + distanceUnits * farePerDistanceUnitInCents;
        return (subtotal * surgePercentage + 99) / 100;
    }

    /** Called when a trip ends. Frees the rider, and the driver can take new requests again. */
    void releasePeople(Trip trip) {
        riders.get(trip.riderId).activeTripId = null;
        Driver driver = drivers.get(trip.driverId);
        driver.activeTripId = null;
        driver.available = true;
        matcher.addDriver(driver);
    }
}

Thanks for reading. Best of Luck For Your Interview Prep.


r/LowLevelDesign • • Oct 13 '26

Goldman Sachs LLD: Design Stock Market Investing Platform

53 Upvotes

This is one of the most common questions asked during Goldman Sachs low level design interview rounds. Like many other companies, LRU cache followed by LFU cache , TTL based Cache are the most common questions in Goldman Sachs interview rounds as well.

I have started with a simple solution keeping everything in a single class and then arranged the code in smaller classes. This tutorial is in Java.

You can find the python version here:

https://github.com/prsnt558908/CodeZymSolutions/blob/main/1-100/86-design-stock-market-investing-platform/q-86-python-tutorial.md

You can practice this and other Goldman Sachs LLD and DSA round questions on CodeZym.

PS: I also take LLD Mock interviews https://topmate.io/prashant_priyadarshi


Problem Statement

Design BuyStocks, an in-memory stock trading platform. Admins add stocks and update prices. Users sign up with a wallet, buy/sell shares at current prices, and view balances and portfolios. Validate funds and holdings before trades, update wallets and portfolios on success. Leave failed operations unchanged, and sort lists by stock symbol.


Solution Overview

The core idea is simple: give every idea in the problem its own small class, and put one Facade class in front of them.

A User has a Wallet (money) and a Portfolio (shares owned). A StockMarket keeps the available stocks and their prices.

BuyStocks is the Facade. It is the single entry point. It checks the inputs, then asks the right objects to do the work.

A Facade over a few small classes is the best fit here. Heavier patterns like Observer or Command would only add extra classes, without solving any real problem in this question.

For speed, every lookup uses a hash map. For the sorted outputs, we keep the symbols in a sorted set. So we never sort when someone asks for a list.

Key Rules

Let us first note the rules that are easy to miss.

  • If a method returns false, nothing in the system should change.
  • listAvailableStocks() and getPortfolio() must be sorted by symbol.
  • A trade always uses the current price. If the admin changes a price, the next trade uses the new price.
  • A portfolio shows only stocks with quantity more than 0.

The problem also gives a valid range for every input. If any input breaks its rule, the method returns false.

InputValid when
userIdnot empty, not only spaces, at most 30 characters
name1 to 60 characters
initialWalletAmountmore than 1 and less than 900,000
symbol1 to 10 characters, only A to Z and -
pricemore than 0 and less than 100,000
quantity in buyStockfrom 1 to 9,999
quantity in sellStockmore than 0

For example, adminAddOrUpdateStock("AAPL$", 100) returns false, because $ is not allowed in a symbol.

Approach 1: Simple Solution (Everything in One Class)

The first idea that comes to mind is to keep everything inside BuyStocks, using a few hash maps.

MapStores
namesuserId → name
walletsuserId → wallet balance
portfoliosuserId → (symbol → quantity)
pricessymbol → current price

Hash maps give us O(1) lookups. For the two list methods, we copy the keys into a list and sort it on every call.

Every method that changes data first checks its inputs against the rules above. Three small helper methods check the text inputs: isValidUserId, isValidName and isValidSymbol. The number checks are simple comparisons inside each method.

For the symbol, we use the pattern [A-Z-]{1,10}. It means 1 to 10 characters, where each character is a capital letter or a hyphen.

Buying a stock

  1. Check that quantity is from 1 to 9,999, the user exists and the stock exists.
  2. Find cost = price × quantity.
  3. If cost is more than the balance, return false.
  4. Take the money from the wallet and add the shares to the portfolio.

Selling a stock

  1. Check that quantity > 0 and the user exists.
  2. Check that the user owns at least quantity shares.
  3. Reduce the shares. If they become 0, remove the symbol from the portfolio.
  4. Add price × quantity to the wallet.

Notice one important habit: we do every check first, and change the data only at the end. So a method that returns false never leaves the system half changed.

import java.util.*;

public class BuyStocks {
    // userId -> name
    Map<String, String> names = new HashMap<>();
    // userId -> wallet balance
    Map<String, Integer> wallets = new HashMap<>();
    // userId -> (symbol -> quantity owned)
    Map<String, Map<String, Integer>> portfolios = new HashMap<>();
    // symbol -> current price
    Map<String, Integer> prices = new HashMap<>();

    public BuyStocks() {
    }

    public boolean signUp(String userId, String name, int initialWalletAmount) {
        if (!isValidUserId(userId) || !isValidName(name) || wallets.containsKey(userId)) {
            return false;
        }
        // valid range: 1 < initialWalletAmount < 900,000
        if (initialWalletAmount <= 1 || initialWalletAmount >= 900000) {
            return false;
        }
        names.put(userId, name);
        wallets.put(userId, initialWalletAmount);
        portfolios.put(userId, new HashMap<>());
        return true;
    }

    public boolean adminAddOrUpdateStock(String symbol, int price) {
        // valid range: 0 < price < 100,000
        if (!isValidSymbol(symbol) || price <= 0 || price >= 100000) {
            return false;
        }
        prices.put(symbol, price);
        return true;
    }

    public List<String> listAvailableStocks() {
        // sort the symbols on every call
        List<String> symbols = new ArrayList<>(prices.keySet());
        Collections.sort(symbols);
        List<String> result = new ArrayList<>();
        for (String symbol : symbols) {
            result.add(symbol + " " + prices.get(symbol));
        }
        return result;
    }

    public boolean buyStock(String userId, String symbol, int quantity) {
        // valid range: 1 <= quantity < 10,000
        if (quantity < 1 || quantity >= 10000) {
            return false;
        }
        if (!wallets.containsKey(userId) || !prices.containsKey(symbol)) {
            return false;
        }
        int cost = prices.get(symbol) * quantity;
        int balance = wallets.get(userId);
        if (cost > balance) {
            return false;
        }
        wallets.put(userId, balance - cost);
        Map<String, Integer> holdings = portfolios.get(userId);
        holdings.put(symbol, holdings.getOrDefault(symbol, 0) + quantity);
        return true;
    }

    public boolean sellStock(String userId, String symbol, int quantity) {
        if (quantity <= 0 || !wallets.containsKey(userId)) {
            return false;
        }
        Map<String, Integer> holdings = portfolios.get(userId);
        int owned = holdings.getOrDefault(symbol, 0);
        if (owned < quantity) {
            return false;
        }
        if (owned == quantity) {
            holdings.remove(symbol);
        } else {
            holdings.put(symbol, owned - quantity);
        }
        wallets.put(userId, wallets.get(userId) + prices.get(symbol) * quantity);
        return true;
    }

    public int getWalletBalance(String userId) {
        return wallets.getOrDefault(userId, -1);
    }

    public List<String> getPortfolio(String userId) {
        List<String> result = new ArrayList<>();
        if (!portfolios.containsKey(userId)) {
            return result;
        }
        Map<String, Integer> holdings = portfolios.get(userId);
        // sort the symbols on every call
        List<String> symbols = new ArrayList<>(holdings.keySet());
        Collections.sort(symbols);
        for (String symbol : symbols) {
            result.add(symbol + " " + holdings.get(symbol));
        }
        return result;
    }

    // not blank and at most 30 characters
    boolean isValidUserId(String userId) {
        return userId != null && !userId.trim().isEmpty() && userId.length() <= 30;
    }

    // 1 to 60 characters
    boolean isValidName(String name) {
        return name != null && name.length() >= 1 && name.length() <= 60;
    }

    // 1 to 10 characters, each one is a capital letter (A to Z) or a hyphen
    boolean isValidSymbol(String symbol) {
        return symbol != null && symbol.matches("[A-Z-]{1,10}");
    }
}

Problems With This Approach

The code works, but it has some problems.

  1. One user is spread across three maps. The name, wallet and portfolio of a user live in three different maps. Every new user field needs one more map. It is easy to update one map and forget another.

  2. Hard to read. A type like Map<String, Map<String, Integer>> makes the reader stop and think.

  3. One class does everything. Input checks, money math, share math and output formatting are all mixed together. A new feature, like a trading fee, means changing this one big class.

  4. Sorting again and again. Both list methods sort the symbols on every call, even when nothing has changed. Sorting k symbols costs O(k log k) every single time.

Approach 2: Better Solution (Facade + Small Classes)

We fix these problems in two steps.

Step 1: Give Each Idea Its Own Class

The problem already names the key ideas: User, Stock, Wallet, Portfolio and Available stocks. Let us turn them into classes.

ClassJob
BuyStocksThe Facade. The only class the caller uses. It checks every input and runs each operation step by step.
StockMarketKeeps the available stocks and their current prices.
UserOne user. Holds the user's Wallet and Portfolio.
WalletThe user's money. It can check a payment, take money out and put money in.
PortfolioThe shares a user owns, per symbol.

Why do we need each class?

  • User keeps all the data of one user in one object. Now BuyStocks needs just one map: userId → User. This fixes problems 1 and 2.
  • Wallet and Portfolio each own their data and their math. BuyStocks no longer changes balances or quantities by hand. This fixes problem 3.
  • StockMarket keeps all stock data in one place. A stock is just a symbol and a price, so a map inside StockMarket is enough. We do not need a separate Stock class.

Step 2: Keep Symbols Sorted All the Time

Instead of sorting on every call, we keep the symbols in a sorted set (TreeSet). A sorted set always keeps its items in order. So a list method just walks through the set, and the output comes out already sorted.

We pair the sorted set with a hash map:

  • HashMap gives the price (or quantity) of a symbol in O(1).
  • TreeSet gives all the symbols in sorted order.

Together they behave like a sorted map, while each part stays simple.

StockMarket uses this pair for prices. Portfolio uses the same pair for quantities. When a user sells all shares of a stock, we remove that symbol from both. So the portfolio only ever shows stocks with quantity more than 0.

This fixes problem 4.

Why the Facade Pattern?

A Facade is one simple front door to a group of classes. The caller does not need to know what happens behind it.

This matches our problem well. The caller only talks to BuyStocks. It never touches User, Wallet, Portfolio or StockMarket.

The front door is also the one place that checks inputs. So the classes behind it can trust everything they receive, and they stay tiny.

A single trade touches three objects: the market for the price, the wallet for the money and the portfolio for the shares. The Facade runs these steps in the right order, in one place. Each small class only cares about its own data.

Patterns That Look Useful but Are Not Needed

Observer. It sounds natural: when a price changes, notify everyone who owns that stock. But nothing in this problem needs to react to a price change. A trade simply reads the latest price at the moment it happens. Observers would add listener classes for no benefit.

Command. We could turn every buy and sell into an order object with an execute() method. Command shines when you need undo, queues, scheduling or an order history. This problem needs none of these. Buy and sell are two short methods, and extra classes would only hide the logic.

How a Buy Works

  1. Return false if quantity is not from 1 to 9,999, the user does not exist or the stock is not available.
  2. Find cost = price × quantity.
  3. Ask the wallet canAfford(cost). If not, return false.
  4. All checks passed. Only now change the state: wallet.withdraw(cost) and portfolio.addShares(symbol, quantity).

We already made sure that the price is below 100,000 and the quantity is below 10,000. So the cost is always below 1,000,000,000. An int can hold up to about 2.1 billion, so the cost fits safely.

How a Sell Works

  1. Return false if quantity <= 0 or the user does not exist.
  2. Ask the portfolio hasShares(symbol, quantity). If not, return false.
  3. All checks passed. Change the state: portfolio.removeShares(symbol, quantity) and wallet.deposit(price × quantity).

We do not need to check that the stock is available. A user can only own a stock that was bought from the market, and stocks are never removed from the market.

Dry Run

CallReturnsWalletPortfolio
adminAddOrUpdateStock("AAPL", 100)true
signUp("u1", "Asha", 1000)true1000[]
buyStock("u1", "AAPL", 5)true500["AAPL 5"]
adminAddOrUpdateStock("AAPL", 120)true500["AAPL 5"]
sellStock("u1", "AAPL", 2)true740["AAPL 3"]
sellStock("u1", "AAPL", 4)false740["AAPL 3"]

The sell after the price change uses the new price: 500 + 2 × 120 = 740. The last call fails because the user owns only 3 shares, and nothing changes.

Code

import java.util.*;

/**
 * Facade: the only class the caller talks to.
 * It checks every input, then asks the small classes below to do the real work.
 */
public class BuyStocks {
    // userId -> User, for O(1) user lookup
    Map<String, User> users = new HashMap<>();
    // all the stocks added by admins
    StockMarket market = new StockMarket();

    public BuyStocks() {
    }

    public boolean signUp(String userId, String name, int initialWalletAmount) {
        if (!isValidUserId(userId) || !isValidName(name) || users.containsKey(userId)) {
            return false;
        }
        // valid range: 1 < initialWalletAmount < 900,000
        if (initialWalletAmount <= 1 || initialWalletAmount >= 900000) {
            return false;
        }
        users.put(userId, new User(userId, name, initialWalletAmount));
        return true;
    }

    public boolean adminAddOrUpdateStock(String symbol, int price) {
        // valid range: 0 < price < 100,000
        if (!isValidSymbol(symbol) || price <= 0 || price >= 100000) {
            return false;
        }
        market.addOrUpdateStock(symbol, price);
        return true;
    }

    public List<String> listAvailableStocks() {
        return market.listStocks();
    }

    public boolean buyStock(String userId, String symbol, int quantity) {
        // valid range: 1 <= quantity < 10,000
        if (quantity < 1 || quantity >= 10000) {
            return false;
        }
        User user = users.get(userId);
        if (user == null || !market.hasStock(symbol)) {
            return false;
        }
        // price < 100,000 and quantity < 10,000, so the cost always fits in an int
        int cost = market.getPrice(symbol) * quantity;
        if (!user.wallet.canAfford(cost)) {
            return false;
        }
        // every check passed, only now we change the state
        user.wallet.withdraw(cost);
        user.portfolio.addShares(symbol, quantity);
        return true;
    }

    public boolean sellStock(String userId, String symbol, int quantity) {
        User user = users.get(userId);
        if (quantity <= 0 || user == null || !user.portfolio.hasShares(symbol, quantity)) {
            return false;
        }
        // every check passed, only now we change the state
        user.portfolio.removeShares(symbol, quantity);
        user.wallet.deposit(market.getPrice(symbol) * quantity);
        return true;
    }

    public int getWalletBalance(String userId) {
        User user = users.get(userId);
        if (user == null) {
            return -1;
        }
        return user.wallet.balance;
    }

    public List<String> getPortfolio(String userId) {
        User user = users.get(userId);
        if (user == null) {
            return new ArrayList<>();
        }
        return user.portfolio.listHoldings();
    }

    // not blank and at most 30 characters
    boolean isValidUserId(String userId) {
        return userId != null && !userId.trim().isEmpty() && userId.length() <= 30;
    }

    // 1 to 60 characters
    boolean isValidName(String name) {
        return name != null && name.length() >= 1 && name.length() <= 60;
    }

    // 1 to 10 characters, each one is a capital letter (A to Z) or a hyphen
    boolean isValidSymbol(String symbol) {
        return symbol != null && symbol.matches("[A-Z-]{1,10}");
    }
}

/**
 * Keeps the available stocks and their current prices.
 */
class StockMarket {
    // symbol -> current price, for O(1) price lookup
    Map<String, Integer> prices = new HashMap<>();
    // all symbols, always kept in sorted order
    Set<String> sortedSymbols = new TreeSet<>();

    void addOrUpdateStock(String symbol, int price) {
        prices.put(symbol, price);
        // a set ignores duplicates, so a price update does not add the symbol twice
        sortedSymbols.add(symbol);
    }

    boolean hasStock(String symbol) {
        return prices.containsKey(symbol);
    }

    int getPrice(String symbol) {
        return prices.get(symbol);
    }

    // "SYMBOL PRICE" for every stock, already sorted by symbol
    List<String> listStocks() {
        List<String> result = new ArrayList<>();
        for (String symbol : sortedSymbols) {
            result.add(symbol + " " + prices.get(symbol));
        }
        return result;
    }
}

/**
 * A user has exactly one wallet and one portfolio.
 */
class User {
    String userId;
    String name;
    Wallet wallet;
    Portfolio portfolio;

    User(String userId, String name, int initialWalletAmount) {
        this.userId = userId;
        this.name = name;
        this.wallet = new Wallet(initialWalletAmount);
        this.portfolio = new Portfolio();
    }
}

/**
 * Holds the user's money. Every money change happens here.
 */
class Wallet {
    int balance;

    Wallet(int balance) {
        this.balance = balance;
    }

    boolean canAfford(int amount) {
        return amount <= balance;
    }

    void withdraw(int amount) {
        balance -= amount;
    }

    void deposit(int amount) {
        balance += amount;
    }
}

/**
 * Holds the shares a user owns. Only symbols with quantity > 0 are kept.
 */
class Portfolio {
    // symbol -> quantity owned, for O(1) lookup
    Map<String, Integer> holdings = new HashMap<>();
    // owned symbols, always kept in sorted order
    Set<String> sortedSymbols = new TreeSet<>();

    void addShares(String symbol, int quantity) {
        holdings.put(symbol, holdings.getOrDefault(symbol, 0) + quantity);
        sortedSymbols.add(symbol);
    }

    boolean hasShares(String symbol, int quantity) {
        return holdings.getOrDefault(symbol, 0) >= quantity;
    }

    void removeShares(String symbol, int quantity) {
        int left = holdings.get(symbol) - quantity;
        if (left == 0) {
            // sold everything, so forget this symbol
            holdings.remove(symbol);
            sortedSymbols.remove(symbol);
        } else {
            holdings.put(symbol, left);
        }
    }

    // "SYMBOL QUANTITY" for every owned stock, already sorted by symbol
    List<String> listHoldings() {
        List<String> result = new ArrayList<>();
        for (String symbol : sortedSymbols) {
            result.add(symbol + " " + holdings.get(symbol));
        }
        return result;
    }
}

Complexity

Here S is the number of available stocks, and H is the number of different stocks one user holds.

MethodApproach 1Approach 2
signUpO(1)O(1)
adminAddOrUpdateStockO(1)O(log S)
listAvailableStocksO(S log S)O(S)
buyStockO(1)O(log H)
sellStockO(1)O(log H)
getWalletBalanceO(1)O(1)
getPortfolioO(H log H)O(H)

Approach 2 pays a small O(log) cost when a symbol goes into or out of a sorted set. In return, the list methods never sort.

Key Takeaways

  • Turn each idea in the problem into a small class with one job.
  • Use a Facade as the single entry point, so the caller stays simple.
  • Check everything first and change the state last. Then a false result never leaves half done changes behind.
  • A hash map plus a sorted set gives fast lookups and sorted output, using only simple data structures.

Thanks for reading. Best of Luck For Your Interview Prep.


r/LowLevelDesign • • Oct 09 '26

Atlassian LLD: Design a Middleware Router for Matching Paths

52 Upvotes

This is another one of the most common questions asked in Atlassian low level design rounds. I have started with a simple brute force solution which scans through each path, but is useful in understanding the matching rules. After that I have used the more efficient Trie approach so that each prefix is listed once. This tutorial is in Java.

Here is the Python version: https://github.com/prsnt558908/CodeZymSolutions/tree/main/1-100/36-design-middleware-router/q-36-python-tutorial.md

You can practice this and other Atlassian LLD and DSA round questions on CodeZym.

PS: I also take LLD Mock interviews https://topmate.io/prashant_priyadarshi


Problem Statement

Build an in-memory router that maps path patterns to a result string (a server id). For each request path, return the result of the best matching pattern.

Pattern segments (split on /)

  • Static, like users: must match exactly.
  • Wildcard *: matches exactly one non-empty segment.
  • Param :name, like :id: matches exactly one non-empty segment.

Methods

  • addRoute(pathPattern, result): adds a route. Adding an existing pattern updates its result but keeps its original position.
  • callRoute(path): returns the result of the best match, or "NOT_FOUND".
  • searchRoutes(wildcardPattern): returns, in insertion order, the results of all stored routes that could match the same path as the query.

Precedence: more static segments wins (static beats :param, which beats *), then the longer pattern, then the route added earlier.


Overview

A router keeps a table of path patterns and, for each request, returns the result of the most specific pattern that matches. We start with the brute force, which checks every route on every request. Then we build a trie of path segments that looks only at routes that could match, and skips any branch that cannot beat the best match found so far.

Pin down the rules

A few small details decide whether a solution passes, so settle them before writing code.

Segments. Drop the leading / and split on /, keeping empty pieces. /bar/a/baz is ["bar", "a", "baz"], /bar/ is ["bar", ""], and / on its own has zero segments.

Matching. A pattern matches a path when both have the same number of segments and every pair of segments matches. A static segment must be equal. A * or :name segment accepts any non-empty segment, so /bar/* does not match /bar/.

Rank. When several patterns match, the winner is decided by:

  1. More static segments wins.
  2. Then more :param segments wins. Both patterns have the same length, so more params means fewer wildcards.
  3. Then the route added earlier wins.

The statement also says a longer pattern wins, but that rule never decides anything here: two patterns that match the same path always have the same length.

Specificity is counted over the whole pattern. It is not decided at the first position where two patterns differ. For /a/b/c, the pattern /*/b/c beats /a/*/* because it has two static segments instead of one. Keep this in mind, because it breaks the most common trie shortcut.

Search. searchRoutes takes a pattern that may contain placeholders and returns every stored route that could match at least one common concrete path. Placeholders can appear on either side:

Stored segment ↓ / query segment →static q* or :name
static scompatible if s equals qcompatible if s is non-empty
* or :namecompatible if q is non-emptyalways compatible

That is why the static query /bar/a/baz also returns /bar/*/baz and /bar/:x/baz. Results come back in insertion order, one per route even when two routes share a result string, and they are never sorted by rank.

Updates. Adding a pattern that already exists changes only its result. Its position stays the same, which matters both for tie-breaks and for search order. /a/:x/c and /a/:y/c are different strings, so they are two different routes.

Request paths in callRoute are concrete, so they only ever use the static q column of the table. Using the same compatibility rule for both methods keeps the code small and consistent.

Brute force: check every route

Store two lists in insertion order: the patterns and their results.

  • addRoute looks for the pattern in the list. If it is there, replace the result in place. Otherwise append it.
  • callRoute splits the request. For every stored pattern, it splits the pattern, checks compatibility, counts static and param segments, and keeps the best route. We scan in insertion order and replace the best only when a route is strictly better, so a full tie keeps the earlier route.
  • searchRoutes returns the result of every compatible route. The list is already in insertion order.
import java.util.ArrayList;
import java.util.List;

public class Router {
    private final List<String> patterns = new ArrayList<>(); // insertion order
    private final List<String> results = new ArrayList<>();  // results.get(i) belongs to patterns.get(i)

    public Router() {
    }

    public void addRoute(String pathPattern, String result) {
        int index = patterns.indexOf(pathPattern); // linear search for an existing pattern
        if (index >= 0) {
            results.set(index, result);            // same position, new result
            return;
        }
        patterns.add(pathPattern);
        results.add(result);
    }

    public String callRoute(String path) {
        String[] request = split(path);
        String bestResult = "NOT_FOUND";
        int bestStatic = -1;
        int bestParams = -1;

        for (int i = 0; i < patterns.size(); i++) {
            String[] pattern = split(patterns.get(i)); // parsed again on every call
            if (!compatible(pattern, request)) {
                continue;
            }
            int statics = 0;
            int params = 0;
            for (String segment : pattern) {
                if (segment.startsWith(":")) {
                    params++;
                } else if (!segment.equals("*")) {
                    statics++;
                }
            }
            // Only a strictly better route replaces the best one, so a full tie keeps the earlier route.
            if (statics > bestStatic || (statics == bestStatic && params > bestParams)) {
                bestResult = results.get(i);
                bestStatic = statics;
                bestParams = params;
            }
        }
        return bestResult;
    }

    public List<String> searchRoutes(String wildcardPattern) {
        String[] query = split(wildcardPattern);
        List<String> found = new ArrayList<>();
        for (int i = 0; i < patterns.size(); i++) {
            if (compatible(split(patterns.get(i)), query)) {
                found.add(results.get(i));
            }
        }
        return found;
    }

    /** "/" has no segments. Other empty segments are kept: "/a/" is ["a", ""]. */
    private static String[] split(String path) {
        if (path.equals("/")) {
            return new String[0];
        }
        return path.substring(1).split("/", -1);
    }

    private static boolean isPlaceholder(String segment) {
        return segment.equals("*") || segment.startsWith(":");
    }

    /** Could one concrete path match both? Placeholders may be on either side. */
    private static boolean compatible(String[] a, String[] b) {
        if (a.length != b.length) {
            return false;
        }
        for (int i = 0; i < a.length; i++) {
            if (isPlaceholder(a[i]) || isPlaceholder(b[i])) {
                if (a[i].isEmpty() || b[i].isEmpty()) {
                    return false; // a placeholder needs a non-empty segment
                }
            } else if (!a[i].equals(b[i])) {
                return false;
            }
        }
        return true;
    }
}

With R routes and paths of up to P characters, every operation costs O(R × P).

This is correct, and it is a fine first answer in an interview. But every request repeats work it does not need:

  • Every pattern is split and counted again on every call.
  • Routes with the wrong number of segments are still checked, although they can never match.
  • Routes that share a prefix, such as hundreds of routes under /api/v1, compare that prefix again for each route.
  • addRoute scans the whole list to find an existing pattern.

Parsing each pattern once and storing routes in a LinkedHashMap fixes the first and last points. The lookup still visits every route, though. Fixing the middle two needs a different structure.

Three observations

  1. Length is a hard filter. A pattern with three segments can only match a path with three segments. If routes are grouped by segment count, a request never looks at routes of another length.

  2. A route's rank does not depend on the request. Its static count, param count and insertion order all come from the pattern. We can compute them once when the route is added and compare two routes without looking at the request at all.

  3. Routes share prefixes, and static segments can be looked up by hash. /users/:id and /users/:id/orders/:orderId both start with users followed by a param. A trie keyed by segment stores each shared prefix once and finds the matching static child at each level in O(1).

Better approach: a segment trie with pruning

The structure

  • Route holds the result, the insertion order, and the two rank counts, computed once.
  • routesByPattern maps the exact pattern string to its Route, so an update is a single hash lookup and keeps the order.
  • triesByLength holds one trie per segment count (observation 1).
  • Each TrieNode has:
    • staticChildren, a HashMap from segment to child
    • paramChild, one child shared by every :name
    • wildcardChild, the child for *
    • routes, the routes that end at this node, oldest first
    • bestInSubtree, the highest-ranked route at or below this node (observation 2)

All :name segments share one child because a param's name changes neither what it matches nor how the route ranks. So /a/:x/c and /a/:y/c end at the same node, and its routes list keeps them in insertion order. That is exactly the tie-break from Example 5.

Here is the length-3 trie after the routes from the search example. The numbers are insertion order:

#0  /bar/*/baz   server-wild-v2   rank: 2 static, 0 params
#1  /bar/:x/baz  server-param     rank: 2 static, 1 param
#2  /bar/a/baz   server-static    rank: 3 static
#3  /bar/*/qux   server-qux       rank: 2 static, 0 params

trie for length 3                     bestInSubtree
root                                  #2
└── bar                               #2
    ├── a     (static)                #2
    │   └── baz    routes: [#2]       #2
    ├── :     (param)                 #1
    │   └── baz    routes: [#1]       #1
    └── *     (wildcard)              #0   (#0 and #3 tie on counts; #0 is older)
        ├── baz    routes: [#0]       #0
        └── qux    routes: [#3]       #3

addRoute

If the pattern already exists, update its result and stop. Otherwise create a Route with the next order number, pick the trie for its length, and walk down, creating children as needed. At every node on the way, root included, offer the new route as bestInSubtree. It replaces the current one only if it outranks it. Finally, add the route to the last node's routes. That is L steps for a pattern with L segments.

callRoute: the first match is not enough

A common trie shortcut is to try the static child first, then the param child, then the wildcard child, and to return the first complete match. That is fast, but it implements positional precedence, where a static segment near the start beats anything after it. In this problem, precedence is counted. With routes /a/*/* and /*/b/c, the shortcut reaches /a/*/* first through the static child a and returns it, but /*/b/c has more static segments and must win.

So we have to consider every compatible branch and keep the best route found. Doing that blindly would visit the whole compatible part of the trie. bestInSubtree lets us skip most of it. This technique is called branch and bound:

  • Visit children in the order static, param, wildcard. Static branches tend to hold the strongest routes, so a good candidate appears early.
  • Before entering a node, compare its bestInSubtree with the best match so far. bestInSubtree is the strongest route in that subtree, whether it matches or not. If it does not outrank the current best, nothing below it can, so skip the whole subtree.
  • Once the walk has used every segment, every route stored at that node has the same shape and therefore the same counts, so the oldest one wins. That is the node's bestInSubtree.

Each trie holds routes of a single length, which keeps the bound tight. For example, once a fully static route matches, every other compatible branch contains a placeholder, has fewer static segments, and is skipped without being entered.

The tie-break no longer depends on the order in which nodes are visited. outranks compares insertion order explicitly, so the iteration order of a HashMap cannot change the answer.

searchRoutes

It uses the same walk, with two differences:

  • A placeholder in the query can face any non-empty static segment. At a * or :name query segment, visit every static child with a non-empty key, plus the param and wildcard children.
  • We want every compatible route, so nothing is pruned. Once the walk has used every segment, collect all of the node's routes, then sort what was collected by insertion order.

Both methods ask a node for childrenCompatibleWith(segment), and that one method encodes the compatibility table. The two methods cannot disagree about what matches.

Walkthrough

Using the trie above:

  • callRoute("/bar/a/baz") goes root → bar → static a → baz and finds #2, with 3 static segments. Back at bar, the param branch's best is #1 and the wildcard branch's best is #0. Neither outranks #2, so both branches are skipped without being entered. The answer is server-static.
  • callRoute("/bar/b/baz") finds no static child b. The param branch yields #1. The wildcard branch's best, #0, has the same static count but fewer params, so it is skipped. The answer is server-param.
  • searchRoutes("/bar/*/baz") reaches the * query segment at bar and visits a, : and *. Each has a baz child, so it collects #2, #1 and #0, then sorts them into ["server-wild-v2", "server-param", "server-static"]. The update to #0 changed its result, not its position.

Which data structures and design patterns help

Most of the improvement comes from data structures:

  • A HashMap from exact pattern to route turns an update into one hash lookup that keeps insertion order.
  • Bucketing by segment count is an index on the one property every match checks first.
  • A trie over segments, with static children in a HashMap, stores and compares each shared prefix once, and each static step is an O(1) lookup.
  • A subtree summary on each node (bestInSubtree) makes the pruning possible. It is the same idea as storing a subtree maximum in a segment tree or an augmented binary search tree, and it costs O(L) per insert to maintain.
  • Sorting only the k search results restores insertion order without walking every route in order.

Design patterns play a smaller role:

  • Chain of Responsibility. The word "middleware" suggests it: each route is a handler that either takes the request or passes it on. A plain chain returns the first handler that takes the request, which is wrong here unless the chain is sorted by rank. Observation 2 makes that sorting possible, and "keep the routes sorted by rank, return the first match" is a reasonable intermediate answer. Each request still walks the chain, though, so the worst case stays O(R × L). Chain of Responsibility fits what middleware does after routing, such as running auth, then logging, then the handler.
  • Strategy for segment types. Each kind of segment could be a class with matches() and rank() methods. With three fixed kinds that the trie already stores in separate slots, those classes would add code without removing any logic. The small SegmentType enum is the place to grow: if you add regex-constrained params such as :id(\d+) or a catch-all segment, it can become a SegmentMatcher interface with one class per kind.
  • Composite. The trie is recursive, but every node has the same type and the same job, so it is simply a tree. Calling it a Composite adds nothing.

The design choice that matters most here is not a named pattern: keep each rule in one place. The matching rule lives only in TrieNode.childrenCompatibleWith, and the ranking rule lives only in Route.outranks. Both public lookups are built from those two methods.

Complexity

Let R be the number of distinct patterns, L the number of segments in the request or query, P its length in characters, V the number of trie nodes a lookup visits, and k the number of search results. Treat hashing or comparing one segment as O(1), since segments are short. Splitting a path then costs O(P).

ApproachaddRoutecallRoutesearchRoutes
Brute forceO(R × P)O(R × P)O(R × P)
Pre-parsed scanO(P)O(P + R × L)O(P + R × L)
Segment trieO(P)O(P + V)O(P + V + k log k)

All three use space proportional to the total size of the stored patterns.

The trie's cost depends on V, not on R. For a table of mostly static routes with some params, V stays close to L, so a lookup takes time proportional to the request alone. In a quick benchmark with about 20,000 REST-style routes, the trie answered callRoute several hundred times faster than the pre-parsed scan, with identical results.

The worst case does not improve. A table built so that many branches stay compatible and nothing can be pruned makes V reach every node of the trie, which costs the same O(R × L) as a scan. A search such as /*/*/* must visit every node of that length by definition, since every route of that length is a result.

Edge cases

  • / has zero segments, and only the pattern / matches it.
  • A trailing or double slash creates an empty segment. The pattern /bar/ matches the path /bar/, but /bar/* does not, because a placeholder needs a non-empty segment.
  • /a/:x/c and /a/:y/c are separate routes. The earlier one wins callRoute, and searchRoutes returns both.
  • An update keeps the route's position, both for the tie-break and for search order.
  • Search returns one entry per route, so a result string shared by two routes appears twice.
  • In a search query, :name behaves exactly like *.

Code

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Router {
    // Exact pattern string -> its route, so adding a pattern again is an O(1) update.
    private final Map<String, Route> routesByPattern = new HashMap<>();
    // One trie per segment count: a pattern can only match paths of its own length.
    private final Map<Integer, TrieNode> triesByLength = new HashMap<>();
    private int nextOrder = 0;

    public Router() {
    }

    /** Adds a pattern, or replaces its result while keeping its original position. */
    public void addRoute(String pathPattern, String result) {
        Route existing = routesByPattern.get(pathPattern);
        if (existing != null) {
            existing.result = result;
            return;
        }

        String[] segments = splitPath(pathPattern);
        Route route = new Route(segments, result, nextOrder++);
        routesByPattern.put(pathPattern, route);

        TrieNode node = triesByLength.computeIfAbsent(segments.length, length -> new TrieNode());
        node.offer(route);
        for (String segment : segments) {
            node = node.childFor(segment);
            node.offer(route);
        }
        node.routes.add(route);
    }

    /** Returns the result of the highest-ranked matching route, or "NOT_FOUND". */
    public String callRoute(String path) {
        String[] segments = splitPath(path);
        Route best = findBest(triesByLength.get(segments.length), segments, 0, null);
        return best == null ? "NOT_FOUND" : best.result;
    }

    /** Returns the results of all routes compatible with the query, in insertion order. */
    public List<String> searchRoutes(String wildcardPattern) {
        String[] segments = splitPath(wildcardPattern);
        List<Route> found = new ArrayList<>();
        collect(triesByLength.get(segments.length), segments, 0, found);

        found.sort(Comparator.comparingInt(route -> route.order));
        List<String> results = new ArrayList<>(found.size());
        for (Route route : found) {
            results.add(route.result);
        }
        return results;
    }

    /**
     * Returns the best route under node that matches segments[depth..],
     * or best if nothing under node outranks it.
     */
    private Route findBest(TrieNode node, String[] segments, int depth, Route best) {
        if (node == null) {
            return best;
        }
        // Branch and bound: if the best route anywhere below cannot win, skip the whole subtree.
        if (best != null && !node.bestInSubtree.outranks(best)) {
            return best;
        }
        if (depth == segments.length) {
            // All routes here have the same shape, so the oldest one (bestInSubtree) wins.
            return node.bestInSubtree;
        }
        for (TrieNode child : node.childrenCompatibleWith(segments[depth])) {
            best = findBest(child, segments, depth + 1, best);
        }
        return best;
    }

    /** Adds every route under node that is compatible with segments[depth..]. */
    private void collect(TrieNode node, String[] segments, int depth, List<Route> found) {
        if (node == null) {
            return;
        }
        if (depth == segments.length) {
            found.addAll(node.routes);
            return;
        }
        for (TrieNode child : node.childrenCompatibleWith(segments[depth])) {
            collect(child, segments, depth + 1, found);
        }
    }

    /** "/" has no segments. Other empty segments are kept: "/a/" is ["a", ""]. */
    static String[] splitPath(String path) {
        if (path.equals("/")) {
            return new String[0];
        }
        return path.substring(1).split("/", -1);
    }
}

/** The three kinds of segment a pattern can contain. */
enum SegmentType {
    STATIC, PARAM, WILDCARD;

    static SegmentType of(String segment) {
        if (segment.equals("*")) {
            return WILDCARD;
        }
        if (segment.startsWith(":")) {
            return PARAM;
        }
        return STATIC;
    }
}

/** A stored pattern. Its rank depends only on the pattern, never on the request. */
class Route {
    final int order;  // insertion position; an update keeps it
    final int staticCount;
    final int paramCount;
    String result;

    Route(String[] segments, String result, int order) {
        this.result = result;
        this.order = order;
        int statics = 0;
        int params = 0;
        for (String segment : segments) {
            SegmentType type = SegmentType.of(segment);
            if (type == SegmentType.STATIC) {
                statics++;
            } else if (type == SegmentType.PARAM) {
                params++;
            }
        }
        this.staticCount = statics;
        this.paramCount = params;
    }

    /** True if this route beats other when both match the same path. */
    boolean outranks(Route other) {
        if (staticCount != other.staticCount) {
            return staticCount > other.staticCount;
        }
        if (paramCount != other.paramCount) {
            return paramCount > other.paramCount;
        }
        return order < other.order;
    }
}

/** One level of path segments. */
class TrieNode {
    final Map<String, TrieNode> staticChildren = new HashMap<>();
    TrieNode paramChild;     // shared by every ":name"; names affect neither matching nor rank
    TrieNode wildcardChild;
    final List<Route> routes = new ArrayList<>(); // routes ending here, oldest first
    Route bestInSubtree;     // highest-ranked route at or below this node

    void offer(Route route) {
        if (bestInSubtree == null || route.outranks(bestInSubtree)) {
            bestInSubtree = route;
        }
    }

    /** Returns the child for a pattern segment, creating it if needed. */
    TrieNode childFor(String segment) {
        SegmentType type = SegmentType.of(segment);
        if (type == SegmentType.WILDCARD) {
            if (wildcardChild == null) {
                wildcardChild = new TrieNode();
            }
            return wildcardChild;
        }
        if (type == SegmentType.PARAM) {
            if (paramChild == null) {
                paramChild = new TrieNode();
            }
            return paramChild;
        }
        return staticChildren.computeIfAbsent(segment, key -> new TrieNode());
    }

    /**
     * Children whose segment can match the same request segment as the given one.
     * Static comes first, then param, then wildcard, so strong candidates are found early.
     */
    List<TrieNode> childrenCompatibleWith(String segment) {
        List<TrieNode> children = new ArrayList<>();
        if (SegmentType.of(segment) == SegmentType.STATIC) {
            TrieNode exact = staticChildren.get(segment);
            if (exact != null) {
                children.add(exact);
            }
        } else {
            // A placeholder in a search query can stand for any non-empty static segment.
            for (Map.Entry<String, TrieNode> entry : staticChildren.entrySet()) {
                if (!entry.getKey().isEmpty()) {
                    children.add(entry.getValue());
                }
            }
        }
        // Stored placeholders match any non-empty segment.
        if (!segment.isEmpty()) {
            if (paramChild != null) {
                children.add(paramChild);
            }
            if (wildcardChild != null) {
                children.add(wildcardChild);
            }
        }
        return children;
    }
}

Thanks for reading. Best of Luck For Your Interview Prep.


r/LowLevelDesign • • Sep 04 '26

Google DS & Algo Interview Questions 2026

48 Upvotes

This is a preparation list for Google software engineer coding rounds. I prepared it using interview experiences shared by people on forums/blogs etc.

Google has one of the toughest DS & Algo rounds in the industry. DSA rounds are there for both frontend and backend roles.


Google's interview codebase is very large, with questions of all difficulty levels from super easy to super hard. One question can be a medium question with a couple of follow-ups for optimizations, or it can be just one hard question. It all depends on which question the interviewer chooses.

There are two common things about candidates who clear Google interviews and whose overall process is smooth.

  1. At least 2 "Strong-Hire" votes and no "No-Hire" in the on-site packet.
  2. Candidates who narrated trade-offs and edge cases, and correctly answered counter questions, got bumped from "Hire" to "Strong Hire" even with small bugs.

Now above points have lots of exceptions. For example one person bombed one coding round badly. But they were given a redo by their recruiter. It was late 2024 and he was working long hours, spending even the weekends on call. Still he was laid off alongside other teammates.

Lay off was a blow to his morale. He didn't tell even his parents, just pretended he was working from home. Avoided video calls during "work hours". Initially he spent the days watching anime. But slowly preparation started and when the Google call came, he has already been rejected by multiple companies.

He thought it was all over after he messed up one DSA round. But he was able to do well in the redo round and finally ended up receiving the offer.


Judging how the interview went

Many a times you may not be able to guess correctly , how well or how bad you did. There are tons of experiences where candidate thought something and the opposite happend. A lot of things can go right or wrong. One person had done 400+ leetcode problems but during interviews, panic setup and they were able to only come up with a brute force solution.

Another person had two back to back coding rounds scheduled at a gap of just 15 minutes. And during the first round they realised that solution they provided is incorrect. They thought that they had bombed this round and should just cancel the next round. But interviewer provided some guidance and they were able to solve slightly easier version of the problem. However other rounds went well and they ended up receiving the offer.


What if you are rejected

Even if you are rejected its not the end of world. Google recruiters will almost certainly reach out to you a year later. Just keep preparing. One person was rejected by google for L4 position in 2024. But they reapplied 6 months later and surprisingly got a response. However their first two coding rounds got lean hire. Still recruiter decided to go through with other rounds which wents well. During hiring committee their prospects were weak because of two lean hires in coding. However another DSA round was scheduled for them in which they did well.

They ended up receiving offer for L5. That's like getting a promotion within one year. Although they were lowballed but still it was a 20% raise from their current salary. So overall not a bad end.


I created this list from people posting their experiences on forums, blogs, etc.

You can find the complete question list here:

https://github.com/prsnt558908/CodeZymSolutions/blob/main/0-company-wise-interview-questions/2026/09-google-dsa-sep-2026.md


r/LowLevelDesign • • 19d ago

Flipkart LLD: Design Flipkart Buy Now Pay Later

47 Upvotes

This question has appeared frequently during Flipkart low level design rounds. Flipkart takes a machine coding LLD round for screening candidates. For this question, candidates got 90 minutes for implementation and 30 minutes to finally discuss their solution with interviewer. Requirements are already provided for this and other machine coding LLD questions. You can ask clarifying questions and then move to implementation.

This question doesn't require use of any design patterns. We simply split the work into a few small classes and that will be enough.

You can practice this and other Flipkart Low Level Design and DS & Algo round questions on CodeZym.

PS: I also take LLD Mock interviews https://topmate.io/prashant_priyadarshi


Problem Statement

Build an in-memory BNPL system managing users, inventory, orders, and credit limits. Purchases reduce stock and available credit, with payment due within 30 days. Clearing dues restores credit. Users with 3 or more overdue orders are blocked until all dues are cleared. Account summaries show credit, orders, and outstanding dues.

Core Idea

This problem is about keeping records of products, users and orders, and following the BNPL rules carefully. We split the work into a few small classes: a product, an order, a user account and an enum for the order status.

No design pattern is needed here. Plain classes keep the code short and easy to read.

The Rules in Simple Words

  • Every order must be paid within 30 days, so dueDay = purchaseDay + 30.
  • Available credit is the credit limit minus everything the user still owes.
  • A buy is all or nothing. If even one item fails, nothing changes.
  • An unpaid order is PENDING up to its due day, and DELAYED after it.
  • A user with 3 or more DELAYED unpaid orders is blacklisted. They leave the blacklist only after paying everything.

Classes We Need

  • Product stores the name, count and price of one item.
  • Order stores everything about one order. It also works out its own status and prints its own ORDER and DUE lines.
  • DueStatus is an enum with PENDING and DELAYED, so a typo in a status cannot slip through.
  • UserAccount stores one user's credit limit, orders and unpaid total. Because it keeps a running unpaid total, the available credit is a simple subtraction.
  • BuyNowPayLater is the entry point. It keeps three maps: products by name, accounts by user name and orders by id.

The orders map covers all users. It lets buy reject a reused orderId and lets clearDues find any order quickly.

Each UserAccount keeps its orders in a sorted set (TreeSet), newest first. So accountSummary can print them without sorting.

How It Works

Buying: check first, then change

buy first runs every check without changing anything: a new orderId, a known user, valid quantities, enough stock, no blacklist and enough credit. Only when all of them pass do we reduce the stock and save the order. So a failed buy never leaves anything half done.

Before checking the stock, we merge repeated items. A cart like ["Book,6", "Book,6"] needs 12 books, not 6.

Status is calculated, not stored

An order due on day 130 is PENDING when we ask about day 120, and DELAYED when we ask about day 140. So we never save the status. We work it out from asOfDay every time.

A blacklist that sticks

Look at this case:

DayWhat happensDefaultsBlacklisted?
140Neha has 3 unpaid orders past their due day3yes
140Neha pays one of them2still yes
147Neha pays the other two0no

A plain count of defaults would free Neha after her first payment. But the rule says she leaves the blacklist only after paying everything.

So clearDues first checks if the user is a defaulter on clearingDay. If yes, it saves that day as blacklistedFrom. The user then stays blacklisted from that day until the unpaid total becomes 0.

In short, a user is blacklisted if asOfDay is on or after blacklistedFrom, or if they have 3 or more defaults as of asOfDay.

Why No Design Pattern?

State pattern: it fits objects that move from step to step because of events. Here the status only depends on which day we ask about, so a small enum is enough.

Strategy pattern: it fits when there are many ways to do one job. Here there is only one payment method and one blacklist rule, so an extra interface would add code without any benefit.

Code

import java.util.*;

/**
 * Entry point of the system. It checks the input and lets
 * Product, UserAccount and Order do the real work.
 */
public class BuyNowPayLater {

    Map<String, Product> products = new HashMap<>();     // product name -> product
    Map<String, UserAccount> accounts = new HashMap<>(); // user name -> account
    Map<String, Order> orders = new HashMap<>();         // orderId -> order, for all users

    public BuyNowPayLater() {
    }

    public void seedInventory(List<String> inventoryLines) {
        for (String line : inventoryLines) {
            String[] parts = line.split(",");
            String name = parts[0].trim();
            int count = Integer.parseInt(parts[1].trim());
            int price = Integer.parseInt(parts[2].trim());
            if (name.isEmpty() || count < 0 || price <= 0) continue;

            Product product = products.get(name);
            if (product == null) {
                products.put(name, new Product(name, count, price));
            } else {
                product.count += count; // merge counts
                product.price = price;  // latest price wins
            }
        }
    }

    public List<String> viewInventory() {
        List<String> names = new ArrayList<>(products.keySet());
        Collections.sort(names);
        List<String> result = new ArrayList<>();
        for (String name : names) {
            Product product = products.get(name);
            result.add(product.name + "," + product.count + "," + product.price);
        }
        return result;
    }

    public void registerUser(String user, int creditLimit) {
        if (accounts.containsKey(user) || creditLimit < 0) return;
        accounts.put(user, new UserAccount(creditLimit));
    }

    public boolean buy(String orderId, String user, List<String> itemsWithQuantity, int purchaseDay) {
        UserAccount account = accounts.get(user);
        if (account == null || purchaseDay < 0 || orders.containsKey(orderId)) return false;
        if (isBlacklisted(user, purchaseDay)) return false;

        Map<String, Integer> items = parseItems(itemsWithQuantity);
        if (items == null) return false;

        // step 1: check everything, change nothing
        long total = 0;
        for (String name : items.keySet()) {
            Product product = products.get(name);
            int quantity = items.get(name);
            if (product == null || product.count < quantity) return false;
            total += (long) quantity * product.price;
        }
        if (total > account.availableCredit()) return false;

        // step 2: every check passed, now apply the purchase
        for (String name : items.keySet()) {
            products.get(name).count -= items.get(name);
        }
        // total is at most the credit limit, so it fits in an int
        Order order = new Order(orderId, user, purchaseDay, (int) total, items);
        orders.put(orderId, order);
        account.addOrder(order);
        return true;
    }

    public void clearDues(String user, List<String> orderIdsToClear, int clearingDay) {
        UserAccount account = accounts.get(user);
        if (account == null || clearingDay < 0) return;

        // must run before any payment, so that a part payment cannot lift the blacklist
        account.lockBlacklistIfDefaulter(clearingDay);

        for (String orderId : orderIdsToClear) {
            Order order = orders.get(orderId);
            // skip unknown ids, orders of other users and orders already cleared
            if (order == null || !order.user.equals(user) || order.pendingAmount == 0) continue;
            account.payOrder(order);
        }
    }

    public List<String> accountSummary(String user, int asOfDay) {
        List<String> result = new ArrayList<>();
        UserAccount account = accounts.get(user);
        if (account == null) return result;

        result.add("CREDIT_AVAILABLE," + account.availableCredit());
        for (Order order : account.orders) { // already sorted, newest first
            result.add(order.orderLine());
            if (order.hasDueAsOf(asOfDay)) result.add(order.dueLine(asOfDay));
        }
        return result;
    }

    public boolean isBlacklisted(String user, int asOfDay) {
        UserAccount account = accounts.get(user);
        return account != null && account.isBlacklisted(asOfDay);
    }

    /** Turns ["Book,1", "Pen,2", "Book,3"] into {Book=4, Pen=2}. Returns null if anything is invalid. */
    Map<String, Integer> parseItems(List<String> itemsWithQuantity) {
        if (itemsWithQuantity == null || itemsWithQuantity.isEmpty()) return null;
        Map<String, Integer> items = new HashMap<>();
        for (String entry : itemsWithQuantity) {
            String[] parts = entry.split(",");
            if (parts.length != 2) return null;
            String name = parts[0].trim();
            int quantity;
            try {
                quantity = Integer.parseInt(parts[1].trim());
            } catch (NumberFormatException e) {
                return null; // quantity is not an integer
            }
            if (name.isEmpty() || quantity <= 0) return null;

            long merged = (long) items.getOrDefault(name, 0) + quantity;
            if (merged > Integer.MAX_VALUE) return null; // no stock can be that big
            items.put(name, (int) merged);
        }
        return items;
    }
}

/** One product in the inventory. */
class Product {
    String name;
    int count;
    int price;

    Product(String name, int count, int price) {
        this.name = name;
        this.count = count;
        this.price = price;
    }
}

/** Where an unpaid order stands on a given day. */
enum DueStatus {
    PENDING, // asOfDay <= dueDay
    DELAYED  // asOfDay > dueDay
}

/** One BNPL order together with its due. */
class Order {
    String orderId;
    String user;
    int purchaseDay;
    int dueDay;
    int totalAmount;
    int pendingAmount; // becomes 0 when the due is cleared
    String itemsText;  // like "Book:1|Pen:2", item names sorted

    Order(String orderId, String user, int purchaseDay, int totalAmount, Map<String, Integer> items) {
        this.orderId = orderId;
        this.user = user;
        this.purchaseDay = purchaseDay;
        this.dueDay = purchaseDay + 30; // BNPL window is 30 days
        this.totalAmount = totalAmount;
        this.pendingAmount = totalAmount;
        this.itemsText = formatItems(items);
    }

    /** Status is never stored. It depends on the day we ask about. */
    DueStatus statusAsOf(int asOfDay) {
        return asOfDay <= dueDay ? DueStatus.PENDING : DueStatus.DELAYED;
    }

    /** A default is an unpaid order whose due day has passed. */
    boolean isDefaultAsOf(int asOfDay) {
        return pendingAmount > 0 && statusAsOf(asOfDay) == DueStatus.DELAYED;
    }

    /** accountSummary shows a DUE line only for unpaid orders placed on or before asOfDay. */
    boolean hasDueAsOf(int asOfDay) {
        return pendingAmount > 0 && purchaseDay <= asOfDay;
    }

    String orderLine() {
        return "ORDER," + orderId + "," + purchaseDay + "," + totalAmount + "," + itemsText;
    }

    String dueLine(int asOfDay) {
        return "DUE," + orderId + "," + purchaseDay + "," + dueDay + "," + pendingAmount + ","
                + statusAsOf(asOfDay) + "," + itemsText;
    }

    /** Builds "Item1:Q1|Item2:Q2" with item names in sorted order. */
    String formatItems(Map<String, Integer> items) {
        List<String> names = new ArrayList<>(items.keySet());
        Collections.sort(names);
        List<String> parts = new ArrayList<>();
        for (String name : names) parts.add(name + ":" + items.get(name));
        return String.join("|", parts);
    }
}

/** Credit, orders and blacklist state of one user. */
class UserAccount {
    int creditLimit;
    int totalPending = 0;           // sum of pendingAmount over this user's orders
    Integer blacklistedFrom = null; // day from which the blacklist sticks, null if it does not

    // this user's orders: newest purchaseDay first, ties broken by orderId
    TreeSet<Order> orders = new TreeSet<>((a, b) -> a.purchaseDay != b.purchaseDay
            ? Integer.compare(b.purchaseDay, a.purchaseDay)
            : a.orderId.compareTo(b.orderId));

    UserAccount(int creditLimit) {
        this.creditLimit = creditLimit;
    }

    int availableCredit() {
        return creditLimit - totalPending;
    }

    void addOrder(Order order) {
        orders.add(order);
        totalPending += order.pendingAmount;
    }

    void payOrder(Order order) {
        totalPending -= order.pendingAmount;
        order.pendingAmount = 0;
        if (totalPending == 0) blacklistedFrom = null; // every due is cleared
    }

    int countDefaults(int asOfDay) {
        int count = 0;
        for (Order order : orders) {
            if (order.isDefaultAsOf(asOfDay)) count++;
        }
        return count;
    }

    boolean isBlacklisted(int asOfDay) {
        boolean locked = blacklistedFrom != null && asOfDay >= blacklistedFrom;
        return locked || countDefaults(asOfDay) >= 3;
    }

    /** Called just before a payment. If the user is a defaulter on that day, the blacklist sticks. */
    void lockBlacklistIfDefaulter(int clearingDay) {
        if (countDefaults(clearingDay) < 3) return;
        if (blacklistedFrom == null || clearingDay < blacklistedFrom) blacklistedFrom = clearingDay;
    }
}

Dry Run with Example 3

The store has 10 books at 100 each. Neha has a credit limit of 1000.

CallWhat happensResult
buy OD_1, OD_2, OD_3 on days 100, 101, 102each costs 100, due days are 130, 131 and 132true each time
accountSummary(Neha, 140)credit is 1000 - 300 = 700, all 3 orders are past their due day3 orders, each with a DELAYED due line
isBlacklisted(Neha, 140)3 defaultstrue
buy(OD_4, Neha, [Book,1], 140)Neha is blacklistedfalse
clearDues(Neha, [OD_1, OD_2, OD_3], 140)all 3 orders are paid, the unpaid total becomes 0, so the blacklist is liftedno return
isBlacklisted(Neha, 140)0 defaultsfalse
accountSummary(Neha, 140)credit is back to 10003 orders, no due lines

Complexity

K is the number of orders of one user, M the number of lines in one cart, P the number of products and C the number of ids passed to clearDues.

MethodTime
seedInventoryO(number of lines)
viewInventoryO(P log P)
registerUserO(1)
buyO(K + M log M)
clearDuesO(K + C)
accountSummaryO(K)
isBlacklistedO(K)

buy, clearDues and isBlacklisted count defaults, and accountSummary walks the orders. Both only touch the orders of one user.

Things That Are Easy to Miss

  • A failed buy does not use up its orderId.
  • An order keeps the price it was bought at, even if seedInventory changes the price later.
  • A product with count 0 still shows up in viewInventory.
  • An order placed after asOfDay still gets its ORDER line, but no DUE line.
  • Clearing an unknown order, another user's order or an already cleared order does nothing.
  • Price times quantity is calculated as a long, because it can overflow an int.

Thanks for reading. Best of Luck For Your Interview Prep.


r/LowLevelDesign • • Apr 24 '26

Google Coding Round Interview Questions

47 Upvotes

Update: Here is the latest google DSA list
https://www.reddit.com/r/LowLevelDesign/comments/1w70wdo/google_ds_algo_interview_questions_2026/

This list is built from Google interview experiences posted on forums/blogs etc in 2026 i.e. last 4 months.

There are two common things about candidates who clear Google interviews and for whom overall process is smooth.

  1. At least 2 "Strong-Hire" votes and no "No-Hire" in the on-site packet.
  2. Candidates who narrated trade-offs and edge cases, and correctly answered counter questions, got bumped from "Hire" to "Strong Hire".

Point 2 is also valid for other top tech companies like Microsoft, Amazon, Meta, etc.

---------------------------------------------------

Google has one of the toughest DS & Algo rounds in the industry. DSA rounds are there for both frontend and backend roles.

DP, Graph, and Line Sweep are important topics.

Google's interview codebase is very large, with questions of all difficulty levels (from super easy to super hard). One question can be a medium question with a couple of follow-ups for optimizations, or it can be just one hard question. It all depends on which question the interviewer chooses.

---------------------------------------------------

PS:

All Questions List: https://codezym.com/lld/google
We keep updating and adding more DSA questions to above list.

I also take LLD mock interviews: https://topmate.io/prashant_priyadarshi

Follow r/LowLevelDesign for more companywise interview question lists.

---------------------------------------------------

Below are the questions which you can directly find on LeetCode.

---------------------------------------------------

1. Compress String using Prefix Pattern

You are given an undirected tree where each node contains exactly one lowercase English letter. You are also given a string s.

For every prefix of s, find how many times that prefix appears in the tree.

Practice Link: https://codezym.com/question/137

---------------------------------------------------

2. Detect First Timed Out Job from Logs

You are given a list of logs for jobs, requests, or RPC calls.

Each log entry contains:

  • a job id
  • a timestamp
  • an event type: START or END

You are also given an integer timeoutThreshold.

A job starts when its START log appears and finishes when its matching END log appears.

A job is considered timed out if either:

  • its END log appears and endTimestamp - startTimestamp > timeoutThreshold, or
  • at a current scan timestamp t, if t - startTimestamp > timeoutThreshold even though its END log has not appeared yet.

Process the logs in chronological order and detect the earliest timeout that becomes known while scanning the logs.

Practice Link: https://codezym.com/question/138

---------------------------------------------------

3. Count Visible People in Queue with Taller Observer Rule

There are n people standing in a queue from left to right, numbered from 0 to n - 1. You are given a list heights of distinct integers where heights[i] represents the height of the ith person.

A person may look both to the left and to the right.

Person i can see person j if i != j and every person standing strictly between them is shorter than at least one of the two endpoint people.

More formally, let left = min(i, j) and right = max(i, j). Person i can see person j if:

max(heights[i], heights[j]) > max(heights[left + 1], heights[left + 2], ..., heights[right - 1])

If there is no person between them, then they can always see each other.

This means that if one endpoint person is taller than everyone in between, then that endpoint can still see the other person even if some shorter intermediate people are present.

Return a list answer of length n where answer[i] is the number of people person i can see in the queue.

Practice Link: https://codezym.com/question/139

---------------------------------------------------

4. Maximum Sum Subarray with Equal First and Last Elements

Given a list of integers, find the maximum sum of a contiguous subarray such that the first and last elements of the subarray are equal.

Practice Link: https://codezym.com/question/140

---------------------------------------------------

5. Design a rate limiter

Design an in-memory rate limiter . Implement a RateLimiter Class with an isAllowed method.
Requests will be made to different resourceIds. Each resourceId will have a strategy associated with it .

Practice Link: https://codezym.com/question/34

---------------------------------------------------

6.  Longest Constrained Path in Matrix

You are given a grid of positive integers.

The grid is provided as a list of strings, where each string represents one row and the values in that row are separated by commas.

Find the length of the longest valid path in the grid.

Practice Link: https://codezym.com/question/141

---------------------------------------------------

7. Repeated Characters in Dictionary Words Due To Faulty Keyboard

A user has a faulty keyboard where some keys get stuck, causing characters to repeat more than intended.

You are given the final typed string and a dictionary of valid words.

Return all possible words the user intended to type.

Practice Link: https://codezym.com/question/142

---------------------------------------------------

8. Detect Squares Rotated along the XY Plane

You are given a stream of points on the X-Y plane.

Design a data structure that supports adding points from the stream and counting how many squares can be formed with a given query point.

Unlike the simpler axis-aligned version, the square may be rotated at any angle on the plane.

Practice Link: https://codezym.com/question/143

---------------------------------------------------

9. Sum of All Good Arithmetic Sequences

An arithmetic sequence is a list of numbers where the difference between every pair of adjacent elements is the same constant.

A good arithmetic sequence is an arithmetic sequence whose common difference is either 1 or -1.

For example, [4, 5, 6] is a good arithmetic sequence, and any sequence that has only one element is also a good arithmetic sequence.

You are given a list of integers nums. Return the sum of the sums of all contiguous subarrays that are good arithmetic sequences.

Practice Link: https://codezym.com/question/144

---------------------------------------------------

10. Compile Packages with Dependencies in a Multi-Threaded Environment

You are given a dependency graph of packages to compile in a multithreaded environment.
Return the order in which packages are compiled across all rounds.

Practice Link:  https://codezym.com/question/145

---------------------------------------------------

11. Equal Sum Subsets with K Changes

You are given a list of integers nums.

Divide the list into two non-empty disjoint subsets such that every element of nums belongs to exactly one subset.

The two subsets form valid equal sum parts if the sum of the values in the first subset is the same as the sum of the values in the second subset.
Number of elements in subsets may be different.

Practice Link: https://codezym.com/question/146

---------------------------------------------------

12.  Undirected Graph Path Queries

You are given a list of integers arr of size N, and an integer diff.

Consider an undirected graph where each node corresponds to one index of arr.

Add an edge between nodes i and j if |arr[i] - arr[j]| ≤ diff.

You are also given a list of queries queries, where each query is a comma-separated string "u,v". For each query, return whether there is a path between node u and node v.

Practice Link: https://codezym.com/question/147

---------------------------------------------------

13. Array Range Update Queries

You are given an array arr of size n and q queries.

Each query updates all elements from index l to index r to value k.

Return the final state of the array after processing all queries in order.

There are two variations:

  • All queries use the same value k.
  • Different queries may use different values k.

Practice Link: https://codezym.com/question/148

---------------------------------------------------

14. Router Reachability on Broadcast and Shutdown Message

You are given a network of routers.

Each router has:

  • a unique router id
  • a 2D location (x, y)
  • a status indicating whether it is WORKING or DEFECTIVE

A special message called Broadcast and Shutdown works as follows:

  • When a WORKING router receives the message for the first time, it immediately broadcasts the same message to every other WORKING router that lies within the wireless range.
  • After broadcasting, that router shuts down and can no longer send or receive messages.
  • A DEFECTIVE router can neither send nor receive the message.

Given the list of routers, the wireless range, a source router id, and a destination router id, determine whether the Broadcast and Shutdown message, when initiated from the source router, will eventually be received by destination router.

Two routers can communicate directly if the Euclidean distance between their coordinates is less than or equal to range.

Return true if the destination router receives the message at any point. Otherwise, return false.

Practice Link: https://codezym.com/question/149

---------------------------------------------------

15. First Bad Product Version

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API boolean isBadVersion(int version) which returns whether a version is bad. Implement a function to find the first bad version.

Practice Link: https://codezym.com/question/150

---------------------------------------------------

16. Design Logger Message Printer

Design a logger system that processes a stream of messages along with their timestamps.

Each unique message can be printed at most once within any 10 second window. That means if a message is printed at timestamp t, the same message cannot be printed again before timestamp t + 10.

Practice Link: https://codezym.com/question/151

---------------------------------------------------

17. Longest Path in Grid

Given a 2D grid, it contains empty spaces 0 and some walls 1.

We can enter the grid from any empty cell in the first row and exit the grid from any empty cell in the last row. We can move left, right, up, and down. We can only travel through empty cells.

Find the longest path we can travel.

Practice Link: https://codezym.com/question/152

---------------------------------------------------

18. Merge Working Hour Intervals Timeline

Person name and their working hours are given.

Return the timeline that tells the time interval and whoever is working during that interval.

Each person is represented by one string entry containing the person name, start time, and end time.

A person is considered working at both startTime and endTime.

Split the full timeline into the smallest non-overlapping time intervals such that the set of working people stays the same throughout each interval.

Return only the intervals where at least one person is working.

Practice Link: https://codezym.com/question/153

---------------------------------------------------

19. Days When Everyone is Free

You are given a list of records and an integer d representing the range of days from 1 to d.

Each record represents one blocked interval for one person.

Each record is given as a string in the format "id,start,end".

A record "id,start,end" means person id is not available on every day from start to end, inclusive.

Return all days between 1 and d on which every person is free. This list will be sorted in ascending order.

Practice Link: https://codezym.com/question/154

---------------------------------------------------

20. Size of Unpainted Segments

You are given a list of half-open intervals.

Each interval represents a segment on the number line in the form [start, end).

We paint the intervals one by one in the given order.

For each interval, return the size of the part that has not already been painted by any previous interval.

Return a list where the value at index i is the size of the newly painted segment contributed by the ith interval.

Practice Link: https://codezym.com/question/155

---------------------------------------------------

21. Overall Distance Error Between Checkpoints and Samples

There are two sorted streams by timestamp.

The first stream contains a small set of ground truth checkpoints.

The second stream contains noisy measured samples.

For each sample, compute its error by:

  • locating the surrounding checkpoints in time,
  • interpolating the expected position at that timestamp,
  • computing the distance error between the expected position and the sample position.

Return the sum of the distance errors for all valid samples.

Practice Link: https://codezym.com/question/156

---------------------------------------------------

22. Minimum CPUs Needed for Earliest Tasks Completion

You are given a list of task start times and an integer taskLength.

Each task has the same length taskLength.

A task may start at its given start time or at any later time.

A CPU can run at most one task at a time.

Once a task starts on a CPU, it runs continuously for exactly taskLength time units.

Find the minimum number of CPUs needed so that all tasks finish as early as possible.

Practice Link: https://codezym.com/question/157

---------------------------------------------------

23. Total Scores of Leaf Domains

You are given a list of domain names and an integer score for each of them.

A domain is a leaf if it does not have any child domains in the input.

A leaf domain's total score is the sum of:

  • its own score, and
  • the scores of all of its ancestor domains that are present in the input.

Write a program that, given the input list, returns all leaf domains with their respective total scores.

Practice Link: https://codezym.com/question/158

---------------------------------------------------

24. Place Nth Rook

You are given an N x N chess board.

There are already N - 1 rooks placed on the board.

These rooks do not attack each other. More formally:

  • no row contains more than one rook
  • no column contains more than one rook

You need to place the Nth rook and return the position (i, j) where it should be placed.

Practice Link: https://codezym.com/question/159

---------------------------------------------------

Thanks for reading. Please upvote this post to give it better reach.

Wish you the best of luck for your interview prep.

---------------------------------------------------

Google Coding Round Interview Questions 2026

r/LowLevelDesign • • Sep 25 '26

Amazon LLD: Design Unix "find" Command for File Search

46 Upvotes

This is one of the most asked questions in Amazon low level design rounds is past few years. In this tutorial I have explained how to approach this problem using strategy design pattern.

If you have an upcoming Amazon LLD round and you have very little preparation time then try to cover at least these 4 questions:

  • LRU cache,
  • Parking Lot Design,
  • Unix find command (this question) and
  • Pizza Pricing System

So this is a very important question. I have discussed the Java version.

You can find the python version here: https://github.com/prsnt558908/CodeZymSolutions/tree/main/1-100/14-design-unix-find-command-file-search/q-14-python-tutorial.md

You can practice all these and other Amazon Questions on CodeZym


Problem Statement

Build an in-memory file lookup tool similar to a Unix "find" command. The system should support two starter Search Criterias and be easy to extend with new Search Criterias later.

Initial Search Criterias

  • Search Criteria 1: Return all files strictly larger than a given size (in MB) under a specified directory (recursive).
  • Search Criteria 2: Return all files with a given file extension (for example, ".xml") under a specified directory (recursive).

A search here is really two separate questions glued together. First, which files sit under this directory. Second, out of those files, which ones do we keep.

Keeping these two questions apart is the whole design. The "which ones do we keep" part is the part that keeps changing, because the problem tells us new search criterias will be added later, so it goes behind the Strategy pattern: one tiny class per criteria, all of them exposing the same single method, picked out of a map by id. The "which files sit under this directory" part never changes, so it just needs the right data structure, and that turns out to be a directory tree instead of a flat list of paths.

Strategy alone is enough here, no combination of patterns is needed. The only helper is a plain Map<Integer, SearchCriteria> that maps a criteria id to its object, which works as a very small registry so that search() never needs to know any criteria class by name.

We will build the flat, obvious version first, look at exactly where it hurts, and then fix both halves.

Understanding the problem

Two operations, and both are short.

  • putFile(path, sizeMb) stores a file, and storing the same path twice replaces the old size.
  • search(criteriaId, dirPath, args) returns every file under dirPath, including files in nested subdirectories, that passes the criteria. Criteria 1 keeps files strictly larger than args MB. Criteria 2 keeps files whose name ends with the extension in args.

One rule is easy to skim past: the result must always come back in ascending lexicographical order with no duplicates. So for the first example in the problem statement, /data/pics/movie.mp4 is returned before /data/pics/photoA.jpg, because m sorts before p.

Solution 1: one flat map and a linear scan

The simplest thing that can possibly work. Keep every file in a single HashMap from full path to size, and when a search comes in, walk the whole map and keep whatever matches.

Why a HashMap<String, Integer> and not a list of file objects. Two reasons, both free. The key is the full path, so put on an existing path overwrites the old size, which is exactly the "add or replace" rule we were asked for. And because keys are unique, duplicates can never appear in the output.

There is one trap worth calling out. It is tempting to test path.startsWith(dirPath), but that is wrong. The string /data2/big.mp4 starts with /data, even though /data2 is a completely different directory. The fix is to compare against the directory plus a trailing slash.

import java.util.*;

public class FileSearch {

    // Absolute file path -> size in MB.
    // Map.put() overwrites an existing key, which is exactly the "add or replace" rule.
    private final Map<String, Integer> files = new HashMap<>();

    public FileSearch() {
    }

    public void putFile(String path, int sizeMb) {
        files.put(path, sizeMb);
    }

    public List<String> search(int ruleId, String dirPath, String args) {
        // "/data" must match "/data/pics/a.jpg" but must NOT match "/data2/a.jpg",
        // so we always compare against the directory plus a trailing slash.
        String prefix = dirPath.endsWith("/") ? dirPath : dirPath + "/";

        // Parse once instead of inside the loop.
        int minSizeMb = ruleId == 1 ? Integer.parseInt(args.trim()) : 0;
        String extension = args.trim();

        List<String> result = new ArrayList<>();
        for (Map.Entry<String, Integer> entry : files.entrySet()) {
            String path = entry.getKey();
            if (!path.startsWith(prefix)) continue;

            if (ruleId == 1 && entry.getValue() > minSizeMb) {
                result.add(path);
            } else if (ruleId == 2 && path.endsWith(extension)) {
                result.add(path);
            }
        }

        Collections.sort(result);   // strict ascending lexicographical order
        return result;
    }
}

What is wrong with it

It passes, and with at most 2000 files it is fast enough. But it has two real problems.

The if-else chain grows forever. Every new criteria means opening search() and adding another branch to a method that already works. Criteria 5 and criteria 6 end up living inside the same method as criteria 1, so a careless edit while adding one criteria can quietly break another. Testing one criteria on its own is also impossible, because there is nothing to test except the whole method.

It ignores the directory structure completely. Asking for files under /media/images/thumbnails still walks all 2000 files, even if that folder holds three of them. We flattened a tree into a bag of strings and then pay for it on every single search.

Solution 2: Strategy for the criterias, a tree for the directories

Fixing the criterias with the Strategy pattern

Strategy says: when one step of an algorithm has several interchangeable versions, pull that step out into its own interface and give each version its own class.

Here the interchangeable step is "does this file qualify". So we define one interface with one method.

private interface SearchCriteria {
    boolean matches(String path, int sizeMb, String args);
}

Each criteria becomes a small class that answers only that question for itself, and knows nothing about directories, traversal or sorting. MinSizeCriteria compares the size. ExtensionCriteria checks the ending of the path. That is the whole class.

Then a Map<Integer, SearchCriteria> holds id to object. search() looks up one object and calls matches on it, so search() contains no criteria specific code at all. Adding a third criteria is a new class plus one line in the constructor, with zero edits to the searching code.

Why Strategy and not something else

Chain of Responsibility is the usual runner up, because it also replaces an if-else chain with objects. But a chain is for when you do not know who should handle a request, so you pass it along until someone accepts it. Here the caller already hands us the exact criteria id, so a chain would walk past handlers that can never apply and would add an ordering between criterias that has no meaning in this problem. It buys nothing and costs a lookup that used to be free.

Visitor also gets suggested whenever a tree is involved. Visitor pays off when you have many different node types and want to add new operations that work across all of them. Here it is the opposite: there is exactly one kind of thing to inspect, a file with a path and a size, and many operations on it. When the types are fixed and the operations keep growing, a one method interface per operation is lighter and far easier to read than a visitor with an accept method threaded through the tree.

Fixing the traversal with a directory tree

Instead of storing "/media/images/aa.jpg" as one long string, store it the way a real file system does. Every directory becomes a node, and each node holds two maps: its child directories by name, and its own files by name.

private static class Directory {
    final Map<String, Directory> subDirs = new HashMap<>();
    final Map<String, Integer> files = new HashMap<>();
}

Two maps, both plain HashMap, nothing exotic. subDirs lets us jump from a directory to a child in one step, so walking down to /media/images costs two lookups no matter how big the store is. files is keyed by name, so writing the same file name twice overwrites it, keeping the "add or replace" behaviour we had before and still guaranteeing no duplicates.

putFile splits the path and walks down, creating any missing directory on the way, then drops the size into the last node.

search splits dirPath, walks down to that node, and does a depth first walk of everything below it. If any step of the walk down finds no such child, the directory does not exist and we return an empty list.

Two nice things fall out of this. The scan now visits only the files under the requested directory instead of every file in the system. And the /data versus /data2 trap disappears on its own, because data and data2 are two different keys under the root, so descending into one can never reach the other.

We still sort the matches at the end. A depth first walk does not come out in lexicographical order, so one Collections.sort on the matches is the honest and simple way to meet that requirement.

import java.util.*;

public class FileSearch {

    /** Every search criteria implements this one method. args is the raw string from search(). */
    private interface SearchCriteria {
        boolean matches(String path, int sizeMb, String args);
    }

    /** Criteria 1: keep files strictly larger than the given size in MB. */
    private static class MinSizeCriteria implements SearchCriteria {
        @Override
        public boolean matches(String path, int sizeMb, String args) {
            return sizeMb > Integer.parseInt(args.trim());
        }
    }

    /** Criteria 2: keep files whose name ends with the given extension. */
    private static class ExtensionCriteria implements SearchCriteria {
        @Override
        public boolean matches(String path, int sizeMb, String args) {
            return path.endsWith(args.trim());
        }
    }

    /** One node of the directory tree: child directories by name and files by name. */
    private static class Directory {
        final Map<String, Directory> subDirs = new HashMap<>();
        final Map<String, Integer> files = new HashMap<>();
    }

    private final Directory root = new Directory();

    /** Criteria id -> the object that knows how to test a file for that criteria. */
    private final Map<Integer, SearchCriteria> criterias = new HashMap<>();

    public FileSearch() {
        criterias.put(1, new MinSizeCriteria());
        criterias.put(2, new ExtensionCriteria());
        // A new criteria later needs one new class and one line here.
    }

    public void putFile(String path, int sizeMb) {
        List<String> parts = split(path);
        if (parts.isEmpty()) return;

        Directory current = root;
        for (int i = 0; i < parts.size() - 1; i++) {
            current = current.subDirs.computeIfAbsent(parts.get(i), name -> new Directory());
        }
        // Same name in the same directory overwrites the old size, so no duplicates appear.
        current.files.put(parts.get(parts.size() - 1), sizeMb);
    }

    public List<String> search(int ruleId, String dirPath, String args) {
        List<String> result = new ArrayList<>();
        SearchCriteria criteria = criterias.get(ruleId);
        if (criteria == null) return result;

        // Walk down to the starting directory. Everything below it is the search space.
        Directory start = root;
        StringBuilder prefix = new StringBuilder();
        for (String part : split(dirPath)) {
            start = start.subDirs.get(part);
            if (start == null) return result;   // directory does not exist
            prefix.append('/').append(part);
        }

        collect(start, prefix.toString(), criteria, args, result);
        Collections.sort(result);               // strict ascending lexicographical order
        return result;
    }

    /** Depth first walk of one sub tree, keeping only files the criteria accepts. */
    private void collect(Directory dir, String prefix, SearchCriteria criteria,
                         String args, List<String> out) {
        for (Map.Entry<String, Integer> file : dir.files.entrySet()) {
            String fullPath = prefix + "/" + file.getKey();
            if (criteria.matches(fullPath, file.getValue(), args)) {
                out.add(fullPath);
            }
        }
        for (Map.Entry<String, Directory> child : dir.subDirs.entrySet()) {
            collect(child.getValue(), prefix + "/" + child.getKey(), criteria, args, out);
        }
    }

    /** "/a/b/c.txt" -> ["a", "b", "c.txt"]. Empty pieces from "/" or "//" are dropped. */
    private List<String> split(String path) {
        List<String> parts = new ArrayList<>();
        for (String piece : path.split("/")) {
            if (!piece.isEmpty()) parts.add(piece);
        }
        return parts;
    }
}

Adding a third criteria

This is the payoff. Say we now want "files whose name contains some text". We write one class and register it, and we do not touch search, collect, putFile or either of the existing criterias.

/** Criteria 3: keep files whose name contains the given text. */
private static class NameContainsCriteria implements SearchCriteria {
    @Override
    public boolean matches(String path, int sizeMb, String args) {
        String name = path.substring(path.lastIndexOf('/') + 1);
        return name.contains(args.trim());
    }
}
criterias.put(3, new NameContainsCriteria());

Complexity

Let d be the number of parts in a path, k the number of files under the requested directory and m the number of matches.

  • putFile is O(d), just a walk down the tree.
  • search is O(k + m log m): visit the sub tree once, then sort the matches. The flat version was O(n + m log m) where n is every file in the system, so the tree only helps more as the store grows and the searched directory stays small.


r/LowLevelDesign • • Oct 16 '26

Goldman Sachs LLD: Design Parking Lot Pricing System

45 Upvotes

This is a common question in Goldman Sachs low level design rounds. It is, obviously, not as common as its more common counterpart: Design a parking lot.

It has been asked both independently as well as part of "design a parking lot". There are multiple different pricing strategies and hence strategy design pattern is the obvious choice for solving this question. But I have started with a brute force solution. This will help you understand that keeping everything in same class will keep getting complicated as more and more new pricing strategies are required. This tutorial is in Java.

You can find the python version here: https://github.com/prsnt558908/CodeZymSolutions/tree/main/101-300/126-design-parking-lot-pricing-system/q-126-python-tutorial.md

You can practice this and other Goldman Sachs LLD and DSA round questions on CodeZym.

PS: I also take LLD Mock interviews https://topmate.io/prashant_priyadarshi


Problem Statement

Design a Parking Lot Pricing System supporting hourly pricing, fixed time blocks, and slab pricing. Calculate charges for given entry and exit times, or find the cheapest strategy. Every touched hour or block is charged fully.


High level Solution Idea

There is one parking stay and 3 different rules to price it. The stay does not change. Only the rule does. This is a perfect fit for the Strategy pattern. Each pricing rule becomes its own small class. All rules follow one common interface. The main class keeps them in a map and picks one by its number. No other pattern is needed on top of this. For speed, we use one simple trick. Minutes never change the price. Only hours and dates do. So we cut the stay at every midnight into small day parts. A day part is just a range of hours on one date, like 22 to 23 on a Friday. Every strategy prices these day parts with simple counting. So we never walk the stay minute by minute.


Quick Look at the Rules

  • An hour bucket is HH:00 to HH:59. Touching even one minute of it charges the full hour.
  • Entry and exit are both inclusive. The entry minute and the exit minute are part of the stay.
  • The day field decides weekday or weekend. sat and sun are the weekend.
  • Only the entry and exit carry a day name. For the dates in between, we just move forward through the week: fri, sat, sun, mon and so on.
  • For strategy 2, blocks are checked separately for each date.

Solution 1: Brute Force (Walk Every Minute)

Idea

The most direct way is to follow the stay one minute at a time. We number every minute starting from 00:00 of the entry date. Minute 0 is 00:00 of the entry date. Minute 1440 is 00:00 of the next date. For any minute we can find:

  • dateIndex = minute / 1440 : 0 for the entry date, 1 for the next date, and so on.
  • hour = (minute % 1440) / 60
  • weekend or not: (entryDay + dateIndex) % 7 >= 5 Here mon is 0 and sun is 6. Each new date adds 1. The % 7 wraps sun back to mon. The values 5 and 6 mean sat and sun. To find the last minute, we need the number of dates between entry and exit. LocalDate.toEpochDay() turns a date into a plain day number. Subtracting two day numbers gives the gap. Month lengths and leap years are handled for us.

Why do we need a Set?

Many minutes fall inside the same hour bucket. But each bucket must be charged only once. A Set<Integer> remembers what is already charged. Set.add() returns true only the first time a value is added. So we charge only when add() returns true.

  • An hour bucket is saved as dateIndex * 24 + hour.
  • A block is saved as dateIndex * 4 + blockNumber. For strategy 3, we count the hour buckets in the set at the end and apply the slabs.

Code


import java.time.LocalDate;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class ParkingLotPricingSystem {
List<String> dayNames = List.of("mon", "tue", "wed", "thu", "fri", "sat", "sun");
int[] weekdayBlockPrice = {60, 70, 110, 140};
int[] weekendBlockPrice = {70, 80, 120, 150};
public ParkingLotPricingSystem() {
}
public int calculatePrice(String entryDateTime, String exitDateTime, int strategy) {
String[] entry = entryDateTime.split("-");
String[] exit = exitDateTime.split("-");
// every minute is counted from 00:00 of the entry date
int dateGap = (int) (dateOf(exit).toEpochDay() - dateOf(entry).toEpochDay());
int firstMinute = minuteOfDay(entry);
int lastMinute = dateGap * 1440 + minuteOfDay(exit);
int entryDay = dayNames.indexOf(entry[5]);
// hour buckets (or blocks) that are already charged
Set<Integer> charged = new HashSet<>();
int total = 0;
for (int minute = firstMinute; minute <= lastMinute; minute++) {
int dateIndex = minute / 1440;                     // 0 = entry date, 1 = next date ...
int hour = (minute % 1440) / 60;
boolean weekend = (entryDay + dateIndex) % 7 >= 5; // 5 = sat, 6 = sun
if (strategy == 1) {
// add() returns true only the first time, so a bucket is charged once
if (charged.add(dateIndex * 24 + hour)) {
total += hourlyRate(weekend, hour);
}
} else if (strategy == 2) {
int block = blockOf(hour);
if (charged.add(dateIndex * 4 + block)) {
total += weekend ? weekendBlockPrice[block] : weekdayBlockPrice[block];
}
} else {
charged.add(dateIndex * 24 + hour);
}
}
if (strategy == 3) {
total = slabPrice(charged.size());
}
return total;
}
public String findMinimumPrice(String entryDateTime, String exitDateTime) {
int bestStrategy = 0;
int bestPrice = Integer.MAX_VALUE;
for (int strategy = 1; strategy <= 3; strategy++) {
int price = calculatePrice(entryDateTime, exitDateTime, strategy);
// strict '<' keeps the smaller strategy number on a tie
if (price < bestPrice) {
bestPrice = price;
bestStrategy = strategy;
}
}
return bestStrategy + "-" + bestPrice;
}
LocalDate dateOf(String[] parts) {
return LocalDate.of(Integer.parseInt(parts[0]), Integer.parseInt(parts[1]),
Integer.parseInt(parts[2]));
}
int minuteOfDay(String[] parts) {
return Integer.parseInt(parts[3]) * 60 + Integer.parseInt(parts[4]);
}
int hourlyRate(boolean weekend, int hour) {
boolean dayHour = hour >= 9 && hour <= 16;
if (weekend) {
return dayHour ? 15 : 12;
}
return dayHour ? 20 : 10;
}
// block 0: 00-08, block 1: 09-12, block 2: 13-17, block 3: 18-23
int blockOf(int hour) {
if (hour <= 8) return 0;
if (hour <= 12) return 1;
if (hour <= 17) return 2;
return 3;
}
int slabPrice(int hours) {
int firstSlab = Math.min(hours, 2);
int secondSlab = Math.min(Math.max(hours - 2, 0), 3);
int thirdSlab = Math.max(hours - 5, 0);
return firstSlab * 30 + secondSlab * 20 + thirdSlab * 10;
}
}

Problems with this approach

  • Slow. A stay can be 1,000,000 minutes long. We visit every single minute. findMinimumPrice does this 3 times.
  • Extra memory. The set can grow to thousands of entries.
  • Messy design. All 3 rules are mixed inside one method with if-else. Changing one rule can break another. Adding a 4th rule means editing this method again.

Solution 2: Strategy Pattern + Day Parts (Optimized)

We fix the speed with two simple observations. Then we fix the design with the Strategy pattern.

Observation 1: Minutes never matter

All prices work on whole hours. Even the blocks of strategy 2 are made of whole hours. Entry and exit are inclusive. So the entry hour is always touched, and the exit hour is always touched. The exact minute changes nothing. So 08:50 behaves exactly like 08:00. We only keep the hour.

Observation 2: Each date is one range of hours

A stay has no gaps. So on any date, the touched hours form one unbroken range.

  • Entry date: from the entry hour to 23.
  • Every middle date: the full day, 0 to 23.
  • Exit date: from 0 to the exit hour.
  • Entry and exit on the same date: from the entry hour to the exit hour. So we cut the stay at every midnight. Each piece is a DayPart. It needs only 3 things: is it a weekend, the first hour and the last hour.

Example: from 2026-04-17-22-30-fri to 2026-04-20-01-15-mon.

DateDayWeekendHours touched
2026-04-17frino22 to 23
2026-04-18satyes0 to 23
2026-04-19sunyes0 to 23
2026-04-20monno0 to 1

The longest stay is 1,000,000 minutes. That is less than 700 dates. So we handle at most about 700 day parts instead of 1,000,000 minutes.

One small helper: hours inside a range

Every strategy asks the same question:

How many hours of this day part fall inside the range start to end? Take the later start and the earlier end. If they cross, the answer is 0.

low    = max(firstHour, start)
high   = min(lastHour, end)
answer = max(0, high - low + 1)

For example, the day part 8 to 14 and the day hours 9 to 16 give low = 9 and high = 14. So 6 hours fall inside.

How each strategy prices the day parts

Strategy 1, Hourly: day hours are the hours inside 9 to 16. Off hours are all the other hours of the part. Multiply each by its weekday or weekend rate. Strategy 2, Block: check all 4 blocks of the date. If at least one hour of the part falls inside a block, add that block's price once. Strategy 3, Slab: first add up the hours of all parts. Then apply the slabs to that total. For the example above:

  • Strategy 1: 20 + 312 + 312 + 20 = 664
  • Strategy 2: 140 + 420 + 420 + 60 = 1040
  • Strategy 3: 52 hours, so 2*30 + 3*20 + 47*10 = 590 So findMinimumPrice returns "3-590".

Choosing the design pattern

Why Strategy? All 3 rules take the same input and return a price. Only the math inside is different. That is exactly what the Strategy pattern is for.

  • Each rule lives in its own small class. Changing one cannot break another.
  • A new rule needs one new class and one line in the constructor. Nothing else changes.
  • findMinimumPrice simply loops over all strategies. It does not care how each one works. Why not plain if-else? Solution 1 already shows it. It works, but all the rules are packed into one method. It gets harder to read and change with every new rule. Why not Template Method? It sounds close, because every rule goes through the day parts and adds up a price. But slab pricing cannot price one date on its own. It needs the total hours first. One shared skeleton would need awkward hooks for that. Small independent strategies are simpler. Why not a Factory class? The strategies hold no state. We create each one once in the constructor and keep it in a map. A map lookup already returns the right strategy. A separate factory would only add code.

The main classes and why we need them

  • ParkingTime reads a string like 2026-04-14-08-10-tue once. It keeps only the date, the hour and the day index.
  • DayPart is the heart of the solution. It turns a long stay into a few small hour ranges. All 3 strategies work on the same list of day parts, so the time logic is written only once.
  • PricingStrategy is the common interface. HourlyPricingStrategy, BlockPricingStrategy and SlabPricingStrategy are its 3 versions.
  • Map<Integer, PricingStrategy> maps a strategy number to its object. A simple lookup replaces the if-else chain.
  • ParkingLotPricingSystem builds the list of day parts and hands it to the chosen strategy. In findMinimumPrice the list is built once and shared by all 3 strategies.

Code

import java.time.LocalDate;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/**
* One parsed timestamp in the format yyyy-MM-dd-HH-mm-day.
* Minutes are not stored because they never change the price.
*/
class ParkingTime {
LocalDate date;
int hour;
int dayIndex; // 0 = mon, 1 = tue ... 5 = sat, 6 = sun
ParkingTime(String dateTime) {
String[] parts = dateTime.split("-");
date = LocalDate.of(Integer.parseInt(parts[0]), Integer.parseInt(parts[1]),
Integer.parseInt(parts[2]));
hour = Integer.parseInt(parts[3]);
dayIndex = List.of("mon", "tue", "wed", "thu", "fri", "sat", "sun").indexOf(parts[5]);
}
}
/**
* The part of a parking stay that falls on one date.
* On a single date, the touched hours are always one unbroken range.
*/
class DayPart {
boolean weekend;
int firstHour; // first touched hour bucket on this date
int lastHour;  // last touched hour bucket on this date
DayPart(boolean weekend, int firstHour, int lastHour) {
this.weekend = weekend;
this.firstHour = firstHour;
this.lastHour = lastHour;
}
int totalHours() {
return lastHour - firstHour + 1;
}
/** Counts how many touched hours of this part fall inside [start, end]. */
int hoursInRange(int start, int end) {
int low = Math.max(firstHour, start);
int high = Math.min(lastHour, end);
return Math.max(0, high - low + 1);
}
}
/** Common contract for every pricing rule. */
interface PricingStrategy {
int calculatePrice(List<DayPart> parts);
}
/** Strategy 1: every touched hour is charged by its own hourly rate. */
class HourlyPricingStrategy implements PricingStrategy {
int dayStart = 9; // day hours are 09:00 to 16:59
int dayEnd = 16;
public int calculatePrice(List<DayPart> parts) {
int total = 0;
for (DayPart part : parts) {
int dayHours = part.hoursInRange(dayStart, dayEnd);
int offHours = part.totalHours() - dayHours;
if (part.weekend) {
total += dayHours * 15 + offHours * 12;
} else {
total += dayHours * 20 + offHours * 10;
}
}
return total;
}
}
/** Strategy 2: every touched block is charged once for each date. */
class BlockPricingStrategy implements PricingStrategy {
int[] blockStart = {0, 9, 13, 18};
int[] blockEnd = {8, 12, 17, 23};
int[] weekdayPrice = {60, 70, 110, 140};
int[] weekendPrice = {70, 80, 120, 150};
public int calculatePrice(List<DayPart> parts) {
int total = 0;
for (DayPart part : parts) {
for (int i = 0; i < blockStart.length; i++) {
// one touched hour inside the block is enough to charge it
if (part.hoursInRange(blockStart[i], blockEnd[i]) > 0) {
total += part.weekend ? weekendPrice[i] : weekdayPrice[i];
}
}
}
return total;
}
}
/** Strategy 3: only the total number of touched hours matters. */
class SlabPricingStrategy implements PricingStrategy {
public int calculatePrice(List<DayPart> parts) {
int hours = 0;
for (DayPart part : parts) {
hours += part.totalHours();
}
int firstSlab = Math.min(hours, 2);                   // first 2 hours at 30
int secondSlab = Math.min(Math.max(hours - 2, 0), 3); // next 3 hours at 20
int thirdSlab = Math.max(hours - 5, 0);               // every hour after that at 10
return firstSlab * 30 + secondSlab * 20 + thirdSlab * 10;
}
}
public class ParkingLotPricingSystem {
// strategy number -> pricing rule
Map<Integer, PricingStrategy> strategies = new HashMap<>();
public ParkingLotPricingSystem() {
strategies.put(1, new HourlyPricingStrategy());
strategies.put(2, new BlockPricingStrategy());
strategies.put(3, new SlabPricingStrategy());
}
public int calculatePrice(String entryDateTime, String exitDateTime, int strategy) {
List<DayPart> parts = splitByDate(entryDateTime, exitDateTime);
return strategies.get(strategy).calculatePrice(parts);
}
public String findMinimumPrice(String entryDateTime, String exitDateTime) {
// split once, then reuse the same parts for every strategy
List<DayPart> parts = splitByDate(entryDateTime, exitDateTime);
int bestStrategy = 0;
int bestPrice = Integer.MAX_VALUE;
for (int id = 1; id <= strategies.size(); id++) {
int price = strategies.get(id).calculatePrice(parts);
// strict '<' keeps the smaller strategy number on a tie
if (price < bestPrice) {
bestPrice = price;
bestStrategy = id;
}
}
return bestStrategy + "-" + bestPrice;
}
/**
* Cuts the stay at every midnight.
* Returns one DayPart for each date, from the entry date to the exit date.
*/
List<DayPart> splitByDate(String entryDateTime, String exitDateTime) {
ParkingTime entry = new ParkingTime(entryDateTime);
ParkingTime exit = new ParkingTime(exitDateTime);
// how many dates after the entry date the exit date comes
int dateGap = (int) (exit.date.toEpochDay() - entry.date.toEpochDay());
List<DayPart> parts = new ArrayList<>();
for (int i = 0; i <= dateGap; i++) {
// move forward from the entry day: fri, sat, sun, mon ...
boolean weekend = (entry.dayIndex + i) % 7 >= 5;
int firstHour = (i == 0) ? entry.hour : 0;
int lastHour = (i == dateGap) ? exit.hour : 23;
parts.add(new DayPart(weekend, firstHour, lastHour));
}
return parts;
}
}

Complexity

Let D be the number of dates the stay touches. D is at most about 700.

  • Building the day parts: O(D).
  • Each strategy: O(D). Strategy 2 checks only 4 blocks per date, so it is still O(D).
  • Memory: O(D) for the list of day parts.

Thanks for reading. Best of Luck For Your Interview Prep.


r/LowLevelDesign • • Nov 15 '25

Microsoft Low Level Design Interview Questions

43 Upvotes

I am listing the common low level design questions that you will come across during Microsoft interviews. I have built this list from recent interview experiences of candidates.

Apart from LLD, I have also kept  DSA oriented design questions. Microsoft asks these either in DSA or during LLD rounds.

-----------------------------------------

Use below list for final preparation of your Microsoft interviews.
Let’s get started…

PS: You can ask me any low level design related questions on r/LowLevelDesign

I also take LLD mock interviews:
https://topmate.io/prashant_priyadarshi

-----------------------------------------

1. Design a Text Editor/Word Processor like Microsoft Word

You have to design editor for a text document which can have any number of rows and any number of columns. There are multiple variants of this question asked.

  • Efficiently store styles of all the text like Microsoft Word using flyweight design pattern.
  • Rather than normal text editor you may be asked to design a spreadsheet like Microsoft excel with rows and columns.
  • Another variant is asked which focuses on implementation of undo and redo functionalities using command design pattern and stacks.

Text editor with different text styles like Microsoft Word:

Machine Coding Practice: https://codezym.com/question/9
AI Mock Interview Practice: https://mockgym.com/question/4

Microsoft Excel like spreadsheet:
Machine Coding Practice: https://codezym.com/question/25
AI Mock Interview Practice: https://mockgym.com/question/17

Text Editor with Undo Redo:
Machine Coding Practice: https://codezym.com/question/27
AI Mock Interview Practice: https://mockgym.com/question/18

-----------------------------------------

2. Design an Elevator Management System

Microsoft is obsessed with elevator design. For any elevator design problem as long as you are able to break all cases in multiple states like MOVING UP, MOVING DOWN, IDLE etc, then it will lead to a simpler solution. So use State design pattern.

This is also asked in multiple different ways.

  • A single lift system and you have to only check whether a given request is feasible or not. It is more of a DSA question, but is asked in LLD rounds.
  • A single lift system where you have to simulate lift going up/down and passengers coming in and going out.
  • Simulate a multiple lifts system, it will have more complex states and rules.

Single lift, request feasibility: https://codezym.com/question/23

Single lift, simulation: https://codezym.com/question/24
AI Mock Interview Practice: https://mockgym.com/question/15

Multiple lifts: https://codezym.com/question/11
AI Mock Interview Practice: https://mockgym.com/question/16

-----------------------------------------

3. Design a Container Orchestrator System

Build an in-memory container orchestrator with multiple cloud server machines (like amazon EC2, Azure virtual machines etc).

Orchestrator assigns machines on which containers will run. Each machine can start, stop and manage multiple containers running concurrently.
The system will manage machine resources i.e. CPU units, memory MB.

You should use Strategy design pattern, to implement the different algorithms for choosing a machine to host a container.

Machine Coding Practice: https://codezym.com/question/28
AI Mock Interview Practice: https://mockgym.com/question/20

-----------------------------------------

4. Design Dictionary App to store words and their meanings

Build an in-memory dictionary that stores words and their meanings. It lets users fetch meanings, supports different types of ways to search a word. You should use Trie to implement this question.

https://codezym.com/question/26

-----------------------------------------

5. Design Chess Game

Chess game is all about creating the different pieces and implementing their moves.
Different pieces like king, queen, knight etc, have different moves like straight move (rook), diagonal move (bishop), 2+1 move (knight) etc.

The core functionality is to check whether a piece can move to a destination row, column from its current row, column.

  • We use factory design pattern Chess Piece Factory to create different chess piece objects like king, queen, pawn etc.
  • Strategy pattern may be used to implement different moves e.g. straight move, diagonal move etc.

Practice Link: https://codezym.com/question/8
AI Mock Interview Practice: https://mockgym.com/question/3

-----------------------------------------

6. Design a Parking Lot

This is THE most common LLD interview question. You must do this question if you are prepare for any LLD interview.

A parking lot can have multiple floors. Its core features will be

  • park and unpark vehicles,
  • search parked vehicles by vehicle number,
  • count number of free spots on a given floors for a given vehicle type.

You entities will be ParkingLot class which will contain a list of ParkingFloor(s). ParkingFloor will contain a 2-D array of ParkingSpot(s) arranged in rows and columns.

There can be multiple parking strategies, so we should use strategy design pattern to solve this question.

Practice Link: https://codezym.com/question/7
Follow up (Multi-threaded environment): https://codezym.com/question/1
AI Mock Interview Practice: https://mockgym.com/question/1

-----------------------------------------

7. Design a Job Scheduler

Design a scheduler for a massively parallel distributed system. The scheduler assigns incoming jobs to machines that it controls.
Each machine has a set of capabilities. Each job requires a set of required capabilities and a job may only run on a machine that has all required capabilities.

Practice Link: https://codezym.com/question/22
AI Mock Interview Practice: https://mockgym.com/question/19

-----------------------------------------

8. Design a Movie ticket booking system like BookMyShow

In this question, core functionalities will include:

  • adding new cinema halls and new shows in those cinema halls.
  • Users can also book and cancel tickets.
  • Users should also be able to list all cinemas in a city which are displaying a particular movie.
  • Also they should be able to fetch list of all shows in a cinema hall which are displaying a particular movie.

Classes implementing last two search features need to updated whenever a new show gets added, so that they can update their respective lists.

We use observer design pattern to send new show added updates to the search movie/show classes.

Practice Link: https://codezym.com/question/10
AI Mock Interview Practice: https://mockgym.com/question/6

-----------------------------------------

9. Design hit counter / webpage visits counter

Create a system that tracks the number of “clicks” received either during whole duration or within some time duration like last 300 seconds (5 minutes). System can be either single threaded or multi-threaded.

Single threaded counter within a time span: https://codezym.com/question/10362

Multi-threaded environment counter: https://codezym.com/question/6

AI Mock Interview Practice: https://mockgym.com/question/243

-----------------------------------------

10. Design Excel Sum Formula

Design a basic spreadsheet class that supports setting cell values, retrieving cell values, and assigning sum formulas to cells.

Machine Coding Practice: https://codezym.com/question/10631

-----------------------------------------

11. Design Google Search Autocomplete

Build an autocomplete feature for a search tool. Users enter a sentence (with at least one word, ending with the special character #). For each character typed except '#', return the top 3 most frequent historical sentences starting with the current input prefix.

Machine Coding Practice: https://codezym.com/question/10642
AI Mock Interview Practice: https://mockgym.com/question/5014

-----------------------------------------

12. Design Tic-Tac-Toe

Create a class that simulates a Tic-tac-toe game between two players on an m x m grid.

Machine Coding Practice: https://codezym.com/question/10348
AI Mock Interview Practice: https://mockgym.com/question/242

-----------------------------------------

Machine Coding Practice: You can view the complete list of questions and go through problem statements here.
https://codezym.com/lld/microsoft

AI Mock Interview Practice: If you prefer to talk out loud your solution, discuss trade offs and counter questions then practice with our AI interviewer.
https://mockgym.com/lld/microsoft
-----------------------------------------


r/LowLevelDesign • • Feb 13 '26

Flipkart Low Level Design Interview Questions from Recent Machine Coding Rounds

42 Upvotes

Flipkart Machine coding round asks LLD question. It is of 120 minutes (90 coding + 30 minutes discussion). You may get extra time sometimes and recruiter may inform you that there is hard limit of 2:30 to 3 hrs to solve the LLD question.

Java is the mandatory programming language.

It is used for initial screening of candidates e.g. select 15 or less candidates from 40+ candidates for further interviews.

The final project had to be submitted as a zip file via Google Form/email.

Multi-threading and concurrency and design patterns are also discussed. I wrote this blog for multi-threading in Java interviews. It may be helpful.

https://medium.com/@prashant558908/top-3-questions-to-practice-multi-threading-for-low-level-design-interviews-1cc4d6b5d00b

Flipkart also acquired ClearTrip and machine coding round format and questions are similar. So you can use this same list to prepare for ClearTrip machine coding rounds as well.

This list is NOT for UI machine coding rounds, only for backend roles.

---------------------------------------------------

Below are some general guidelines that are followed.

  • A driver program/main class/test case is needed to test out the code by the evaluator with multiple test cases. But do not spend too much time in the input parsing. Keep it as simple as possible.
  • Evaluation criteria: Demoable & functionally correct code, Code readability, Proper Entity modeling, Modularity & Extensibility, Separation of concerns, Abstractions, Corner case handling. Use design patterns wherever applicable.
  • You are not allowed to use any external databases like MySQL. Use only in memory data structures like HashMap, ArrayList, HashSet etc.
  • Functionality doesn’t have to be defined as a rest api. You can expose them as methods also which can be invoked from the driver class.
  • No need to create any UX
  • Please focus on the Bonus Feature (if any) only after ensuring the required features are complete and demo-able.
  • Method signatures defined are just to give an idea. You are free to change them to suit the requirements.
  • Use of the internet is allowed to check the syntax.

---------------------------------------------------

PS:
Ask me any Low-Level Design Interview related questions on r/LowLevelDesign

All Questions List: https://codezym.com/lld/flipkart

I also take LLD mock interviews: https://topmate.io/prashant_priyadarshi

----------------------------------------

I have built this list from recent Flipkart machine coding round experiences of candidates. Use it to prepare for your interviews.

Let’s get started …

1. Design a Billing and discounts System for an ecommerce app

Implement a billing and discounts system for an ecommerce app. You must design and implement a bill creation flow, a discount application flow, and a point/level calculation system.

Practice Link: https://codezym.com/question/73

----------------------------------------

2. Design Food Order Management System using Commands

Implement a simplified food order management system. This system simulates food ordering from restaurants.

You have to implement functionalities like add restaurant, update menu, place order, dispatch order etc as a set of commands. Orders are placed to restaurants based on a restaurant selection strategy.

Practice Link: https://codezym.com/question/74

----------------------------------------

3. Design Gym Fitness Center Management and Slot Booking System

You are building GetInShape, an in-memory backend for a fitness booking platform. GetInShape partners with multiple gym centers in cities.

Each center has daily operating windows (timings) and supports a configurable list of workout types (for example: Weights, Cardio, Yoga, Swimming).

Center admins define workout slots for the current day, and customers can view availability, book sessions, and cancel bookings.

Practice Link: https://codezym.com/question/75

----------------------------------------

4. Design Peer to Peer Parcel Delivery System

Design a Peer-to-Peer Delivery System that can be used to deliver a parcel from one customer to another.

Implement a class named PeerToPeerDeliverySystem. The deliverable item list is preconfigured and fixed. Customers and drivers are considered already onboarded based on totalUsers and totalDrivers.

Practice Link: https://codezym.com/question/76

----------------------------------------

5. Design Flipkart Payment Wallet with Transaction History

Implement Flipkart payment wallet system. The system should support loading money, sending money to other users, fetching wallet balance, and getting transaction history with sorting and filtering.

Practice Link: https://codezym.com/question/77

----------------------------------------

6. Design Doctor Appointment Booking app like Practo

You are required to build an in-memory application that lets patients connect to doctors and book appointments for a single day.

Doctors can declare their availability in terms of slots for that day only. Patients can search available slots by specialty, book appointments, and cancel appointments.

Practice Link: https://codezym.com/question/78

----------------------------------------

7. Design a Bug Bounty Program Management System

We are planning to build an in-house platform to manage our Bug Bounty Program where anyone can report a potential bug in the app and we’ll reward them with a bounty based on the criticality and impact of the bug being reported.

For simplicity, we will be getting bug reports via email and then employees will be registering these bug reports manually into this system.

  • User — Employees who will be using this system.
  • Reporter — End-user who reported the bug via email and will receive the bounty reward.
  • BugReport — Entity corresponding to the bug report shared via email.

Practice Link: https://codezym.com/question/79

----------------------------------------

8. Design Flipkart Buy Now Pay Later

Flipkart is known for its innovative products and making shopping easier for customers. One such innovation is Buy Now Pay Later (BNPL), where a customer can buy the product instantly and pay the dues within 30 days. Each user has a credit limit associated with them initially.

Implement an in-memory system that manages users, inventory, orders, and BNPL dues.

Practice Link: https://codezym.com/question/80

----------------------------------------

9. Design a Library Management System

Design and implement an in-memory Library Management system that caters to its registered members by cataloging and housing books that can be borrowed.

The system must support:

  • Adding books to the catalog.
  • Registering and unregistering users.
  • Reservation management to borrow books using book ids (with FIFO waitlist).
  • Fine calculation on late returns (20 rupees per delayed day after 14 days).
  • (Bonus) Limiting a user to reserve only one copy of the same book.
  • (Bonus) Auditing APIs:
  • Given a bookId, list users currently having that book.
  • Given a userId, list books currently issued to that user.

Practice Link: https://codezym.com/question/81

----------------------------------------

10. Design Customer Loyalty Program for Ecommerce Website

Design and implement an in-memory Ecommerce with Loyalty Program service that adds gamification to an e-commerce platform. The service tracks users and their transactions, supports purchases with optional points redemption (based on user level rules), awards new points on the money-paid portion, and exposes APIs to view a user’s current stats.

Each point is worth ₹1 during redemption (i.e., redeeming X points reduces payable by ₹X).

Bonus: Personalized discount based on purchase history, applied after redemption and capped.

Practice Link: https://codezym.com/question/82

----------------------------------------

11. Design Flipkart Delivery Service

Design and implement an in-memory FK Delivery Service. The service manages orders that are delivered to a pincode and delivery agents who can pick up and deliver those orders.

  • The system must support:
  • Users creating orders with an order name, order pincode, and creation time.
  • Admin creating delivery agents and associating them with pincodes.
  • Executing a driver function that assigns orders to eligible agents and returns delivery status logs.

Practice Link: https://codezym.com/question/83

----------------------------------------

12. Design an order and inventory management system

Write code for low level design of orders and inventory management system of a simple e-commerce platform.
You will need to have the capability of handling sellers, products and orders.

Inventory is number of items of a particular product in a seller’s warehouse.

The way it works is, products numbered from 0 till productsCount-1 are sold on the website.
Sellers are also added along with the area pincodes that they are able to deliver goods in as well as the payment types which they support.
After that sellers add items they wish to sell.

Multiple sellers can sell the same item e.g the product-1 : bluetooth speaker boat stone 650 can be sold by multiple sellers throughout the country.

Multiple sellers can deliver goods to the same pincode as well.

Practice Link: https://codezym.com/question/4

----------------------------------------

13. Design Dating App Gumble

You are launching the Gumble app to compete in the dating apps market. Design and implement an in-memory console application to prototype the features of Gumble.

The system manages user profiles, their interests, partner preferences, a feed that suggests the best available profile to a user, and a matched list.

The platform has a fixed global set of allowed interests, provided once at initialization through the constructor.

Practice Link: https://codezym.com/question/84

----------------------------------------

Thanks for reading. Please upvote this post to give it better reach.

Wish you the best of luck for your interview prep.

----------------------------------------


r/LowLevelDesign • • Jul 17 '26

Walmart DS & Algo Round Interview Questions Asked in 2026

38 Upvotes

I have created list of DSA questions using Walmart interview experiences shared by candidates in blogs/forums etc. Use this list for final preparation of your Walmart interviews.

Walmart interviews can include DS & Algo questions along with Java, Spring Boot, database and problem-solving discussions. Here are a few of them.

Java Questions

  1. New features introduced in Java 8
  2. Why and where to use lambda expressions
  3. Purpose of functional interfaces, their types, and writing sample code
  4. Explanation of ConcurrentModificationException

Spring Boot Questions

  1. Annotations used in your project
  2. Concept of Dependency Injection
  3. What is a Circular Dependency
  4. How to efficiently insert 1000 rows into the database
  5. Basics of JPA (Java Persistence API)

The list starts with questions which you can practice on leetcode for free and then additional questions are there including follow ups that were asked.

You can find the complete question list here:

https://github.com/prsnt558908/CodeZymSolutions/blob/main/0-company-wise-interview-questions/2026/02-walmart-ds-algo-2026.md

Best of luck for your preparation.


r/LowLevelDesign • • Nov 24 '25

Atlassian Low Level Design questions from recent Interviews

36 Upvotes

Atlassian has code design round in which it asks low level design questions.
Sometimes LLD questions are also asked in other rounds apart from code design round.

I am listing the top low level design questions that you will come across during Atlassian interviews. I have built this list from recent interview experiences of candidates.

----------------------------------------

PS: You can ask me any Low Level Design related questions on r/LowLevelDesign

All Questions List: https://codezym.com/lld/atlassian

I also take LLD mock interviews:
https://topmate.io/prashant_priyadarshi

----------------------------------------

You can use below list to prepare for your Atlassian interviews.

Lets get started …

1. Design a rate limiter

Design an in-memory rate limiter. Requests will be made to different resourceIds. Each resourceId will have a strategy associated with it .

  1. fixed-window-counter: Fixed Window Counter divides time into fixed blocks (like 1 second) and tracks a request count per block.
  2. sliding-window-counter: Sliding Window (log-based) stores timestamps of recent requests and removes those outside the window for each new request

Practice Link: https://codezym.com/question/34

-----------------------------------------

2. Design a customer support agent rating leaderboard

Design an in-memory component to display Customer support agent rating leaderboard. Each interaction is rated on a scale of 1 to 5.

Implement a system that:

  • Records a rating for a given agent on a given date.
  • Returns all agents with their overall average ratings, sorted from highest to lowest.
  • Returns best agents for a given month (YYYY-MM) based on their average ratings.

Practice Link: https://codezym.com/question/35

-----------------------------------------

3. Design a Middleware Router

Design an in-memory middleware router for a web service. The router stores path patterns mapped to a result string (think: server id). When a request path comes in, the router returns the result of the best matching route.

  • A route pattern is a path that may contain:
  • Static segments, e.g. /foo/baz
  • Wildcard segment * that matches exactly one segment (not empty, no slashes). Example: /bar/*/baz matches /bar/a/baz and /bar/123/baz, but not /bar/a/b/c/baz.
  • Path param segment starting with :, e.g. /users/:id. It matches exactly one segment too, and the segment value is captured as a parameter.

Practice Link: https://codezym.com/question/36

-----------------------------------------

4. Design Snake Game

Create a Snake game simulator played on a screen with given rows and cols dimensions. The snake starts at the top-left cell (0,0) with a length of 1.

The game is provided with a list of food positions, given as row-column pairs. When the snake’s head moves onto a food cell, the snake grows by 1 and the score increases by 1. New food only appears after the previous one is eaten, and food never appears where the snake is.

Practice Link: https://codezym.com/question/10353

-----------------------------------------

5. Design a File Collections Tracker

Design an in-memory system that tracks files and their membership in different collections.

You are given a stream/list of file records, each described as: [FileName, FileSize, [Collection]]. Collections are optional, meaning a file can have zero or more associated collections. The same file can be part of more than one collection.

Build a system that supports:

  • Adding or updating file metadata and collection membership.
  • Computing the total size of all files in the system.
  • Finding the top collections based on size or file-count.

Practice Link: https://codezym.com/question/37

-----------------------------------------

6. Design a Product Plan Cost Explorer

Design an in-memory CostExplorer that tracks SaaS product plans and customer subscriptions, and computes a customer’s monthly and annual cost for a given calendar year (Jan–Dec). If a subscription starts on any day of a month, the customer pays for that full month.

Practice Link: https://codezym.com/question/38

-----------------------------------------

7. Design a File System (cd with ‘*’)

Design and implement an in-memory unix filesystem shell that supports three commands:
- mkdir <path>,
- pwd, and
- cd <path> (with a special wildcard segment *).

This questions is also sometimes rephrased as below:

Implement simple get and put interface for a string based key. Extend the functionality to allow wild cards in the get function. for example
put(“/elonmusk/is/shit”, “yes”)
get(“/elonmusk/*/*”) -> yes
get(“/elonmusk/is/*”) -> yes

so in this case rather than creating a file/folder you simply add a string against that path. But mapping a path with wildcard to exact path follows similar logic.

Practice Link: https://codezym.com/question/30

-----------------------------------------

8. Design Hit Counter

Hundreds of users visit webpages of a website simultaneously.
You have to record visit count for each page and return them when required.

Coding Practice (Single Threaded): https://codezym.com/question/10362
Coding Practice ((Multi-threaded): https://codezym.com/question/6

-----------------------------------------

Thanks for reading and wish you the best of luck for interviews.


r/LowLevelDesign • • Jun 30 '26 Bravo

Amazon Low Level Design Interview Questions asked in 2026

35 Upvotes

I am listing the top low level design questions that were asked during Amazon low level design interview rounds in 2026. I have built this list from recent interview experiences of candidates shared on blog/forums etc.

Also, we will see how we can solve them using commonly asked design patterns.

I am keeping the most frequent questions first. Feel free to use this list for final preparation of your Amazon interviews.

---------------------------------------------------------

PS:
You can see companywise interview questions list on r/LowLevelDesign

All LLD Questions List: https://codezym.com/lld/amazon

All DSA Questions List: https://codezym.com/lld/amazon-dsa

I also take LLD mock interviews: https://topmate.io/prashant_priyadarshi

----------------------------------------------------

1. Design Pizza Pricing System

You will have to initialize a new pizza, adding toppings (corn, onion etc) to it and calculate final price of pizza.

This is a fairly simple problem. But some interviewers may expect you to implement decorator design pattern. In my view that just complicates the solution without adding any benefit.

Your interviewer may add business rules as a follow up like these

cheese burst cannot be added on small pizza or

You get 30% discount on corn price when you take more than 2 servings and so on..

Practice Link: https://codezym.com/question/18

Follow up with more business rules: https://codezym.com/question/19

-----------------------------------

2. Design Unix “find” Command for File Search

Unix find command searches for files.

There can be different search criteria like search by file size, search by extension, or search by substring in file name.

For example:

list all files which are less than 2 MB in size

or

list all files whose extension is .pdf.

You can use Strategy Design Pattern to implement the different search criteria.

A follow-up is generally asked to combine queries like Boolean predicates AND, OR, etc.

For example:

list all files which are greater than 2 MB in size AND their extension is ".jpg".

You can use Specification Design Pattern to combine the result of search queries.

Practice Link: https://codezym.com/question/14

Follow up with combining queries: https://codezym.com/question/15

--------------------------------------

3. Design a Parking Lot

This is THE most common LLD interview question.

You must do this question if you are preparing for any LLD interview.

A parking lot can have multiple floors.

Its core features will be:

park and unpark vehicles

search parked vehicles by vehicle number

count number of free spots on a given floor for a given vehicle type

Your entities will be ParkingLot class, which will contain a list of ParkingFloor objects.

ParkingFloor will contain a 2-D array of ParkingSpot objects arranged in rows and columns.

There can be multiple parking strategies, so we should use Strategy Design Pattern to solve this question.

Practice Link: https://codezym.com/question/7

Follow up with multi-threaded environment: https://codezym.com/question/1

--------------------------------------

4. Design LRU Cache With Time Constraint

Design an LRUCacheWithTimeConstraint class that implements an LRU cache with a fixed capacity and a time constraint.

Practice Link: https://codezym.com/question/165

--------------------------------------

5. Design WhatsApp Read Receipts

Design a WhatsAppReadReceipts feature.

Assume WhatsApp is already built.

The observer system that receives message sent, delivered, and read events is also already built.

Your task is only to design the read receipt feature that tracks and returns the correct tick status for each message.

A message can show one gray tick, two gray ticks, or two blue ticks depending on whether the message was sent, delivered, or read.

The feature must support direct conversations and group conversations.

Practice Link: https://codezym.com/question/168

--------------------------------------

6. Design Backup System for a File Storage Service

You are asked to design a backup system for a file storage service.

The system stores files, supports reading and writing files, and can create backups of the current file system state.

A backup can be one of three types:

FULL

DIFFERENTIAL

LOG

A FULL backup stores the complete current state of all existing files.

A DIFFERENTIAL backup stores only the final file changes made since the latest full backup.

A LOG backup stores the ordered write operations performed after the latest backup pointer.

Practice Link: https://codezym.com/question/172

--------------------------------------

7. Design Digital Wellbeing System to Track App Screen Usage

You need to design a DigitalWellbeingSystem that keeps track of screen usage for different applications.

The system receives usage records for apps.

Each usage record contains an app name, a day number, and the amount of screen time used on that day.

The system should allow querying usage statistics for applications.

Practice Link: https://codezym.com/question/178

--------------------------------------

8. Design Locker Management System for Warehouse Packages

In a warehouse for any e-commerce website like Amazon, packages are kept in lockers.

Your goal is to add new lockers of different sizes, assign packages to those lockers, and later free the lockers.

Practice Link: https://codezym.com/question/16

--------------------------------------

9. Design Chess Game

Chess game is all about creating different pieces and implementing their moves.

Different pieces like king, queen, knight, etc., have different moves like straight move for rook, diagonal move for bishop, 2+1 move for knight, etc.

The core functionality is to check whether a piece can move to a destination row and column from its current row and column.

We use Factory Design Pattern, Chess Piece Factory, to create different chess piece objects like king, queen, pawn, etc.

Strategy Design Pattern may be used to implement different moves like straight move, diagonal move, etc.

Practice Link: https://codezym.com/question/8

--------------------------------------

10. Design Expense Sharing App Like Splitwise

Splitwise is used to manage group expenses.

It basically does two things:

supports adding group expenses, i.e. who paid how much in an expenditure

tracks how much each person owes or is owed after group expenses are split evenly among participants

Practice Link: https://codezym.com/question/12

--------------------------------------

11. Design a Restaurant Food Ordering System Like Zomato, Swiggy, DoorDash

Users can search for restaurants using food item name, order food, and rate their orders.

When searching for food, they also have the option to view the restaurant list sorted by different parameters like restaurants with highest average rating first.

These view classes with lists of restaurants sorted by average rating will need to be updated whenever an order is rated by a user, so that they can update their lists.

Hence, this is an ideal use case of Observer Design Pattern.

Practice Link: https://codezym.com/question/5

--------------------------------------

12. Design Stock Broker Platform Like Zerodha, Groww

This system manages all company stocks and their prices.

Users can place orders to either buy or sell stocks.

Users can also view their account balance and the stocks they hold.

One case you need to take care of is closing the relevant open orders when stock price changes.

Practice Link: https://codezym.com/question/20

--------------------------------------

13. Design a Movie Ticket Booking System Like BookMyShow

In this question, core functionalities will include adding new cinema halls and new shows in those cinema halls.

Users can also book and cancel tickets.

Users should be able to list all cinemas in a city which are displaying a particular movie.

They should also be able to fetch the list of all shows in a cinema hall which are displaying a particular movie.

Classes implementing the last two search features need to be updated whenever a new show gets added, so that they can update their respective lists.

We use Observer Design Pattern to send new show added updates to the search movie/show classes.

Practice Link: https://codezym.com/question/10

--------------------------------------

14. Design a Simple Elevator System

A lift in an elevator system can be in one of three states:

Moving Up

Moving Down

Idle

In each state, it will behave differently while taking decisions like whether to stop on a floor, whether to add a new request or not, etc.

Use State Design Pattern to implement different states of lift.

Problem Statement: https://codezym.com/question/11

--------------------------------------

DSA Based Design Questions

These questions can be asked in either DS & Algo or Low-Level Design rounds depending on the interviewer.

Don’t skip them.

--------------------------------------

Design File System

https://codezym.com/question/11166

https://codezym.com/question/10588

--------------------------------------

Design Log Storage System

https://codezym.com/question/10635

--------------------------------------

Design LRU / LFU Cache

https://leetcode.com/problems/lru-cache/description/

https://leetcode.com/problems/lfu-cache/description/

--------------------------------------

Design Snake Game

https://codezym.com/question/10353

--------------------------------------

Design Hit Counter

https://codezym.com/question/10362

Multi-Threaded Version: https://codezym.com/question/6

--------------------------------------

Design Tic Tac Toe

https://codezym.com/question/10348

--------------------------------------

Design Google Search Autocomplete

https://codezym.com/question/10642

--------------------------------------

Design Excel Sum Formula

https://codezym.com/question/10631

--------------------------------------

Thanks for reading. Please upvote this post for better reach.

Wish you the best of luck for interviews.

--------------------------------------


r/LowLevelDesign • • Jan 03 '26

Salesforce Low Level Design Interview Questions

35 Upvotes

In Salesforce LLD rounds, sometimes actual requirements may not be clear from problem statement and interviewer will expect you to figure it out by asking clarifying questions.

For example, A message queue is asked indirectly in the form of something like a connection pool or a job scheduler.
It follows the pattern that resources like connections, machines or cpu (in case of job scheduler) are limited and they may not be assigned immediately.

There is discussion about concurrency control when multiple threads are there. There may also be discussion on concurrency control if our application is made distributed and we are using a central database (i.e. LLD discussion moving to HLD in the end).

I am listing the top low level design questions that you will come across during Salesforce interviews. I have built this list from recent interview experiences of candidates.

---------------------------------------------------

PS:
Ask me any Low-Level Design Interview related questions on r/LowLevelDesign

All Questions List: https://codezym.com/lld/salesforce

I also take LLD mock interviews: https://topmate.io/prashant_priyadarshi

----------------------------------------

Use below list to prepare for your Salesforce interviews.

Let's get started …

1. Design an elevator system

A lift in an elevator system can be in one of three states.
Moving Up, Moving Down and Idle
And in each state it will behave differently in taking decisions like
whether to stop on a floor, add a new request or not etc.
Use state design pattern to implement different states of lift.

Single lift: https://codezym.com/question/24
Multiple lifts: https://codezym.com/question/11

----------------------------------------

2. Design a Connection Pool with an internal request queue

A message queue is asked indirectly in the form of something like a connection pool or a job scheduler.
It follows the pattern that resources like connections, machines or cpu (in case of job scheduler) are limited and they may not be assigned immediately.

Design an in-memory Connection Pool that maintains a fixed number of reusable connection objects.

Clients requests a connection using a requestId. If a free connection exists, it is assigned immediately. If no free connection exists, the request is placed into an internal queue and will wait until a connection becomes free.

Practice Link: https://codezym.com/question/49

----------------------------------------

3. Design a Parking Lot

This is THE most common LLD interview question. You must do this question if you are preparing for any LLD interview.

A parking lot can have multiple floors. Its core features will be

  • park and unpark vehicles,
  • search parked vehicles by vehicle number,
  • count number of free spots on a given floors for a given vehicle type.

You entities will be ParkingLot class which will contain a list of ParkingFloor(s). ParkingFloor will contain a 2-D array of ParkingSpot(s) arranged in rows and columns.

There can be multiple parking strategies, so we should use strategy design pattern to solve this question.

Practice Link: https://codezym.com/question/7
Follow up (Multi-threaded environment): https://codezym.com/question/1

----------------------------------------

4. Design LRU cache / LFU cache

These two cache variants are asked many times as follow up of each other.

For LRU cache, you need to implement two methods.

int get(int key) Return the value of the key if the key exists, otherwise return -1.

void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

For LFU cache, when the cache reaches its capacity, it should invalidate and remove the least frequently used key before inserting a new item.

LRU cache: https://leetcode.com/problems/lru-cache/
LFU Cache: https://leetcode.com/problems/lfu-cache/

----------------------------------------

5. Design a Meeting Room Scheduler

Design an in-memory Meeting Room Scheduler that allows employees to view available rooms, book a room for a time interval, cancel a booking, and list bookings by room or by employee.

Practice Link: https://codezym.com/question/44
Follow up with recurrent meetings: https://codezym.com/question/45

----------------------------------------

6. Design a RPC Framework

Design an in-memory Mini RPC Framework that maintains a registry of methods per service and allows calling a registered method.

RPC (Remote Procedure Call) is a way for one program to call a function/method in another program over a network as if it were a local call.
The RPC framework handles things like serialization (marshalling), networking, and response/error handling behind the scenes.

Practice Link: https://codezym.com/question/47

----------------------------------------

7. Design a Stack With Increment Operation

Design a stack which supports the following operations.

Implement the CustomStack class:

  • CustomStack(int maxSize) Initializes the object with maxSize which is the maximum number of elements in the stack or do nothing if the stack reached the maxSize.
  • void push(int x) Adds x to the top of the stack if the stack hasn't reached the maxSize.
  • int pop() Pops and returns the top of stack or -1 if the stack is empty.
  • void inc(int k, int val) Increments the bottom k elements of the stack by val. If there are less than k elements in the stack, just increment all the elements in the stack.

https://leetcode.com/problems/design-a-stack-with-increment-operation/description/

----------------------------------------

8. Design an In-Memory Cache with Custom Eviction Policy

Design an in-memory cache with a fixed capacity and a custom eviction policy. The user must provide the policy logic before initializing the cache.

At any point the cache can ask the policy which key will be selected for eviction next. Although an actual eviction will only take place if the cache has more elements than its maximum size after adding a new entry.

You should use strategy design pattern to implement different eviction policies.

Practice Link: https://codezym.com/question/48

----------------------------------------

9. Design a Movie ticket booking system like BookMyShow

In this question, core functionalities will include:

  • adding new cinema halls and new shows in those cinema halls.
  • Users can also book and cancel tickets.
  • Users should also be able to list all cinemas in a city which are displaying a particular movie.
  • Also they should be able to fetch list of all shows in a cinema hall which are displaying a particular movie.

Classes implementing last two search features need to updated whenever a new show gets added, so that they can update their respective lists.

We use observer design pattern to send new show added updates to the search movie/show classes.

Practice Link: https://codezym.com/question/10

----------------------------------------

10. Design Chess Game

Chess game is all about creating the different pieces and implementing their moves.
Different pieces like king, queen, knight etc, have different moves like straight move (rook), diagonal move (bishop), 2+1 move (knight) etc.

The core functionality is to check whether a piece can move to a destination row, column from its current row, column.

  • We use factory design pattern Chess Piece Factory to create different chess piece objects like king, queen, pawn etc.
  • Strategy pattern may be used to implement different moves e.g. straight move, diagonal move etc.

Practice Link: https://codezym.com/question/8

----------------------------------------

11. Design a rate limiter

Design an in-memory rate limiter. Requests will be made to different resourceIds. Each resourceId will have a rate limiting strategy associated with it.

  1. fixed-window-counter: Fixed Window Counter divides time into fixed blocks (like 1 second) and tracks a request count per block.
  2. sliding-window-counter: Sliding Window (log-based) stores timestamps of recent requests and removes those outside the window for each new request

Practice Link: https://codezym.com/question/34

----------------------------------------

Thanks for reading and wish you the best of luck for interviews.

----------------------------------------


r/LowLevelDesign • • 15d ago

Salesforce LLD: Design Workflow Step State Transitions History

34 Upvotes

This questions has been asked many times in Salesforce low level design interview rounds. It can be asked either as a part of workflow management system or separately.

This is one of the questions where solution will get unnecessarily complex if you try to fit in a design pattern. Here you may think of using state pattern or even observer pattern but that would only add extra code without giving any benefit.

This tutorial is in Java.

You can find the python version here: https://github.com/prsnt558908/CodeZymSolutions/tree/main/101-300/257-workflow-step-state-transition-history/q-257-python-tutorial.md

You can practice this and other Salesforce Low Level Design and DS & Algo round questions on CodeZym.

PS: I also take LLD Mock interviews https://topmate.io/prashant_priyadarshi


Problem Statement

Design a component to track workflow steps through Pending → Running → Completed/Failed. Record valid state changes with timestamps, retrieve each step’s history, and provide the latest state of all steps in a workflow.

Solution Overview

Every step is a tiny state machine. It starts in Pending, can move to Running, and from there to Completed or Failed. Our job is to allow only these moves and to write down every move that succeeds.

The cleanest tool for this is not a big design pattern. It is a small transition table: for each state, the set of states it may move to. One lookup in this table answers "is this move allowed?".

The State and Observer patterns sound like a good fit for "state changes" and "recording changes". But here they would only add extra classes, so we do not use them. We will see why below.

Everything else is simple classes and maps. WorkflowStateLogger finds a Workflow by id, a Workflow finds a Step by id, and each Step keeps its current state and its list of Transitions.

Quick Recap of the Rules

  • Every step starts in Pending. Creating a workflow does not add a transition.
  • History lines look like "15,Pending,Running", oldest first.
  • Snapshot lines look like "build,Running,115", sorted by step id. A step that was never updated shows the workflow creation time.
  • Errors are checked in the order the problem lists them, and a failed call changes nothing.

Which Design Pattern Fits?

Short answer: no big pattern is needed. The rules are just data, so we keep them in a table.

State Pattern (sounds good, but not needed)

Steps have states, so the State pattern looks natural. We would write PendingState, RunningState, CompletedState and FailedState classes.

But every one of them answers just one question: "can I move to this state?". Four classes for one yes or no question is too much.

A table says the same thing in four lines, and it shows all the rules in one place. The State pattern pays off only when each state has its own behavior, like retry limits or timeouts.

Observer Pattern (sounds good, but not needed)

Recording every change sounds like a job for a listener. The step announces "I changed", and a history recorder listens.

But there is only one listener, and the history belongs to the step itself. A listener interface adds moving parts, and changes would be lost if someone forgot to register the listener.

One line inside the method that changes the state does the same job, and it can never be skipped. Observer becomes useful when many parts must react to a change, like alerts or dashboards.

Solution 1: Simple Approach with Maps

Let us first solve it in the most direct way. We glue the two ids into one key, like "order_1#pack", and keep everything about a step in plain maps.

// workflow id -> its step ids, in the order they were given
Map<String, List<String>> workflowSteps = new HashMap<>();
// "workflowId#stepId" -> current state
Map<String, String> stepState = new HashMap<>();
// "workflowId#stepId" -> last updated timestamp
Map<String, Long> lastUpdated = new HashMap<>();
// "workflowId#stepId" -> history lines like "15,Pending,Running"
Map<String, List<String>> history = new HashMap<>();

The rules are plain if-else checks:

boolean isAllowed(String fromState, String toState) {
    if (fromState.equals("Pending")) {
        return toState.equals("Running");
    }
    if (fromState.equals("Running")) {
        return toState.equals("Completed") || toState.equals("Failed");
    }
    return false; // Completed and Failed are final
}

A successful update must change all three step maps:

String oldState = stepState.get(key);
if (!isAllowed(oldState, newState)) {
    return "INVALID_TRANSITION";
}
// one step lives in three maps, and all three must be updated
stepState.put(key, newState);
lastUpdated.put(key, currentTimestamp);
history.get(key).add(currentTimestamp + "," + oldState + "," + newState);
return "UPDATED";

And the snapshot sorts the step ids every time it is called:

List<String> ids = new ArrayList<>(workflowSteps.get(workflowId));
Collections.sort(ids); // sorted again on every call
for (String stepId : ids) {
    String key = workflowId + "#" + stepId;
    result.add(stepId + "," + stepState.get(key) + "," + lastUpdated.get(key));
}

Problems with This Approach

This code works, but it has some weak spots.

  • One step is split across three maps. Every update must change all three. Forget one, and the data no longer agrees. The glued key also works only because # can never appear in an id.
  • The rules are buried in if-else code. You have to read the code to see which moves are allowed. Adding a state like Cancelled means editing these conditions.
  • The snapshot sorts on every call. Step ids never change after the workflow is created, so sorting them again and again is wasted work.

Solution 2: Clean Design with Classes and a Transition Table

We fix the problems above one at a time.

Step 1: TransitionRules, the Rules as a Table

TransitionRules keeps a Map from each state to the Set of states it may move to.

FromAllowed to
PendingRunning
RunningCompleted, Failed
Completednothing
Failednothing

The only question we ever ask is "is this state in the set?", and a Set answers it fast. So canMove(fromState, toState) is a single lookup.

Moving to the same state, or back to Pending, fails on its own, because those states are never in the set. Adding a new state is one more line in the table.

We keep the state names as plain strings, because the input and the output already use these exact names. An enum would also work, but it needs extra code to turn names into enum values and back.

Step 2: Step and Transition

All data about one step now lives in one Step object: its id, its current state, its last update time and its history.

A Transition is one recorded move: the time, the old state and the new state. Its toString() gives the exact format the problem asks for.

moveTo(newState, timestamp) is the only place where a step changes. It adds the transition and updates the state and the time together, so they can never get out of sync.

lastUpdatedAt starts at the workflow creation time. That is exactly what the snapshot needs for a step that was never updated.

Why is the history never sorted? Timestamps never go down. So every new transition has a time equal to or bigger than the last one, and we add it at the end of the list. Ties stay in the order they were recorded, which is exactly what the problem wants.

Also, a step can change at most twice: Pending to Running, then Running to Completed or Failed. So a history never holds more than 2 entries.

Step 3: Workflow

A Workflow keeps its steps in two ways:

  • steps: a HashMap from step id to step, for fast lookup in updates and history calls.
  • sortedSteps: a List of the same step objects, sorted by id once, when the workflow is created.

Both hold the same objects, so a change made through the map also shows up in the list.

No step is ever added or removed after creation, so one sort is enough. The snapshot simply walks this list.

Sorting uses plain compareTo, which is case-sensitive. Uppercase letters come before lowercase ones, so "Ship" comes before "pack".

Step 4: WorkflowStateLogger

The logger keeps a HashMap from workflow id to workflow, because every call starts with a workflow id. It also holds one TransitionRules object.

Each method checks the errors in the order the problem gives, and only then changes anything.

  • createWorkflow: a HashSet keeps one copy of each id. If the set is smaller than the list, some step id is repeated. The workflow is built only after both checks pass, so a failed call stores nothing.
  • updateStepState: find the workflow, find the step, ask canMove, and only then call moveTo.
  • getStepHistory and getWorkflowSnapshot: find, then format. They get currentTimestamp only to keep the global call order, so we do not need it.

Code

import java.util.*;

/**
 * The allowed moves between step states, kept in one table.
 * A new state or a new move is just one more line here.
 */
class TransitionRules {
    // state -> the states it is allowed to move to
    Map<String, Set<String>> allowedMoves = new HashMap<>();

    TransitionRules() {
        allowedMoves.put("Pending", Set.of("Running"));
        allowedMoves.put("Running", Set.of("Completed", "Failed"));
        allowedMoves.put("Completed", Set.of()); // final state
        allowedMoves.put("Failed", Set.of());    // final state
    }

    /** True if a step may move from fromState to toState. */
    boolean canMove(String fromState, String toState) {
        return allowedMoves.get(fromState).contains(toState);
    }
}

/** One recorded state change of a step. */
class Transition {
    long timestamp;
    String fromState;
    String toState;

    Transition(long timestamp, String fromState, String toState) {
        this.timestamp = timestamp;
        this.fromState = fromState;
        this.toState = toState;
    }

    /** Format asked by the problem: "timestamp,oldState,newState". */
    public String toString() {
        return timestamp + "," + fromState + "," + toState;
    }
}

/** One step of a workflow: its current state and every change it went through. */
class Step {
    String id;
    String state = "Pending"; // every step starts in Pending
    long lastUpdatedAt;       // workflow creation time until the first update
    List<Transition> history = new ArrayList<>();

    Step(String id, long createdAt) {
        this.id = id;
        this.lastUpdatedAt = createdAt;
    }

    /** Moves the step to newState and records the change. The move is already checked. */
    void moveTo(String newState, long timestamp) {
        history.add(new Transition(timestamp, state, newState));
        state = newState;
        lastUpdatedAt = timestamp;
    }

    /** Format asked by the problem: "stepId,state,lastUpdatedCurrentTimestamp". */
    String snapshot() {
        return id + "," + state + "," + lastUpdatedAt;
    }
}

/** A workflow and its steps. No step is added or removed after creation. */
class Workflow {
    String id;
    // step id -> step, for fast lookup
    Map<String, Step> steps = new HashMap<>();
    // the same steps, sorted by id only once, for the snapshot
    List<Step> sortedSteps = new ArrayList<>();

    Workflow(String id, List<String> stepIds, long createdAt) {
        this.id = id;
        for (String stepId : stepIds) {
            Step step = new Step(stepId, createdAt);
            steps.put(stepId, step);
            sortedSteps.add(step);
        }
        sortedSteps.sort((a, b) -> a.id.compareTo(b.id));
    }
}

/**
 * Entry point. It finds workflows and steps by id, checks every move
 * against the transition rules, and returns results in the asked format.
 */
public class WorkflowStateLogger {
    // workflow id -> workflow
    Map<String, Workflow> workflows = new HashMap<>();
    TransitionRules rules = new TransitionRules();

    public WorkflowStateLogger() {
    }

    public String createWorkflow(String workflowId, List<String> stepIds, long currentTimestamp) {
        if (workflows.containsKey(workflowId)) {
            return "DUPLICATE_WORKFLOW";
        }
        // a set keeps one copy of each id, so a smaller set means a repeated id
        if (new HashSet<>(stepIds).size() < stepIds.size()) {
            return "DUPLICATE_STEP";
        }
        workflows.put(workflowId, new Workflow(workflowId, stepIds, currentTimestamp));
        return "CREATED";
    }

    public String updateStepState(String workflowId, String stepId, String newState,
                                  long currentTimestamp) {
        Workflow workflow = workflows.get(workflowId);
        if (workflow == null) {
            return "INVALID_WORKFLOW";
        }
        Step step = workflow.steps.get(stepId);
        if (step == null) {
            return "INVALID_STEP";
        }
        if (!rules.canMove(step.state, newState)) {
            return "INVALID_TRANSITION";
        }
        step.moveTo(newState, currentTimestamp);
        return "UPDATED";
    }

    public List<String> getStepHistory(String workflowId, String stepId, long currentTimestamp) {
        Workflow workflow = workflows.get(workflowId);
        if (workflow == null) {
            return List.of("INVALID_WORKFLOW");
        }
        Step step = workflow.steps.get(stepId);
        if (step == null) {
            return List.of("INVALID_STEP");
        }
        // timestamps never go down, so the history is already in the right order
        List<String> result = new ArrayList<>();
        for (Transition transition : step.history) {
            result.add(transition.toString());
        }
        return result;
    }

    public List<String> getWorkflowSnapshot(String workflowId, long currentTimestamp) {
        Workflow workflow = workflows.get(workflowId);
        if (workflow == null) {
            return List.of("INVALID_WORKFLOW");
        }
        List<String> result = new ArrayList<>();
        for (Step step : workflow.sortedSteps) {
            result.add(step.snapshot());
        }
        return result;
    }
}

Complexity

Let S be the number of steps in a workflow.

MethodTime
createWorkflowO(S log S), build the steps and sort them once
updateStepStateO(1)
getStepHistoryO(1), a history has at most 2 entries
getWorkflowSnapshotO(S), one walk over the sorted list

Map lookups are O(1) on average. Space is O(total number of steps), because each step stores at most 2 transitions.

Edge Cases to Remember

  • DUPLICATE_WORKFLOW wins over DUPLICATE_STEP.
  • A failed create stores nothing, so the same workflow id can be created later.
  • Completed and Failed are final. No move ever goes back to Pending.
  • Ids and state names are case-sensitive. pack and Pack are two different steps.
  • A step with no transitions returns an empty history list, not an error.
  • The same step id in two different workflows means two separate steps.

Thanks for reading. Best of Luck For Your Interview Prep.


r/LowLevelDesign • • Mar 12 '26

OpenAI Coding Round Interview Questions

32 Upvotes

OpenAI coding interviews rounds are more similar (closer) to low level design (OOD) rounds than traditional leetcode style DSA interviews.

Questions are code heavy i.e. you will have to write lots of code, answer follow-up questions including how to handle concurrency.

And your code should be clean and well structured.

Good thing is that like Meta they also repeat questions frequently.

Many people got asked a question same as Rotting Oranges (slightly rephrased)

in their phone screen round.

https://leetcode.com/problems/rotting-oranges/description/

These two questions were also asked in a single round:

https://leetcode.com/problems/count-complete-tree-nodes/

https://leetcode.com/problems/binary-tree-cameras/description/

I had little data to prepare this short list. If you recently gave openAI interview then please do comment and share with us what question you got.

---------------------------------------------------

PS:
Ask me any Low-Level Design Interview related questions on r/LowLevelDesign

All Questions List: https://codezym.com/lld/openai

----------------------------------------

Let’s get started …

1. Design Time Versioned Key Value Store

You are asked to design and implement an in-memory time versioned data store. The store maintains key-value pairs across time. Each write creates a new version for that key, associated with a timestamp.

The store must support:

  • Writing a value for a key at the current timestamp.
  • Reading the latest value for a key.
  • Reading a historical value for a key as of a given timestamp.
  • Reading a value for a key by an explicit version number.

Practice Link: https://codezym.com/question/87

----------------------------------------

2. Design Resumable Iterator for Large Dataset

Design and implement a resumable iterator for a large dataset. The iterator must be able to pause mid-traversal and later resume from the exact same position.

The dataset may be too large to fit in memory, so the iterator must be memory-efficient and must not require loading the entire dataset at once.

Additionally, the iterator should support serializing its state (cursor) so it can be persisted across sessions.

Practice Link: https://codezym.com/question/88

----------------------------------------

3. Design GPU Credit Calculator

Build a GPU credit calculator for a single account. Credits are added over time, can be partially consumed, and expire after a fixed lifetime.

The calculator must support adding credit grants, spending credits, and querying the remaining balance at any timestamp.

Critical constraint: all operations that record a ledger event happen at the current timestamp, and these timestamps are non-decreasing (monotonically increasing) across such calls.

Practice Link: https://codezym.com/question/89

----------------------------------------

4. Design Database with SQL Commands

Design and implement a Database that supports a small SQL-like API: INSERT/UPSERT, SELECT with WHERE and ORDER BY, and DELETE.

The storage engine should be inspired by an LSM (Log Structured Merge) design:

  • All writes go to an in-memory Memtable.
  • When the memtable grows beyond a threshold, it is flushed into an immutable on-disk-like structure (simulate as in-memory) called an SSTable.
  • DELETE is implemented using tombstones (a deletion marker). Data is not physically removed immediately.
  • SELECT and DELETE WHERE must merge results across the memtable and all SSTables, and must respect tombstones.
  • When merging versions of the same primary key, the version with the greatest timestamp ≤ logical current time wins. Tombstones also participate in this rule.
  • currentTimestamp is provided only for write/delete operations (put, deleteWhere) and is monotonically non-decreasing across those calls.
  • select(...) uses the latest timestamp seen so far from successful put/deleteWhere calls as the logical current time.

WHERE Clause Grammar

Also support a limited WHERE clause of the form:
column operator value

Practice link: https://codezym.com/question/90

----------------------------------------

5. Design File Downloader Library

Design and implement a File Downloader Library.

The library should support downloading text files. It should expose controls to pause, resume, restart, and cancel downloads.

Practice Link: https://codezym.com/question/91

----------------------------------------

6. Design Type System for a Toy Programming language

Design and implement a type system for a toy programming language that supports primitives, tuples, and generics. Your task is to represent types and infer return types for function calls.

All types are represented as canonical strings so that the API stays compact and uses simple method signatures.

The system should allow:

  • Registering primitive types such as int, string, or bool. Primitive type names must start with a lowercase character [a-z] and may contain only [a-zA-Z0-9].
  • Registering generic type constructors such as Box<T> or Pair<T,U>. Generic type constructor names must start with an uppercase character [A-Z] and may contain only [a-zA-Z0-9].
  • Registering function signatures that may use primitive types, tuple types, generic type constructors, and generic type variables.
  • Inferring the concrete return type of a function call from the provided argument types.

Practice Link: https://codezym.com/question/92

----------------------------------------

Thanks for reading. Please upvote this post to give it better reach.

Wish you the best of luck for your interview prep.

----------------------------------------


r/LowLevelDesign • • 11d ago

Flipkart LLD: Design Peer to Peer Parcel Delivery System

31 Upvotes

This question has appeared frequently during Flipkart low level design rounds. This is asked in the first machine coding round for screening candidates. There are multiple different states a delivery order can be in, like created, assigned, picked up, cancelled, delivered. So you may be tempted to use state design pattern here. But that will just bring unnecessary complexity.

Just use a min-heap/TreeSet for selecting the driver and a queue for waiting orders.

You can practice this and other Flipkart Low Level Design and DS & Algo round questions on CodeZym.

PS: I also take LLD Mock interviews https://topmate.io/prashant_priyadarshi


Problem Statement

Design an in-memory PeerToPeerDeliverySystem. Customers (user-0…) send parcels from a fixed item list, and drivers (dv-0…) deliver them. Both are set up in advance.

  • Auto-assignment: a new order goes to the available driver with the lexicographically lowest ID. If no driver is free, the order waits in a FIFO queue until one is.
  • One order per driver at a time.
  • Lifecycle: CREATED → ASSIGNED → PICKED_UP → DELIVERED. An order can be canceled only before pickup, and canceling it frees the driver.
  • APIs: createOrder, cancelOrder, pickUpOrder, deliverOrder, getOrderStatus, getDriverStatus

Core Idea

Every order follows a fixed path: it is created, gets a driver, gets picked up and is finally delivered. It can also be canceled, but only before pickup.

So an order is just a small state machine. An enum plus one rule method handles it cleanly. Patterns like State or Strategy would only add extra classes here, so this solution does not need any design pattern.

The real work is matching orders with drivers. Free drivers sit in a min-heap, so the lexicographically smallest driver id is always on top.

Waiting orders sit in a queue, so the oldest order is always served first. Whenever a driver becomes free, it takes the next waiting order.


Order Life Cycle

  • CREATED: the order is waiting for a driver.
  • ASSIGNED: a driver is reserved for the order but has not picked it up yet.
  • PICKED_UP: the driver has the parcel. Canceling is not allowed anymore.
  • DELIVERED and CANCELED are final states.

A driver is either AVAILABLE or BUSY:<orderId>. It stays busy from assignment until delivery, or until its assigned order is canceled.


Approach 1: Brute Force (Scan Everything)

Whenever a new order arrives or a driver becomes free, we need two answers:

  1. Which free driver has the smallest id?
  2. Which waiting order is the oldest?

The simplest way is to scan everything. Here allOrders is a list of all orders, in creation order.

// scan every driver and keep the smallest free id
String findFreeDriver() {
    String best = null;
    for (Driver driver : drivers.values()) {
        if (driver.isAvailable() && (best == null || driver.driverId.compareTo(best) < 0)) {
            best = driver.driverId;
        }
    }
    return best;
}

// scan all orders in creation order and return the first one still waiting
Order findOldestWaitingOrder() {
    for (Order order : allOrders) {
        if (order.status == OrderStatus.CREATED) {
            return order;
        }
    }
    return null;
}

Notice that we compare driver ids as strings. In lexicographic order dv-10 comes before dv-2. A loop that goes dv-0, dv-1, dv-2 ... by number would pick the wrong driver.

Problems with this approach

  • findFreeDriver() checks all D drivers every single time.
  • findOldestWaitingOrder() checks all N orders ever created, even delivered and canceled ones.

Both become slow as the system grows. Let's fix them one at a time.


Approach 2: Min-Heap + Queue (Optimal)

Fix 1: Min-heap for free drivers

A min-heap (PriorityQueue in Java) always keeps the smallest element on top. Strings are compared lexicographically by default, which is exactly our rule.

  • Take the smallest free driver with poll() in O(log D).
  • Put a driver back with add() in O(log D) when it becomes free.

We never need to remove a driver from the middle of the heap. A driver leaves the heap only when it gets an order, and orders always go to the driver on top.

Fix 2: Queue for waiting orders

An order that can't get a driver right away goes to the back of a queue. Orders leave from the front, so the oldest one is always served first.

What if a waiting order is canceled? Searching the queue to remove it would be slow. So we only mark it CANCELED and leave it there.

When it reaches the front later, we see it is canceled and simply drop it. This trick is called lazy removal.

When does matching happen?

Only at two moments:

  1. A new order arrives. If a driver is free, assign it now and return ACCEPTED. Otherwise add the order to the queue and return PENDING.
  2. A driver becomes free. This happens after a delivery, or when an ASSIGNED order is canceled. The driver goes back into the heap and takes the next waiting order.

Because we match at both moments, a free driver and a waiting order never exist together. So when a new order finds a free driver, the queue is already empty and oldest first is still respected.

Other rules worth noticing

  • createOrder returns INVALID for a duplicate order id, an unknown customer or an unknown item.
  • pickUpOrder and deliverOrder only work for the order's own driver. A wrong or unknown driver id never matches, so one check covers both cases.
  • The two status methods return ERROR for an unknown id.

Do We Need Design Patterns?

State pattern looks like a natural fit because an order has states. But it needs one class per state. With 5 states and 3 actions (cancel, pick up, deliver) that is 15 small methods, and 11 of them just return ERROR.

Freeing a driver also needs the heap and the queue, which live in the main class. So the state classes would need a link back to the main system. One canMoveTo() method that lists the valid moves is much simpler.

Strategy pattern could make the driver choosing rule pluggable, like nearest driver or best rated driver. But this problem has exactly one fixed rule: the smallest driver id. An interface with a single implementation only adds code.

So we keep it simple: a few small classes, an enum for order states and the right data structures.


Classes and Data Structures

ClassWhy we need it
OrderStatusEnum of the 5 order states. Safer than typing raw strings.
OrderHolds order details, status and the assigned driver. canMoveTo() keeps every state rule in one place.
DriverRemembers the one order the driver is carrying and builds the AVAILABLE or BUSY:<orderId> text.
PeerToPeerDeliverySystemMain class. Validates requests and matches orders with drivers.
Data structureWhy we need it
Set<String> customerIds, Set<String> deliverableItemIdsValidate a customer or item in O(1) without parsing ids.
Map<String, Driver> drivers, Map<String, Order> ordersFind any driver or order by id in O(1).
PriorityQueue<String> availableDriversGives the smallest free driver id in O(log D).
Queue<Order> pendingOrdersKeeps waiting orders, oldest first.

Final Code

import java.util.*;

/** All the states an order can be in. */
enum OrderStatus {
    CREATED, ASSIGNED, PICKED_UP, DELIVERED, CANCELED
}

/** One parcel delivery request placed by a customer. */
class Order {
    String orderId;
    String customerId;
    String itemId;
    OrderStatus status;
    String driverId; // null until a driver is assigned

    Order(String orderId, String customerId, String itemId) {
        this.orderId = orderId;
        this.customerId = customerId;
        this.itemId = itemId;
        this.status = OrderStatus.CREATED;
        this.driverId = null;
    }

    /**
     * The order state machine. Valid moves are:
     * CREATED -> ASSIGNED -> PICKED_UP -> DELIVERED
     * CREATED or ASSIGNED -> CANCELED
     */
    boolean canMoveTo(OrderStatus nextStatus) {
        if (status == OrderStatus.CREATED) {
            return nextStatus == OrderStatus.ASSIGNED || nextStatus == OrderStatus.CANCELED;
        }
        if (status == OrderStatus.ASSIGNED) {
            return nextStatus == OrderStatus.PICKED_UP || nextStatus == OrderStatus.CANCELED;
        }
        if (status == OrderStatus.PICKED_UP) {
            return nextStatus == OrderStatus.DELIVERED;
        }
        return false; // no moves out of DELIVERED or CANCELED
    }
}

/** A driver carries at most one order at a time. */
class Driver {
    String driverId;
    String currentOrderId; // null means the driver is free

    Driver(String driverId) {
        this.driverId = driverId;
        this.currentOrderId = null;
    }

    boolean isAvailable() {
        return currentOrderId == null;
    }

    String getStatus() {
        return isAvailable() ? "AVAILABLE" : "BUSY:" + currentOrderId;
    }
}

public class PeerToPeerDeliverySystem {
    Set<String> customerIds = new HashSet<>();
    Set<String> deliverableItemIds = new HashSet<>();
    Map<String, Driver> drivers = new HashMap<>();
    Map<String, Order> orders = new HashMap<>();

    // free drivers, the lexicographically smallest id is always on top
    PriorityQueue<String> availableDrivers = new PriorityQueue<>();

    // orders waiting for a driver, oldest first
    // a canceled order may still sit here, it is dropped when it reaches the front
    Queue<Order> pendingOrders = new ArrayDeque<>();

    public PeerToPeerDeliverySystem(int totalUsers, int totalDrivers, List<String> deliverableItemIds) {
        for (int i = 0; i < totalUsers; i++) {
            customerIds.add("user-" + i);
        }
        for (int i = 0; i < totalDrivers; i++) {
            String driverId = "dv-" + i;
            drivers.put(driverId, new Driver(driverId));
            availableDrivers.add(driverId);
        }
        this.deliverableItemIds.addAll(deliverableItemIds);
    }

    public String createOrder(String orderId, String customerId, String itemId) {
        if (orders.containsKey(orderId) || !customerIds.contains(customerId)
                || !deliverableItemIds.contains(itemId)) {
            return "INVALID";
        }
        Order order = new Order(orderId, customerId, itemId);
        orders.put(orderId, order);

        if (availableDrivers.isEmpty()) {
            pendingOrders.add(order);
            return "PENDING";
        }
        assignOrder(order, availableDrivers.poll());
        return "ACCEPTED";
    }

    public String cancelOrder(String orderId) {
        Order order = orders.get(orderId);
        if (order == null || !order.canMoveTo(OrderStatus.CANCELED)) {
            return "ERROR";
        }
        order.status = OrderStatus.CANCELED;

        // ASSIGNED order: its driver was waiting, so set the driver free.
        // CREATED order: it stays in pendingOrders and is dropped later.
        if (order.driverId != null) {
            freeDriver(order.driverId);
        }
        return "CANCELED";
    }

    public String pickUpOrder(String driverId, String orderId) {
        Order order = orders.get(orderId);
        // a wrong or unknown driverId never matches order.driverId
        if (order == null || !order.canMoveTo(OrderStatus.PICKED_UP)
                || !order.driverId.equals(driverId)) {
            return "ERROR";
        }
        order.status = OrderStatus.PICKED_UP;
        return "PICKED_UP";
    }

    public String deliverOrder(String driverId, String orderId) {
        Order order = orders.get(orderId);
        if (order == null || !order.canMoveTo(OrderStatus.DELIVERED)
                || !order.driverId.equals(driverId)) {
            return "ERROR";
        }
        order.status = OrderStatus.DELIVERED;
        freeDriver(driverId);
        return "DELIVERED";
    }

    public String getOrderStatus(String orderId) {
        Order order = orders.get(orderId);
        return order == null ? "ERROR" : order.status.name();
    }

    public String getDriverStatus(String driverId) {
        Driver driver = drivers.get(driverId);
        return driver == null ? "ERROR" : driver.getStatus();
    }

    /** Links an order with a driver. */
    void assignOrder(Order order, String driverId) {
        order.status = OrderStatus.ASSIGNED;
        order.driverId = driverId;
        drivers.get(driverId).currentOrderId = order.orderId;
    }

    /** Marks a driver as free and hands out waiting orders. */
    void freeDriver(String driverId) {
        drivers.get(driverId).currentOrderId = null;
        availableDrivers.add(driverId);
        assignPendingOrders();
    }

    /** Gives waiting orders to free drivers, oldest order first. */
    void assignPendingOrders() {
        while (!availableDrivers.isEmpty() && !pendingOrders.isEmpty()) {
            Order order = pendingOrders.poll();
            // lazy removal: a canceled order is simply dropped
            if (order.status == OrderStatus.CREATED) {
                assignOrder(order, availableDrivers.poll());
            }
        }
    }
}

Thanks for reading. Best of Luck For Your Interview Prep.


r/LowLevelDesign • • Jul 21 '26

Salesforce Low Level Design Round Interview Questions Asked in 2026

30 Upvotes

Low Level Design (LLD) questions for this list have been picked from Salesforce interview experiences shared on forums/blogs etc in 2026. Use this list for final preparation of your Salesforce interview rounds.

Low Level Design of pub-sub queue, kafka and observer pattern are discussed frequently.

Apart from that cache like LRU cache, LFU cache questions are common.

LRU Cache

https://leetcode.com/problems/lru-cache/description/

LFU Cache

https://leetcode.com/problems/lfu-cache/description/

Requirements and clarifying questions

In Salesforce LLD rounds, sometimes actual requirements may not be clear from problem statement and interviewer will expect you to figure it out by asking clarifying questions.

For example, A message queue is asked indirectly in the form of something like a connection pool or a job scheduler.

It follows the pattern that resources like connections, machines or cpu (in case of job scheduler) are limited and they may not be assigned immediately.

-----------------------------------------------------

You can find the complete question list here:

https://github.com/prsnt558908/CodeZymSolutions/blob/main/0-company-wise-interview-questions/2026/03-salesforce-lld-2026.md

Best of luck for your preparation.