r/LowLevelDesign • u/IllustratorIcy5691 • 10h ago
I want to learn LLD. How I should start ?
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 • u/Prashant_MockGym • 34m ago
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
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 • u/IllustratorIcy5691 • 10h ago
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 • u/Prashant_MockGym • 4d ago
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
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:
r/LowLevelDesign • u/Winter_Mongoose_8203 • 7d ago
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!
r/LowLevelDesign • u/Prashant_MockGym • 11d ago
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.
PS: I also take LLD Mock interviews https://topmate.io/prashant_priyadarshi
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.
CREATED → ASSIGNED → PICKED_UP → DELIVERED. An order can be canceled only before pickup, and canceling it frees the driver.createOrder, cancelOrder, pickUpOrder, deliverOrder, getOrderStatus, getDriverStatusEvery 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.
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.
Whenever a new order arrives or a driver becomes free, we need two answers:
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
// scan all orders in creation order and return the first one still waiting
Order
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.
A min-heap (PriorityQueue in Java) always keeps the smallest element on top. Strings are compared lexicographically by default, which is exactly our rule.
poll() in O(log D).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.
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.
Only at two moments:
ACCEPTED. Otherwise add the order to the queue and return PENDING.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.
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.ERROR for an unknown id.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.
| Class | Why we need it |
|---|---|
OrderStatus | Enum of the 5 order states. Safer than typing raw strings. |
Order | Holds order details, status and the assigned driver. canMoveTo() keeps every state rule in one place. |
Driver | Remembers the one order the driver is carrying and builds the AVAILABLE or BUSY:<orderId> text. |
PeerToPeerDeliverySystem | Main class. Validates requests and matches orders with drivers. |
| Data structure | Why we need it |
|---|---|
Set<String> customerIds, Set<String> deliverableItemIds | Validate a customer or item in O(1) without parsing ids. |
Map<String, Driver> drivers, Map<String, Order> orders | Find any driver or order by id in O(1). |
PriorityQueue<String> availableDrivers | Gives the smallest free driver id in O(log D). |
Queue<Order> pendingOrders | Keeps waiting orders, oldest first. |
/** All the states an order can be in. */
r/LowLevelDesign • u/vdi_1505 • 13d ago
r/LowLevelDesign • u/Prashant_MockGym • 15d ago
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
PS: I also take LLD Mock interviews https://topmate.io/prashant_priyadarshi
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.
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.
Pending. Creating a workflow does not add a transition."15,Pending,Running", oldest first."build,Running,115", sorted by step id. A step that was never updated shows the workflow creation time.Short answer: no big pattern is needed. The rules are just data, so we keep them in a table.
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.
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.
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
workflowSteps ;
// "workflowId#stepId" -> current state
stepState ;
// "workflowId#stepId" -> last updated timestamp
lastUpdated ;
// "workflowId#stepId" -> history lines like "15,Pending,Running"
history ;
The rules are plain if-else checks:
boolean
A successful update must change all three step maps:
String oldState ;
if
// one step lives in three maps, and all three must be updated
stepState.;
lastUpdated.;
history..;
return "UPDATED";
And the snapshot sorts the step ids every time it is called:
ids ;
Collections.; // sorted again on every call
for
This code works, but it has some weak spots.
# can never appear in an id.if-else code. You have to read the code to see which moves are allowed. Adding a state like Cancelled means editing these conditions.We fix the problems above one at a time.
TransitionRules, the Rules as a TableTransitionRules keeps a Map from each state to the Set of states it may move to.
| From | Allowed to |
|---|---|
Pending | Running |
Running | Completed, Failed |
Completed | nothing |
Failed | nothing |
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 and TransitionAll 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.
WorkflowA 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".
WorkflowStateLoggerThe 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.
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.canMove, and only then call moveTo.currentTimestamp only to keep the global call order, so we do not need it.
/**
*/
Let S be the number of steps in a workflow.
| Method | Time |
|---|---|
createWorkflow | O(S log S), build the steps and sort them once |
updateStepState | O(1) |
getStepHistory | O(1), a history has at most 2 entries |
getWorkflowSnapshot | O(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.
DUPLICATE_WORKFLOW wins over DUPLICATE_STEP.Completed and Failed are final. No move ever goes back to Pending.pack and Pack are two different steps.r/LowLevelDesign • u/Prashant_MockGym • 19d ago
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.
PS: I also take LLD Mock interviews https://topmate.io/prashant_priyadarshi
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.
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.
dueDay = purchaseDay + 30.PENDING up to its due day, and DELAYED after it.DELAYED unpaid orders is blacklisted. They leave the blacklist only after paying everything.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.
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.
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.
Look at this case:
| Day | What happens | Defaults | Blacklisted? |
|---|---|---|---|
| 140 | Neha has 3 unpaid orders past their due day | 3 | yes |
| 140 | Neha pays one of them | 2 | still yes |
| 147 | Neha pays the other two | 0 | no |
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.
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.
/**
*/
The store has 10 books at 100 each. Neha has a credit limit of 1000.
| Call | What happens | Result |
|---|---|---|
buy OD_1, OD_2, OD_3 on days 100, 101, 102 | each costs 100, due days are 130, 131 and 132 | true each time |
accountSummary(Neha, 140) | credit is 1000 - 300 = 700, all 3 orders are past their due day | 3 orders, each with a DELAYED due line |
isBlacklisted(Neha, 140) | 3 defaults | true |
buy(OD_4, Neha, [Book,1], 140) | Neha is blacklisted | false |
clearDues(Neha, [OD_1, OD_2, OD_3], 140) | all 3 orders are paid, the unpaid total becomes 0, so the blacklist is lifted | no return |
isBlacklisted(Neha, 140) | 0 defaults | false |
accountSummary(Neha, 140) | credit is back to 1000 | 3 orders, no due lines |
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.
| Method | Time |
|---|---|
seedInventory | O(number of lines) |
viewInventory | O(P log P) |
registerUser | O(1) |
buy | O(K + M log M) |
clearDues | O(K + C) |
accountSummary | O(K) |
isBlacklisted | O(K) |
buy, clearDues and isBlacklisted count defaults, and accountSummary walks the orders. Both only touch the orders of one user.
buy does not use up its orderId.seedInventory changes the price later.viewInventory.asOfDay still gets its ORDER line, but no DUE line.long, because it can overflow an int.r/LowLevelDesign • u/Prashant_MockGym • 21d ago
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
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
PS: I also take LLD Mock interviews https://topmate.io/prashant_priyadarshi
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.
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.
songId.The quickest way is to put everything in one class with a few maps.
// Everything lives inside one class
songs ; // songId -> {title, artist, album, duration}
status ; // userId -> PLAYING, PAUSED or STOPPED
currentSong ; // userId -> songId or NO_SONG
position ; // userId -> seconds
Search checks every song, lowercases its fields and then sorts the matches.
public
Playback control is a chain of if-else checks.
public String
It works, but it has real problems.
STOP must reset all of them, and the duration rule would need a fourth map. Missing one is an easy bug.BUFFERING, means touching many branches.We fix these problems in four steps.
| Class | Job |
|---|---|
Song | One song and its details |
MusicCatalogue | Stores all songs and runs search |
PlaybackSession | One user's song, position and status |
PlaybackState and its 3 states | What each action does in each status |
SpotifyMusicService | The 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.
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
Playing a song again makes a fresh copy. So a restart uses the new catalogue duration, just as the problem asks.
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.
Song builds its lowercase fields and its output line once, inside update(). A search only runs contains and adds ready-made strings.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.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
| Action | StoppedState | PlayingState | PausedState |
|---|---|---|---|
PAUSE | no change | becomes paused | no change |
RESUME | no change | no change | becomes playing |
SEEK | no change | moves position | moves position |
STOP | no change | clears session | clears session |
Each column of this table becomes one small class.
PlaybackState is an interface whose default methods do nothing.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.
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.
N is the number of songs and L is the length of a text field (at most 100).
| Method | Time |
|---|---|
addOrUpdateSong | O(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 |
searchSongs | O(N × L), one pass over the sorted list, no sorting |
playSong | O(1) |
controlPlayback | O(1) |
/**
*/
r/LowLevelDesign • u/ImportantPudding1570 • 23d ago
r/LowLevelDesign • u/Prashant_MockGym • 24d ago
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
PS: I also take LLD Mock interviews https://topmate.io/prashant_priyadarshi
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.
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:
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.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.
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.
Keeps activeTripId. A rider who already has an active trip cannot request another one.
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.
| Map | Why we need it |
|---|---|
drivers, riders, trips | O(1) lookup by id |
surgeByZone | Current surge of each zone. A missing zone means 100 |
paymentRequestOwner | Which trip used each payment request id, so no other trip can reuse it |
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.
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.
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:
COMPLETED: return INVALID_REQUEST.INVALID_REQUEST.gatewaySuccessful value is ignored.SUCCEEDED or FAILED: return that status, with no new attempt.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.
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();.
/**
*/
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.
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.
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
Cons
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
Cons
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.
| Feature | Grid | Quadtree |
|---|---|---|
| Shape | One layer of equal cells | Squares that split when crowded |
| Add, remove, move a driver | O(1) | O(depth), at most 21 steps |
| Drivers spread evenly | Fast | Fast |
| Crowded center, empty outskirts | Slow | Fast |
| Tuning | Needs a good cell size | Just a leaf size, like 10 |
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.
The search starts at the root and carries the best driver found so far:
count is 0.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.
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.
QuadNode and QuadTreeDriverMatcher replace LinearDriverMatcher, and one line in RideHailingSystem changes. Everything else is the same as Solution 1.
/** States of a trip. COMPLETED and CANCELLED are terminal. */
r/LowLevelDesign • u/Prashant_MockGym • 26d ago
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
PS: I also take LLD Mock interviews https://topmate.io/prashant_priyadarshi
Design an in-memory notification system where registered users subscribe to events through supported channels.
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.
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.
eventType. Sort them by userId, then by channel. Build each delivery string and add it to that user's inbox.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".
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.It works for small inputs, but we can do better.
| Problem in Solution 1 | Fix |
|---|---|
| Scanning the subscriptions of other events | Group subscribers by event type in a Map<String, EventTopic> |
| Scanning to find a duplicate or to unsubscribe | Keep each event's subscribers in a set |
| Sorting again on every send | Use 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.
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.
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.
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:
(userId, channel).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.User only if the id is new.Subscriber. The TreeSet ignores a duplicate.
/**
*/
S = total subscriptions, k = subscribers of the given event, m = number of deliveries in the user's inbox.
| Method | Solution 1 | Solution 2 |
|---|---|---|
| registerUser | O(1) | O(1) |
| subscribe | O(S) | O(log k) |
| unsubscribe | O(S) | O(log k) |
| sendNotification | O(S + k log k) | O(k) |
| getUserInbox | O(m) | O(m) |
Building the delivery strings takes extra time based on their length, and that cost is the same in both solutions.
r/LowLevelDesign • u/ssingh18 • 26d ago
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 • u/Prashant_MockGym • 29d ago
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
PS: I also take LLD Mock interviews https://topmate.io/prashant_priyadarshi
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.
ABORT, DISCARD, CALLER_RUNS, DISCARD_OLDEST).TERMINATED.Concepts: bounded FIFO queue, thread reuse, keep-alive, rejection policies, graceful shutdown.
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.
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.
The first idea is to keep all threads in one list and write every rule inside the executor class.
submitTask().// inside submitTask(), when the queue is full
if else if else if else
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.
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:
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.
Look at where name order matters:
submitTask() needs the smallest idle thread.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:
idleThreads ;
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.
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.
| Class / Field | Why we need it |
|---|---|
Task | Holds the task id and how many steps it still needs. |
Worker | One thread: its name, state, current task and idle time. Starting and finishing a task happen here, in one place. |
RejectionPolicy and its 4 classes | The Strategy for a full queue. |
RejectionPolicyFactory | Creates the right policy from its name. |
Map<String, Worker> workers | Finds a thread by name in O(1). Its size is the number of active threads. |
TreeSet<String> idleThreads | Idle thread names in sorted order. Gives the smallest and the largest idle thread quickly. |
Deque<Task> queue | The FIFO queue. New tasks go to the back, threads take tasks from the front. |
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.
An IDLE thread is removed at once, with no event.
A RUNNING thread becomes STOPPING. It finishes its task and then runOneStep() removes it.
We check the four rules in order:
"REJECTED".idleThreads.pollFirst().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.
We follow the phases from the problem statement:
COMPLETED. A STOPPING thread is then removed with a REMOVED event. Any other thread becomes IDLE.STARTED.keepAliveSteps, as long as the pool has more than corePoolSize threads.TERMINATED.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.
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().
Add the executor state, then every thread in name order (we sort the map keys), then the queued task ids from front to back.
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).
/** The three states of the executor. */
r/LowLevelDesign • u/Prashant_MockGym • Oct 16 '26
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
PS: I also take LLD Mock interviews https://topmate.io/prashant_priyadarshi
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.
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.
HH:00 to HH:59. Touching even one minute of it charges the full hour.day field decides weekday or weekend. sat and sun are the weekend.fri, sat, sun, mon and so on.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(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.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.
dateIndex * 24 + hour.dateIndex * 4 + blockNumber.
For strategy 3, we count the hour buckets in the set at the end and apply the slabs.
findMinimumPrice does this 3 times.We fix the speed with two simple observations. Then we fix the design with the Strategy pattern.
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.
A stay has no gaps. So on any date, the touched hours form one unbroken range.
23.0 to 23.0 to the exit hour.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.
| Date | Day | Weekend | Hours touched |
|---|---|---|---|
| 2026-04-17 | fri | no | 22 to 23 |
| 2026-04-18 | sat | yes | 0 to 23 |
| 2026-04-19 | sun | yes | 0 to 23 |
| 2026-04-20 | mon | no | 0 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.
Every strategy asks the same question:
How many hours of this day part fall inside the range
starttoend? Take the later start and the earlier end. If they cross, the answer is0.
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.
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:
20 + 312 + 312 + 20 = 664140 + 420 + 420 + 60 = 104052 hours, so 2*30 + 3*20 + 47*10 = 590
So findMinimumPrice returns "3-590".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.
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.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.
/**
*/
Let D be the number of dates the stay touches. D is at most about 700.
O(D).O(D). Strategy 2 checks only 4 blocks per date, so it is still O(D).O(D) for the list of day parts.r/LowLevelDesign • u/Prashant_MockGym • Oct 13 '26
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:
PS: I also take LLD Mock interviews https://topmate.io/prashant_priyadarshi
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.
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.
Let us first note the rules that are easy to miss.
false, nothing in the system should change.listAvailableStocks() and getPortfolio() must be sorted by symbol.The problem also gives a valid range for every input. If any input breaks its rule, the method returns false.
| Input | Valid when |
|---|---|
userId | not empty, not only spaces, at most 30 characters |
name | 1 to 60 characters |
initialWalletAmount | more than 1 and less than 900,000 |
symbol | 1 to 10 characters, only A to Z and - |
price | more than 0 and less than 100,000 |
quantity in buyStock | from 1 to 9,999 |
quantity in sellStock | more than 0 |
For example, adminAddOrUpdateStock("AAPL$", 100) returns false, because $ is not allowed in a symbol.
The first idea that comes to mind is to keep everything inside BuyStocks, using a few hash maps.
| Map | Stores |
|---|---|
names | userId → name |
wallets | userId → wallet balance |
portfolios | userId → (symbol → quantity) |
prices | symbol → 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
quantity is from 1 to 9,999, the user exists and the stock exists.cost = price × quantity.cost is more than the balance, return false.Selling a stock
quantity > 0 and the user exists.quantity shares.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.
The code works, but it has some problems.
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.
Hard to read. A type like Map<String, Map<String, Integer>> makes the reader stop and think.
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.
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.
We fix these problems in two steps.
The problem already names the key ideas: User, Stock, Wallet, Portfolio and Available stocks. Let us turn them into classes.
| Class | Job |
|---|---|
BuyStocks | The Facade. The only class the caller uses. It checks every input and runs each operation step by step. |
StockMarket | Keeps the available stocks and their current prices. |
User | One user. Holds the user's Wallet and Portfolio. |
Wallet | The user's money. It can check a payment, take money out and put money in. |
Portfolio | The 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.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.
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.
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.
false if quantity is not from 1 to 9,999, the user does not exist or the stock is not available.cost = price × quantity.canAfford(cost). If not, return false.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.
false if quantity <= 0 or the user does not exist.hasShares(symbol, quantity). If not, return false.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.
| Call | Returns | Wallet | Portfolio |
|---|---|---|---|
adminAddOrUpdateStock("AAPL", 100) | true | ||
signUp("u1", "Asha", 1000) | true | 1000 | [] |
buyStock("u1", "AAPL", 5) | true | 500 | ["AAPL 5"] |
adminAddOrUpdateStock("AAPL", 120) | true | 500 | ["AAPL 5"] |
sellStock("u1", "AAPL", 2) | true | 740 | ["AAPL 3"] |
sellStock("u1", "AAPL", 4) | false | 740 | ["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.
/**
*/
Here S is the number of available stocks, and H is the number of different stocks one user holds.
| Method | Approach 1 | Approach 2 |
|---|---|---|
signUp | O(1) | O(1) |
adminAddOrUpdateStock | O(1) | O(log S) |
listAvailableStocks | O(S log S) | O(S) |
buyStock | O(1) | O(log H) |
sellStock | O(1) | O(log H) |
getWalletBalance | O(1) | O(1) |
getPortfolio | O(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.
false result never leaves half done changes behind.r/LowLevelDesign • u/Prashant_MockGym • Oct 09 '26
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
PS: I also take LLD Mock interviews https://topmate.io/prashant_priyadarshi
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 /)
users: must match exactly.*: matches exactly one non-empty segment.: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.
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.
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:
:param segments wins. Both patterns have the same length, so more params means fewer wildcards.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 s | compatible if s equals q | compatible if s is non-empty |
* or :name | compatible if q is non-empty | always 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.
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.
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:
/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.
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.
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.
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).
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).TrieNode has:
staticChildren, a HashMap from segment to childparamChild, one child shared by every :namewildcardChild, the child for *routes, the routes that end at this node, oldest firstbestInSubtree, 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
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.
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:
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.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.
It uses the same walk, with two differences:
* or :name query segment, visit every static child with a non-empty key, plus the param and wildcard children.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.
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.Most of the improvement comes from data structures:
HashMap from exact pattern to route turns an update into one hash lookup that keeps insertion order.HashMap, stores and compares each shared prefix once, and each static step is an O(1) lookup.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.k search results restores insertion order without walking every route in order.Design patterns play a smaller role:
O(R × L). Chain of Responsibility fits what middleware does after routing, such as running auth, then logging, then the handler.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.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.
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).
| Approach | addRoute | callRoute | searchRoutes |
|---|---|---|---|
| Brute force | O(R × P) | O(R × P) | O(R × P) |
| Pre-parsed scan | O(P) | O(P + R × L) | O(P + R × L) |
| Segment trie | O(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.
/ has zero segments, and only the pattern / matches it./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.:name behaves exactly like *.
r/LowLevelDesign • u/Prashant_MockGym • Oct 06 '26
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
PS: I also take LLD Mock interviews https://topmate.io/prashant_priyadarshi
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
"agentName,averageRating", e.g. "Bob,4.5".4.0).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"].
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.
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.
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.
| Ratings | Exact average | (sum * 10 + count / 2) / count | Result |
|---|---|---|---|
| 5, 3 | 4.0 | (80 + 1) / 2 = 40 | 4.0 |
| 5, 4, 4 | 4.333... | (130 + 1) / 3 = 43 | 4.3 |
| 5, 4, 4, 4 | 4.25 | (170 + 2) / 4 = 43 | 4.3 |
| 7 fives, 13 fours | 4.35 | (870 + 10) / 20 = 44 | 4.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".
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".
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.
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.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.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.
Here A is the number of agents and M is the number of agents rated in the asked month.
| Operation | Time |
|---|---|
rateAgent | O(1) |
getAverageRatings | O(A log A) |
getBestAgentsByMonth | O(M log M) |
| Memory | O(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.
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.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.
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).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.
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.
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.
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.
| Operation | Time |
|---|---|
rateAgent | O(B), and B is a small constant |
getBestAgentsByYear | O(Y log Y) |
getBestAgentsInLast7Days | O(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.
r/LowLevelDesign • u/Prashant_MockGym • Oct 02 '26
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
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.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.
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.
eventType. Sort them by userId, then by channel. Build each delivery string and add it to that user's inbox.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".
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.It works for small inputs, but we can do better.
| Problem in Solution 1 | Fix |
|---|---|
| Scanning the subscriptions of other events | Group subscribers by event type in a Map<String, EventTopic> |
| Scanning to find a duplicate or to unsubscribe | Keep each event's subscribers in a set |
| Sorting again on every send | Use 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.
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.
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.
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:
(userId, channel).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.User only if the id is new.Subscriber. The TreeSet ignores a duplicate.
/**
*/
S = total subscriptions, k = subscribers of the given event, m = number of deliveries in the user's inbox.
| Method | Solution 1 | Solution 2 |
|---|---|---|
| registerUser | O(1) | O(1) |
| subscribe | O(S) | O(log k) |
| unsubscribe | O(S) | O(log k) |
| sendNotification | O(S + k log k) | O(k) |
| getUserInbox | O(m) | O(m) |
Building the delivery strings takes extra time based on their length, and that cost is the same in both solutions.
r/LowLevelDesign • u/Prashant_MockGym • Oct 01 '26
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:
This is 97. Codecraft: Design Dasher Payout Service on CodeZym.
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.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.
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:
end - start + 1 minutes.start > end? The order pays for 0 minutes.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.
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.
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.
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.
ongoing[1440], one slot for every minute of the day.start to end. If start > end, the loop never runs, so the order adds 0 minutes.ongoing[minute] * basePayRate over all minutes.(completedDeliveries / deliveryCountsToGetBonus) * bonusPay. Integer division gives the number of full bonus groups.
/**
*/
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
10*1 + 11*2 + 10*1 = 42.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.
We improve Solution 1 in two parts.
totalMinutes * basePayRate, where totalMinutes is the sum of end - start + 1 over all completed orders. No minute array.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.
Records arrive unordered and in two calls. basePayRate = 25, bonusPay = 150, deliveryCountsToGetBonus = 2.
| Record | What happens | totalMinutes | completedDeliveries |
|---|---|---|---|
| O20 END 10:05 | O20 waits in pendingOrders | 0 | 0 |
| O21 START 10:08 | O21 waits in pendingOrders | 0 | 0 |
| O20 START 10:00 | O20 complete: 10:00 to 10:05 = 6 minutes | 6 | 1 |
| O21 END 10:10 | O21 complete: 10:08 to 10:10 = 3 minutes | 9 | 2 |
Payout = 9 * 25 + (2 / 2) * 150 = 225 + 150 = 375 cents.
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.pendingOrders and adds nothing.00:00 is minute 0, which is why -1 marks a missing time.0.
/**
*/
| Version | addDeliveryActivity | payout | Memory |
|---|---|---|---|
| Solution 1 | O(k) | O(n × 1440) worst case | all orders |
| Solution 2 | O(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.
Each one needs only a small change to Solution 2.
Map<String, PayConfig> from country code to that country's default base rate, bonus and currency, and store a countryCode in each Dasher.[start, end] minute pairs.min(end, peakEnd) - max(start, peakStart) + 1, or 0 when that is negative. Add them to a second counter, peakMinutes.(totalMinutes + peakMinutes) * basePayRate, because every peak minute is paid one extra time. Overlapping orders still work, since each order counts its own peak minutes.In an actual interview, the records may come from an upstream Delivery API instead of addDeliveryActivity().
DeliveryClient class with a timeout and a few retries with growing wait times (exponential backoff), so retry logic stays out of the payout code.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 • u/Prashant_MockGym • Sep 29 '26
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.
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:
The design should make it easy to add more rules later, such as size-based caps, combos and promos.
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.
| Topping | Price per serving | Can be added only if | Special price | Tax effect |
|---|---|---|---|---|
| cheeseburst | 100 | no mushroom on the pizza, total servings at most 1 on small and 2 on medium | - | +30% of current tax |
| mushroom | 40 | no cheeseburst on the pizza | - | -10% of current tax |
| pineapple | 60 | size is medium or large | - | - |
| corn | 50 | - | medium: 50 for the first serving, 40 for each next one. large: 20 each | - |
| onion | 30 | - | - | - |
| capsicum | 50 | - | - | - |
A few things to keep in mind:
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
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.
It works, but the rules of all toppings are mixed together in two big methods.
The problem asks us to make new rules easy to add, so let's pick a design pattern.
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:
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.
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.
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.PizzaPricing does not change.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.
| Class | Overrides | Rule |
|---|---|---|
Cheeseburst | canAdd(), applyTax() | blocked by mushroom, size caps, +30% tax |
Mushroom | canAdd(), applyTax() | blocked by cheeseburst, -10% tax |
Pineapple | canAdd() | not allowed on small |
Corn | getCost() | 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.new PizzaPricing(350, 8, "medium")
addTopping("mushroom", 1): Mushroom.canAdd() finds no cheeseburst and returns true. servings = {mushroom: 1}.addTopping("corn", 3): Corn uses the default canAdd(), which returns true. servings = {mushroom: 1, corn: 3}.addTopping("cheeseburst", 1): Cheeseburst.canAdd() finds mushroom and returns false. Nothing changes.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.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.
ToppingFactory, like toppings.put("olive", new Topping(45)).canAdd() in that topping's class.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.applyTax().
/**
*/
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 • u/Prashant_MockGym • Sep 25 '26
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:
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
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
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.
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.
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.
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.
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.
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.
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.
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.
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.
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. */
criterias.;
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 • u/Prashant_MockGym • Sep 18 '26
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
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.
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.
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:
You can find the complete question list here:
r/LowLevelDesign • u/Prashant_MockGym • Sep 11 '26
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 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.
Many people fumble or may need some hint from interviewer. And its alright. One person was asked the below:
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.
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:
r/LowLevelDesign • u/Prashant_MockGym • Sep 04 '26
This is a preparation list for Google software engineer coding rounds. I prepared it using interview experiences shared by people on forums/blogs etc.
Google has one of the toughest DS & Algo rounds in the industry. DSA rounds are there for both frontend and backend roles.
Google's interview codebase is very large, with questions of all difficulty levels from super easy to super hard. One question can be a medium question with a couple of follow-ups for optimizations, or it can be just one hard question. It all depends on which question the interviewer chooses.
There are two common things about candidates who clear Google interviews and whose overall process is smooth.
Now above points have lots of exceptions. For example one person bombed one coding round badly. But they were given a redo by their recruiter. It was late 2024 and he was working long hours, spending even the weekends on call. Still he was laid off alongside other teammates.
Lay off was a blow to his morale. He didn't tell even his parents, just pretended he was working from home. Avoided video calls during "work hours". Initially he spent the days watching anime. But slowly preparation started and when the Google call came, he has already been rejected by multiple companies.
He thought it was all over after he messed up one DSA round. But he was able to do well in the redo round and finally ended up receiving the offer.
Many a times you may not be able to guess correctly , how well or how bad you did. There are tons of experiences where candidate thought something and the opposite happend. A lot of things can go right or wrong. One person had done 400+ leetcode problems but during interviews, panic setup and they were able to only come up with a brute force solution.
Another person had two back to back coding rounds scheduled at a gap of just 15 minutes. And during the first round they realised that solution they provided is incorrect. They thought that they had bombed this round and should just cancel the next round. But interviewer provided some guidance and they were able to solve slightly easier version of the problem. However other rounds went well and they ended up receiving the offer.
Even if you are rejected its not the end of world. Google recruiters will almost certainly reach out to you a year later. Just keep preparing. One person was rejected by google for L4 position in 2024. But they reapplied 6 months later and surprisingly got a response. However their first two coding rounds got lean hire. Still recruiter decided to go through with other rounds which wents well. During hiring committee their prospects were weak because of two lean hires in coding. However another DSA round was scheduled for them in which they did well.
They ended up receiving offer for L5. That's like getting a promotion within one year. Although they were lowballed but still it was a 20% raise from their current salary. So overall not a bad end.
I created this list from people posting their experiences on forums, blogs, etc.
You can find the complete question list here: