Low Level Design (LLD) & Machine Coding

Round format: 1-2 hr coding session. Design a class structure + implement it in Python. Tested at: CRED, BrowserStack, Razorpay, Flipkart, Meesho.

---

Interview Approach (how to tackle LLD round)

1. Clarify (5 min)
   - Who are the users? What are the core operations?
   - Scale? Concurrency? Persistence needed?

2. Core entities (5 min)
   - Identify classes, their state, relationships

3. Interface first (5 min)
   - Define public methods before implementing
   - Agree with interviewer

4. Implement (30-40 min)
   - Start with data structures
   - Then business logic
   - Handle edge cases last

5. Extensibility (5 min)
   - "To add X, I'd add a Strategy/Observer/..."

---

SOLID Principles (verbal)

---

Design Patterns (know these 5)

Strategy — swap algorithms at runtime

from abc import ABC, abstractmethod

class SortStrategy(ABC):
    @abstractmethod
    def sort(self, data: list) -> list: ...

class QuickSort(SortStrategy):
    def sort(self, data): ...

class MergeSort(SortStrategy):
    def sort(self, data): ...

class Sorter:
    def __init__(self, strategy: SortStrategy):
        self._strategy = strategy
    def sort(self, data):
        return self._strategy.sort(data)

Observer — pub/sub within a process

class EventBus:
    def __init__(self):
        self._listeners: dict[str, list] = {}

    def subscribe(self, event: str, fn):
        self._listeners.setdefault(event, []).append(fn)

    def publish(self, event: str, data=None):
        for fn in self._listeners.get(event, []):
            fn(data)

Factory — create objects without specifying concrete class

class NotificationFactory:
    @staticmethod
    def create(channel: str) -> Notification:
        if channel == "email": return EmailNotification()
        if channel == "sms":   return SMSNotification()
        raise ValueError(f"Unknown channel: {channel}")

Decorator — wrap behaviour without subclassing

class LoggingProcessor(PaymentProcessor):
    def __init__(self, processor: PaymentProcessor):
        self._processor = processor

    def process(self, amount):
        print(f"Processing {amount}")
        result = self._processor.process(amount)
        print(f"Result: {result}")
        return result

Singleton — one instance globally

class Config:
    _instance = None

    def __new__(cls):
        if cls._instance is None:
            cls._instance = super().__new__(cls)
        return cls._instance

---

Problem 1: LRU Cache

O(1) get + O(1) put. Interview favourite.

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = OrderedDict()  # insertion-order dict

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)  # mark as recently used
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)  # evict LRU (first item)

Follow-up: "How to make thread-safe?" → Wrap get/put with threading.Lock(). Or use threading.RLock if methods call each other.

---

Problem 2: Rate Limiter (Token Bucket)

import threading
import time

class RateLimiter:
    def __init__(self, capacity: int, refill_rate: float):
        self.capacity = capacity
        self.tokens = capacity
        self.refill_rate = refill_rate  # tokens per second
        self.last_refill = time.time()
        self.lock = threading.Lock()

    def _refill(self):
        now = time.time()
        elapsed = now - self.last_refill
        new_tokens = elapsed * self.refill_rate
        self.tokens = min(self.capacity, self.tokens + new_tokens)
        self.last_refill = now

    def allow(self) -> bool:
        with self.lock:
            self._refill()
            if self.tokens >= 1:
                self.tokens -= 1
                return True
            return False

---

Problem 3: Parking Lot

from abc import ABC, abstractmethod
from enum import Enum

class VehicleType(Enum):
    BIKE = "bike"
    CAR = "car"
    TRUCK = "truck"

class Vehicle(ABC):
    def __init__(self, plate: str, type: VehicleType):
        self.plate = plate
        self.type = type

class Car(Vehicle):
    def __init__(self, plate): super().__init__(plate, VehicleType.CAR)

class ParkingSpot:
    def __init__(self, id: str, type: VehicleType):
        self.id = id
        self.type = type
        self.vehicle: Vehicle | None = None

    @property
    def is_free(self): return self.vehicle is None

    def park(self, v: Vehicle): self.vehicle = v
    def vacate(self): self.vehicle = None

class ParkingLot:
    def __init__(self):
        self.spots: dict[str, ParkingSpot] = {}

    def add_spot(self, spot: ParkingSpot):
        self.spots[spot.id] = spot

    def park(self, vehicle: Vehicle) -> ParkingSpot | None:
        for spot in self.spots.values():
            if spot.is_free and spot.type == vehicle.type:
                spot.park(vehicle)
                return spot
        return None  # full

    def leave(self, spot_id: str):
        if spot_id in self.spots:
            self.spots[spot_id].vacate()

---

Problem 4: Event Emitter

from collections import defaultdict
from typing import Callable

class EventEmitter:
    def __init__(self):
        self._events: dict[str, list[Callable]] = defaultdict(list)

    def on(self, event: str, fn: Callable) -> None:
        self._events[event].append(fn)

    def off(self, event: str, fn: Callable) -> None:
        self._events[event] = [f for f in self._events[event] if f != fn]

    def emit(self, event: str, *args, **kwargs) -> None:
        for fn in self._events[event]:
            fn(*args, **kwargs)

    def once(self, event: str, fn: Callable) -> None:
        def wrapper(*args, **kwargs):
            fn(*args, **kwargs)
            self.off(event, wrapper)
        self.on(event, wrapper)

---

Problem 5: Splitwise (Debt Simplification)

from collections import defaultdict

class Splitwise:
    def __init__(self):
        self.balances: dict[str, float] = defaultdict(float)

    def add_expense(self, paid_by: str, amount: float, participants: list[str]):
        share = amount / len(participants)
        self.balances[paid_by] += amount
        for p in participants:
            self.balances[p] -= share

    def settle(self) -> list[tuple]:
        creditors = [(p, b) for p, b in self.balances.items() if b > 0]
        debtors   = [(p, -b) for p, b in self.balances.items() if b < 0]
        creditors.sort(key=lambda x: -x[1])
        debtors.sort(key=lambda x: -x[1])

        transactions = []
        i, j = 0, 0
        while i < len(creditors) and j < len(debtors):
            cp, ca = creditors[i]
            dp, da = debtors[j]
            amount = min(ca, da)
            transactions.append((dp, cp, round(amount, 2)))
            creditors[i] = (cp, ca - amount)
            debtors[j]   = (dp, da - amount)
            if creditors[i][1] == 0: i += 1
            if debtors[j][1] == 0:   j += 1
        return transactions

---

Python OOP Patterns to Know

# Abstract base class
from abc import ABC, abstractmethod
class Shape(ABC):
    @abstractmethod
    def area(self) -> float: ...

# Dataclass for value objects
from dataclasses import dataclass
@dataclass
class Point:
    x: float
    y: float

# Property for encapsulation
class Temperature:
    def __init__(self, celsius):
        self._celsius = celsius

    @property
    def fahrenheit(self):
        return self._celsius * 9/5 + 32

    @fahrenheit.setter
    def fahrenheit(self, value):
        self._celsius = (value - 32) * 5/9

---

Related

• [[Python/Language Core/Object Oriented Programming]] — Python OOP depth
• [[Python/Libraries/Asyncio]] — async patterns for concurrent LLD
• [[DSA/DSA Techniques for Interviews/Heap & Priority Queue]] — used in many LLD problems