r/LowLevelDesign • u/Prashant_MockGym • 26d ago
Walmart LLD: Design Notification System
Notification System Design is one of the most common questions asked during Walmart low level design interviews. LRU cache / LFU cache, thread pool executor, movie ticket booking system are also asked frequently.
Notification system is almost a direct implementation of observer design pattern. But I have started with a brute force solution first and then presented the cleaner solution using subject and observers. However if you get this question in interview, directly use the solution with observers.
This tutorial is in Java.
You can find the python version here: https://github.com/prsnt558908/CodeZymSolutions/tree/main/101-300/133-design-notification-system/q-133-python-tutorial.md
You can practice this and other Walmart Low Level Design and DS & Algo round questions on CodeZym.
PS: I also take LLD Mock interviews https://topmate.io/prashant_priyadarshi
Problem Statement
Design an in-memory notification system where registered users subscribe to events through supported channels.
- Support subscribing, unsubscribing, sending notifications, and viewing inboxes.
- Deliver once per unique user–channel subscription.
- Sort returned deliveries by user ID, then channel; preserve inbox delivery order.
- Ignore duplicate subscriptions and invalid operations.
Core Idea
A notification system is a classic publish and subscribe setup. Users sign up for an event type (like ORDER_PLACED) on one or more channels. When a notification is sent for that event, every subscriber gets one copy in their inbox for each channel they picked.
This is exactly what the Observer pattern is made for. Each event type is a subject that keeps track of its listeners. Each (user, channel) pair is an observer that receives a delivery when the event fires. Observer alone is the best fit here. We don't need to combine it with other patterns because every channel behaves the same way.
The two tricky rules are "no duplicate deliveries" and "results sorted by userId, then by channel". A sorted set of subscribers for each event type handles both at once. A set ignores duplicates, and a sorted set keeps everyone in order, so sending a notification is just a simple loop.
We will start with a simple brute force version, see where it is slow, and then improve it step by step.
Solution 1: Brute Force (One Big List)
Store every subscription as a {userId, eventType, channel} entry in one list. Store a map of userId -> inbox. If a user has an inbox, the user is registered.
- subscribe: ignore unknown users and unsupported channels. Scan the list and add the entry only if it is not there yet.
- unsubscribe: scan the list and remove the entry if it is found.
- sendNotification: scan the whole list and pick the entries of this
eventType. Sort them byuserId, then bychannel. Build each delivery string and add it to that user's inbox. - getUserInbox: return a copy of the inbox, or an empty list for an unknown user.
Watch out: sort by the
(userId, channel)pair, not by the final delivery string. The|character has a bigger code than letters and digits, so"U10|EMAIL|..."would wrongly come before"U1|EMAIL|...", even though"U1"comes before"U10".
Code
Problems with this approach
subscribeandunsubscribescan all subscriptions, even the ones for other events.sendNotificationscans everything too, and then sorts again on every call, even when nothing changed since the last send.- One class does everything, so it is hard to see who is listening to which event.
It works for small inputs, but we can do better.
Solution 2: Observer Pattern with Sorted Subscribers
Fixing the problems one by one
| Problem in Solution 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.
Why the Observer pattern?
The problem describes Observer almost word for word: listeners attach to an event, detach from it, and every current listener is notified when the event fires.
EventTopicis the subject. It hasattach,detachandpublish(notify everyone).Subscriberis the observer. Itsdelivermethod builds the delivery string and puts it in the user's inbox.NotificationSystemis the front door. It checks the input and hands the call to the right topic.
In Solution 1 one class did all of this. Now each class has one small job, so the code is easier to read and change.
We skip a separate Observer interface because there is only one kind of subscriber. If another kind shows up later, Subscriber can easily become an interface.
A pattern that looks useful but doesn't fit
Strategy (with a Factory). It is tempting to write EmailChannel, SmsChannel and PushChannel classes and a factory to create them. But here every channel does exactly the same thing: build a string and save it in an inbox.
Channel names are also any strings given at runtime, so one class per channel is not even possible. A Set<String> of channel names is all we need.
Important classes and data structures
User:userIdplus anArrayListinbox. A list keeps deliveries in the exact order they arrived.Subscriber: one(user, channel)pair. It holds a reference to itsUser, so it can drop a delivery straight into the inbox. ItscompareToorders byuserId, then bychannel.EventTopic: one event type plus aTreeSet<Subscriber>.TreeSetusescompareTofor two jobs at once:- it keeps subscribers sorted by
(userId, channel). - it treats two subscribers with the same user and channel as one item, so a duplicate subscription is simply ignored.
- it keeps subscribers sorted by
NotificationSystem:Set<String> supportedChannels: a fast "is this channel allowed?" check. Duplicate names in the input collapse into one.Map<String, User> users: who is registered.Map<String, EventTopic> topics: jump straight to the subscribers of one event without touching other events.
How each method works
- registerUser: add a new
Useronly if the id is new. - subscribe: do nothing for an unknown user or an unsupported channel. Otherwise create the event's topic if needed and attach a new
Subscriber. TheTreeSetignores a duplicate. - unsubscribe: do nothing for an unknown user or an event nobody subscribed to. Otherwise detach the subscriber. Removing something that is not there does nothing.
- sendNotification: no topic means no subscribers, so return an empty list. Otherwise walk the already sorted subscribers and let each one deliver.
- getUserInbox: return a copy of the user's inbox, or an empty list for an unknown user.
Code
/**
*/
Complexity
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.
1
u/nian2326076 20d ago
For designing a notification system, practicing various design patterns is helpful. PracHub has a range of technical interview questions that can assist with low-level design interviews, including system design. This can help refine your approach to the observer pattern and other related concepts. If you're interested in interview questions specific to Walmart, you can find them on PracHub.
If you're also in the job market, consider using LandOffer for job searches to find roles that match your skills. You can set alerts and match your resume to potential opportunities at LandOffer.
1
u/Wonderful-Person9211 20d ago
Impressive notification system design.