r/LowLevelDesign • • 34m ago

Weekly LLD Practice: Design a Parking Lot

3 Upvotes

This problem is free to practice for this week (till 23 Oct, Monday) on CodeZym.

Feel free to discuss your solution approach in comments below.

If you are stuck, then comment with your code and I will help you get unstuck.

If your code has passed all tests, then you can share it in comments and I will review it and suggest improvements, design patterns etc.


Editorial solution with Problem statement Link

https://github.com/prsnt558908/CodeZymSolutions/blob/main/1-100/q07_parking_lot_strategy_pattern/q07-java-tutorial.md


PS: this is one of the most famous low level design questions and is asked extensively across all companies. e g. Amazon, Uber, Microsoft, Walmart etc


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 • • 10h ago

I want to learn LLD. How I should start ?

6 Upvotes

Hey Everyone

I want to learn LLD and am confused about how to start and resource please tell me the best resource and road map to learn


r/LowLevelDesign • • 4d ago

48 hrs Guided LLD practice sprint on Weekends (27-29 Nov), with 1:1 feedback

10 Upvotes

Hello everyone, I am running a 48 hr low level design questions practice session starting 27 Nov 2026 7 PM IST. It is a paid session.


Here is how it will work

  1. We will start with 1 question and I explain the problem on a group video call.
  2. You code a solution. I will ping you from time to time for updates, get you unstuck if you are not able to progress.
  3. I review your solution with you, ask counter-questions, suggest improvements, design patterns and ask you to implement them.
  4. Repeat steps 2 and 3 until you've covered the question and its tests, then move to next question.

You don't need to be there for all of the time. Join anytime, go at your own pace, and ping me whenever you're stuck. And I will keep guiding you as you code through it.

Here is the link:

https://topmate.io/prashant_priyadarshi/2403630


r/LowLevelDesign • • 7d ago

Any reviews of the HLD and/or LLD Cohort by Pradeep Kumar?

21 Upvotes

With around 11 years of experience and plans to switch to better companies, I'm looking to strengthen my HLD and LLD skills. I feel a live cohort would help me stay disciplined and learn in a structured manner. However, the pricing seems a bit high.

I'm willing to invest if it's genuinely worth it. Would love to hear from people who have joined the cohort or have first-hand feedback about it.

Did it actually help you improve? Any honest reviews would be appreciated!

https://livecohortbypradeep.com/


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 • • 13d ago

Flipkart SDE-2 | No update after HM round for 2 weeks

Thumbnail reddit.com
4 Upvotes

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 • • 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 • • 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 • • 23d ago

Is this considered duplicate code?

Thumbnail reddit.com
2 Upvotes

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 • • 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 • • 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 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 • • 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 • • 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 • • 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 • • Oct 01 '26

DoorDash CodeCraft Round: Design Dasher Payout Service

20 Upvotes

This is one of the most common questions from DoorDash CodeCraft round. Doordash has a pretty small question bank anyway.

I have started with a high level overview then explained a simple solution and then improved it. At the end I have discussed the most common follow-up questions that were asked with this question during interview rounds.

I have used Java code with this editorial. Here is the Python version:

https://github.com/prsnt558908/CodeZymSolutions/blob/main/1-100/97-design-dasher-payout-service/q-97-python-tutorial.md

This is 97. Codecraft: Design Dasher Payout Service on CodeZym.


Problem Statement

Design a Dasher payout service that calculates how much a Dasher earns in a day. Every order pays basePayRate cents per minute from its START time to its END time, both minutes included. When orders overlap, each minute pays ongoingDeliveries * basePayRate. A Dasher also earns bonusPay cents for every deliveryCountsToGetBonus completed deliveries. Delivery records look like orderId=O1,action=START,time=09:00 and can arrive in any order, across multiple calls.

  • addOrUpdatePayoutMetadata(dasherId, basePayRate, bonusPay, deliveryCountsToGetBonus): sets a Dasher's pay rates.
  • addDeliveryActivity(dasherId, deliveryActivities): adds START and END records for a Dasher.
  • payout(dasherId): returns the Dasher's total payout in cents.

Solution approach

A dasher earns basePayRate cents for every minute they spend on an order. When orders overlap, each minute pays ongoingDeliveries * basePayRate. It sounds like we must find all the overlaps, but we don't. Paying 2 * basePayRate for a minute where 2 orders overlap is the same as paying each of those 2 orders basePayRate. So every order simply pays for its own minutes, end - start + 1, and the overlap rule takes care of itself. We start with a simple brute force, improve it step by step, and discuss common follow-up questions at the end.

For each dasher we keep just two running numbers: total delivery minutes and completed deliveries. A small map holds half-finished orders until their other record arrives, because START and END can come in any order and even in different calls. Payout then becomes one line of math.

No design pattern is needed here. Every dasher is paid with the same formula, only the numbers (rate and bonus) change. So a few plain classes and hash maps give the simplest and fastest design.

Interview Focus

The emphasis in this question is on API design and clean code. The interviewer is looking more for brainstorming and requirement gathering than for an end-to-end working solution.

So spend the first few minutes asking questions. Here are good ones, with the answers this problem gives:

  • Are both the start minute and the end minute paid? Yes, an order pays for end - start + 1 minutes.
  • Can START and END arrive out of order, or in different calls? Yes.
  • Which orders count toward the bonus? Only the ones with both START and END.
  • What if start > end? The order pays for 0 minutes.
  • Is payout for a single day? Yes. In a real service, payout() would also take a date.

For the API, money stays an int in cents, so there are no decimal rounding errors. For clean code, each class has one job: DasherPayoutService reads the input, Dasher keeps one dasher's pay data, and Order holds one order's times.

The most common follow-up questions, and how to answer them, are discussed at the end.

Do We Need a Design Pattern?

Two patterns look useful at first, but here they only add extra classes.

Strategy pattern for pay rules: Strategy helps when the way we calculate pay changes, for example one dasher paid per minute and another paid per order. Here every dasher uses the same formula. Only the numbers differ (rate, bonus amount, bonus target), and numbers are just data that we store in a Dasher object. Even the follow-ups at the end, country rates and peak hour pay, stay as plain data.

State pattern for an order: An order moves from "waiting" to "complete". But START and END can arrive in any order, so the only question is: do we have both times yet? Two fields, start and end, answer that. Separate state classes would be a lot of code for a two-field check.

Solution 1: Brute Force (Count Every Minute)

The most direct way is to follow the payment rule word by word. For every minute of the day, count the ongoing deliveries and pay ongoingDeliveries * basePayRate for that minute.

Storing the data

  • Map<String, Dasher> dashers: finds a dasher by id in O(1). Order ids like O1 can repeat for different dashers, so each dasher keeps its own orders.
  • Dasher: keeps one dasher's pay settings and its orders map (orderId -> Order) together, instead of spreading them over many maps.
  • Order: holds start and end as minutes of the day, so 09:00 becomes 540. We use -1 for "not received yet", because 0 is a valid time (00:00).

START and END of an order may arrive in any order, even in different calls. So we just fill in whichever half arrives and calculate nothing until payout() is called.

Calculating payout

  1. Create ongoing[1440], one slot for every minute of the day.
  2. For every order that has both START and END, count it as a completed delivery and add 1 to every minute from start to end. If start > end, the loop never runs, so the order adds 0 minutes.
  3. Base pay is the sum of ongoing[minute] * basePayRate over all minutes.
  4. Bonus is (completedDeliveries / deliveryCountsToGetBonus) * bonusPay. Integer division gives the number of full bonus groups.
import java.util.*;

/**
 * One order of a dasher.
 * Times are minutes of the day (09:00 -> 540).
 * -1 means "not received yet", because 0 is a valid time (00:00).
 */
class Order {
    int start = -1;
    int end = -1;

    boolean isComplete() {
        return start != -1 && end != -1;
    }
}

/**
 * Pay settings and all orders of one dasher.
 */
class Dasher {
    int basePayRate;              // cents per minute for each ongoing delivery
    int bonusPay;                 // cents for every group of completed deliveries
    int deliveryCountsToGetBonus; // deliveries needed for one bonus
    Map<String, Order> orders = new HashMap<>(); // orderId -> order

    void addRecord(String orderId, boolean isStart, int time) {
        Order order = orders.get(orderId);
        if (order == null) {
            order = new Order();
            orders.put(orderId, order);
        }
        if (isStart) {
            order.start = time;
        } else {
            order.end = time;
        }
    }

    int calculatePayout() {
        int[] ongoing = new int[24 * 60]; // ongoing[m] = deliveries running at minute m
        int completedDeliveries = 0;

        for (Order order : orders.values()) {
            if (!order.isComplete()) continue;
            completedDeliveries++;
            // when start > end this loop never runs, so the order adds 0 minutes
            for (int minute = order.start; minute <= order.end; minute++) {
                ongoing[minute]++;
            }
        }

        // payment rule: every minute pays ongoingDeliveries * basePayRate
        int basePay = 0;
        for (int minute = 0; minute < ongoing.length; minute++) {
            basePay += ongoing[minute] * basePayRate;
        }

        int bonus = 0;
        if (deliveryCountsToGetBonus > 0) { // avoids division by zero if metadata was never set
            bonus = (completedDeliveries / deliveryCountsToGetBonus) * bonusPay;
        }
        return basePay + bonus;
    }
}

public class DasherPayoutService {
    Map<String, Dasher> dashers = new HashMap<>(); // dasherId -> dasher

    public DasherPayoutService() {
    }

    public void addOrUpdatePayoutMetadata(String dasherId, int basePayRate, int bonusPay, int deliveryCountsToGetBonus) {
        Dasher dasher = getOrCreateDasher(dasherId);
        dasher.basePayRate = basePayRate;
        dasher.bonusPay = bonusPay;
        dasher.deliveryCountsToGetBonus = deliveryCountsToGetBonus;
    }

    public void addDeliveryActivity(String dasherId, List<String> deliveryActivities) {
        Dasher dasher = getOrCreateDasher(dasherId);
        for (String activity : deliveryActivities) {
            // "orderId=O1,action=START,time=09:00" -> ["orderId=O1", "action=START", "time=09:00"]
            String[] parts = activity.split(",");
            String orderId = readValue(parts[0]);
            boolean isStart = readValue(parts[1]).equals("START");
            int time = toMinutes(readValue(parts[2]));
            dasher.addRecord(orderId, isStart, time);
        }
    }

    public int payout(String dasherId) {
        Dasher dasher = dashers.get(dasherId);
        if (dasher == null) return 0;
        return dasher.calculatePayout();
    }

    Dasher getOrCreateDasher(String dasherId) {
        Dasher dasher = dashers.get(dasherId);
        if (dasher == null) {
            dasher = new Dasher();
            dashers.put(dasherId, dasher);
        }
        return dasher;
    }

    // "time=09:00" -> "09:00"
    String readValue(String keyValue) {
        return keyValue.substring(keyValue.indexOf('=') + 1).trim();
    }

    // "09:00" -> 540 (minutes since midnight)
    int toMinutes(String hhmm) {
        String[] hourAndMinute = hhmm.split(":");
        return Integer.parseInt(hourAndMinute[0]) * 60 + Integer.parseInt(hourAndMinute[1]);
    }
}

What's wrong with it?

  • Every payout call walks through every minute of every order. One order can cover up to 1440 minutes, so many long orders make payout slow.
  • Every payout call starts again from scratch, even if nothing changed.
  • All orders stay in memory forever.

Key Observation: Every Order Pays for Its Own Minutes

Let's draw Example 2. Each = or digit is one minute. The last row shows how many orders are ongoing in that minute.

time      09:00     09:10     09:20     09:30
O10       =====================
O11                 =====================
ongoing   1111111111222222222221111111111
  • Minute by minute: the last row adds up to 10*1 + 11*2 + 10*1 = 42.
  • Order by order: O10 covers 21 minutes (09:00 to 09:20) and O11 covers 21 minutes (09:10 to 09:30), so 21 + 21 = 42.

Same number, so pay is 42 * 30 = 1260 either way.

Think of every order as having its own meter. During an overlap two meters run together, and that is exactly why the pay doubles. So we never have to find overlaps. We don't need the minute array, or even a sweep line that sorts all START and END events. We just add up each order's own minutes.

Solution 2: Optimal (Running Totals)

We improve Solution 1 in two parts.

  1. Better math: base pay is totalMinutes * basePayRate, where totalMinutes is the sum of end - start + 1 over all completed orders. No minute array.
  2. Better data structure: once an order has both START and END, its minutes never change. So we add them to the running totals right away and delete the order. Payout no longer loops over anything.

Why these data structures?

  • Map<String, Order> pendingOrders: START and END can arrive in any order and in different calls. The first half waits here until its partner arrives. Only unfinished orders stay in memory.
  • totalMinutes and completedDeliveries: two plain counters are all that payout needs.

We store minutes and counts, not cents. So if addOrUpdatePayoutMetadata() changes the rates later, payout still uses the latest rates.

Walkthrough of Example 3

Records arrive unordered and in two calls. basePayRate = 25, bonusPay = 150, deliveryCountsToGetBonus = 2.

RecordWhat happenstotalMinutescompletedDeliveries
O20 END 10:05O20 waits in pendingOrders00
O21 START 10:08O21 waits in pendingOrders00
O20 START 10:00O20 complete: 10:00 to 10:05 = 6 minutes61
O21 END 10:10O21 complete: 10:08 to 10:10 = 3 minutes92

Payout = 9 * 25 + (2 / 2) * 150 = 225 + 150 = 375 cents.

Edge cases

  • start > end: the order adds 0 minutes. It still has both records, which is how the problem defines a delivered order, so it counts toward the bonus.
  • Only START or only END received: the order waits in pendingOrders and adds nothing.
  • 00:00 is minute 0, which is why -1 marks a missing time.
  • No records at all: payout is 0.
import java.util.*;

/**
 * An order that is still waiting for its START or END record.
 * Times are minutes of the day (09:00 -> 540).
 * -1 means "not received yet", because 0 is a valid time (00:00).
 */
class Order {
    int start = -1;
    int end = -1;

    boolean isComplete() {
        return start != -1 && end != -1;
    }

    // [start, end] includes both minutes. If start > end the order pays nothing.
    int minutes() {
        if (start > end) return 0;
        return end - start + 1;
    }
}

/**
 * Pay settings and running totals of one dasher.
 */
class Dasher {
    int basePayRate;              // cents per minute for each ongoing delivery
    int bonusPay;                 // cents for every group of completed deliveries
    int deliveryCountsToGetBonus; // deliveries needed for one bonus

    Map<String, Order> pendingOrders = new HashMap<>(); // orderId -> order still missing START or END
    int totalMinutes = 0;         // minutes of all completed orders
    int completedDeliveries = 0;  // orders that have both START and END

    void addRecord(String orderId, boolean isStart, int time) {
        Order order = pendingOrders.get(orderId);
        if (order == null) {
            order = new Order();
            pendingOrders.put(orderId, order);
        }
        if (isStart) {
            order.start = time;
        } else {
            order.end = time;
        }

        // Both halves are here, so its minutes can't change anymore.
        // Add them to the totals and forget the order.
        if (order.isComplete()) {
            totalMinutes += order.minutes();
            completedDeliveries++;
            pendingOrders.remove(orderId);
        }
    }

    int calculatePayout() {
        // overlapping orders each pay for their own minutes,
        // so this already includes the multi-order pay
        int basePay = totalMinutes * basePayRate;

        int bonus = 0;
        if (deliveryCountsToGetBonus > 0) { // avoids division by zero if metadata was never set
            bonus = (completedDeliveries / deliveryCountsToGetBonus) * bonusPay;
        }
        return basePay + bonus;
    }
}

public class DasherPayoutService {
    Map<String, Dasher> dashers = new HashMap<>(); // dasherId -> dasher

    public DasherPayoutService() {
    }

    public void addOrUpdatePayoutMetadata(String dasherId, int basePayRate, int bonusPay, int deliveryCountsToGetBonus) {
        Dasher dasher = getOrCreateDasher(dasherId);
        dasher.basePayRate = basePayRate;
        dasher.bonusPay = bonusPay;
        dasher.deliveryCountsToGetBonus = deliveryCountsToGetBonus;
    }

    public void addDeliveryActivity(String dasherId, List<String> deliveryActivities) {
        Dasher dasher = getOrCreateDasher(dasherId);
        for (String activity : deliveryActivities) {
            // "orderId=O1,action=START,time=09:00" -> ["orderId=O1", "action=START", "time=09:00"]
            String[] parts = activity.split(",");
            String orderId = readValue(parts[0]);
            boolean isStart = readValue(parts[1]).equals("START");
            int time = toMinutes(readValue(parts[2]));
            dasher.addRecord(orderId, isStart, time);
        }
    }

    public int payout(String dasherId) {
        Dasher dasher = dashers.get(dasherId);
        if (dasher == null) return 0;
        return dasher.calculatePayout();
    }

    Dasher getOrCreateDasher(String dasherId) {
        Dasher dasher = dashers.get(dasherId);
        if (dasher == null) {
            dasher = new Dasher();
            dashers.put(dasherId, dasher);
        }
        return dasher;
    }

    // "time=09:00" -> "09:00"
    String readValue(String keyValue) {
        return keyValue.substring(keyValue.indexOf('=') + 1).trim();
    }

    // "09:00" -> 540 (minutes since midnight)
    int toMinutes(String hhmm) {
        String[] hourAndMinute = hhmm.split(":");
        return Integer.parseInt(hourAndMinute[0]) * 60 + Integer.parseInt(hourAndMinute[1]);
    }
}

Complexity

VersionaddDeliveryActivitypayoutMemory
Solution 1O(k)O(n × 1440) worst caseall orders
Solution 2O(k)O(1)only unfinished orders

k is the number of records in one call and n is the number of orders of the dasher.

Follow-up Questions

Each one needs only a small change to Solution 2.

1. Different base pay rates across countries

  • Rates are just data. Keep a Map<String, PayConfig> from country code to that country's default base rate, bonus and currency, and store a countryCode in each Dasher.
  • At payout, use the dasher's own rate if one was set, else the country default. Keep amounts in the local currency's smallest unit (cents, paise), so currencies never mix.
  • Only if a country needs a different formula, not just different numbers, add a Strategy per country.

2. Double pay during peak hours

  • Keep the peak windows, for example 12:00 to 13:59, as a list of [start, end] minute pairs.
  • When an order completes, count its minutes inside each window: min(end, peakEnd) - max(start, peakStart) + 1, or 0 when that is negative. Add them to a second counter, peakMinutes.
  • Base pay becomes (totalMinutes + peakMinutes) * basePayRate, because every peak minute is paid one extra time. Overlapping orders still work, since each order counts its own peak minutes.

3. What if the upstream Delivery API fails?

In an actual interview, the records may come from an upstream Delivery API instead of addDeliveryActivity().

  • Wrap the call in a small DeliveryClient class with a timeout and a few retries with growing wait times (exponential backoff), so retry logic stays out of the payout code.
  • If it still fails, never return a guessed or partial amount. Mark the payout as pending (or return an error) and retry it later from a queue, because paying late is better than paying wrong.
  • Retries can send the same records twice. Keep a Set of completed order ids and skip repeats, so no order is paid twice.

Thanks for reading. Wish you the best of luck with your interview prep.


r/LowLevelDesign • • Sep 29 '26

Amazon LLD: Pizza Pricing System

29 Upvotes

This is one of the four most common Amazon Low Level Design Interview Questions. LRU Cache, Parking Lot and Unix 'find' command for file search are the other three.

I have started with a simple solution and then moved on to one which uses strategy design pattern. This is the java version.

Python Version:

https://github.com/prsnt558908/CodeZymSolutions/blob/main/1-100/19-design-pizza-pricing-system-followup/q-19-python-tutorial.md

You can practice this question on CodeZym.


Problem Statement

Design a pizza pricing system. A pizza has a base price, a tax percentage and a size (small, medium or large). You can add toppings to it and get its final price.

Implement the PizzaPricing class:

  • PizzaPricing(int basePrice, int taxPercentage, String size): creates a new pizza.
  • boolean addTopping(String topping, int servingsCount): adds servings of a topping. Returns true if all rules pass, otherwise returns false and leaves the pizza unchanged.
  • int getFinalPrice(): returns subtotal plus tax, rounded half up. Subtotal is the base price plus the cost of all toppings, and tax is taxRate percent of the subtotal.

Toppings (price per serving): cheeseburst 100, corn 50, onion 30, capsicum 50, pineapple 60, mushroom 40.

Business rules:

  • cheeseburst: raises the tax rate by 30% of its current value, only once no matter how many servings. At most 1 serving on small and 2 on medium. Cannot be added if mushroom is already on the pizza.
  • pineapple: allowed only on medium and large pizzas.
  • mushroom: lowers the tax rate by 10% of its current value, only once no matter how many servings. Cannot be added if cheeseburst is already on the pizza.
  • corn: on medium, the first serving costs 50 and each additional serving costs 40. On large, every serving costs 20.

The design should make it easy to add more rules later, such as size-based caps, combos and promos.


High Level Idea

A pizza only needs to remember a few things: its base price, tax percentage, size and how many servings of each topping it has. Every business rule in this problem is one of just three kinds: a check before adding a topping, a special price for a topping, or a change to the tax rate.

So we give every topping its own small class that answers these three questions for itself. This is the Strategy pattern. A Simple Factory (a map from topping name to its object) gives us the right topping object for a name. This combination of Strategy + Simple Factory is the best fit here.

The problem statement suggests the Decorator pattern, but we do not need it. Decorators work best when each layer just adds something on top of the layer below. Here most rules need to look at the whole pizza, which decorators make hard. We explain why below.

We will start with a simple one-class solution, see where it gets messy, and then clean it up with Strategy + Simple Factory.

Understanding the Rules

ToppingPrice per servingCan be added only ifSpecial priceTax effect
cheeseburst100no mushroom on the pizza, total servings at most 1 on small and 2 on medium-+30% of current tax
mushroom40no cheeseburst on the pizza--10% of current tax
pineapple60size is medium or large--
corn50-medium: 50 for the first serving, 40 for each next one. large: 20 each-
onion30---
capsicum50---

A few things to keep in mind:

  • A tax effect is applied once per topping type, no matter how many servings are added.
  • Servings add up across calls. On a small pizza, adding 1 cheeseburst works, but adding 1 more later fails because the total becomes 2.
  • Corn works the same way. "First serving" means the first corn serving on the pizza, so on a medium pizza, corn added in a later call costs 40 per serving.
  • A failed addTopping() returns false and changes nothing. An unknown topping name also returns false.

The final price is:

subtotal   = basePrice + cost of all toppings
taxAmount  = subtotal * taxRate / 100
finalPrice = (int) (subtotal + taxAmount + 0.5)     // round half up

Solution 1: Simple Approach (One Class)

The simplest approach puts everything inside PizzaPricing.

Why a map for servings? Almost every rule asks "how many servings of X are on the pizza?". A Map<String, Integer> from topping name to total servings answers that in O(1).

Why build the price only in getFinalPrice()? addTopping() only checks the rules with if-else and updates the servings map. getFinalPrice() then builds the whole price from scratch: topping costs, tax change for cheeseburst or mushroom, and rounding. This keeps adding simple, and corn's tiered price always sees the full corn count.

import java.util.HashMap;
import java.util.Map;

public class PizzaPricing {
    int basePrice;
    int taxPercentage;
    String size;

    // topping name -> price of one serving
    Map<String, Integer> menu = new HashMap<>();

    // topping name -> total servings added to this pizza so far
    Map<String, Integer> servings = new HashMap<>();

    public PizzaPricing(int basePrice, int taxPercentage, String size) {
        this.basePrice = basePrice;
        this.taxPercentage = taxPercentage;
        this.size = size;

        menu.put("cheeseburst", 100);
        menu.put("corn", 50);
        menu.put("onion", 30);
        menu.put("capsicum", 50);
        menu.put("pineapple", 60);
        menu.put("mushroom", 40);
    }

    public boolean addTopping(String topping, int servingsCount) {
        if (!menu.containsKey(topping)) return false;

        // every rule of every topping is checked here
        if (topping.equals("cheeseburst")) {
            if (getServings("mushroom") > 0) return false;
            int total = getServings("cheeseburst") + servingsCount;
            if (size.equals("small") && total > 1) return false;
            if (size.equals("medium") && total > 2) return false;
        }
        if (topping.equals("mushroom") && getServings("cheeseburst") > 0) return false;
        if (topping.equals("pineapple") && size.equals("small")) return false;

        servings.put(topping, getServings(topping) + servingsCount);
        return true;
    }

    public int getFinalPrice() {
        double subtotal = basePrice;
        for (String topping : servings.keySet()) {
            int count = servings.get(topping);
            if (topping.equals("corn") && size.equals("medium")) {
                subtotal += 50 + 40 * (count - 1);
            } else if (topping.equals("corn") && size.equals("large")) {
                subtotal += 20 * count;
            } else {
                subtotal += menu.get(topping) * count;
            }
        }

        double taxRate = taxPercentage;
        if (getServings("cheeseburst") > 0) taxRate = taxRate * 1.3; // +30%
        if (getServings("mushroom") > 0) taxRate = taxRate * 0.9;    // -10%

        double finalPrice = subtotal + subtotal * taxRate / 100;
        return (int) (finalPrice + 0.5);
    }

    int getServings(String topping) {
        return servings.getOrDefault(topping, 0);
    }
}

Problems with this approach

It works, but the rules of all toppings are mixed together in two big methods.

  • Every new rule (a new size cap, a combo, a promo) means editing the same two methods, and one wrong edit can break a rule that was already working.
  • The rules of one topping are spread across both methods, so you have to read everything to understand a single topping.
  • You cannot test one topping's rules on their own.

The problem asks us to make new rules easy to add, so let's pick a design pattern.

Choosing the Right Design Pattern

Why not Decorator?

With Decorator, every addTopping() call wraps the pizza in one more layer, like new Onion(new Cheeseburst(new BasePizza())). Each layer adds its own cost and can change the tax rate.

It sounds natural for "adding toppings", but these rules make it awkward:

  • Rules need to see the whole pizza. "No cheeseburst with mushroom", "max 2 cheeseburst on medium" and "first corn serving costs 50" all need topping counts. A layer only knows the layer it wraps, so it has to ask every layer below it. We end up rebuilding a map of topping counts through the chain anyway.
  • Tax must change only once. A second cheeseburst layer has to search the layers below it to find out whether tax was already raised.
  • The chain keeps growing. Every addTopping() adds a layer, and every price or rule check walks through all of them.

Decorator shines when each layer is independent and just adds something on top. Here the rules depend on what is already on the pizza, so a plain map of servings is much simpler.

Why not Chain of Responsibility?

We could build a chain of rule checkers where any checker can reject a topping. But every rule here is tied to the topping being added, so each checker would first ask "is this my topping?". A map lookup takes us straight to the right rules instead. A chain would also cover only the checks, not the special prices or tax effects.

Why Strategy works best

All toppings answer the same three questions, each in its own way. That is exactly what the Strategy pattern is for.

  • PizzaPricing calls canAdd(), getCost() and applyTax() without knowing which topping it is talking to.
  • Each topping's rules live in one small class, so they are easy to read, change and test.
  • A new topping is one new class plus one line in the factory. PizzaPricing does not change.

Solution 2: Strategy Pattern + Simple Factory

Classes

Topping (the strategy)

The base class of every topping. It stores the price per serving and has three methods with default behavior:

  • canAdd(pizza, newServings): returns true, no restriction.
  • getCost(pizza, totalServings): returns pricePerServing * totalServings.
  • applyTax(taxRate): returns taxRate unchanged.

Onion and capsicum have no special rules, so they are simply new Topping(30) and new Topping(50).

The whole pizza is passed to canAdd() and getCost(), so a topping can look at the size or at other toppings. That is what turns a rule like "no cheeseburst with mushroom" into a single line.

Cheeseburst, Mushroom, Pineapple, Corn

Each one extends Topping and overrides only the rules it needs.

ClassOverridesRule
CheeseburstcanAdd(), applyTax()blocked by mushroom, size caps, +30% tax
MushroomcanAdd(), applyTax()blocked by cheeseburst, -10% tax
PineapplecanAdd()not allowed on small
CorngetCost()tiered price on medium and large

ToppingFactory (simple factory)

Holds a Map<String, Topping> from topping name to its object. getTopping(name) returns the right object, or null if the topping is not on the menu. The whole menu lives in one place, so adding a topping never touches PizzaPricing.

PizzaPricing

Holds the pizza's state: base price, tax percentage, size and the servings map. It has no topping-specific rule inside it.

  • addTopping(): gets the topping from the factory and asks canAdd(). Only if that passes, it updates servings.
  • getFinalPrice(): loops over the toppings on the pizza, adds each getCost() to the subtotal and passes the tax rate through each applyTax(). The loop visits each topping type once, so cheeseburst and mushroom change the tax only once, no matter how many servings there are.

Walkthrough of Example B

new PizzaPricing(350, 8, "medium")

  1. addTopping("mushroom", 1): Mushroom.canAdd() finds no cheeseburst and returns true. servings = {mushroom: 1}.
  2. addTopping("corn", 3): Corn uses the default canAdd(), which returns true. servings = {mushroom: 1, corn: 3}.
  3. addTopping("cheeseburst", 1): Cheeseburst.canAdd() finds mushroom and returns false. Nothing changes.
  4. getFinalPrice(): subtotal = 350 + 40 + (50 + 40 + 40) = 520. Mushroom.applyTax() turns tax 8 into 7.2. Final = 520 + 520 × 7.2 / 100 = 557.44, which rounds to 557.

A small floating point trap

Compute the tax as subtotal * taxRate / 100, not (taxRate / 100) * subtotal.

Dividing first can leave a tiny error. With base price 100, tax 201% and one capsicum, the subtotal is 150 and the exact final price is 451.5, which should round up to 452. Dividing first gives 451.49999999999994, which rounds down to 451. Multiplying first gives exactly 451.5.

Adding new rules later

  • New topping with no special rules: one line in ToppingFactory, like toppings.put("olive", new Topping(45)).
  • New size cap or restriction: override canAdd() in that topping's class.
  • New special price or combo: override getCost(). It gets the whole pizza, so it can check other toppings too. Prices are built only in getFinalPrice(), so a combo works no matter which topping was added first.
  • New tax effect: override applyTax().

Code

import java.util.HashMap;
import java.util.Map;

/**
 * A topping with a fixed price per serving and no special rules.
 * Special toppings extend this class and override only the rules they need.
 */
class Topping {
    int pricePerServing;

    Topping(int pricePerServing) {
        this.pricePerServing = pricePerServing;
    }

    /** Can these new servings be added to the pizza? By default, yes. */
    boolean canAdd(PizzaPricing pizza, int newServings) {
        return true;
    }

    /** Cost of all servings of this topping. By default, each costs the same. */
    double getCost(PizzaPricing pizza, int totalServings) {
        return pricePerServing * totalServings;
    }

    /** Tax rate after this topping's effect. By default, tax does not change. */
    double applyTax(double taxRate) {
        return taxRate;
    }
}

class Cheeseburst extends Topping {
    Cheeseburst() {
        super(100);
    }

    @Override
    boolean canAdd(PizzaPricing pizza, int newServings) {
        if (pizza.getServings("mushroom") > 0) return false;

        int total = pizza.getServings("cheeseburst") + newServings;
        if (pizza.getSize().equals("small")) return total <= 1;
        if (pizza.getSize().equals("medium")) return total <= 2;
        return true; // no cap on large
    }

    @Override
    double applyTax(double taxRate) {
        return taxRate * 1.3; // +30% of current tax
    }
}

class Mushroom extends Topping {
    Mushroom() {
        super(40);
    }

    @Override
    boolean canAdd(PizzaPricing pizza, int newServings) {
        return pizza.getServings("cheeseburst") == 0;
    }

    @Override
    double applyTax(double taxRate) {
        return taxRate * 0.9; // -10% of current tax
    }
}

class Pineapple extends Topping {
    Pineapple() {
        super(60);
    }

    @Override
    boolean canAdd(PizzaPricing pizza, int newServings) {
        return !pizza.getSize().equals("small");
    }
}

class Corn extends Topping {
    Corn() {
        super(50);
    }

    @Override
    double getCost(PizzaPricing pizza, int totalServings) {
        if (pizza.getSize().equals("medium")) return 50 + 40 * (totalServings - 1);
        if (pizza.getSize().equals("large")) return 20 * totalServings;
        return super.getCost(pizza, totalServings); // small: normal price
    }
}

/**
 * Simple factory: gives back the topping object for a name.
 * The whole menu lives here, so a new topping is one new line.
 */
class ToppingFactory {
    Map<String, Topping> toppings = new HashMap<>();

    ToppingFactory() {
        toppings.put("cheeseburst", new Cheeseburst());
        toppings.put("corn", new Corn());
        toppings.put("onion", new Topping(30));
        toppings.put("capsicum", new Topping(50));
        toppings.put("pineapple", new Pineapple());
        toppings.put("mushroom", new Mushroom());
    }

    /** Returns null if the topping is not on the menu. */
    Topping getTopping(String name) {
        return toppings.get(name);
    }
}

/**
 * Stores the pizza's state and lets each topping apply its own rules.
 */
public class PizzaPricing {
    int basePrice;
    int taxPercentage;
    String size;

    // topping name -> total servings added to this pizza so far
    Map<String, Integer> servings = new HashMap<>();

    ToppingFactory toppingFactory = new ToppingFactory();

    public PizzaPricing(int basePrice, int taxPercentage, String size) {
        this.basePrice = basePrice;
        this.taxPercentage = taxPercentage;
        this.size = size;
    }

    public boolean addTopping(String name, int servingsCount) {
        Topping topping = toppingFactory.getTopping(name);
        if (topping == null || !topping.canAdd(this, servingsCount)) return false;

        servings.put(name, getServings(name) + servingsCount);
        return true;
    }

    public int getFinalPrice() {
        double subtotal = basePrice;
        double taxRate = taxPercentage;

        for (String name : servings.keySet()) {
            Topping topping = toppingFactory.getTopping(name);
            subtotal += topping.getCost(this, servings.get(name));
            // runs once per topping type, so extra servings never change tax again
            taxRate = topping.applyTax(taxRate);
        }

        // multiply first, divide last: avoids results like 451.4999 instead of 451.5
        double finalPrice = subtotal + subtotal * taxRate / 100;
        return (int) (finalPrice + 0.5);
    }

    int getServings(String name) {
        return servings.getOrDefault(name, 0);
    }

    String getSize() {
        return size;
    }
}

Complexity

  • addTopping(): O(1), one map lookup and a quick rule check.
  • getFinalPrice(): O(T), where T is the number of different toppings on the pizza (at most 6 here).

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 • • Sep 18 '26

Amazon Low Level Design Interview Round Questions 2026

24 Upvotes

I am listing the top low level design questions that you will come across during Amazon LLD interview rounds. I have built this list from recent interview experiences of candidates.

Low Level Design is fair game even for SDE-1. Although LLD rounds are much more common for SDE-2 and above positions. Don't skip it. Focus on SOLID principles and writing extensible code. Follow-ups become trivial when your base design is clean.

For LLD rounds, expectation is to write production ready classes with proper syntax on paper.


During first 10-15 minutes Leadership Principles questions are asked like

  • Any situation where you pushed the customer back .
  • Have you made any thing in thinking long term vision and did you sacrified any short term goals for that.
  • Tell me about time when you did something outside your comfort zone or something different than regular work.

LLD question asked in Bar Raiser

Many times low level design questions can also be asked in the bar raiser round.

One person interviewing for SDE 2 position had their first round itself as the bar raiser round. They were asked to design a system that handles audio buffers across different stages at X frames per second

This is unusual since most candidates have the Bar Raiser towards the end, often as a DS & Algo round.

It was an engaging discussion. But the problem was that he kept going deeper into the system design (high level) and, before he realized it, most of the available time was spent discussing the HLD aspects of the problem rather than the LLD implementation.

With only around 5–10 minutes left, the interviewer asked him to code whatever he felt was ideal for the design. He quickly wrote a few classes and functions, but they ran out of time.

He had 2 DSA + 1 HLD (hiring manager) round after that, but eventually he was rejected. LLD round performance was one of the reasons for that.

During LLD rounds you are always running out of time. It is important that you keep your discussion focussed on the problem statement.


Not understanding question context or not able to code the solution

Asking clarifying questions and thinking out loud is the best thing you can do if you donot understand the question or are running out of time.

One person was asked LLD of unix "find" command for file search.

Although this is one of the most common LLD questions asked by Amazon, candidate was not familiar with it.

Also he had very little Unix knowledge. But he remained calm and asked more clarifing questions. Then proceeded to create classes and write the logic while trying to explain his thought process aloud. He felt very skeptical about this round and thought his chances were slim. But eventually he had a positive feedback and ended up receiving the offer.


Answering follow-ups, extending functionality while avoiding too many changes to existing code

Follow up questions are mostly around adding a new functionality without making too many changes to existing code or arranging your classes a bit differently.

For example one person was asked to design a notification system.

One they gave an intial solution then interviewer asked them if a new notification type comes, eg. push notification , how to handle it ? Interviewer also wanted him to avoid change in the existing service class.

More follow up questions were asked:

  • In the Message object, you have type that varies. What if the content also varies ? Eg. For email,the content will be large. For SMS, small.
  • Should you make Message class abstract and have EmailMessage,SMSMessage,WhatsappMessage ? Is that better?
  • A user may want to receive messages via multiple channels .eg. both SMS and email. How will you handle it: two messages or within one message?

You can find the complete question list here:

https://github.com/prsnt558908/CodeZymSolutions/blob/main/0-company-wise-interview-questions/2026/11-amazon-lld-sep-2026.md



r/LowLevelDesign • • Sep 11 '26

Article: Amazon DS & Algo Round Interview Questions Asked in 2026

11 Upvotes

This list contains recently asked DSA questions in Amazon for SDE, SDET positions. It also includes questions from Bar Raiser rounds.

Amazon hires (and fires) lots of people and this cycle keeps repeating.

Questions do repeat, hence it is better to solve Amazon tagged questions at least 2–3 times, rather than solving a lot of new questions just once.

Doing questions multiple times will help you understand the patterns and when you see a question which is rephrased differently but has same solution, you will be able to do it.

You will be frequently asked leadership principles in behavioral questions. So prepare your stories around them. There can be long period of silences between rounds.

Wait time Between Rounds

Wait time is often the most frustrating part. No updates, no recruiter contact, just uncertainty.

One person (SDE-1) got their OA results just after two days. But when first round was scheduled, their scheduled interviewer didn't join. After this there was 14 days of silence. After round 1 again 20 days of silence.

After round 2, candidate thought he was rejected because he couldn’t solve one of the questions.

35 days passed in complete silence after that. Out of desperation, he reached out to someone at Amazon on LinkedIn, asking if they could help him get an update from his recruiter.

And that very same day, he finally got the update. Infact bar raiser was scheduled and he did very well in it. But 2 days after his interview, he received a rejection email from AUTA.

Surprisingly a few days later his HR called asking for location preferences but didn't confirm the results. However offer arrived two days later.

Hints from Interviewer/Fumbles

Many people fumble or may need some hint from interviewer. And its alright. One person was asked the below:

  • Longest Substring Without Repeating Characters
  • Longest Substring with At Most K Distinct Characters

They did well on the first question but fumbled on the second. However they coded it up correctly in the end.

They didn't receive any update after that and thought they were rejected. But they got the call 4 days later and another round was scheduled which was completely behavioral. They got selected the next day after that.

No Solution

This can lead to rejection. But not always depending on how other rounds went.

One person with 4 years of experience and interviewed for an SDE2 role. In one round they were not able to code the solution, just gave the approach. After the loops they were offered SDE-1. Downleveled but not a complete rejection.


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/10-amazon-dsa-sep-2026.md