On this page

LLD Practice: Medium

These problems introduce real-world complexity: multiple stakeholders, concurrent access, state machines, and integration with external systems. Each problem should take 45-60 minutes. Focus on the core domain model first, then layer in cross-cutting concerns like concurrency and error handling.

The page started with 10 problems (Problems 1–10). Problems 11–15 add five classic case studies that interviewers ask at this level: library, ATM, movie booking, hotel and Splitwise. The ladder below orders all 15. Do the Easy ladder first. When you finish this one, go on to LLD Practice: Hard.

The ladder

#ProblemWhat it practisesTime boxFull case study
1Library Management (P11)Book vs copy modelling, Strategy for fines, two desks lending the last copy45 minLibrary Management
2ATM (P12)State pattern, Chain of Responsibility for notes, atomic withdrawal45 minATM
3Booking Calendar (P7)Interval overlap, slot generation, preventing double booking50 minMeeting Room Booking
4Notification System (P1)Strategy (channels), Template Method (pipeline), retries, rate limits50 minNotification Service
5Movie Booking (P13)Seat holds with timeouts, all-or-nothing locking of several seats50 minMovie Booking
6Hotel Management (P14)Date-range availability, booking state machine, overbooking under concurrency55 minHotel Management
7Splitwise (P15)Strategy (split types), money rounding, balance simplification50 minSplitwise
8Inventory Management (P6)Reservations with expiry, atomic conditional updates, Strategy for warehouses50 minShopping Cart
9Order Management (P5)State machine with guards, sub-orders, Saga with compensation55 minFood Delivery, Shopping Cart
10Payment Gateway (P2)Adapter, idempotency keys, safe failover55 min—
11Search Autocomplete (P8)Trie with cached top-K, ranking, copy-on-write rebuilds50 min—
12File Storage Service (P9)Content-addressed storage, versioning, multipart upload, access control60 minFile System
13Social Media Feed (P3)Strategy (fanout), cursor pagination, ranking60 min—
14Ride Matching (P4)Spatial index, offer timeouts, ride state machine, assigning a driver once60 minRide Sharing
15Workflow Engine (P10)DAG execution, State, Command with compensation, persistence60 minTask Scheduler

How to use this ladder

  1. Go in order. Rungs 1–7 are domain models with one hard concurrency point each. Rungs 8–15 add external systems (payment providers, storage, maps) that you have to hide behind interfaces.
  2. Time-box with the LLD Interview Framework. At this level the interviewer expects the concurrency step. Name the shared state and the lock before the time is up.
  3. Open "Hints" after five minutes stuck, "Solution outline" after the timer. Most outlines end with the edge cases interviewers like to ask about. Check you'd have an answer for each one.
  4. Practise one rung as a 90-minute machine coding round each week: runnable code, an in-memory store, a small driver and tests.
  5. Move to Hard once rungs 9–15 feel routine.

Problem 1: Notification System

Design a notification system that sends messages across multiple channels (email, SMS, push, in-app) with templates, scheduling, user preferences, and delivery tracking.

Requirements

  • Multiple channels: Email, SMS, Push Notification, In-App
  • Template engine with variable substitution
  • User notification preferences (opt-in/opt-out per channel per notification type)
  • Priority levels: LOW, MEDIUM, HIGH, CRITICAL
  • Scheduling: send now or schedule for later
  • Delivery tracking: sent, delivered, failed, read
  • Rate limiting per user per channel
  • Retry failed deliveries with backoff

Key Classes

classDiagram
    class NotificationService {
        +send(request: NotificationRequest): string
        +schedule(request, sendAt): string
        +getStatus(notificationId): DeliveryStatus
        +cancel(notificationId)
    }

    class NotificationRequest {
        -userId: string
        -type: NotificationType
        -templateId: string
        -variables: Map
        -priority: Priority
        -channels: Channel[]
    }

    class Channel {
        <<interface>>
        +send(message: RenderedMessage): DeliveryResult
        +getDeliveryStatus(externalId): Status
    }

    class EmailChannel {
        +send(message): DeliveryResult
    }

    class SMSChannel {
        +send(message): DeliveryResult
    }

    class PushChannel {
        +send(message): DeliveryResult
    }

    class UserPreferences {
        +isOptedIn(userId, type, channel): boolean
        +getPreferredChannels(userId, type): Channel[]
    }

    class TemplateEngine {
        +render(templateId, variables): RenderedMessage
    }

    NotificationService --> Channel
    NotificationService --> UserPreferences
    NotificationService --> TemplateEngine
    EmailChannel ..|> Channel
    SMSChannel ..|> Channel
    PushChannel ..|> Channel

Design Hints

  • Strategy Pattern for channels — each channel implements send() differently
  • Template Method for the notification pipeline: validate → check preferences → render template → rate check → send → track
  • Observer Pattern for delivery status updates — webhook callbacks from providers
  • Priority queue for send ordering: CRITICAL notifications skip the queue
  • State machine for delivery status: PENDING -> SENT -> DELIVERED -> READ or PENDING -> SENT -> FAILED -> RETRY -> ...
Hints
  • One request can become several deliveries (email and push). Track status per delivery (notification × channel), not per notification.
  • Sending to a provider and recording that you sent are two steps. If the process crashes between them, will a retry send a duplicate email? Pass an idempotency key to the provider where it supports one.
  • Preferences and quiet hours are filters that run before the channel. CRITICAL alerts (a password reset, fraud) usually bypass opt-outs and quiet hours. Ask.
  • A scheduled notification is a delayed job. Where does it live while it waits, and what happens if the user opts out before it fires?
Solution outline
  • Entities: NotificationRequest, Notification (id, user, type, priority, status), Delivery (notification, channel, attempt count, status, provider message id), Template (per channel and locale), UserPreferences, Channel, DeliveryResult.
  • Pipeline: validate → resolve the user's channels from preferences → render the template per channel → check the per-user, per-channel rate limit → enqueue a delivery in a priority queue → a worker calls channel.send() → record the result → on a transient failure, re-enqueue with backoff, and on a permanent one (invalid number), mark it FAILED.
  • Patterns: Strategy for channels. Template Method or a list of pipeline steps (each step an object, closer to Chain of Responsibility). The step list is easier to extend. Observer for provider webhooks updating status. Adapter around each provider SDK.
  • Concurrency: worker pool consuming a priority queue. Separate queues per priority stop a flood of LOW marketing messages from starving CRITICAL ones. Status updates from webhooks race with the worker's own update: only allow forward transitions (SENT → DELIVERED, never DELIVERED → SENT), and use compare-and-set on the status.
  • Edge cases: a template variable missing (fail at render time, before sending), a user with no verified channel, duplicate requests from the caller (dedupe by a client-supplied key), and cancelling a notification that is already sending.
  • Full version: Notification Service.

Problem 2: Payment Gateway Abstraction

Design an abstraction layer over multiple payment providers (Stripe, PayPal, Razorpay) with unified interface, automatic failover, and transaction management.

Requirements

  • Unified API for charge, refund, capture, cancel
  • Multiple payment methods: card, bank transfer, wallet
  • Provider selection: primary + fallback
  • Idempotency: same payment request must not charge twice
  • Webhook handling for async payment updates
  • Transaction log with audit trail
  • PCI compliance: never store full card numbers

Key Classes

classDiagram
    class PaymentGateway {
        +charge(request: ChargeRequest): PaymentResult
        +refund(paymentId, amount?): RefundResult
        +capture(authorizationId): CaptureResult
        +getPaymentStatus(paymentId): PaymentStatus
    }

    class PaymentProvider {
        <<interface>>
        +authorize(request): AuthResult
        +capture(authId): CaptureResult
        +charge(request): ChargeResult
        +refund(chargeId, amount): RefundResult
    }

    class StripeProvider {
        +authorize(request): AuthResult
        +charge(request): ChargeResult
    }

    class PayPalProvider {
        +authorize(request): AuthResult
        +charge(request): ChargeResult
    }

    class IdempotencyStore {
        +get(key): StoredResult?
        +set(key, result, ttl)
    }

    class TransactionLog {
        +record(event: PaymentEvent)
        +getHistory(paymentId): PaymentEvent[]
    }

    PaymentGateway --> PaymentProvider
    PaymentGateway --> IdempotencyStore
    PaymentGateway --> TransactionLog
    StripeProvider ..|> PaymentProvider
    PayPalProvider ..|> PaymentProvider

Design Hints

  • Adapter Pattern for payment providers — normalize different APIs to a common interface
  • State Machine for payment lifecycle: CREATED -> AUTHORIZED -> CAPTURED -> SETTLED or CREATED -> AUTHORIZED -> VOIDED
  • Idempotency key stored in a map: before processing, check if this key was already processed and return cached result
  • Failover: if primary provider returns a network error (not a business error like "card declined"), retry with the fallback provider
  • Never store raw card details — use tokenized references from the provider

Correction (2026-11-10): a network error does not mean the charge failed

The failover hint above says to retry with the fallback provider on a network error. That's only safe when you know the request never reached the primary, for example a connection refused or a DNS failure before anything was sent. A timeout or a dropped connection after sending is ambiguous. The primary may have charged the card and the response was lost. Failing over then charges the customer twice. For ambiguous failures: mark the payment UNKNOWN, query the primary for its status (using the same idempotency key or your own reference), and fail over only once the primary confirms nothing happened. A webhook or reconciliation job settles payments that stay UNKNOWN.

Hints
  • Write down the payment states first. Every API method is a transition, and the state machine decides which calls are legal (you can't refund an authorization that was never captured).
  • The idempotency check and the "mark in progress" step must be one atomic step. Otherwise two identical requests arriving together both pass the check.
  • Classify errors into three buckets: business (card declined: don't retry, don't fail over), definitely-not-sent (safe to fail over), and ambiguous (see the correction above).
  • Money: store amounts as integer minor units plus a currency code. Some currencies have 0 or 3 decimal places.
Solution outline
  • Entities: PaymentGateway (the facade), PaymentProvider (port), StripeAdapter, PayPalAdapter and RazorpayAdapter, Payment (id, idempotency key, amount, currency, status, provider, provider reference), PaymentEvent (append-only audit), IdempotencyStore, ProviderRouter.
  • Charge flow: atomically putIfAbsent(idempotencyKey, IN_PROGRESS). If a finished result exists, return it. If one is in progress, return 409 or wait. Create the Payment, then the router picks a provider. Call it through the adapter, record the event, update the state and store the final result under the key.
  • Patterns: Adapter per provider. Facade for the gateway. State for the payment lifecycle. Strategy for provider routing (by cost, success rate, currency or card network). A circuit breaker per provider so failover kicks in quickly.
  • Concurrency: the idempotency store is the lock. Use one row per key with a unique constraint, or ConcurrentHashMap.putIfAbsent in memory. Webhooks and the synchronous response can arrive in either order. Apply each transition only if it's valid from the current state (compare-and-set on status, or a version column).
  • Edge cases: partial refunds adding up to more than the captured amount, a webhook for a payment you don't know yet (store and replay it), a currency the chosen provider doesn't support, and an idempotency key reused with a different amount (reject it).

Problem 3: Social Media Feed

Design the feed generation system for a social media platform that supports posts, follows, likes, and algorithmic ranking.

Requirements

  • Users can create posts (text, image, video)
  • Follow/unfollow users
  • Generate personalized feed from followed users' posts
  • Feed strategies: chronological and ranked (by engagement)
  • Pagination with cursor-based pagination
  • Feed pre-generation (fanout-on-write) vs on-demand (fanout-on-read)
  • Support for celebrities (millions of followers)

Key Classes

classDiagram
    class FeedService {
        +getFeed(userId, cursor?): FeedPage
        +refreshFeed(userId)
    }

    class FeedGenerator {
        <<interface>>
        +generate(userId, cursor): Post[]
    }

    class FanoutOnWrite {
        +onPostCreated(post): void
        +generate(userId, cursor): Post[]
    }

    class FanoutOnRead {
        +generate(userId, cursor): Post[]
    }

    class HybridFanout {
        -followerThreshold: number
        +onPostCreated(post): void
        +generate(userId, cursor): Post[]
    }

    class FeedRanker {
        +rank(posts: Post[], userId): Post[]
    }

    FeedService --> FeedGenerator
    FeedService --> FeedRanker
    FanoutOnWrite ..|> FeedGenerator
    FanoutOnRead ..|> FeedGenerator
    HybridFanout ..|> FeedGenerator

Design Hints

  • Hybrid fanout: regular users use fanout-on-write (pre-compute feeds), celebrities use fanout-on-read (too expensive to write to millions of follower feeds)
  • The threshold is typically around 10K-50K followers
  • Strategy Pattern for feed generation — switch between chronological and ranked
  • Cursor-based pagination: use (timestamp, postId) as cursor for stable pagination
  • Feed cache: pre-computed feeds stored in Redis sorted sets (ZRANGEBYSCORE for cursor queries)
  • Ranking signals: recency, engagement (likes/comments), author affinity, content type preference
Hints
  • This is a design for an in-process model, not a distributed system. Keep feeds as in-memory structures behind a FeedStore interface, and say where Redis would slot in.
  • An offset (page 3 of 20) breaks when new posts arrive: items shift and the user sees duplicates. That's why the cursor is (timestamp, postId).
  • Ranked feeds and cursors don't mix easily, because scores change. A common answer is to rank a fixed candidate window and paginate within it.
  • Unfollow: does an old post from that author vanish from the pre-computed feed right away, or at the next rebuild?
Solution outline
  • Entities: User, Post (id, author, createdAt, content, counters), FollowGraph (followers and followees per user), FeedStore (per-user list of post ids, capped at N), FeedGenerator (strategy), FeedRanker (strategy), Cursor.
  • Write path (fanout-on-write): when a post is created, append its id to the feed of every follower. Skip authors above the celebrity threshold.
  • Read path: merge the user's stored feed with the recent posts of the celebrities they follow (fanout-on-read), using a k-way merge by (createdAt, id) that starts after the cursor. Rank if the feed is ranked, cut to the page size and return the last item as the next cursor.
  • Patterns: Strategy for both generation and ranking. Observer for onPostCreated triggering the fanout. Hybrid fanout is itself a strategy that chooses per author.
  • Concurrency: fanout runs asynchronously on a worker pool, so posting returns fast. Each user's feed list needs its own lock or a concurrent structure (a concurrent skip list keyed by (createdAt, id) keeps it ordered with lock-free reads). Likes are counters: use atomics, not read-then-write.
  • Edge cases: a deleted post still sitting in feeds (filter on read using a tombstone set), a user who follows nobody (show a cold-start feed), a user who becomes a celebrity (switch strategy for new posts only), and two posts with the same timestamp (the id tie-breaker in the cursor).

Problem 4: Ride Matching Engine

Design the matching engine that pairs riders with nearby drivers in a ride-hailing application.

Requirements

  • Riders request rides with pickup and destination locations
  • Drivers broadcast location every few seconds
  • Match rider to best available driver based on: distance, ETA, rating, acceptance rate
  • Driver can accept or decline (timeout: 15 seconds)
  • If declined, offer to next best driver
  • Surge pricing based on supply/demand ratio in an area
  • Support for ride types: economy, premium, shared

Key Classes

classDiagram
    class MatchingEngine {
        +requestRide(rideRequest): MatchResult
        +onDriverLocationUpdate(driverId, location)
        +onDriverResponse(driverId, rideId, accepted)
    }

    class SpatialIndex {
        +findNearby(location, radius): Driver[]
        +update(driverId, location)
        +remove(driverId)
    }

    class DriverScorer {
        +score(driver, rideRequest): number
    }

    class SurgePricing {
        +calculateMultiplier(area): number
        +getAreaDemand(area): SupplyDemand
    }

    class RideStateMachine {
        +transition(event): RideState
    }

    MatchingEngine --> SpatialIndex
    MatchingEngine --> DriverScorer
    MatchingEngine --> SurgePricing
    MatchingEngine --> RideStateMachine

Design Hints

  • Geospatial index for driver locations — use a grid/quadtree or H3 hex cells for O(1) nearby lookups (Correction (2026-11-10): only the fixed grid and H3 cell lookups are O(1) per cell. A quadtree lookup is O(log n) plus the number of results, and any "nearby" query must also check neighbouring cells, so the real cost grows with how many drivers are in them.)
  • Scoring function: score = w1 * (1/distance) + w2 * rating + w3 * acceptanceRate + w4 * (1/eta)
  • State Machine for ride lifecycle: REQUESTED -> MATCHING -> DRIVER_ASSIGNED -> PICKUP -> IN_RIDE -> COMPLETED
  • Driver offer chain: sort drivers by score, offer to top driver, if timeout/decline, offer to next
  • Surge: grid the city into zones, track request rate vs available drivers per zone, adjust multiplier
Hints
  • The race that matters: two ride requests choose the same top driver at the same moment. Exactly one offer may be outstanding per driver.
  • The 15-second offer timeout is a scheduled event. When it fires, the driver may have accepted a millisecond earlier, so the accept and the timeout race too.
  • Location updates arrive far more often than ride requests. Make the update path cheap: move the driver between grid cells only when the cell changes.
  • Keep the rider-facing ride state machine separate from the driver's own status (OFFLINE, AVAILABLE, OFFERED, ON_TRIP).
Solution outline
  • Entities: Rider, Driver (status, location, rating, acceptance rate, vehicle type), RideRequest, Ride (state, rider, driver, fare), Offer (ride, driver, expiry), SpatialIndex, DriverScorer, SurgePricing, MatchingEngine.
  • Request flow: find drivers in nearby cells with status AVAILABLE and the right vehicle type. Score them and sort, giving a candidate list. For the top candidate, atomically switch AVAILABLE → OFFERED (if that fails, the driver was taken, so try the next one), create an Offer and schedule its timeout. On accept, switch the ride to DRIVER_ASSIGNED and the driver to ON_TRIP. On decline or timeout, put the driver back to AVAILABLE and offer to the next candidate. If the list runs out, widen the radius or report no drivers.
  • Patterns: State for the ride and the driver. Strategy for scoring and for pricing (surge as a decorator on the base fare is also fine). Observer to push status to rider and driver apps.
  • Concurrency: the driver's status field is the lock. Use compare-and-set (AtomicReference<DriverStatus> or a version number), so assignment is exclusive without a global lock. Accept and timeout both try to resolve the same Offer with compare-and-set from PENDING, and whoever loses does nothing. The spatial index uses a lock per cell, or ConcurrentHashMap<cellId, Set<driverId>>.
  • Edge cases: a driver going offline while holding an offer, a rider cancelling during matching (cancel the outstanding offer), stale locations (ignore drivers not heard from in 30 seconds), and shared rides (several requests per ride, with capacity and detour limits).
  • Full version: Ride Sharing.

Problem 5: Order Management System

Design an order management system that handles order creation, payment, fulfillment, and refunds with proper state management.

Requirements

  • Order lifecycle: create, pay, fulfill, ship, deliver, return, refund
  • Multiple items per order from different sellers
  • Order splitting: if items ship from different warehouses, create sub-orders
  • Inventory reservation during checkout
  • Cancellation rules: can cancel before shipping, partial cancel after
  • Refund calculation: item price, shipping, discounts, taxes

Key Classes

interface OrderService {
  createOrder(cart: Cart, userId: string): Promise<Order>;
  processPayment(orderId: string, paymentMethod: PaymentMethod): Promise<PaymentResult>;
  cancelOrder(orderId: string, reason: string): Promise<CancellationResult>;
  requestRefund(orderId: string, items: RefundItem[]): Promise<RefundResult>;
}

// State machine with allowed transitions
type OrderState = 'CREATED' | 'PAYMENT_PENDING' | 'PAID' | 'PROCESSING' |
                  'PARTIALLY_SHIPPED' | 'SHIPPED' | 'DELIVERED' |
                  'RETURN_REQUESTED' | 'RETURNED' | 'REFUNDED' | 'CANCELLED';

// Order splitting
interface SubOrder {
  id: string;
  parentOrderId: string;
  sellerId: string;
  warehouseId: string;
  items: OrderItem[];
  status: OrderState;
  shippingInfo?: ShippingInfo;
}

Design Hints

  • State Machine Pattern — define valid transitions and guards (cannot ship a cancelled order)
  • Strategy Pattern for refund calculation — different rules for full refund, partial, restocking fee
  • Order splitting: group items by warehouse/seller, create sub-orders with independent lifecycles
  • Inventory reservation: reserve on order creation, release on cancellation, deduct on shipment
  • Use the Saga Pattern for the checkout flow: create order -> reserve inventory -> process payment -> confirm
Hints
  • Draw the transition table before writing code: from-state, event, to-state, guard. Most bugs in this problem are illegal transitions that nothing prevented.
  • When an order splits into sub-orders, the parent's state is derived from its children (some shipped means PARTIALLY_SHIPPED). Don't store it separately, or the two will drift apart.
  • Each saga step needs a compensating action: release inventory, refund payment. What if a compensation itself fails?
  • Refunds: discounts and coupons applied to the whole order must be shared across items, so a partial return refunds the right share.
Solution outline
  • Entities: Order (id, user, items, totals, status), OrderItem (product, seller, quantity, unit price, discount share), SubOrder (per warehouse or seller), OrderStateMachine (transition table), Shipment, Refund, RefundCalculator.
  • Checkout saga: create the order (CREATED), reserve inventory (on failure, cancel), take payment (on failure, release inventory and cancel), mark it PAID, split it into sub-orders and hand them to fulfilment. Persist each step's outcome so a crash can resume or compensate.
  • Patterns: State, or a transition table with guards. The table is often clearer when there are many states and few behaviours per state. Strategy for refund rules. Command for saga steps, each with execute() and compensate(). Observer to emit order events to email, analytics and so on.
  • Concurrency: a user cancelling while the warehouse ships is the classic race. Both are transitions on the same order, so serialise them with a version column (optimistic locking) or a lock per order. Whichever transition commits first wins, and the other fails its guard ("can't cancel: already shipped").
  • Edge cases: cancelling one item of a multi-item order, a return after a partial refund, payment succeeding after the reservation expired, and the same item from two sellers.
  • Full versions: Food Delivery (order lifecycle with assignment) and Shopping Cart & Checkout.

Problem 6: Inventory Management System

Design an inventory system that tracks stock levels across multiple warehouses with reservation, allocation, and low-stock alerts.

Requirements

  • Multi-warehouse inventory tracking
  • Stock operations: add, remove, reserve, release, transfer
  • Reservation system: hold stock for N minutes during checkout
  • Automatic allocation: choose warehouse closest to customer
  • Low stock alerts with configurable thresholds
  • Batch import/export of inventory data
  • Audit trail for all stock movements

Key Classes

interface InventoryService {
  getStock(productId: string, warehouseId?: string): StockLevel;
  reserve(productId: string, quantity: number, warehouseId?: string): Reservation;
  releaseReservation(reservationId: string): void;
  commitReservation(reservationId: string): void;
  transfer(productId: string, quantity: number, fromWarehouse: string, toWarehouse: string): Transfer;
}

interface StockLevel {
  productId: string;
  warehouseId: string;
  available: number;    // physical - reserved
  reserved: number;     // held for pending orders
  physical: number;     // actual count in warehouse
  incoming: number;     // in-transit from supplier
}

Design Hints

  • available = physical - reserved — never let available go below zero
  • Reservation expiry: background job releases expired reservations
  • Warehouse selection: Strategy Pattern — closest distance, lowest cost, balanced load
  • Optimistic locking for concurrent stock updates: UPDATE inventory SET stock = stock - 1 WHERE product_id = $1 AND stock >= 1
  • Event-driven alerts: publish stock.low event when available drops below threshold

Correction (2026-11-10): that UPDATE is a conditional atomic update, not optimistic locking

The UPDATE ... WHERE stock >= 1 statement is a guarded atomic update. The database checks the condition and decrements in one statement under a row lock, so there's no read-then-write gap. It's the right tool here. Optimistic locking is different: you read a row together with its version, compute the change in application code, then write ... WHERE id = $1 AND version = $2, and retry if zero rows changed. Use optimistic locking when the new value can't be expressed as one SQL expression. Also, in this page's model the guard should be on available stock, for example UPDATE stock_levels SET reserved = reserved + $qty WHERE product_id = $1 AND warehouse_id = $2 AND physical - reserved >= $qty. Then check that exactly one row was updated.

Hints
  • Write the invariants down: 0 ≤ reserved ≤ physical, available = physical − reserved. Every operation must keep them true. Turn them into assertions.
  • A reservation has a lifecycle (HELD, COMMITTED, RELEASED, EXPIRED), and only HELD can move. Expiry and commit can race.
  • A transfer between warehouses is two updates. What does the system show while the stock is on the truck?
  • The audit trail is an append-only list of movements. Could stock levels be computed from it? (That's event sourcing. Mention it, don't build it.)
Solution outline
  • Entities: Product, Warehouse (location), StockLevel (product × warehouse: physical, reserved, incoming), Reservation (id, product, warehouse, quantity, expiresAt, status), StockMovement (audit: type, quantity, reason, time), AllocationStrategy, AlertRule.
  • Reserve: the strategy ranks warehouses (closest, cheapest, most stock). For each one, try the guarded update: reserved += q if physical − reserved ≥ q. The first success creates a Reservation with an expiry. Commit: HELD → COMMITTED, physical −= q, reserved −= q. Release or expire: HELD → RELEASED or EXPIRED, reserved −= q. Transfer: decrement at the source and add to incoming at the destination, then on receipt move incoming to physical.
  • Patterns: Strategy for warehouse choice. Observer for low-stock alerts. Command for movements if you want undo or replay.
  • Concurrency: use one lock per StockLevel (product × warehouse), never a global one. The reservation status change is a compare-and-set from HELD, so commit and expiry can't both apply. An order that needs stock from two warehouses must lock them in a fixed order (by id) to avoid deadlock.
  • Edge cases: reserving more than any single warehouse holds (split the reservation, or fail if the interviewer wants a single shipment), a negative quantity in an import, an expiry job running late (still safe, thanks to compare-and-set), and an alert that flaps around the threshold (add hysteresis).
  • Related case study: Shopping Cart & Checkout reserves stock at checkout. Movie Booking uses the same hold-with-timeout idea for seats.

Problem 7: Booking Calendar

Design a calendar system for a service business (salon, clinic, consultancy) that handles slot-based bookings, availability, and conflicts.

Requirements

  • Service providers define availability (weekly schedule + exceptions)
  • Clients book time slots for specific services
  • Services have different durations (30 min, 60 min, etc.)
  • Prevent double-booking (concurrent booking safety)
  • Buffer time between appointments
  • Recurring availability with holiday overrides
  • Cancellation and rescheduling with configurable policies

Key Classes

interface BookingService {
  getAvailableSlots(providerId: string, date: Date, serviceId: string): TimeSlot[];
  book(slot: TimeSlot, clientId: string, serviceId: string): Booking;
  cancel(bookingId: string): CancelResult;
  reschedule(bookingId: string, newSlot: TimeSlot): Booking;
}

interface AvailabilityRule {
  providerId: string;
  dayOfWeek: number;       // 0-6
  startTime: string;       // "09:00"
  endTime: string;         // "17:00"
  bufferMinutes: number;   // 15 min between appointments
}

interface TimeSlot {
  start: Date;
  end: Date;
  providerId: string;
  available: boolean;
}

Design Hints

  • Slot generation: generate all possible slots from availability rules, subtract booked slots
  • Conflict detection: new_start < existing_end AND new_end > existing_start means overlap
  • Pessimistic locking: SELECT ... FOR UPDATE when creating a booking to prevent double-booking
  • Buffer time: extend each booking by buffer minutes when checking for conflicts
  • Recurring rules: generate slots from weekly schedule, then apply exception overrides (holidays, time-off)

Correction (2026-11-10): `SELECT ... FOR UPDATE` can't lock a booking that doesn't exist yet

Locking the overlapping booking rows prevents nothing when there are no overlapping rows yet. Two transactions both find zero conflicts, both lock nothing, and both insert. This is a phantom, and plain row locks don't prevent it. Working options:

  • Lock a row that always exists, such as the provider's row: SELECT ... FROM providers WHERE id = $1 FOR UPDATE. Then check for conflicts and insert. This serialises bookings per provider.
  • Use a database constraint. In PostgreSQL that's an exclusion constraint: EXCLUDE USING gist (provider_id WITH =, tstzrange(start_at, end_at) WITH &&), which needs the btree_gist extension for the = part.
  • Run at SERIALIZABLE isolation and retry on serialization failures.

In an in-memory LLD answer, the equivalent of the first option is a lock per provider held around "check conflicts, then insert".

Hints
  • Treat every interval as half-open, [start, end). Then a 10:00–11:00 booking and an 11:00–12:00 booking don't overlap, and the overlap test is the one-liner above.
  • Store and compare instants in UTC, but expand weekly rules in the provider's time zone. "Every Monday 09:00" crosses a daylight saving change otherwise.
  • Buffer time belongs to the existing booking: widen it to [start − buffer, end + buffer) when checking conflicts, not the new slot twice.
  • Rescheduling is "book new, then cancel old" as one atomic step. If the new slot fails, the old booking must survive.
Solution outline
  • Entities: Provider (time zone, weekly AvailabilityRules, Exceptions such as holidays or time off), Service (duration, buffer), Booking (provider, client, service, [start, end), status), TimeSlot (value object), CancellationPolicy.
  • Available slots for a day: expand the weekly rules to intervals for that date, subtract exceptions, subtract existing bookings widened by the buffer, then step through the free intervals in increments (for example every 15 minutes), keeping starts where start + duration fits.
  • Book: take the provider lock, re-check overlap against confirmed bookings (never trust the slot list the client saw), insert, release. Keep bookings per provider in a sorted structure (TreeMap<start, Booking>), so the conflict check only looks at the neighbours: floorEntry(newStart) and the entries just after it.
  • Patterns: Strategy for cancellation policies (free until 24 hours before, 50% fee after) and for slot granularity. Observer for reminders and calendar sync.
  • Concurrency: a lock per provider, as in the correction above. Booking two providers at once (a doctor and a room) means taking both locks in a fixed order.
  • Edge cases: a booking across midnight, a provider changing availability after bookings exist (keep the existing bookings and flag them), a client double-booking themselves with two providers, and DST days with 23 or 25 hours.
  • Full version: Meeting Room Booking covers the same interval-conflict core.

Problem 8: Search Autocomplete

Design a search autocomplete system that suggests completions as the user types, with ranking, personalization, and typo tolerance.

Requirements

  • Return top 5-10 suggestions as user types each character
  • Ranking: popularity, recency, personalization
  • Typo tolerance (fuzzy matching)
  • Response time: < 50ms
  • Support for phrase suggestions (multi-word)
  • Filter inappropriate suggestions
  • Learning from user selections (boost selected suggestions)

Key Classes

classDiagram
    class AutocompleteService {
        +suggest(prefix: string, userId?: string, limit?: number): Suggestion[]
        +recordSelection(query: string, userId: string)
        +indexTerm(term: string, weight: number)
    }

    class TrieNode {
        -children: Map~char, TrieNode~
        -topSuggestions: Suggestion[]
        -isEndOfWord: boolean
    }

    class FuzzyMatcher {
        +findMatches(input: string, maxEditDistance: number): string[]
    }

    class RankingEngine {
        +rank(suggestions: Suggestion[], userId?: string): Suggestion[]
    }

    AutocompleteService --> TrieNode
    AutocompleteService --> FuzzyMatcher
    AutocompleteService --> RankingEngine

Design Hints

  • Trie data structure for prefix matching — store pre-computed top-K suggestions at each node
  • When a new search becomes popular, update top-K at affected trie nodes
  • Fuzzy matching: Levenshtein distance for edit distance 1-2, or BK-tree for efficient fuzzy search
  • Ranking score: score = popularity * recency_decay * (1 + personalization_boost)
  • Content filtering: maintain a blocklist trie, reject suggestions that match
  • Optimization: pre-compute suggestions at each trie node, so lookup is O(prefix_length), not O(prefix_length + sorting)
Hints
  • Caching top-K at every node makes reads cheap and writes expensive: one popular query changes the top-K of every prefix of it. How often do weights really need to change?
  • Personalisation doesn't fit inside a shared trie. Fetch global candidates (say the top 50), then re-rank them with the user's history.
  • Fuzzy matching on every keystroke is expensive. Try exact prefix first, and only fall back to fuzzy when exact returns too few results.
  • Normalise input (case, extra spaces, accents) the same way at index time and query time.
Solution outline
  • Entities: TrieNode (children, top-K list of suggestion ids), Suggestion (text, weight, last-used time), AutocompleteService, Ranker, FuzzyMatcher, Blocklist.
  • Query: normalise, walk the trie along the prefix, take the cached top-K, drop blocked items, re-rank with personal signals and return the limit. If fewer than the limit come back, run the fuzzy matcher (edit distance 1 for short prefixes) and merge.
  • Updates: record selections into a counter map. A periodic job rebuilds the trie, or updates the top-K along changed paths, from those counts with a recency decay.
  • Patterns: Strategy for ranking. Decorator for filters (blocklist, then personalisation) wrapped around a base suggester. Composite is visible in the trie itself, but don't oversell it.
  • Concurrency: reads vastly outnumber writes. Build a new trie in the background and publish it by swapping one reference (copy-on-write at the whole-index level). Readers never lock and always see a consistent trie. Selection counters are LongAdders or atomics.
  • Edge cases: an empty prefix (return trending queries or nothing), a prefix with no matches, very long input (cap the length), and offensive completions of innocent prefixes (filter on output, not just input).

Problem 9: File Storage Service

Design a file storage service (like a simplified S3) with upload, download, metadata, versioning, and access control.

Requirements

  • Upload files of any size (up to 5GB)
  • Multipart upload for large files
  • Download with range requests (resume interrupted downloads)
  • File metadata: name, size, content type, tags, custom metadata
  • Versioning: keep previous versions, restore to any version
  • Access control: public, private, shared with specific users
  • Deduplication: don't store duplicate files twice

Key Classes

interface FileStorageService {
  upload(file: FileUploadRequest): Promise<FileObject>;
  initiateMultipartUpload(metadata: FileMetadata): Promise<UploadSession>;
  uploadPart(sessionId: string, partNumber: number, data: Buffer): Promise<PartResult>;
  completeMultipartUpload(sessionId: string, parts: PartResult[]): Promise<FileObject>;
  download(fileId: string, range?: ByteRange): Promise<ReadableStream>;
  getMetadata(fileId: string): Promise<FileMetadata>;
  listVersions(fileId: string): Promise<FileVersion[]>;
  restoreVersion(fileId: string, versionId: string): Promise<FileObject>;
  share(fileId: string, userId: string, permission: Permission): Promise<ShareLink>;
}

interface FileObject {
  id: string;
  name: string;
  size: number;
  contentType: string;
  checksum: string;     // SHA-256 for dedup
  versionId: string;
  createdAt: Date;
  owner: string;
  storageLocation: string; // Internal path
}

Design Hints

  • Content-addressable storage for dedup: storageKey = SHA-256(fileContent), if key exists, just add a reference
  • Multipart upload: split file into chunks (5-100MB each), upload independently, reassemble on complete
  • Versioning: each upload creates a new version; previous versions remain until explicitly deleted
  • Access control: RBAC at the file/folder level — owner, editor, viewer roles
  • Range requests: respond with HTTP 206 Partial Content, read specific byte range from storage
Hints
  • Separate the blob (bytes, addressed by hash) from the file object (name, owner, versions, permissions, pointing at a blob). Deduplication, versioning and renames all get simpler.
  • Deleting a file must not delete a blob that another file still points at. Reference counting, or a mark-and-sweep garbage collector?
  • A multipart upload is a session with a state (OPEN, COMPLETED, ABORTED) and an expiry. Parts can arrive out of order and be retried.
  • For access checks, which comes first: the file's own grants or the folder's? Pick a rule (most specific wins, or deny wins) and stick to it.
Solution outline
  • Entities: Blob (hash, size, storage location, reference count), FileObject (id, name, owner, folder, current version), FileVersion (version id, blob hash, created at, author), Folder, UploadSession (parts map: part number → part hash), Grant (principal, permission, resource), StorageBackend (interface: local disk, S3, in-memory for tests).
  • Upload: stream the bytes while computing SHA-256. If a blob with that hash exists, discard the copy and increment its reference count. Otherwise store it. Then append a FileVersion and point currentVersion at it. Restore: append a new version that points at the old blob. Don't rewrite history. Multipart complete: check every part is present and its hash matches, concatenate in part order (or keep a manifest), then continue as a normal upload.
  • Patterns: Composite for folders and files. Strategy or a port for the storage backend. Proxy for an access-checking wrapper around the service. Memento-like thinking for versions.
  • Concurrency: two uploads to the same file at once both create versions, and the last commit becomes current. Make the "append version, set current" step atomic per file (a lock per file, or compare-and-set on a version counter). Reference counts change atomically, and garbage collection must not delete a blob that an in-progress upload just matched by hash. Add a grace period before deleting.
  • Edge cases: hash collisions (assume SHA-256 doesn't collide, but say so), a zero-byte file, range requests past the end of the file (return 416), abandoned multipart sessions (an expiry job cleans them up), and sharing a file inside a private folder.
  • Related case study: File System for the folder tree, paths and permissions.

Problem 10: Workflow Engine

Design a workflow engine that executes multi-step business processes with branching, parallel execution, human tasks, and error handling.

Requirements

  • Define workflows as DAGs with steps, conditions, and parallel branches
  • Step types: automated (code), human task (approval), timer (wait), sub-workflow
  • Conditional branching: if/else, switch based on step output
  • Parallel execution with join (wait for all) or race (wait for first)
  • Timeout and retry per step
  • Workflow versioning: running workflows continue with old version
  • Pause, resume, and cancel running workflows

Key Classes

classDiagram
    class WorkflowEngine {
        +startWorkflow(definitionId, input): WorkflowInstance
        +getStatus(instanceId): WorkflowStatus
        +completeHumanTask(taskId, output)
        +cancel(instanceId)
        +pause(instanceId)
        +resume(instanceId)
    }

    class WorkflowDefinition {
        -id: string
        -version: number
        -steps: Step[]
        -transitions: Transition[]
    }

    class Step {
        <<interface>>
        +execute(context): StepResult
    }

    class AutomatedStep {
        -handler: Function
        +execute(context): StepResult
    }

    class HumanTaskStep {
        -assignee: string
        -form: FormDefinition
        +execute(context): StepResult
    }

    class ParallelGateway {
        -branches: Step[][]
        -joinType: ALL | RACE
        +execute(context): StepResult
    }

    WorkflowEngine --> WorkflowDefinition
    WorkflowDefinition --> Step
    AutomatedStep ..|> Step
    HumanTaskStep ..|> Step
    ParallelGateway ..|> Step

Design Hints

  • State Machine for workflow instance status: CREATED -> RUNNING -> PAUSED -> COMPLETED | FAILED | CANCELLED (Correction (2026-11-10): read this as a set of states, not one chain. PAUSED goes back to RUNNING when resumed. A workflow finishes from RUNNING, as COMPLETED or FAILED, and CANCELLED is reachable from RUNNING or PAUSED. Transitions: CREATED → RUNNING, RUNNING ⇄ PAUSED, RUNNING → COMPLETED or FAILED, and RUNNING or PAUSED → CANCELLED.)
  • Command Pattern for steps — each step encapsulates an operation that can be executed, retried, or compensated
  • Workflow execution: iterate through steps following transitions, evaluate conditions at gateways
  • Persistence: save workflow state after each step completion — enables resume after crash
  • Human tasks: create a "task inbox" for the assignee, workflow pauses until task is completed
  • Parallel gateway: fork creates N concurrent step chains, join waits for all (or first) to complete
Hints
  • Split the definition (immutable, versioned: steps and transitions) from the instance (mutable: current position, variables, step history). Running instances keep a reference to the exact definition version they started with.
  • A human task or a timer step can take days. The engine must not hold a thread for it. The instance waits as data, and an event (task completed, timer fired) wakes it.
  • With a RACE join, what happens to the losing branches? Cancel them, and possibly compensate.
  • Persist after every step. On restart, which steps are safe to re-run? Steps should be idempotent, or record "started" and "finished" separately.
Solution outline
  • Entities: WorkflowDefinition (id, version, steps, transitions with conditions), Step (AutomatedStep, HumanTaskStep, TimerStep, SubWorkflowStep, ParallelGateway, ExclusiveGateway), WorkflowInstance (definition ref, status, a set of active "tokens", context variables, history), StepExecution (attempts, status, output), TaskInbox, TimerService, InstanceStore.
  • Engine loop: an event (start, step finished, task completed, timer fired) loads the instance, advances its tokens through the transitions whose conditions hold, and schedules the next steps: automated ones on a worker pool, human ones into the inbox, timers in the timer service. Then it saves the instance. Parallel gateways split one token into N. The join counts arrivals (ALL) or takes the first and cancels the rest (RACE).
  • Patterns: State for the instance. Command for steps (execute, compensate). Composite for sub-workflows and gateways containing steps. Strategy for retry policies. Interpreter if conditions are a small expression language.
  • Concurrency: handle events for one instance one at a time (a lock or a queue per instance), so two branches finishing together don't both "advance" from the same old snapshot. Save with optimistic concurrency (a version number) to catch a second engine node doing the same. Different instances run fully in parallel.
  • Edge cases: pausing while an automated step is mid-flight (let it finish, but don't schedule more), cancelling with compensation in reverse order, a definition change while instances are running (old ones keep the old version), and a human task reassigned or expired.
  • Related case study: Task Scheduler covers delayed jobs, priorities and the worker pool underneath.

Problem 11: Library Management

Design the lending side of a library: members borrow and return physical copies of books, with limits, due dates, fines and holds.

Requirements

  • A book (title, ISBN, authors) has many physical copies, each tracked separately
  • Members borrow up to a limit (default 3) for a loan period (default 14 days)
  • Late returns incur a daily fine with a cap
  • Members can place a hold on a book when no copy is available; the next returned copy goes to the first hold
  • Search by title, author or ISBN
  • Several librarian desks work at the same time
Hints
  • Book and BookCopy are different classes. Mixing them up is the most common mistake in this problem.
  • Inject a clock. Fines are about dates, and tests can't wait 14 days.
  • Two desks lending the last copy at once is the concurrency question. Holds make it sharper: a returned copy must go to the hold queue, not to whoever happens to be at a desk.
Solution outline
  • Entities: Book (ISBN, title, authors), BookCopy (id, book, status: AVAILABLE, ON_LOAN, ON_HOLD_SHELF or LOST), Member (id, tier, active loans), Loan (copy, member, borrowedAt, dueAt, returnedAt), Hold (book, member, placedAt, status), FinePolicy, Catalog (search indexes).
  • Borrow: check the member's limit and any unpaid fines, then claim an available copy (or the copy on the hold shelf for this member), create a Loan and mark the copy ON_LOAN. Return: close the loan, compute the fine with the policy, then if a hold queue exists, mark the copy ON_HOLD_SHELF for the first member. Otherwise mark it AVAILABLE.
  • Patterns: Strategy for fines and member tiers. Observer to notify members when a held book arrives. A repository interface per entity keeps storage in memory.
  • Concurrency: claim a copy with a compare-and-set on its status (AVAILABLE → ON_LOAN), or a lock per book covering its copies and hold queue together. The member's loan count is checked and incremented under the member's lock. When you need both locks, take them in a fixed order (book, then member) to avoid deadlock.
  • Edge cases: returning on the due date (not late), returning a copy that isn't on loan, a member with an expired membership, and a hold whose member never collects (expire it after N days and pass the copy on).
  • Full version: Library Management, also used as the worked example in the LLD Interview Framework.

Problem 12: ATM

Design the software for an ATM that authenticates a card, lets the user check balance, withdraw and deposit, and dispenses notes.

Requirements

  • Insert card → enter PIN (3 attempts, then the card is retained) → choose transaction → eject card
  • Withdrawals check the account balance, a daily limit and the cash available in the machine
  • Dispense using the available note denominations (e.g. 2000/500/200/100)
  • The bank account is shared with other channels (online banking, other ATMs)
  • Cancel is possible at any step and must eject the card
Hints
  • The same button means different things in different steps. That's the State pattern again, as in the vending machine, but now with a remote bank behind it.
  • Dispensing notes with fixed denominations is a chain: each cassette takes what it can and passes the rest on.
  • What if the bank approves the withdrawal but the dispenser jams? The debit must be reversed.
Solution outline
  • Entities: ATM (context: state, card reader, cash dispenser, bank client), ATMState (Idle, CardInserted, Authenticated, Transacting, OutOfService), Card, Account (held at the bank), Transaction (Withdrawal, Deposit, BalanceInquiry), CashDispenser, NoteCassette (denomination, count), BankService (interface).
  • Withdraw: check the machine can make the amount from its cassettes (a dry run along the chain), then ask the bank to debit atomically (balance and daily limit checked on the bank side), then dispense. If dispensing fails, send a reversal to the bank and log the incident.
  • Patterns: State for the session flow. Chain of Responsibility for note cassettes. Command for transactions, so they can be logged and reversed. Adapter around the bank network protocol.
  • Concurrency: the ATM itself has one user. The real shared state is the account at the bank: the debit must be an atomic conditional update (balance >= amount), or a lock per account. Never read the balance in the ATM and subtract locally.
  • Edge cases: the machine can't make the exact amount (offer the nearest amount it can), wrong PIN three times, a network failure after the debit request (ambiguous, so reconcile instead of retrying blindly), and the user walking away without taking the card or cash.
  • Full version: ATM.

Problem 13: Movie Booking

Design a movie ticket booking system: cinemas, screens, shows, seat maps, and booking with payment.

Requirements

  • Browse movies and shows by city, cinema and time
  • View the seat map for a show with seat types and prices
  • Select several seats; they are held for the user for a few minutes while they pay
  • Confirm on payment success; release on failure, cancel or timeout
  • No seat may ever be sold twice
Hints
  • A seat in a show is the unit of inventory, not the seat in the screen. ShowSeat is the class you lock.
  • Holding 4 seats is all-or-nothing. If seat 3 is taken, seats 1 and 2 must be released.
  • Lock seats in a fixed order (by seat id). Two users grabbing overlapping seat sets in different orders would otherwise deadlock.
Solution outline
  • Entities: Movie, Cinema, Screen (seat layout), Show (movie, screen, start time), ShowSeat (show, seat, type, price, status: AVAILABLE, HELD or BOOKED, holdExpiresAt, heldBy), Booking (user, show, seats, amount, status), Payment.
  • Hold: sort the requested seats, then for each one compare-and-set AVAILABLE → HELD (or treat HELD with a past expiry as available). On any failure, roll back the seats already held and report which seat failed. Create a PENDING booking with the hold expiry.
  • Confirm: on payment success, check the hold is still yours and not expired, move the seats HELD → BOOKED and the booking to CONFIRMED. If the hold expired first, refund.
  • Patterns: Strategy for pricing (seat type, time of day, demand). State for the booking. Observer for seat-map updates to other viewers. A Facade for the booking service.
  • Concurrency: compare-and-set per ShowSeat, or a lock per show for simplicity. Expiry can be lazy: a held seat whose expiry has passed counts as available on the next hold attempt. Then no timer is needed, and a sweeper job only tidies up.
  • Edge cases: payment succeeding a second after the hold expired, a user holding seats in two tabs, a show cancelled with bookings, and leaving single isolated seats (a rule some cinemas enforce).
  • Full version: Movie Booking.

Problem 14: Hotel Management

Design a hotel reservation system: room types, availability over date ranges, booking, check-in, check-out and billing.

Requirements

  • Rooms have a number, type (single, double, suite) and base rate
  • Search availability for a room type over a check-in/check-out date range
  • Book a room type for a date range; assign a specific room at check-in
  • Booking lifecycle: confirmed → checked in → checked out, or cancelled / no-show
  • Pricing varies by season, weekday/weekend and length of stay
  • Two guests booking the last room for overlapping dates must not both succeed
Hints
  • A stay is a half-open date range [checkIn, checkOut). The check-out day is free for the next guest.
  • If guests book a type and get a room at check-in, availability is a count per type per night, not a set of free rooms. Count confirmed bookings for each night in the range.
  • The race: two requests both see "1 left" and both book. Where does "check count, then insert" become atomic?
Solution outline
  • Entities: Room (number, type, status), RoomType, Guest, Reservation (guest, type, [checkIn, checkOut), status, assigned room), RatePlan / PricingStrategy, Invoice, Charge.
  • Availability: for each night in the range, the rooms of that type minus the reservations of that type covering that night. The type is available only if every night has at least one free. Keep a per-type, per-night counter map so this is O(nights) instead of a scan over every reservation.
  • Book: under the room type's lock, check every night in the range, then increment all the nightly counters and create the reservation. Cancel: decrement them. Check-in: choose a specific room of the type that is clean and not assigned to an overlapping stay, using an allocation strategy.
  • Patterns: State for the reservation lifecycle. Strategy for pricing (seasonal, weekend, long-stay discount, chained as decorators) and for room allocation. Observer for housekeeping after check-out.
  • Concurrency: a lock per room type (or per type and night, locked in date order) around check-and-increment. In a database: a row per type and night with a guarded update, UPDATE inventory SET booked = booked + 1 WHERE type = $1 AND night = $2 AND booked < total, for every night in one transaction.
  • Edge cases: check-out before check-in, a zero-night stay, extending a stay (re-check only the new nights), and a room going into maintenance while it has future assignments.
  • Full version: Hotel Management.

Problem 15: Splitwise

Design an expense-sharing app: groups of friends add shared expenses, and the app tracks who owes whom and suggests settlements.

Requirements

  • Users, groups, and expenses paid by one (or more) users and split among participants
  • Split types: equal, exact amounts, percentages, shares
  • Show each user's balance, and pairwise "A owes B" amounts
  • Simplify debts: suggest the fewest payments that settle a group
  • Record settlements; edit or delete an expense
Hints
  • Money as integer minor units. Splitting 100 three ways gives 33, 33, 34. Decide who gets the extra unit, deterministically.
  • Each split type validates differently: exact amounts must add up to the total, percentages to 100. That's one strategy per type.
  • Debt simplification works on net balances only. Who paid for what no longer matters at that point.
Solution outline
  • Entities: User, Group, Expense (id, payer(s), total, split type, splits, created by), Split (user, amount), SplitStrategy (Equal, Exact, Percent, Share), BalanceSheet (net balance per user per group), Settlement.
  • Add expense: the strategy turns the input into exact per-user amounts (rounding remainders assigned deterministically, for example to the first users by id) and validates that they add up to the total. Then update the balance sheet: credit the payer, debit each participant. Edit or delete: reverse the old expense's effect, then apply the new one.
  • Simplify: compute net balances, put debtors and creditors in two heaps, repeatedly settle the largest debtor against the largest creditor for the smaller of the two amounts, and push the remainder back. This gives at most n − 1 payments. Finding the true minimum is NP-hard. Mention it, then use the greedy method.
  • Patterns: Strategy for split types. Observer for notifications. Command for expenses if undo is wanted.
  • Concurrency: two people adding expenses to the same group at once both update the balance sheet. Use a lock per group, or make balance updates atomic adds (LongAdder or merge on a concurrent map). Balances are sums, so the order doesn't matter.
  • Edge cases: the payer is also a participant, a participant leaving a group with a non-zero balance, multi-currency groups, and percentages like 33.33 + 33.33 + 33.33.
  • Full version: Splitwise.

Progression Guide

ProblemKey PatternReal-World System
Notification SystemStrategy + PipelineSendGrid, Twilio
Payment GatewayAdapter + State MachineStripe, Adyen
Social Media FeedFanout + CachingTwitter, Instagram
Ride MatchingSpatial Index + ScoringUber, Lyft
Order ManagementState Machine + SagaShopify, Amazon
Inventory SystemLocking + EventsWarehouse systems
Booking CalendarConflict DetectionCalendly, Doctolib
Search AutocompleteTrie + RankingGoogle Search, Algolia
File StorageContent-Addressable StorageS3, GCS
Workflow EngineDAG + State MachineTemporal, Airflow
Library ManagementStrategy + Locking per copyLibrary back-office systems
ATMState + Chain of ResponsibilityBank ATM software
Movie BookingSeat holds + Compare-and-setBookMyShow, Fandango
Hotel ManagementDate-range inventory + StateHotel property-management systems
SplitwiseStrategy + Greedy settlementSplitwise, Tricount