DEV Community: Dev Cookies

Low-Level Design (LLD) of a Heap (Priority Queue) in Java

Dev Cookies — Thu, 09 Jul 2026 17:06:40 +0000

Target Audience: Software Engineers, Backend Engineers, Java Developers, SDE Interview Preparation

Introduction
What is a Heap?
Heap Properties
Types of Heap
Internal Representation
Parent/Child Index Formula
Designing Our Heap
Core Operations
Insert (Heapify Up)
Remove (Heapify Down)
Peek
Build Heap
Heap Sort
Complete Java Implementation
Time Complexity
Design Improvements
Java PriorityQueue Internals
Interview Questions
Summary

1. Introduction

A Heap is a specialized tree-based data structure optimized for retrieving the highest or lowest priority element efficiently.

Unlike a Binary Search Tree, a Heap does not maintain complete ordering. It guarantees that only the root node has the highest (Max Heap) or lowest (Min Heap) priority.

Common use cases:

Priority Queue
Task Scheduling
CPU Scheduling
Dijkstra's Algorithm
Prim's MST
Top K Problems
Median Finder
Merge K Sorted Lists
Event Processing

2. What is a Heap?

A Heap is a Complete Binary Tree satisfying the Heap Property.

Example (Min Heap):

Every parent is less than or equal to its children.

3. Heap Properties

Complete Binary Tree

Every level is completely filled except possibly the last.

Last level fills from left to right.

Example

Invalid

      10
     /  \
   null 30

Heap Property

For Min Heap

Parent <= Children

For Max Heap

Parent >= Children

4. Types of Heap

Min Heap

Root contains minimum.

Max Heap

Root contains maximum.

5. Internal Representation

Unlike trees, Heap is stored in an Array.

Index

0 1 2 3 4 5

Array

2 5 8 9 10 15

Tree

No explicit Node objects are required.

6. Parent/Child Formula

Suppose current index = i

Parent

(i - 1) / 2

Left Child

2 * i + 1

Right Child

2 * i + 2

Example

Array

Index

0 1 2 3 4 5

Value

2 5 8 9 10 15

Node at index 1

Value = 5

Left = 3

Right = 4

7. Designing Our Heap

We need

Dynamic Array
Size
insert()
remove()
peek()
heapifyUp()
heapifyDown()
buildHeap()

Step 1 — Heap Skeleton

public class MinHeap {

    private int[] heap;
    private int size;
    private static final int DEFAULT_CAPACITY = 10;

    public MinHeap() {
        heap = new int[DEFAULT_CAPACITY];
    }
}

Step 2 — Resize Array

private void ensureCapacity() {
    if (size == heap.length) {
        heap = java.util.Arrays.copyOf(heap, heap.length * 2);
    }
}

Step 3 — Insert

Algorithm

Insert at end

↓

Heapify Up

↓

Done

Implementation

public void insert(int value) {

    ensureCapacity();

    heap[size] = value;

    heapifyUp(size);

    size++;
}

Heapify Up

Example

Insert 3

Before

      5
     / \
    8   9

Insert

      5
     / \
    8   9
   /
  3

Swap

Swap Again

Implementation

private void heapifyUp(int index) {

    while (index > 0) {

        int parent = (index - 1) / 2;

        if (heap[parent] <= heap[index])
            break;

        swap(parent, index);

        index = parent;
    }
}

Step 4 — Peek

public int peek() {

    if (size == 0)
        throw new RuntimeException("Heap Empty");

    return heap[0];
}

Step 5 — Remove Root

Algorithm

Replace root

↓

Last element

↓

Delete last

↓

Heapify Down

Implementation

public int remove() {

    if (size == 0)
        throw new RuntimeException("Heap Empty");

    int value = heap[0];

    heap[0] = heap[size - 1];

    size--;

    heapifyDown(0);

    return value;
}

Heapify Down

Before

Swap

Swap Again

Implementation

private void heapifyDown(int index) {

    while (true) {

        int left = 2 * index + 1;
        int right = 2 * index + 2;

        int smallest = index;

        if (left < size && heap[left] < heap[smallest])
            smallest = left;

        if (right < size && heap[right] < heap[smallest])
            smallest = right;

        if (smallest == index)
            break;

        swap(index, smallest);

        index = smallest;
    }
}

Swap

private void swap(int i, int j) {

    int temp = heap[i];
    heap[i] = heap[j];
    heap[j] = temp;
}

Build Heap

Instead of inserting one by one

9 4 8 1 5 2

We perform heapify from the last non-leaf node.

Algorithm

Start from

(n / 2) - 1

↓

Heapify Down

↓

Repeat until root

Implementation

public void buildHeap(int[] arr) {

    heap = java.util.Arrays.copyOf(arr, arr.length);

    size = arr.length;

    for (int i = (size / 2) - 1; i >= 0; i--) {
        heapifyDown(i);
    }
}

Time Complexity

O(n)

Complete Java Implementation

import java.util.Arrays;

public class MinHeap {

    private int[] heap;
    private int size;
    private static final int DEFAULT_CAPACITY = 10;

    public MinHeap() {
        heap = new int[DEFAULT_CAPACITY];
    }

    public void insert(int value) {
        ensureCapacity();
        heap[size] = value;
        heapifyUp(size);
        size++;
    }

    public int peek() {
        if (size == 0)
            throw new IllegalStateException("Heap is empty");
        return heap[0];
    }

    public int remove() {
        if (size == 0)
            throw new IllegalStateException("Heap is empty");

        int root = heap[0];
        heap[0] = heap[size - 1];
        size--;

        if (size > 0) {
            heapifyDown(0);
        }

        return root;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void buildHeap(int[] arr) {
        heap = Arrays.copyOf(arr, Math.max(arr.length, DEFAULT_CAPACITY));
        size = arr.length;

        for (int i = (size / 2) - 1; i >= 0; i--) {
            heapifyDown(i);
        }
    }

    private void heapifyUp(int index) {
        while (index > 0) {
            int parent = (index - 1) / 2;

            if (heap[parent] <= heap[index])
                break;

            swap(parent, index);
            index = parent;
        }
    }

    private void heapifyDown(int index) {
        while (true) {

            int left = 2 * index + 1;
            int right = 2 * index + 2;
            int smallest = index;

            if (left < size && heap[left] < heap[smallest])
                smallest = left;

            if (right < size && heap[right] < heap[smallest])
                smallest = right;

            if (smallest == index)
                break;

            swap(index, smallest);
            index = smallest;
        }
    }

    private void ensureCapacity() {
        if (size == heap.length) {
            heap = Arrays.copyOf(heap, heap.length * 2);
        }
    }

    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }
}

Time Complexity

Operation	Complexity
Insert	O(log n)
Remove	O(log n)
Peek	O(1)
Build Heap	O(n)
Search	O(n)

Why Build Heap is O(n)?

Although heapifyDown() can take O(log n), most nodes are near the leaves and require very little work. The total cost across all nodes sums to O(n), making Floyd's Build Heap algorithm much faster than inserting n elements individually (O(n log n)).

Java `PriorityQueue` Internals

Java's PriorityQueue is implemented as a binary min-heap backed by a dynamically resized array.

Key characteristics:

Default initial capacity: 11
Supports natural ordering or a custom Comparator
offer() → insert
poll() → remove minimum
peek() → read minimum
Automatically grows as needed
Not thread-safe (PriorityBlockingQueue is the concurrent alternative)

Common Interview Questions

Why use an array instead of nodes?

A complete binary tree has a predictable structure, so parent/child relationships are derived by index. This removes pointer overhead and improves cache locality.

Why is insertion O(log n)?

A new element may travel from the last level to the root during heapifyUp.

Why can't we perform binary search on a heap?

Only the parent-child relationship is ordered. Siblings and subtrees are not globally sorted.

Difference between Heap and BST?

Heap	BST
Complete binary tree	Ordered binary tree
Root is min/max	Left < Root < Right
Search O(n)	Search O(log n) (balanced)
Peek O(1)	Min/Max requires traversal

When should you use a Heap?

Priority scheduling
Top-K problems
K-way merge
Graph algorithms (Dijkstra, Prim)
Running median
Event simulation

Design Improvements for Production

A production-ready heap implementation would typically include:

Generic implementation (Heap<T>)
Support for custom Comparator<T>
Configurable Min/Max Heap
decreaseKey() / increaseKey() operations
Indexed heap for efficient updates
Bulk construction from collections
Iterator support
Thread-safe variant if needed
Stable ordering for equal priorities (optional)

Summary

A Heap is one of the most fundamental data structures for implementing efficient priority-based algorithms. Understanding its array representation, heapifyUp, heapifyDown, and buildHeap operations provides a strong foundation for both coding interviews and designing high-performance scheduling, caching, and graph-processing systems.

Low-Level Design (LLD) of HashMap in Java — Build Your Own HashMap from Scratch

Dev Cookies — Thu, 09 Jul 2026 16:29:02 +0000

Target Audience: Software Engineers, Backend Engineers, Java Developers, SDE Interview Preparation

Introduction
What is HashMap?
Internal Architecture
Core Concepts
Designing Our Own HashMap
Node Class
Hash Function
Bucket Array
Put Operation
Get Operation
Remove Operation
Collision Handling
Rehashing / Resizing
Time Complexity
Complete Java Implementation
Improvements over our implementation
Java HashMap Internal Working
Interview Questions
Design Decisions
Summary

1. Introduction

HashMap is one of the most frequently used data structures in Java.

It provides

O(1) average insertion
O(1) average lookup
O(1) average deletion

Almost every backend application uses HashMap.

Examples:

Caching
Session Storage
Database Index
Frequency Counting
Memoization
Graph Representation
LRU Cache
Object Registry

2. What is a HashMap?

HashMap stores data as

Key → Value

Example

100 → Alice

101 → Bob

102 → Charlie

Instead of searching linearly,

HashMap computes

hash(key)

and directly jumps to the location.

3. Internal Architecture

             Bucket Array

        +----------------------+
0 ----> |  null                |
1 ----> |  Node                |
2 ----> |  Node -> Node        |
3 ----> |  null                |
4 ----> |  Node                |
5 ----> |  Node -> Node ->Node |
6 ----> |  null                |
        +----------------------+

Each bucket stores a linked list (or tree in Java 8+).

4. Core Components

A HashMap contains

Bucket Array

     ↓

Each Bucket

     ↓

Linked List

     ↓

    Node

     ↓

    Key
   Value
   Hash
   Next

5. Designing Our HashMap

We need

Bucket Array

Hash Function

put()

get()

remove()

resize()

size()

load factor

Step 1 — Node

class Node<K, V> {

    final K key;

    V value;

    Node<K, V> next;

    Node(K key, V value) {
        this.key = key;
        this.value = value;
    }
}

Each node stores

Key

Value

Pointer

Step 2 — HashMap Skeleton

public class MyHashMap<K, V> {

    private static final int DEFAULT_CAPACITY = 16;

    private Node<K, V>[] buckets;

    private int size;

    @SuppressWarnings("unchecked")
    public MyHashMap() {
        buckets = new Node[DEFAULT_CAPACITY];
    }
}

Bucket Array

Initially

Index

0

1

2

3

4

...

15

Capacity = 16

Step 3 — Hash Function

We convert any object into bucket index.

private int getIndex(K key) {

    if (key == null)
        return 0;

    return Math.abs(key.hashCode()) % buckets.length;
}

Example

hashCode()

  ↓

24567

  ↓

24567 % 16

  ↓

  7

Store in bucket 7.

Why modulo?

Suppose

hash = 982374623

Array size

982374623 % 16

    ↓

    15

Always inside array.

Step 4 — Put Operation

Algorithm

Compute bucket

      ↓

    Empty?

      ↓

    Insert

     Else

   Traverse

      ↓

  Existing key?

      ↓

    Update

     Else

    Append

Implementation

public void put(K key, V value) {

    int index = getIndex(key);

    Node<K, V> head = buckets[index];

    if (head == null) {
        buckets[index] = new Node<>(key, value);
        size++;
        return;
    }

    Node<K, V> current = head;

    while (true) {

        if ((current.key == key) ||
                (current.key != null && current.key.equals(key))) {

            current.value = value;
            return;
        }

        if (current.next == null)
            break;

        current = current.next;
    }

    current.next = new Node<>(key, value);

    size++;
}

Example

Insert

Apple

↓

Bucket 3

Bucket 3

Apple

Insert

Banana

↓

Bucket 3

Apple -> Banana

Collision handled.

Step 5 — Get Operation

Algorithm

Find bucket

↓

Traverse

↓

Key Found

↓

Return value

Implementation

public V get(K key) {

    int index = getIndex(key);

    Node<K, V> current = buckets[index];

    while (current != null) {

        if ((current.key == key) ||
                (current.key != null && current.key.equals(key))) {

            return current.value;
        }

        current = current.next;
    }

    return null;
}

Example

Bucket

Apple -> Mango -> Orange

Searching Mango

Apple

↓

No

↓

Mango

↓

Found

Step 6 — Remove Operation

Algorithm

Bucket

↓

Traverse

↓

Previous Node

↓

Reconnect

Implementation

public V remove(K key) {

    int index = getIndex(key);

    Node<K, V> current = buckets[index];

    Node<K, V> previous = null;

    while (current != null) {

        if ((current.key == key) ||
                (current.key != null && current.key.equals(key))) {

            if (previous == null)
                buckets[index] = current.next;
            else
                previous.next = current.next;

            size--;

            return current.value;
        }

        previous = current;
        current = current.next;
    }

    return null;
}

Collision Handling

Suppose

A

↓

Bucket 5

B

↓

Bucket 5

C

↓

Bucket 5

Stored as

Bucket 5

A

↓

B

↓

C

This is called

Separate Chaining

Rehashing

Suppose

Capacity

Load Factor

0.75

Threshold

16 × 0.75 = 12

After inserting 13th element

Resize

16

↓

32

Then reinsert all entries.

Resize Implementation

private void resize() {

    Node<K, V>[] oldBuckets = buckets;

    buckets = new Node[oldBuckets.length * 2];

    size = 0;

    for (Node<K, V> head : oldBuckets) {

        while (head != null) {

            put(head.key, head.value);

            head = head.next;
        }
    }
}

Add Resize Check

private static final float LOAD_FACTOR = 0.75f;

public void put(K key, V value) {

    if ((float)(size + 1) / buckets.length >= LOAD_FACTOR) {
        resize();
    }

    int index = getIndex(key);

    ...
}

Complete Java Implementation

public class MyHashMap<K, V> {

    private static class Node<K, V> {
        K key;
        V value;
        Node<K, V> next;

        Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    private static final int DEFAULT_CAPACITY = 16;
    private static final float LOAD_FACTOR = 0.75f;

    private Node<K, V>[] buckets;
    private int size;

    @SuppressWarnings("unchecked")
    public MyHashMap() {
        buckets = new Node[DEFAULT_CAPACITY];
    }

    private int getIndex(K key) {
        if (key == null)
            return 0;

        return Math.abs(key.hashCode()) % buckets.length;
    }

    public void put(K key, V value) {

        if ((float) (size + 1) / buckets.length >= LOAD_FACTOR)
            resize();

        int index = getIndex(key);

        Node<K, V> head = buckets[index];

        if (head == null) {
            buckets[index] = new Node<>(key, value);
            size++;
            return;
        }

        Node<K, V> current = head;

        while (true) {

            if ((current.key == key) ||
                    (current.key != null && current.key.equals(key))) {

                current.value = value;
                return;
            }

            if (current.next == null)
                break;

            current = current.next;
        }

        current.next = new Node<>(key, value);

        size++;
    }

    public V get(K key) {

        int index = getIndex(key);

        Node<K, V> current = buckets[index];

        while (current != null) {

            if ((current.key == key) ||
                    (current.key != null && current.key.equals(key))) {

                return current.value;
            }

            current = current.next;
        }

        return null;
    }

    public V remove(K key) {

        int index = getIndex(key);

        Node<K, V> current = buckets[index];
        Node<K, V> previous = null;

        while (current != null) {

            if ((current.key == key) ||
                    (current.key != null && current.key.equals(key))) {

                if (previous == null)
                    buckets[index] = current.next;
                else
                    previous.next = current.next;

                size--;

                return current.value;
            }

            previous = current;
            current = current.next;
        }

        return null;
    }

    @SuppressWarnings("unchecked")
    private void resize() {

        Node<K, V>[] oldBuckets = buckets;

        buckets = new Node[oldBuckets.length * 2];

        size = 0;

        for (Node<K, V> head : oldBuckets) {

            while (head != null) {

                put(head.key, head.value);

                head = head.next;
            }
        }
    }

    public int size() {
        return size;
    }
}

Time Complexity

Operation	Average	Worst
Put	O(1)	O(n)
Get	O(1)	O(n)
Remove	O(1)	O(n)
Resize	O(n)	O(n)

How Java 8 Improved HashMap

Before Java 8:

Bucket

↓

Linked List

Worst Case

O(n)

After Java 8:

If a bucket becomes too large (default threshold: 8 nodes) and the table has sufficient capacity (at least 64), the linked list is converted into a Red-Black Tree.

Bucket

↓

Red-Black Tree

Lookup

O(log n)

If the number of nodes later drops below 6, it converts back to a linked list.

Additional Optimizations in JDK HashMap

The production HashMap includes several improvements beyond our educational implementation:

Bit spreading: Mixes high bits into low bits using h ^ (h >>> 16) for better bucket distribution.
Power-of-two capacity: Bucket array size is always a power of two.
Fast index calculation: Uses (capacity - 1) & hash instead of %.
Cached hash value: Each node stores the computed hash to avoid recalculating it.
Fail-fast iterators: Detect concurrent structural modifications using modCount.
Tree bins: Uses TreeNode (Red-Black Tree) for heavily loaded buckets.
Null key support: Stores the null key in bucket 0.
Threshold-based resizing: Doubles capacity when size > capacity × loadFactor.

Common Interview Questions

1. Why is the default capacity 16?

Power of two enables efficient bitwise indexing.
Good balance between memory and performance.

2. Why is the default load factor 0.75?

Minimizes collisions while avoiding excessive memory usage.

3. Why are power-of-two capacities important?

Because index calculation becomes:

index = (capacity - 1) & hash;

which is faster than modulo.

4. Why store the hash in the node?

To avoid recomputing hashCode() during lookups and tree operations.

5. What happens if `hashCode()` is poorly implemented?

Many keys map to the same bucket, causing long chains or trees and degrading performance.

6. Is `HashMap` thread-safe?

No. Use:

ConcurrentHashMap
Collections.synchronizedMap(...)
External synchronization

Key Design Takeaways

Use an array of buckets for direct access.
Convert keys to bucket indices using a hash function.
Handle collisions with separate chaining (and tree bins in JDK).
Resize when the load factor threshold is exceeded.
Favor power-of-two capacities for efficient indexing.
Ensure key classes implement both equals() and hashCode() correctly.

Summary

Building a HashMap from scratch demonstrates many core LLD concepts:

Generic classes
Encapsulation
Linked list composition
Hashing
Collision resolution
Dynamic resizing
Performance trade-offs
Clean object-oriented design

Understanding this implementation is valuable not only for Java interviews but also for designing high-performance in-memory data structures and caches in production systems.

Parking Lot System Low-Level Design (LLD) in Java

Dev Cookies — Thu, 09 Jul 2026 13:30:59 +0000

Complete Interview Guide | SOLID Principles | Design Patterns | Production-Ready Architecture

Introduction

The Parking Lot is one of the most frequently asked Low-Level Design (LLD) interview questions at companies like Amazon, Microsoft, Uber, Walmart, Oracle, Adobe, Atlassian, and Flipkart.

It tests a candidate's understanding of:

Object-Oriented Design (OOD)
SOLID Principles
Design Patterns
Object Relationships
Extensibility
Clean Code
Domain Modeling

Unlike algorithm questions, the focus is on designing a flexible, maintainable, and scalable system.

Problem Statement

Design a Parking Lot System that supports:

Multiple parking floors
Multiple parking spot types
Multiple vehicle types
Parking ticket generation
Vehicle entry and exit
Fee calculation
Display available parking spaces
Multiple payment methods
Reservation support (optional)

Functional Requirements

Core Features

Park a vehicle
Unpark a vehicle
Generate parking ticket
Calculate parking fee
Find nearest available parking spot
Display available spots
Track occupied spots

Optional Features

EV charging spots
Reserved parking
VIP parking
Online booking
Dynamic pricing
Lost ticket handling
License plate recognition
Multi-entry/multi-exit gates

Non-Functional Requirements

High Availability
Thread Safety
Scalability
Extensibility
Low Latency
Fault Tolerance
Maintainability

Real-World Examples

Airport Parking
Shopping Mall
IT Parks
Hospitals
Railway Stations
Apartment Complexes
Smart City Parking
Event Parking

High-Level Architecture

                    Client
                       │
                       ▼
               ParkingLotFacade
                       │
        ┌──────────────┼──────────────┐
        ▼              ▼              ▼
 Entry Gate      Exit Gate      Display Board
        │              │
        ▼              ▼
 TicketService    PaymentService
        │              │
        └──────┬───────┘
               ▼
        ParkingManager
               │
      ┌────────┴─────────┐
      ▼                  ▼
 Parking Floors     Spot Allocation
      │
      ▼
 Parking Spots

Core Components

Component	Responsibility
ParkingLot	Root aggregate
ParkingFloor	Contains parking spots
ParkingSpot	Represents a parking space
Vehicle	Vehicle details
Ticket	Parking ticket
Gate	Entry/Exit management
Payment	Fee collection
PricingStrategy	Parking fee calculation

Domain Model

                    +--------------------+
                    |    ParkingLot      |
                    +--------------------+
                    | id                 |
                    | name               |
                    +---------+----------+
                              |
                     1        |       *
                              |
                              ▼
                    +--------------------+
                    | ParkingFloor       |
                    +--------------------+
                    | floorNo            |
                    +---------+----------+
                              |
                     1        |       *
                              |
                              ▼
                    +--------------------+
                    | ParkingSpot        |
                    +--------------------+
                    | spotId             |
                    | type               |
                    | occupied           |
                    +---------+----------+
                              |
                              |
                              ▼
                    +--------------------+
                    | Vehicle            |
                    +--------------------+

Design Patterns Used

Pattern	Purpose
Facade	Single entry point (`ParkingLotFacade`)
Strategy	Spot allocation, pricing, payment
Factory	Create vehicles and tickets
State	Parking spot state
Observer	Display board updates
Singleton	Parking lot configuration
Builder	Ticket creation
Repository	Data persistence abstraction

Enumerations

Vehicle Type

public enum VehicleType {
    MOTORCYCLE,
    CAR,
    SUV,
    BUS,
    TRUCK,
    ELECTRIC
}

Spot Type

public enum SpotType {
    MOTORCYCLE,
    COMPACT,
    LARGE,
    ELECTRIC,
    HANDICAPPED
}

Spot Status

public enum SpotStatus {
    AVAILABLE,
    OCCUPIED,
    RESERVED,
    OUT_OF_SERVICE
}

Vehicle

public abstract class Vehicle {

    private final String registrationNumber;
    private final VehicleType vehicleType;

    protected Vehicle(String registrationNumber,
                      VehicleType vehicleType) {
        this.registrationNumber = registrationNumber;
        this.vehicleType = vehicleType;
    }

    public String getRegistrationNumber() {
        return registrationNumber;
    }

    public VehicleType getVehicleType() {
        return vehicleType;
    }
}

Parking Spot

public class ParkingSpot {

    private final String spotId;
    private final SpotType spotType;
    private SpotStatus status;

    public ParkingSpot(String spotId,
                       SpotType spotType) {
        this.spotId = spotId;
        this.spotType = spotType;
        this.status = SpotStatus.AVAILABLE;
    }

    public boolean isAvailable() {
        return status == SpotStatus.AVAILABLE;
    }

    public void occupy() {
        status = SpotStatus.OCCUPIED;
    }

    public void release() {
        status = SpotStatus.AVAILABLE;
    }
}

Ticket

import java.time.Instant;
import java.util.UUID;

public class ParkingTicket {

    private final String ticketId;
    private final Vehicle vehicle;
    private final ParkingSpot parkingSpot;
    private final Instant entryTime;

    public ParkingTicket(Vehicle vehicle,
                         ParkingSpot parkingSpot) {
        this.ticketId = UUID.randomUUID().toString();
        this.vehicle = vehicle;
        this.parkingSpot = parkingSpot;
        this.entryTime = Instant.now();
    }

    // getters
}

Spot Allocation Strategy

public interface SpotAllocationStrategy {

    ParkingSpot allocate(
            Vehicle vehicle,
            ParkingFloor floor);

}

Example implementations:

NearestSpotStrategy
FirstAvailableStrategy
RandomSpotStrategy
EVPriorityStrategy

Pricing Strategy

import java.math.BigDecimal;
import java.time.Duration;

public interface PricingStrategy {

    BigDecimal calculateFee(
            Vehicle vehicle,
            Duration duration);

}

Possible implementations:

HourlyPricingStrategy
FlatRatePricingStrategy
WeekendPricingStrategy
DynamicPricingStrategy

Payment Strategy

import java.math.BigDecimal;

public interface PaymentStrategy {

    void pay(BigDecimal amount);

}

Implementations:

CashPayment
CardPayment
UpiPayment
WalletPayment

Parking Manager

public interface ParkingManager {

    ParkingTicket park(Vehicle vehicle);

    void unpark(String ticketId);

}

The manager coordinates:

Spot allocation
Ticket generation
Spot release
Fee calculation
Payment

Parking Flow

Vehicle Arrives
       │
       ▼
Entry Gate
       │
       ▼
Find Available Spot
       │
       ▼
Allocate Spot
       │
       ▼
Generate Ticket
       │
       ▼
Open Barrier

Exit Flow

Vehicle Arrives
       │
       ▼
Scan Ticket
       │
       ▼
Calculate Fee
       │
       ▼
Process Payment
       │
       ▼
Release Spot
       │
       ▼
Open Barrier

Display Board

The display board observes parking spot changes.

Floor 1

Compact : 12

Large : 5

Electric : 3

Motorcycle : 18

This is a good use case for the Observer Pattern, where display boards update automatically when spot availability changes.

Thread Safety

Use:

ConcurrentHashMap for active tickets
ReentrantLock or synchronized blocks for spot allocation
Atomic operations when updating availability
Database transactions for ticket creation and payment

Avoid:

Two vehicles acquiring the same spot simultaneously
Global synchronization across the entire parking lot

Database Design

Parking Spot

Column	Type
spot_id	VARCHAR
floor_id	VARCHAR
spot_type	ENUM
status	ENUM

Parking Ticket

Column	Type
ticket_id	UUID
vehicle_number	VARCHAR
spot_id	VARCHAR
entry_time	TIMESTAMP
exit_time	TIMESTAMP
amount	DECIMAL

Payment

Column	Type
payment_id	UUID
ticket_id	UUID
payment_type	ENUM
amount	DECIMAL
status	ENUM

SOLID Principles

Principle	Application
Single Responsibility	Separate classes for allocation, pricing, payment, and ticketing.
Open/Closed	Add new pricing or allocation strategies without modifying existing code.
Liskov Substitution	Any pricing or payment strategy can be substituted.
Interface Segregation	Small interfaces (`PricingStrategy`, `PaymentStrategy`, `SpotAllocationStrategy`).
Dependency Inversion	`ParkingManager` depends on abstractions rather than concrete implementations.

Production Enhancements

Multi-gate synchronization
Distributed parking management
QR-code or RFID tickets
ANPR (Automatic Number Plate Recognition)
EV charging reservations
Online pre-booking
Lost ticket workflow
Dynamic surge pricing
Occupancy analytics
Mobile app integration
Event-driven notifications
Integration with payment gateways

Complexity Analysis

Operation	Complexity
Find Spot	O(log n) or O(1)*
Park Vehicle	O(log n)
Unpark Vehicle	O(1)
Generate Ticket	O(1)
Calculate Fee	O(1)

*With indexed free-spot structures (e.g., per-floor priority queues or maps), spot lookup can approach O(1). A naive linear scan is O(n).

Common Interview Follow-up Questions

How would you prevent two vehicles from getting the same parking spot?
How would you support multiple entry and exit gates concurrently?
How would you implement the "nearest available spot" algorithm?
How would you reserve parking spots for VIPs or disabled users?
How would you support electric vehicle charging stations?
How would you implement dynamic pricing during peak hours?
How would you recover if payment succeeds but the exit gate fails to open?
How would you design the system for multiple parking lots across different cities?
How would you handle a lost parking ticket?
How would you keep display boards synchronized with real-time spot availability?

Interview Tips

Focus on Extensibility

Instead of hardcoding:

Vehicle types
Pricing rules
Spot allocation logic
Payment methods

Abstract them behind interfaces and use the Strategy Pattern.

Explain Why the Facade Pattern Fits

ParkingLotFacade provides a simple API such as:

ParkingTicket park(Vehicle vehicle);

Receipt unpark(String ticketId);

Internally it coordinates:

Spot allocation
Ticket generation
Pricing
Payment
Display updates

This keeps client code simple while hiding implementation complexity.

Key Takeaways

Model the domain with clear entities: ParkingLot, ParkingFloor, ParkingSpot, Vehicle, and ParkingTicket.
Use Strategy Pattern for spot allocation, pricing, and payment to support future extensions.
Use Facade Pattern to expose a simple API while coordinating multiple subsystems.
Design for concurrency to avoid duplicate spot allocation.
Discuss production concerns like multi-gate coordination, reservations, dynamic pricing, analytics, and distributed deployment to demonstrate senior-level design thinking.

Banking Ledger System Low-Level Design (LLD) in Java

Dev Cookies — Thu, 09 Jul 2026 13:27:50 +0000

Complete Interview Guide | Double-Entry Accounting | ACID Transactions | Production-Ready Architecture

Introduction

A Banking Ledger System is one of the most practical Low-Level Design (LLD) interview questions because it combines:

Object-Oriented Design (OOD)
Financial Domain Modeling
ACID Transactions
Double-Entry Accounting
Concurrency Control
Auditability
Idempotency
Event-Driven Architecture

Companies such as Amazon, Microsoft, Stripe, PayPal, Razorpay, PhonePe, Visa, Mastercard, and banks frequently discuss ledger concepts in interviews.

A ledger is the source of truth for all financial transactions. Account balances should be derived from ledger entries, not maintained as the primary source of truth.

Problem Statement

Design a Banking Ledger System that supports:

Create accounts
Credit money
Debit money
Transfer funds
View transaction history
Maintain account balances
Audit every transaction
Ensure atomicity and consistency
Prevent duplicate processing (idempotency)

Functional Requirements

Core Features

Create customer accounts
Record deposits
Record withdrawals
Transfer between accounts
Retrieve ledger history
Query account balance
Reverse transactions
Idempotent transaction processing

Non-Functional Requirements

ACID compliant
Highly available
Strong consistency
Thread-safe
Fault tolerant
Immutable audit trail
Horizontally scalable

Real-World Use Cases

Bank accounts
Digital wallets
UPI transactions
Credit card systems
Payment gateways
Trading platforms
Payroll systems
Expense management

Core Banking Principle: Double-Entry Accounting

Every financial transaction creates at least two ledger entries.

Transfer ₹1000

Alice Account      -1000 (Debit)
Bob Account        +1000 (Credit)

Total Change = 0

This guarantees:

No money is created unexpectedly
No money disappears unexpectedly
Every movement is traceable

High-Level Architecture

                    Client
                       │
                       ▼
                Ledger Service
                       │
      ┌────────────────┼────────────────┐
      ▼                ▼                ▼
 Account Service   Transaction Engine   Ledger Store
      │                │                │
      ▼                ▼                ▼
 Account Repo     Journal Entries    Database
                       │
                       ▼
                  Audit Log

Core Components

Component	Responsibility
Account	Customer account
LedgerEntry	Immutable debit/credit record
Transaction	Groups ledger entries
LedgerService	Business operations
BalanceCalculator	Computes balances
AuditService	Tracks changes
TransactionRepository	Stores transactions

Domain Model

                  +----------------------+
                  |      Account         |
                  +----------------------+
                  | accountId            |
                  | customerId           |
                  | status               |
                  +----------+-----------+
                             |
                             |
                     1        |       *
                             |
                             ▼
                  +----------------------+
                  |    LedgerEntry       |
                  +----------------------+
                  | transactionId        |
                  | accountId            |
                  | amount               |
                  | type                 |
                  | timestamp            |
                  +----------+-----------+
                             |
                             |
                             ▼
                  +----------------------+
                  |    Transaction       |
                  +----------------------+
                  | transactionId        |
                  | status               |
                  | referenceId          |
                  +----------------------+

Design Patterns Used

Pattern	Purpose
Strategy	Balance calculation, fee policies
Factory	Create transaction types
Builder	Construct immutable transactions
Command	Represent financial operations
State	Transaction lifecycle
Observer	Notifications and auditing
Repository	Data access abstraction
Singleton	Configuration services

Enumerations

Entry Type

public enum EntryType {

    DEBIT,
    CREDIT

}

Transaction Status

public enum TransactionStatus {

    PENDING,
    SUCCESS,
    FAILED,
    REVERSED

}

Account

public class Account {

    private final String accountId;

    private final String customerId;

    private AccountStatus status;

    // getters

}

Ledger Entry

import java.math.BigDecimal;
import java.time.Instant;

public class LedgerEntry {

    private final String transactionId;

    private final String accountId;

    private final EntryType type;

    private final BigDecimal amount;

    private final Instant timestamp;

    public LedgerEntry(
            String transactionId,
            String accountId,
            EntryType type,
            BigDecimal amount) {

        this.transactionId = transactionId;
        this.accountId = accountId;
        this.type = type;
        this.amount = amount;
        this.timestamp = Instant.now();
    }

}

Transaction

import java.util.List;

public class Transaction {

    private final String transactionId;

    private final List<LedgerEntry> entries;

    private TransactionStatus status;

    private final String idempotencyKey;

    public Transaction(
            String transactionId,
            List<LedgerEntry> entries,
            String idempotencyKey) {

        this.transactionId = transactionId;
        this.entries = entries;
        this.idempotencyKey = idempotencyKey;
        this.status = TransactionStatus.PENDING;
    }

}

Ledger Service

public interface LedgerService {

    void deposit(String accountId, BigDecimal amount);

    void withdraw(String accountId, BigDecimal amount);

    void transfer(
            String fromAccount,
            String toAccount,
            BigDecimal amount);

}

Transfer Flow

Client

   │

   ▼

Validate Accounts

   │

   ▼

Check Balance

   │

   ▼

Create Transaction

   │

   ▼

Create Debit Entry

   │

   ▼

Create Credit Entry

   │

   ▼

Persist Both Entries (Single DB Transaction)

   │

   ▼

Commit

   │

   ▼

Publish Event

Transfer Example

Transfer ₹500

Transaction ID : TX100

Ledger

--------------------------------

Alice

Debit

₹500

Bob

Credit

₹500

Balance Calculation

Recommended approach: derive the balance from immutable ledger entries.

Balance = Σ(Credits) − Σ(Debits)

For performance, many production systems maintain a cached/materialized balance that is derived from and periodically reconciled against the ledger.

Idempotency

Every external financial request should include an Idempotency Key.

POST /transfer

Idempotency-Key: abc123

If the same request is retried:

Already Processed

Return Previous Result

This prevents duplicate transfers caused by retries or network failures.

Database Schema

Account

Column	Type
account_id	UUID
customer_id	UUID
status	ENUM

Transaction

Column	Type
transaction_id	UUID
status	ENUM
idempotency_key	VARCHAR (UNIQUE)
created_at	TIMESTAMP

Ledger Entry

Column	Type
entry_id	UUID
transaction_id	UUID
account_id	UUID
entry_type	ENUM
amount	DECIMAL
created_at	TIMESTAMP

Concurrency Control

Use:

Database transactions
Optimistic locking (version columns)
Pessimistic locking for high-contention accounts
Consistent account lock ordering to avoid deadlocks
Idempotency keys
Retry with exponential backoff for transient conflicts

Thread Safety

Prefer:

Stateless services
ACID database transactions
Immutable ledger entries
Optimistic locking

Avoid:

Updating balances without transaction boundaries
Shared mutable in-memory state as the source of truth

Transaction Lifecycle

             CREATED
                 │
                 ▼
             VALIDATED
                 │
                 ▼
             PENDING
                 │
        ┌────────┴────────┐
        ▼                 ▼
     SUCCESS           FAILED
        │
        ▼
     REVERSED

Production Enhancements

Event sourcing
Outbox Pattern for reliable event publishing
CDC (Change Data Capture)
Multi-currency support
Exchange rate service
Scheduled reconciliation jobs
Fraud detection
AML/KYC integration
Settlement engine
Ledger snapshots
Read replicas for reporting
Encryption of sensitive data
Comprehensive audit logs

SOLID Principles

Principle	Application
Single Responsibility	Separate services for ledger, accounts, auditing, and balance calculation.
Open/Closed	New transaction or fee types can be added without modifying existing logic.
Liskov Substitution	Different repository implementations can be substituted transparently.
Interface Segregation	Small interfaces (`LedgerService`, `AccountRepository`, `AuditService`).
Dependency Inversion	Business logic depends on abstractions rather than database implementations.

Complexity Analysis

Operation	Complexity
Create Transaction	O(1)
Create Ledger Entries	O(1)
Transfer	O(1) (excluding I/O)
Balance Calculation	O(n) over ledger entries
Cached Balance Lookup	O(1)

Common Interview Follow-up Questions

Why use double-entry accounting instead of updating balances directly?
How would you guarantee atomicity across debit and credit entries?
How would you prevent duplicate transfers?
How would you implement transaction reversal?
How would you reconcile cached balances with the ledger?
How would you support millions of transactions per day?
How would you shard ledger data while preserving consistency?
When would you use optimistic locking versus pessimistic locking?
How would you design the ledger for multi-currency transactions?
How would you integrate the ledger with Kafka using the Outbox Pattern?

Interview Tips

Explain the Difference Between Account Balance and Ledger

Ledger: Immutable source of truth containing every financial movement.
Balance: A derived or cached value computed from the ledger.

Emphasize Financial Correctness

Double-entry accounting
ACID transactions
Idempotency
Immutable audit trail
Consistency over availability for core financial operations

Mention Production Considerations

Event sourcing (where appropriate)
Outbox Pattern + Kafka
CDC for downstream systems
Optimistic locking
Reconciliation jobs
Monitoring and alerting
Disaster recovery and backups

Key Takeaways

Model every financial operation as an immutable Transaction containing balanced Ledger Entries.
Use double-entry accounting to ensure every debit has a corresponding credit.
Treat the ledger as the source of truth; balances are derived or cached views.
Ensure ACID transactions, idempotency, and auditability for every operation.
Design for extensibility using Repository, Strategy, Factory, and Command patterns.
Discuss concurrency, reconciliation, distributed messaging, and operational concerns to demonstrate senior-level system design expertise.

Task Scheduler Low-Level Design (LLD) in Java

Dev Cookies — Thu, 09 Jul 2026 13:26:45 +0000

Complete Interview Guide | SOLID Principles | Design Patterns | Production-Ready Architecture

Introduction

A Task Scheduler is a common Low-Level Design (LLD) interview question asked by companies like Amazon, Microsoft, Google, Atlassian, Uber, Walmart, and Oracle.

It evaluates a candidate's understanding of:

Object-Oriented Design (OOD)
SOLID Principles
Design Patterns
Java Concurrency
Scheduling Algorithms
Thread Pools
Extensibility
Production System Design

Real-world schedulers include:

Spring @Scheduled
Quartz Scheduler
Linux Cron
Kubernetes CronJobs
Windows Task Scheduler
Airflow
Jenkins Scheduler

Problem Statement

Design a Task Scheduler that can:

Schedule a task to run at a specific time
Schedule recurring tasks
Cancel scheduled tasks
Pause and resume tasks
Execute tasks asynchronously
Support priorities
Retry failed tasks
Be thread-safe
Be easily extensible

Functional Requirements

Core Features

Schedule one-time tasks
Schedule recurring tasks
Cancel tasks
Pause tasks
Resume tasks
Retry failed tasks
Execute multiple tasks concurrently

Optional Features

Cron expressions
Task dependencies
Distributed scheduling
Persistence
Monitoring
Metrics
Notifications

Non-Functional Requirements

High Throughput
Low Latency
Thread Safe
Fault Tolerant
Scalable
Extensible
Maintainable

Real-World Use Cases

Email Scheduler
Payment Retry
Notification Service
Data Cleanup Jobs
ETL Pipelines
Report Generation
Database Backup
Order Expiry
Subscription Renewal
Cache Refresh

High-Level Architecture

                 Client
                    │
                    ▼
          TaskSchedulerService
                    │
     ┌──────────────┼──────────────┐
     ▼              ▼              ▼
 Scheduler      Task Queue      TaskStore
     │
     ▼
 Priority Queue
     │
     ▼
 Worker Threads
     │
     ▼
 TaskExecutor
     │
     ▼
 Runnable Task

Core Components

Component	Responsibility
Task	Represents a scheduled job
Scheduler	Decides when to execute
Executor	Executes tasks
Queue	Holds pending tasks
Worker	Picks and executes tasks
Retry Policy	Handles failures
Trigger	Determines execution time

Object Model

                +--------------------+
                |   TaskScheduler    |
                +--------------------+
                | schedule()         |
                | cancel()           |
                | pause()            |
                | resume()           |
                +---------+----------+
                          |
                          ▼
                 +----------------+
                 | ScheduledTask  |
                 +----------------+
                 | id             |
                 | name           |
                 | trigger        |
                 | runnable       |
                 | status         |
                 | priority       |
                 +----------------+
                          |
          ---------------------------------
          |               |               |
          ▼               ▼               ▼
     OneTime         FixedDelay      CronTask

Design Patterns Used

Pattern	Purpose
Strategy	Different scheduling strategies
Factory	Create triggers
Command	Represent executable task
Observer	Task completion notification
State	Task lifecycle
Singleton	Scheduler instance
Builder	Create complex task objects
Template Method	Common execution flow

Class Design

Task Status

public enum TaskStatus {

    SCHEDULED,
    RUNNING,
    PAUSED,
    COMPLETED,
    FAILED,
    CANCELLED

}

Priority

public enum Priority {

    HIGH,
    MEDIUM,
    LOW

}

Task Interface

public interface Task {

    void execute();

}

Scheduled Task

import java.time.Instant;
import java.util.UUID;

public class ScheduledTask {

    private final String id;

    private final String name;

    private final Task task;

    private Instant nextExecutionTime;

    private Priority priority;

    private TaskStatus status;

    public ScheduledTask(
            String name,
            Task task,
            Instant nextExecutionTime,
            Priority priority) {

        this.id = UUID.randomUUID().toString();
        this.name = name;
        this.task = task;
        this.nextExecutionTime = nextExecutionTime;
        this.priority = priority;
        this.status = TaskStatus.SCHEDULED;
    }

    // getters

}

Task Comparator

Tasks should be executed based on:

Earliest execution time
Highest priority

import java.util.Comparator;

public class TaskComparator
        implements Comparator<ScheduledTask> {

    @Override
    public int compare(
            ScheduledTask t1,
            ScheduledTask t2) {

        int time =
                t1.getNextExecutionTime()
                  .compareTo(t2.getNextExecutionTime());

        if (time != 0)
            return time;

        return t2.getPriority()
                 .ordinal()
                - t1.getPriority()
                    .ordinal();

    }

}

Scheduler Queue

PriorityBlockingQueue<ScheduledTask>

Why?

Thread-safe
Automatically sorted
Multiple producers
Multiple consumers

Scheduler Service

public interface TaskScheduler {

    void schedule(ScheduledTask task);

    void cancel(String taskId);

    void pause(String taskId);

    void resume(String taskId);

}

Implementation

import java.util.concurrent.*;

public class TaskSchedulerImpl
        implements TaskScheduler {

    private final PriorityBlockingQueue<ScheduledTask> queue =
            new PriorityBlockingQueue<>(
                    100,
                    new TaskComparator());

    private final ExecutorService workers =
            Executors.newFixedThreadPool(5);

    @Override
    public void schedule(
            ScheduledTask task) {

        queue.offer(task);

    }

    @Override
    public void cancel(String id) {

        queue.removeIf(
                t -> t.getId().equals(id));

    }

    @Override
    public void pause(String id) {

        // update status

    }

    @Override
    public void resume(String id) {

        // update status

    }

}

Worker Thread

while(true){

    ScheduledTask task = queue.take();

    if(task.getNextExecutionTime()
            .isAfter(Instant.now())){

        queue.offer(task);

        Thread.sleep(100);

        continue;
    }

    workers.submit(
            () -> task.getTask().execute());

}

Example

Task emailTask =
        () -> System.out.println("Sending Email");

ScheduledTask task =
        new ScheduledTask(

                "Email",

                emailTask,

                Instant.now().plusSeconds(5),

                Priority.HIGH

        );

scheduler.schedule(task);

Thread Safety

Use:

PriorityBlockingQueue
ConcurrentHashMap
AtomicInteger
ExecutorService
ScheduledExecutorService
ReentrantLock (when needed)

Avoid:

Global synchronization
Manual thread management
Shared mutable state

Task Lifecycle

             CREATED
                 │
                 ▼
           SCHEDULED
                 │
                 ▼
             WAITING
                 │
                 ▼
             RUNNING
          ┌──────┴──────┐
          ▼             ▼
     COMPLETED      FAILED
                         │
                         ▼
                      RETRYING
                         │
                         ▼
                     COMPLETED

Retry Strategy

Implement a RetryPolicy interface:

public interface RetryPolicy {

    boolean shouldRetry(int attempt);

    long nextDelay(int attempt);

}

Possible implementations:

Fixed Delay
Exponential Backoff
Randomized Backoff

Scheduling Strategies

One-Time

Runs exactly once.

Fixed Delay

Task finishes

↓

Wait 10 sec

↓

Run again

Fixed Rate

0 sec

10 sec

20 sec

30 sec

Runs at a constant interval regardless of task duration.

Cron

0 0 * * *

Every hour

Production Improvements

Instead of a custom scheduler loop, prefer:

ScheduledExecutorService
Quartz Scheduler
Spring Scheduler
Kubernetes CronJobs
Airflow (workflow scheduling)

Additional enhancements:

Persistent task storage
Leader election for distributed deployments
Metrics (Micrometer/Prometheus)
Dead Letter Queue (DLQ) for repeatedly failing tasks
Graceful shutdown
Dynamic worker pool sizing
Task timeouts and cancellation
Distributed locks for singleton execution

SOLID Principles

Principle	Application
Single Responsibility	`Task`, `Scheduler`, `Executor`, and `RetryPolicy` each have one responsibility.
Open/Closed	Add new trigger or retry strategies without modifying scheduler logic.
Liskov Substitution	Any `Task` or `RetryPolicy` implementation can be substituted.
Interface Segregation	Small, focused interfaces (`Task`, `TaskScheduler`, `RetryPolicy`).
Dependency Inversion	Scheduler depends on abstractions instead of concrete task implementations.

Complexity Analysis

Operation	Complexity
Schedule Task	O(log n)
Fetch Next Task	O(log n)
Cancel Task	O(n)*
Execute Task	O(1) + task execution time

*Using only a PriorityBlockingQueue, cancellation requires searching the queue. A production implementation typically combines a ConcurrentHashMap<taskId, Task> with the priority queue to achieve faster lookups and state management.

Common Interview Follow-up Questions

Why use a PriorityBlockingQueue instead of a regular PriorityQueue?
How would you support millions of scheduled tasks efficiently?
How would you implement cron expressions?
How would you prevent duplicate execution in a distributed system?
How would you handle scheduler crashes and task recovery?
How would you guarantee "exactly once" or "at least once" execution semantics?
How would you implement exponential backoff retries?
How would you support task dependencies (DAGs)?
How would you ensure fairness when multiple tasks have the same execution time?
When would you choose ScheduledExecutorService over a custom scheduler?

Key Interview Takeaways

Use PriorityBlockingQueue to efficiently order tasks by execution time.
Use ExecutorService or ScheduledExecutorService for concurrent execution instead of manually creating threads.
Separate scheduling, execution, retry, and storage into distinct components to follow SOLID principles.
Design for extensibility with Strategy, Command, and Factory patterns.
Discuss production concerns such as persistence, distributed scheduling, retries, monitoring, and graceful shutdown to demonstrate senior-level system design thinking.

This design provides a clean, interview-friendly foundation that can be extended into a production-grade scheduler similar in architecture to Quartz or Spring's scheduling infrastructure.

LRU Cache LLD

Dev Cookies — Thu, 09 Jul 2026 13:25:21 +0000

The LRU (Least Recently Used) Cache is one of the most frequently asked Java LLD interview questions. It evaluates:

OOP Design
Data Structures
SOLID Principles
Time Complexity
Thread Safety
Extensibility

A good interview solution should achieve O(1) time complexity for both get() and put() operations.

Problem Statement

Design an LRU Cache that supports:

get(key)
put(key, value)
Fixed capacity
Evict Least Recently Used item when full
O(1) operations
Thread-safe (Bonus)

Example:

Capacity = 3

put(1, A)
put(2, B)
put(3, C)

Cache:
3 → 2 → 1

get(1)

Cache:
1 → 3 → 2

put(4, D)

Evict 2

Cache:
4 → 1 → 3

Functional Requirements

Get value by key
Insert/Update key-value pair
Fixed cache capacity
Automatic eviction of least recently used entry

Non-Functional Requirements

O(1) read/write
Memory efficient
Extensible
Thread-safe
Generic implementation

Why HashMap + Doubly Linked List?

HashMap
-------------------
1 -> Node
2 -> Node
3 -> Node

            ▲
            │

Head <-> 3 <-> 2 <-> 1 <-> Tail
       MRU               LRU

Responsibilities

HashMap

O(1) lookup

Doubly Linked List

O(1) insertion
O(1) deletion
O(1) move to front

Time Complexity

Operation	Complexity
get	O(1)
put	O(1)
remove	O(1)
moveToFront	O(1)

Class Diagram

                +----------------------+
                |      LRUCache<K,V>   |
                +----------------------+
                | capacity             |
                | Map<K,Node<K,V>>     |
                | head                 |
                | tail                 |
                +----------------------+
                | get()                |
                | put()                |
                | removeNode()         |
                | addToFront()         |
                +----------+-----------+
                           |
                           |
                    +------v------+
                    | Node<K,V>   |
                    +-------------+
                    | key         |
                    | value       |
                    | prev        |
                    | next        |
                    +-------------+

Node Class

class Node<K, V> {

    K key;
    V value;

    Node<K, V> prev;
    Node<K, V> next;

    Node(K key, V value) {
        this.key = key;
        this.value = value;
    }
}

LRU Cache Implementation

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

public class LRUCache<K, V> {

    private final int capacity;
    private final Map<K, Node<K, V>> cache;

    private final Node<K, V> head;
    private final Node<K, V> tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();

        head = new Node<>(null, null);
        tail = new Node<>(null, null);

        head.next = tail;
        tail.prev = head;
    }

    public synchronized V get(K key) {

        Node<K, V> node = cache.get(key);

        if (node == null) {
            return null;
        }

        moveToFront(node);
        return node.value;
    }

    public synchronized void put(K key, V value) {

        Node<K, V> node = cache.get(key);

        if (node != null) {
            node.value = value;
            moveToFront(node);
            return;
        }

        if (cache.size() == capacity) {

            Node<K, V> lru = tail.prev;

            removeNode(lru);

            cache.remove(lru.key);
        }

        Node<K, V> newNode = new Node<>(key, value);

        cache.put(key, newNode);

        addToFront(newNode);
    }

    private void moveToFront(Node<K, V> node) {

        removeNode(node);

        addToFront(node);
    }

    private void addToFront(Node<K, V> node) {

        node.next = head.next;
        node.prev = head;

        head.next.prev = node;

        head.next = node;
    }

    private void removeNode(Node<K, V> node) {

        node.prev.next = node.next;

        node.next.prev = node.prev;
    }

    static class Node<K, V> {

        K key;
        V value;

        Node<K, V> prev;
        Node<K, V> next;

        Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
}

Driver

public class Main {

    public static void main(String[] args) {

        LRUCache<Integer, String> cache = new LRUCache<>(3);

        cache.put(1, "A");
        cache.put(2, "B");
        cache.put(3, "C");

        System.out.println(cache.get(1));

        cache.put(4, "D");

        System.out.println(cache.get(2));
        System.out.println(cache.get(3));
        System.out.println(cache.get(4));
    }
}

Execution

put(1,A)

1

put(2,B)

2 → 1

put(3,C)

3 → 2 → 1

get(1)

1 → 3 → 2

put(4,D)

Evict 2

4 → 1 → 3

Design Patterns Used

Pattern	Purpose
Template (optional)	Base cache abstraction
Strategy (optional)	Eviction policy (LRU, LFU, FIFO)
Factory (optional)	Cache creation
Singleton (optional)	Shared cache instance
Decorator (optional)	Metrics, logging

SOLID Principles

Principle	Application
Single Responsibility	`Node` stores data, `LRUCache` manages cache behavior.
Open/Closed	Eviction logic can be abstracted to support new policies.
Liskov Substitution	Alternative cache implementations can implement the same interface.
Interface Segregation	Define a small `Cache<K,V>` interface (`get`, `put`, `remove`, `clear`).
Dependency Inversion	Depend on a `Cache` abstraction rather than a concrete implementation.

Production Enhancements

A production-grade cache often includes:

Cache<K,V> interface
Pluggable eviction policies (LRU, LFU, FIFO)
Time-based expiration (TTL/TTI)
Maximum memory limit
Statistics (hits, misses, evictions)
Asynchronous loading (LoadingCache)
Background cleanup
Persistence support
Distributed cache support (Redis, Hazelcast)
Read-write locking (ReentrantReadWriteLock) for improved concurrency

Common Interview Follow-up Questions

Why use a Doubly Linked List instead of a singly linked list?

Removal and movement of arbitrary nodes require O(1) access to both previous and next nodes.

Why use dummy head and tail nodes?

They eliminate edge cases when adding or removing nodes at the ends of the list.

Why can't a HashMap alone implement an LRU cache?

A HashMap provides fast lookup but does not maintain recency order.

How would you make this implementation more concurrent?

Replace synchronized methods with ReentrantReadWriteLock or use segmented locking to reduce contention.

How would you support different eviction strategies?

Extract an EvictionPolicy interface and implement LRU, LFU, or FIFO strategies using the Strategy pattern.

How would you add expiration (TTL)?

Store an expiration timestamp with each node and lazily or periodically remove expired entries.

How does this compare to Java's LinkedHashMap?

LinkedHashMap can implement LRU using access-order mode and overriding removeEldestEntry(), but implementing it manually demonstrates understanding of the underlying data structures.

This implementation is the standard LLD solution expected in Java interviews because it combines HashMap + Doubly Linked List to achieve O(1) get() and put() while remaining clean, extensible, and easy to explain.

Rate Limiter LLD Design

Dev Cookies — Thu, 09 Jul 2026 13:23:54 +0000

A Rate Limiter is one of the most common LLD/System Design interview questions asked by companies like Amazon, Uber, PhonePe, Walmart, Microsoft, Google, and Atlassian.

A strong interview solution should demonstrate:

OOP design
SOLID principles
Thread safety
Extensibility
Selection of appropriate algorithms
Clean architecture

Problem Statement

Design a Rate Limiter that:

Limits requests per user/API/IP.
Supports multiple algorithms.
Is thread-safe.
Is easy to extend with new algorithms.
Can be integrated with Spring Boot APIs.

Example:

Allow 5 requests per minute

Request 1 -> Allowed
Request 2 -> Allowed
...
Request 5 -> Allowed
Request 6 -> Rejected

Functional Requirements

Limit requests
Multiple clients
Configurable limits
Different algorithms
Fast lookup
Thread-safe

Non-Functional Requirements

High throughput
Low latency
Extensible
Memory efficient
Distributed-ready

Supported Algorithms

Algorithm	Time	Memory	Interview Frequency
Fixed Window	O(1)	Low	⭐⭐⭐⭐⭐
Sliding Window Log	O(log n)	High	⭐⭐⭐⭐
Sliding Window Counter	O(1)	Medium	⭐⭐⭐⭐⭐
Token Bucket	O(1)	Low	⭐⭐⭐⭐⭐
Leaky Bucket	O(1)	Low	⭐⭐⭐⭐

High-Level Design

        Client
         │
       B ▼
     RateLimiter
         │
         ▼
 RateLimiterStrategy
         │
 ┌──────┼──────────┐
 ▼      ▼            ▼
Fixed  Token      Sliding
Window Bucket      Window

        │
        ▼
Storage
(HashMap / Redis)

Design Patterns

Pattern	Usage
Strategy	Different rate-limiting algorithms
Factory	Create algorithm implementations
Singleton	Configuration/manager (optional)
Dependency Injection	Inject strategy into service
Template Method (optional)	Common workflow

Core Models

Request Context

public class RequestContext {

    private final String clientId;
    private final long timestamp;

    public RequestContext(String clientId) {
        this.clientId = clientId;
        this.timestamp = System.currentTimeMillis();
    }

    public String getClientId() {
        return clientId;
    }

    public long getTimestamp() {
        return timestamp;
    }
}

Strategy Interface

public interface RateLimiterStrategy {

    boolean allow(RequestContext request);

}

Implementation 1: Fixed Window Counter

Idea

Window = 60 seconds

Counter

User A

1
2
3
4
5

Next request

Rejected

After 60 sec

Counter resets

Data Structure

ConcurrentHashMap

Key
↓

UserId

Value

Window Counter

Window Model

class Window {

    long startTime;
    AtomicInteger count;

}

Fixed Window Strategy

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicInteger;

public class FixedWindowRateLimiter implements RateLimiterStrategy {

    private final long windowSizeMillis;
    private final int maxRequests;

    private final ConcurrentHashMap<String, Window> windows =
            new ConcurrentHashMap<>();

    public FixedWindowRateLimiter(int maxRequests,
                                  long windowSizeMillis) {

        this.maxRequests = maxRequests;
        this.windowSizeMillis = windowSizeMillis;
    }

    @Override
    public boolean allow(RequestContext request) {

        Window window = windows.computeIfAbsent(
                request.getClientId(),
                k -> new Window(System.currentTimeMillis()));

        synchronized (window) {

            long current = System.currentTimeMillis();

            if(current - window.startTime >= windowSizeMillis) {

                window.startTime = current;
                window.count.set(0);

            }

            if(window.count.incrementAndGet() <= maxRequests)
                return true;

            return false;

        }

    }

    static class Window {

        long startTime;

        AtomicInteger count = new AtomicInteger();

        Window(long startTime) {
            this.startTime = startTime;
        }

    }

}

Rate Limiter Service

public class RateLimiter {

    private final RateLimiterStrategy strategy;

    public RateLimiter(RateLimiterStrategy strategy) {
        this.strategy = strategy;
    }

    public boolean allow(String clientId) {
        return strategy.allow(new RequestContext(clientId));
    }
}

Client

public class Main {

    public static void main(String[] args) {

        RateLimiter limiter =
                new RateLimiter(
                        new FixedWindowRateLimiter(
                                5,
                                60000));

        for(int i=1;i<=7;i++) {

            System.out.println(
                    limiter.allow("USER-1"));

        }

    }

}

Output:

true
true
true
true
true
false
false

How to Add More Algorithms

Since the design uses the Strategy Pattern, adding a new algorithm is straightforward:

TokenBucketRateLimiter implements RateLimiterStrategy
SlidingWindowRateLimiter implements RateLimiterStrategy
LeakyBucketRateLimiter implements RateLimiterStrategy

No changes are required in the RateLimiter service, satisfying the Open/Closed Principle.

Thread Safety

ConcurrentHashMap for concurrent client access.
AtomicInteger for efficient counter updates.
Synchronization at the per-client window level, avoiding a global lock.
Minimal contention because each client has its own window object.

SOLID Principles

Principle	Application
Single Responsibility	Each strategy implements one algorithm.
Open/Closed	New algorithms can be added without modifying existing code.
Liskov Substitution	Any `RateLimiterStrategy` can be substituted.
Interface Segregation	Small, focused strategy interface.
Dependency Inversion	`RateLimiter` depends on the abstraction, not concrete implementations.

Production Enhancements

For a production-ready distributed rate limiter, consider:

Use Redis with atomic operations (INCR, EXPIRE) or Lua scripts for shared state across instances.
Support configurable limits per API, tenant, or user.
Implement asynchronous cleanup of inactive clients.
Add metrics (allowed, rejected, latency) via Micrometer/Prometheus.
Return Retry-After headers for HTTP 429 responses.
Support burst traffic using the Token Bucket algorithm.
Integrate with API gateways (NGINX, Envoy, Kong, Spring Cloud Gateway).

Common Interview Follow-up Questions

Why use ConcurrentHashMap instead of HashMap?
Why is AtomicInteger used instead of int?
How would you implement a distributed rate limiter?
How do you avoid memory leaks from inactive clients?
Which algorithm handles burst traffic best?
How would you implement rate limiting in Redis?
How would you support different limits for different users or APIs?
How would you expose remaining quota and reset time?
How would you benchmark the implementation under high concurrency?
When would you choose Token Bucket over Sliding Window?

This design is suitable for Java LLD interviews and can be progressively extended into a production-grade, distributed rate-limiting service.

Logger System LLD (Java)

Dev Cookies — Thu, 09 Jul 2026 13:22:02 +0000

Problem Statement

Design a Logger Framework that supports:

Multiple Log Levels
- DEBUG
- INFO
- WARN
- ERROR
- FATAL
Multiple Output Destinations
- Console
- File
- Database
- Kafka (future)
- ElasticSearch (future)
Configurable Minimum Log Level
Thread Safe
Easy to extend

Functional Requirements

Log message
Timestamp
Log Level
Destination
Format message

Non Functional Requirements

Extensible
Low Coupling
High Cohesion
Open Closed Principle
Thread Safe
Singleton Logger

Interview Expectation

Application
      │
      ▼
 Logger (Singleton)
      │
      ▼
 LogManager
      │
      ▼
Formatter
      │
      ▼
Appender
 ├── ConsoleAppender
 ├── FileAppender
 ├── DatabaseAppender

Design Patterns Used

Pattern	Why
Singleton	One Logger instance
Strategy	Different Appenders
Factory	Create appenders
Builder	Build LogMessage
Chain of Responsibility (Optional)	Multiple appenders
Dependency Injection	Loose coupling

Step 1: Log Level

public enum LogLevel {

    DEBUG(1),
    INFO(2),
    WARN(3),
    ERROR(4),
    FATAL(5);

    private final int priority;

    LogLevel(int priority) {
        this.priority = priority;
    }

    public int getPriority() {
        return priority;
    }
}

Step 2: Log Message

import java.time.LocalDateTime;

public class LogMessage {

    private final LogLevel level;
    private final String message;
    private final LocalDateTime timestamp;

    public LogMessage(LogLevel level, String message) {
        this.level = level;
        this.message = message;
        this.timestamp = LocalDateTime.now();
    }

    public LogLevel getLevel() {
        return level;
    }

    public String getMessage() {
        return message;
    }

    public LocalDateTime getTimestamp() {
        return timestamp;
    }
}

Step 3: Formatter

public interface LogFormatter {

    String format(LogMessage message);

}

Default Formatter

public class DefaultFormatter implements LogFormatter {

    @Override
    public String format(LogMessage message) {

        return String.format(
                "[%s] [%s] %s",
                message.getTimestamp(),
                message.getLevel(),
                message.getMessage());

    }

}

Step 4: Appender

public interface Appender {

    void append(LogMessage message);

}

Console Appender

public class ConsoleAppender implements Appender {

    private final LogFormatter formatter;

    public ConsoleAppender(LogFormatter formatter) {
        this.formatter = formatter;
    }

    @Override
    public void append(LogMessage message) {
        System.out.println(formatter.format(message));
    }
}

File Appender

import java.io.FileWriter;
import java.io.IOException;

public class FileAppender implements Appender {

    private final LogFormatter formatter;

    public FileAppender(LogFormatter formatter) {
        this.formatter = formatter;
    }

    @Override
    public void append(LogMessage message) {

        try(FileWriter writer = new FileWriter("app.log", true)) {

            writer.write(formatter.format(message));
            writer.write("\n");

        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}

Step 5: Logger

import java.util.List;

public class Logger {

    private static volatile Logger instance;

    private final List<Appender> appenders;

    private LogLevel minimumLevel;

    private Logger(List<Appender> appenders,
                   LogLevel minimumLevel) {

        this.appenders = appenders;
        this.minimumLevel = minimumLevel;
    }

    public static Logger getInstance(List<Appender> appenders,
                                     LogLevel level) {

        if (instance == null) {

            synchronized (Logger.class) {

                if (instance == null) {

                    instance = new Logger(appenders, level);

                }

            }

        }

        return instance;
    }

    public void log(LogLevel level,
                    String message) {

        if(level.getPriority() < minimumLevel.getPriority())
            return;

        LogMessage logMessage =
                new LogMessage(level, message);

        for(Appender appender : appenders)
            appender.append(logMessage);

    }

}

Client

import java.util.List;

public class Main {

    public static void main(String[] args) {

        LogFormatter formatter =
                new DefaultFormatter();

        Appender console =
                new ConsoleAppender(formatter);

        Appender file =
                new FileAppender(formatter);

        Logger logger =
                Logger.getInstance(
                        List.of(console, file),
                        LogLevel.INFO);

        logger.log(LogLevel.INFO,
                "Application Started");

        logger.log(LogLevel.DEBUG,
                "Debug Message");

        logger.log(LogLevel.ERROR,
                "Database Down");

    }

}

Output

[2026-07-09T10:30] [INFO] Application Started

[2026-07-09T10:31] [ERROR] Database Down

(DEBUG ignored)

UML

                    +------------------+
                    |      Logger      |
                    +------------------+
                    | minimumLevel     |
                    | appenders        |
                    +------------------+
                          |
          -------------------------------
          |                             |
          ▼                             ▼
 +----------------+             +----------------+
 |   Appender     |             | LogFormatter   |
 +----------------+             +----------------+
 | append()       |             | format()       |
 +----------------+             +----------------+
      ▲
      │
-----------------------------
|             |             |
▼             ▼             ▼
Console    File       Database
Appender    Appender    Appender

                ▲
                |
          +--------------+
          | LogMessage   |
          +--------------+
          | level        |
          | timestamp    |
          | message      |
          +--------------+

SOLID Principles

Principle	Application
SRP	`LogMessage`, `Appender`, `Formatter`, `Logger` each have a single responsibility.
OCP	Add new appenders or formatters without modifying existing classes.
LSP	Any `Appender` implementation can replace another.
ISP	Small focused interfaces (`Appender`, `LogFormatter`).
DIP	`Logger` depends on abstractions rather than concrete implementations.

Common Interview Follow-up Questions

How would you support asynchronous logging?

Introduce a BlockingQueue<LogMessage> and a dedicated worker thread or thread pool that consumes log events and dispatches them to appenders.

How would you prevent logging from blocking application threads?

Use non-blocking queues, batching, and asynchronous appenders with configurable backpressure policies.

How would you support log rotation?

Create a RollingFileAppender that rotates files based on size or time (daily/hourly) and manages retention.

How would you support multiple log formats?

Implement additional LogFormatter strategies such as JsonFormatter, XmlFormatter, or custom templates.

How would you enable configuration from a properties or YAML file?

Build a LoggerConfiguration component and an AppenderFactory to instantiate appenders based on external configuration.

How would you make the logger thread-safe?

Keep shared state immutable where possible, use thread-safe collections if appenders are modified at runtime, and ensure appenders handle concurrent writes correctly.

How would you add contextual information (e.g., request ID, user ID)?

Introduce a Mapped Diagnostic Context (MDC) using ThreadLocal to automatically enrich each LogMessage.

How would you support filtering?

Add a LogFilter abstraction (Strategy pattern) to filter messages by package, marker, or custom predicates before dispatching.

Possible Extensions

AsyncLogger
RollingFileAppender
DatabaseAppender
KafkaAppender
ElasticSearchAppender
JsonFormatter
XMLFormatter
LoggerFactory
LoggerConfiguration
LogFilter
MDC (Mapped Diagnostic Context)
Rate limiting and sampling
Dynamic log level updates
Metrics for dropped/processed log events

This design demonstrates strong OOP fundamentals, SOLID principles, and extensibility while remaining concise enough to explain in a typical 30–45 minute LLD interview.

Functional Programming in Java — Complete Guide for Modern Backend Engineers

Dev Cookies — Wed, 27 May 2026 16:22:10 +0000

Functional Programming (FP) in Java became mainstream after Java 8 and transformed how we write collections processing, asynchronous workflows, APIs, and clean business logic.

This guide covers:

Functional Programming basics
Functional Interfaces
Lambda Expressions
Method References
Stream API
Optional
Built-in Functional Interfaces
Functional Composition
Parallel Streams
Best Practices
Performance Considerations
Interview Questions
Real-world backend examples

1. What is Functional Programming?

Functional Programming is a programming paradigm where:

Functions are treated as first-class citizens
Data is immutable whenever possible
Side effects are minimized
Declarative style is preferred over imperative style

Instead of:

List<String> result = new ArrayList<>();

for (String name : names) {
    if (name.startsWith("A")) {
        result.add(name.toUpperCase());
    }
}

We write:

List<String> result = names.stream()
        .filter(name -> name.startsWith("A"))
        .map(String::toUpperCase)
        .toList();

2. Why Functional Programming?

Advantages

Cleaner code
Less boilerplate
Easier parallelism
Better readability
Easier testing
Declarative programming
Better collection processing

3. Functional Interface

A Functional Interface contains exactly one abstract method.

Java provides:

@FunctionalInterface

annotation.

Example

@FunctionalInterface
interface Calculator {
    int operate(int a, int b);
}

Usage:

public class Main {

    public static void main(String[] args) {

        Calculator add = (a, b) -> a + b;

        System.out.println(add.operate(10, 20));
    }
}

Output:

4. Lambda Expressions

Lambda expression provides implementation of functional interfaces.

Syntax

(parameters) -> expression

(parameters) -> {
    statements
}

Examples

No Parameter

Runnable task = () -> System.out.println("Running");

Single Parameter

Consumer<String> printer = name -> System.out.println(name);

Multiple Parameters

BinaryOperator<Integer> sum = (a, b) -> a + b;

5. Built-in Functional Interfaces

Package:

java.util.function

5.1 Predicate

Used for conditions.

Predicate<Integer> isEven = num -> num % 2 == 0;

System.out.println(isEven.test(10));

Output:

true

Combining Predicates

Predicate<Integer> greaterThan10 = n -> n > 10;
Predicate<Integer> even = n -> n % 2 == 0;

Predicate<Integer> combined =
        greaterThan10.and(even);

System.out.println(combined.test(20));

5.2 Function

Transforms input to output.

Function<String, Integer> length = str -> str.length();

System.out.println(length.apply("Java"));

Function Chaining

Function<Integer, Integer> multiply = x -> x * 2;
Function<Integer, Integer> square = x -> x * x;

Function<Integer, Integer> result =
        multiply.andThen(square);

System.out.println(result.apply(5));

Steps:

5 * 2 = 10
10 * 10 = 100

5.3 Consumer

Consumes input without returning value.

Consumer<String> print = msg -> System.out.println(msg);

print.accept("Hello");

5.4 Supplier

Produces value.

Supplier<Double> random = () -> Math.random();

System.out.println(random.get());

5.5 UnaryOperator

Input and output same type.

UnaryOperator<Integer> square = x -> x * x;

System.out.println(square.apply(5));

5.6 BinaryOperator

Two inputs same type → one output same type.

BinaryOperator<Integer> add = (a, b) -> a + b;

System.out.println(add.apply(10, 20));

6. Method References

Cleaner alternative to lambda.

Types

Type	Example
Static Method	`Math::abs`
Instance Method	`String::toUpperCase`
Constructor	`ArrayList::new`

Example

List<String> names = List.of("john", "alice");

names.stream()
        .map(String::toUpperCase)
        .forEach(System.out::println);

7. Stream API

Stream API is the heart of Functional Programming in Java.

Streams process data declaratively.

Stream Pipeline

Source → Intermediate Operations → Terminal Operation

Example

List<Integer> nums = List.of(1,2,3,4,5);

nums.stream()
        .filter(n -> n % 2 == 0)
        .map(n -> n * n)
        .forEach(System.out::println);

Output:

4
16

8. Intermediate Operations

These are lazy operations.

filter()

List<String> names = List.of("John", "Adam", "Alex");

names.stream()
        .filter(name -> name.startsWith("A"))
        .forEach(System.out::println);

map()

Transforms data.

List<String> names = List.of("john", "alex");

names.stream()
        .map(String::toUpperCase)
        .forEach(System.out::println);

sorted()

List<Integer> nums = List.of(5,1,9,2);

nums.stream()
        .sorted()
        .forEach(System.out::println);

distinct()

List<Integer> nums = List.of(1,1,2,2,3);

nums.stream()
        .distinct()
        .forEach(System.out::println);

limit()

Stream.iterate(1, n -> n + 1)
        .limit(5)
        .forEach(System.out::println);

skip()

List<Integer> nums = List.of(1,2,3,4,5);

nums.stream()
        .skip(2)
        .forEach(System.out::println);

flatMap()

Very important for nested collections.

List<List<String>> data = List.of(
        List.of("A", "B"),
        List.of("C", "D")
);

data.stream()
        .flatMap(List::stream)
        .forEach(System.out::println);

Output:

A
B
C
D

9. Terminal Operations

collect()

List<String> result = names.stream()
        .map(String::toUpperCase)
        .collect(Collectors.toList());

reduce()

Aggregation.

List<Integer> nums = List.of(1,2,3,4);

int sum = nums.stream()
        .reduce(0, Integer::sum);

System.out.println(sum);

count()

long count = nums.stream()
        .filter(n -> n % 2 == 0)
        .count();

anyMatch()

boolean exists = nums.stream()
        .anyMatch(n -> n > 10);

allMatch()

boolean allEven = nums.stream()
        .allMatch(n -> n % 2 == 0);

findFirst()

Optional<Integer> first =
        nums.stream().findFirst();

10. Collectors

groupingBy()

Map<String, List<String>> grouped =
        names.stream()
                .collect(Collectors.groupingBy(
                        name -> name.substring(0,1)
                ));

counting()

Map<String, Long> countMap =
        names.stream()
                .collect(Collectors.groupingBy(
                        name -> name,
                        Collectors.counting()
                ));

partitioningBy()

Map<Boolean, List<Integer>> result =
        nums.stream()
                .collect(Collectors.partitioningBy(
                        n -> n % 2 == 0
                ));

joining()

String joined = names.stream()
        .collect(Collectors.joining(", "));

11. Optional

Optional avoids NullPointerException.

Creating Optional

Optional<String> name =
        Optional.of("Java");

Optional<String> empty =
        Optional.empty();

Common Methods

isPresent()

if(name.isPresent()) {
    System.out.println(name.get());
}

orElse()

String value =
        name.orElse("Default");

orElseGet()

String value =
        name.orElseGet(() -> "Generated");

map()

Optional<String> upper =
        name.map(String::toUpperCase);

Best Practice

Avoid:

if(optional.isPresent()) {
    return optional.get();
}

Prefer:

return optional.orElse("default");

12. Stream Lazy Evaluation

Intermediate operations execute only when terminal operation is called.

Example

Stream.of(1,2,3)
        .filter(n -> {
            System.out.println("Filtering");
            return n > 1;
        });

Nothing executes because no terminal operation exists.

Add Terminal Operation

Stream.of(1,2,3)
        .filter(n -> {
            System.out.println("Filtering");
            return n > 1;
        })
        .count();

Now execution happens.

13. Parallel Streams

Used for parallel data processing.

Example

List<Integer> nums =
        IntStream.rangeClosed(1, 100)
                .boxed()
                .toList();

nums.parallelStream()
        .map(n -> n * 2)
        .forEach(System.out::println);

When to Use Parallel Streams

Use when:

CPU intensive tasks
Large datasets
Stateless operations
Independent computations

Avoid when:

Shared mutable state
IO operations
Small datasets

14. Functional Composition

Combining functions together.

Example

Function<Integer, Integer> multiply = x -> x * 2;
Function<Integer, Integer> add = x -> x + 3;

Function<Integer, Integer> combined =
        multiply.andThen(add);

System.out.println(combined.apply(5));

Output:

compose()

Function<Integer, Integer> composed =
        multiply.compose(add);

System.out.println(composed.apply(5));

Execution:

(5 + 3) * 2 = 16

15. Real Backend Examples

Filtering Employees

class Employee {
    String name;
    int salary;

    public Employee(String name, int salary) {
        this.name = name;
        this.salary = salary;
    }

    public int getSalary() {
        return salary;
    }

    public String getName() {
        return name;
    }
}

List<Employee> employees = List.of(
        new Employee("John", 50000),
        new Employee("Alex", 90000),
        new Employee("David", 70000)
);

List<String> highPaid =
        employees.stream()
                .filter(e -> e.getSalary() > 60000)
                .map(Employee::getName)
                .toList();

System.out.println(highPaid);

Grouping Transactions

Map<String, List<Transaction>> grouped =
        transactions.stream()
                .collect(Collectors.groupingBy(
                        Transaction::getStatus
                ));

Counting Frequencies

Map<String, Long> freq =
        words.stream()
                .collect(Collectors.groupingBy(
                        Function.identity(),
                        Collectors.counting()
                ));

16. Common Stream Interview Problems

Find Duplicate Elements

Set<Integer> seen = new HashSet<>();

List<Integer> duplicates =
        nums.stream()
                .filter(n -> !seen.add(n))
                .toList();

Frequency Map

Map<String, Long> map =
        names.stream()
                .collect(Collectors.groupingBy(
                        Function.identity(),
                        Collectors.counting()
                ));

Find Second Highest Number

int secondHighest =
        nums.stream()
                .distinct()
                .sorted(Comparator.reverseOrder())
                .skip(1)
                .findFirst()
                .orElseThrow();

Convert List to Map

Map<Integer, String> map =
        employees.stream()
                .collect(Collectors.toMap(
                        Employee::getId,
                        Employee::getName
                ));

17. Common Mistakes

Using Streams for Everything

Bad:

stream.forEach(list::add);

Prefer direct collection.

Shared Mutable State

Bad:

List<Integer> result = new ArrayList<>();

nums.parallelStream()
        .forEach(result::add);

Unsafe.

Reusing Streams

Bad:

Stream<Integer> stream = nums.stream();

stream.count();
stream.forEach(System.out::println);

Throws exception.

18. Performance Considerations

Streams vs Loops

Loops may be faster for:

Tight CPU loops
Primitive-heavy operations

Streams are better for:

Readability
Declarative logic
Complex transformations
Parallelism

Primitive Streams

Avoid boxing overhead.

Use:

IntStream
LongStream
DoubleStream

Example:

int sum = IntStream.rangeClosed(1, 100)
        .sum();

19. Best Practices

Prefer Immutability

Good:

List<String> result =
        names.stream().toList();

Keep Lambdas Small

Bad:

.filter(x -> {
    // 30 lines
})

Extract methods instead.

Use Method References

Prefer:

String::toUpperCase

over:

s -> s.toUpperCase()

Avoid Side Effects

Bad:

stream.forEach(db::save);

20. Advanced Stream Operations

teeing()

Java 12+

var result = nums.stream()
        .collect(Collectors.teeing(
                Collectors.minBy(Integer::compare),
                Collectors.maxBy(Integer::compare),
                (min, max) -> Map.of(
                        "min", min.get(),
                        "max", max.get()
                )
        ));

takeWhile()

List<Integer> result =
        List.of(1,2,3,4,1,2)
                .stream()
                .takeWhile(n -> n < 4)
                .toList();

dropWhile()

List<Integer> result =
        List.of(1,2,3,4,1,2)
                .stream()
                .dropWhile(n -> n < 4)
                .toList();

21. Functional Programming + CompletableFuture

Very powerful in backend systems.

CompletableFuture.supplyAsync(() -> fetchUser())
        .thenApply(User::getName)
        .thenAccept(System.out::println);

22. Functional Style Error Handling

Traditional

try {
    process();
} catch (Exception e) {
    handle(e);
}

Functional Style

Optional.ofNullable(data)
        .map(this::transform)
        .ifPresent(System.out::println);

23. Important Interview Questions

Theory Questions

What is Functional Programming?
What is a Functional Interface?
Difference between map and flatMap?
Difference between intermediate and terminal operations?
What is lazy evaluation?
What is method reference?
Difference between Predicate and Function?
What is Optional?
What are Parallel Streams?
Difference between forEach and peek?

Coding Questions

Find duplicates using streams
Frequency map
Group anagrams
Second highest salary
Flatten nested lists
Partition odd/even
Top K frequent elements
Employee grouping
Stream API transformations

24. Summary

Functional Programming in Java enables:

Declarative coding
Cleaner transformations
Better readability
Easier concurrency
Powerful collection processing

Core pillars:

Functional Interfaces
Lambdas
Method References
Stream API
Optional
Functional Composition

Modern Java backend development heavily relies on these concepts in:

Spring Boot
Reactive Programming
Microservices
Data Pipelines
Async Processing
Event-driven systems

Mastering Functional Programming significantly improves code quality and interview performance.

Unbounded Knapsack Pattern — Complete Interview Guide

Dev Cookies — Thu, 21 May 2026 13:51:50 +0000

The Unbounded Knapsack pattern is one of the most important Dynamic Programming patterns asked in coding interviews.

Unlike 0/1 Knapsack, here you can use an item multiple times.

This pattern appears in:

Coin Change
Rod Cutting
Integer Break
Minimum Coins
Ribbon Cutting
Perfect Squares
Combination Sum
Target Sum Variations

1. What is Unbounded Knapsack?

You are given:

weights[]
values[]
a bag capacity W

You may take an item:

0 times
1 time
multiple times

Goal:
Maximize total profit/value.

2. Difference Between 0/1 and Unbounded Knapsack

Feature	0/1 Knapsack	Unbounded Knapsack
Pick item once	✅	❌
Pick item multiple times	❌	✅
DP transition	`dp[i-1]`	`dp[i]`
Common use	Subset problems	Coin/Rod problems

3. Core Recurrence

For item i:

If we take it:

value[i] + solve(i, remainingWeight - weight[i])

Notice:

solve(i, ...)

NOT:

solve(i + 1, ...)

Because we can reuse the same item.

4. Generic Recursive Template

class Solution {

    public int knapsack(int[] wt, int[] val, int capacity) {
        return dfs(0, capacity, wt, val);
    }

    private int dfs(int index, int remaining,
                    int[] wt, int[] val) {

        if (index == wt.length || remaining == 0) {
            return 0;
        }

        int skip = dfs(index + 1, remaining, wt, val);

        int take = 0;

        if (wt[index] <= remaining) {
            take = val[index] +
                    dfs(index,
                        remaining - wt[index],
                        wt, val);
        }

        return Math.max(skip, take);
    }
}

Time Complexity:

O(2^N)

5. Memoization (Top-Down DP)

class Solution {

    Integer[][] dp;

    public int knapsack(int[] wt, int[] val, int capacity) {

        dp = new Integer[wt.length][capacity + 1];

        return dfs(0, capacity, wt, val);
    }

    private int dfs(int index,
                    int remaining,
                    int[] wt,
                    int[] val) {

        if (index == wt.length || remaining == 0) {
            return 0;
        }

        if (dp[index][remaining] != null) {
            return dp[index][remaining];
        }

        int skip = dfs(index + 1, remaining, wt, val);

        int take = 0;

        if (wt[index] <= remaining) {
            take = val[index] +
                    dfs(index,
                        remaining - wt[index],
                        wt, val);
        }

        return dp[index][remaining] =
                Math.max(skip, take);
    }
}

Complexity:

Time: O(N * W)
Space: O(N * W)

6. Bottom-Up DP

State

dp[i][w]
= max profit using first i items
with capacity w

Transition

If we take current item again:

take = value[i-1] + dp[i][w - weight[i-1]]

Notice:

dp[i]

not:

dp[i-1]

Code

class Solution {

    public int unboundedKnapsack(int[] wt,
                                 int[] val,
                                 int capacity) {

        int n = wt.length;

        int[][] dp = new int[n + 1][capacity + 1];

        for (int i = 1; i <= n; i++) {

            for (int w = 0; w <= capacity; w++) {

                int skip = dp[i - 1][w];

                int take = 0;

                if (wt[i - 1] <= w) {
                    take = val[i - 1]
                            + dp[i][w - wt[i - 1]];
                }

                dp[i][w] = Math.max(skip, take);
            }
        }

        return dp[n][capacity];
    }
}

7. Space Optimized DP

class Solution {

    public int unboundedKnapsack(int[] wt,
                                 int[] val,
                                 int capacity) {

        int[] dp = new int[capacity + 1];

        for (int i = 0; i < wt.length; i++) {

            for (int w = wt[i];
                 w <= capacity;
                 w++) {

                dp[w] = Math.max(
                        dp[w],
                        val[i] + dp[w - wt[i]]
                );
            }
        }

        return dp[capacity];
    }
}

Complexity:

Time: O(N * W)
Space: O(W)

8. How to Identify Unbounded Knapsack

Look for these clues:

Keywords

unlimited supply
infinite transactions
can reuse
multiple times
any number of times

Common Structures

maximize/minimize
combinations
count ways
repeated selection

9. Most Important Variations

A. Coin Change I (Minimum Coins)

Problem

Minimum coins needed to make amount.

Transition

dp[amount] =
1 + dp[amount - coin]

Code

class Solution {

    public int coinChange(int[] coins, int amount) {

        int[] dp = new int[amount + 1];

        Arrays.fill(dp, amount + 1);

        dp[0] = 0;

        for (int coin : coins) {

            for (int a = coin;
                 a <= amount;
                 a++) {

                dp[a] = Math.min(
                        dp[a],
                        1 + dp[a - coin]
                );
            }
        }

        return dp[amount] > amount
                ? -1
                : dp[amount];
    }
}

B. Coin Change II (Count Combinations)

Problem

Count total ways to form amount.

Code

class Solution {

    public int change(int amount, int[] coins) {

        int[] dp = new int[amount + 1];

        dp[0] = 1;

        for (int coin : coins) {

            for (int a = coin;
                 a <= amount;
                 a++) {

                dp[a] += dp[a - coin];
            }
        }

        return dp[amount];
    }
}

C. Rod Cutting Problem

Idea

Cut rod into pieces to maximize profit.

Mapping

Rod Cutting	Knapsack
rod length	capacity
piece size	weight
piece profit	value

Code

class Solution {

    public int cutRod(int[] price, int n) {

        int[] dp = new int[n + 1];

        for (int len = 1; len <= n; len++) {

            for (int cut = 1;
                 cut <= len;
                 cut++) {

                dp[len] = Math.max(
                        dp[len],
                        price[cut - 1]
                                + dp[len - cut]
                );
            }
        }

        return dp[n];
    }
}

D. Integer Break

Problem

Break integer into parts for maximum product.

Code

class Solution {

    public int integerBreak(int n) {

        int[] dp = new int[n + 1];

        dp[1] = 1;

        for (int num = 2; num <= n; num++) {

            for (int cut = 1; cut < num; cut++) {

                dp[num] = Math.max(
                        dp[num],
                        Math.max(
                                cut * (num - cut),
                                cut * dp[num - cut]
                        )
                );
            }
        }

        return dp[n];
    }
}

E. Perfect Squares

Problem

Minimum perfect squares summing to n.

Code

class Solution {

    public int numSquares(int n) {

        int[] dp = new int[n + 1];

        Arrays.fill(dp, Integer.MAX_VALUE);

        dp[0] = 0;

        for (int i = 1; i * i <= n; i++) {

            int square = i * i;

            for (int j = square;
                 j <= n;
                 j++) {

                dp[j] = Math.min(
                        dp[j],
                        1 + dp[j - square]
                );
            }
        }

        return dp[n];
    }
}

F. Maximum Ribbon Cut

Problem

Maximum pieces from ribbon lengths.

Code

class Solution {

    public int maxCuts(int[] ribbonLengths,
                       int total) {

        int[] dp = new int[total + 1];

        Arrays.fill(dp, -1);

        dp[0] = 0;

        for (int ribbon : ribbonLengths) {

            for (int len = ribbon;
                 len <= total;
                 len++) {

                if (dp[len - ribbon] != -1) {

                    dp[len] = Math.max(
                            dp[len],
                            1 + dp[len - ribbon]
                    );
                }
            }
        }

        return dp[total];
    }
}

10. Pattern Recognition Cheat Sheet

Problem Type	Goal
Maximum profit	Use `Math.max`
Minimum coins	Use `Math.min`
Count ways	Use addition
Exact fill	Use INF or -1
Reuse allowed	Unbounded

11. Important DP Loop Direction

Unbounded Knapsack

for (int w = weight;
     w <= capacity;
     w++)

FORWARD traversal.

0/1 Knapsack

for (int w = capacity;
     w >= weight;
     w--)

BACKWARD traversal.

12. Top Interview Questions

Beginner

Coin Change
Coin Change II
Rod Cutting
Integer Break
Perfect Squares

Medium

Combination Sum IV
Maximum Ribbon Cut
Minimum Cost for Tickets
Dice Roll Sum
Target Sum Variants

Advanced

Cutting Segments
Burst Balloons (DP interval relation)
Partition Array for Maximum Sum
Cherry Pickup variations
Unbounded Subsequence DP

13. Master Template

for (item : items) {

    for (capacity from itemWeight -> maxCapacity) {

        dp[capacity] =
                operation(
                        dp[capacity],
                        currentValue +
                        dp[capacity - itemWeight]
                );
    }
}

14. Common Mistakes

1. Using backward traversal

Wrong for unbounded problems.

2. Using `dp[i-1]`

Should often use:

dp[i]

because item reuse is allowed.

3. Confusing combinations vs permutations

Combination

coin outer loop
amount inner loop

Permutation

amount outer loop
coin inner loop

15. Interview Strategy

When you see:

infinite supply
reuse allowed
minimum coins
rod cutting
count ways repeatedly

Think:

UNBOUNDED KNAPSACK

Then decide:

Goal	Operation
maximize	max
minimize	min
count ways	+

16. Final Revision Notes

Core Formula

dp[w] = \max(dp[w],\ value[i] + dp[w-weight[i]])

Loop Order

for item
    for capacity increasing

Complexity

Approach	Time	Space
Recursion	Exponential	O(N)
Memoization	O(NW)	O(NW)
Tabulation	O(NW)	O(NW)
Optimized	O(NW)	O(W)

17. Best Problems to Practice

Problem	Platform
Coin Change	LeetCode 322
Coin Change II	LeetCode 518
Rod Cutting	GFG
Integer Break	LeetCode 343
Perfect Squares	LeetCode 279
Combination Sum IV	LeetCode 377
Minimum Cost Tickets	LeetCode 983
Maximum Ribbon Cut	Educative/GFG

Backtracking for Coding Interviews: Combination vs Permutation (with Top Problems)

Dev Cookies — Sat, 14 Mar 2026 10:19:46 +0000

Backtracking is one of the most important patterns for coding interviews. Many problems on platforms like LeetCode revolve around generating combinations, permutations, subsets, and solving constraint problems.

Understanding when to use combinations vs permutations is the key to solving these problems quickly.

1. Combination vs Permutation

Before writing code, the first question you should ask is:

Does order matter?

Combination

In combinations:

Order does NOT matter

Example:

[1,2] == [2,1]

Both represent the same combination.

Mathematical Formula

Code Logic

We avoid duplicates by moving the index forward.

void combination(int start, List<Integer> path){

    result.add(new ArrayList<>(path));

    for(int i=start;i<n;i++){

        path.add(nums[i]);

        combination(i+1,path);

        path.remove(path.size()-1);
    }
}

Key Logic

Next recursion → i + 1

Because previous elements should not be reused before the current index.

Permutation

In permutations:

Order matters

Example:

[1,2] ≠ [2,1]

Both are different permutations.

Mathematical Formula

Code Logic

We must track which elements are already used.

void permutation(List<Integer> path, boolean[] used){

    if(path.size()==n){
        result.add(new ArrayList<>(path));
        return;
    }

    for(int i=0;i<n;i++){

        if(used[i]) continue;

        used[i]=true;
        path.add(nums[i]);

        permutation(path,used);

        path.remove(path.size()-1);
        used[i]=false;
    }
}

Key Logic

Loop from 0 → n
Track visited elements

Quick Comparison

Feature	Combination	Permutation
Order matters	No	Yes
Index movement	i+1	always 0→n
Visited array	Not needed	Needed
Duplicates avoided	index movement	visited array

2. Core Backtracking Principle

Every backtracking solution follows this pattern:

choose
explore
unchoose

Code structure:

path.add(x);

dfs(...);

path.remove(path.size()-1);

3. Most Important Backtracking Patterns

Backtracking problems can usually be classified into 5 templates.

Pattern 1: Subsets (Pick / Not Pick)

Used when every element has two choices.

include
exclude

Template:

void dfs(int i,List<Integer> path){

    if(i==n){
        ans.add(new ArrayList<>(path));
        return;
    }

    path.add(nums[i]);
    dfs(i+1,path);

    path.remove(path.size()-1);

    dfs(i+1,path);
}

Top problems:

Subsets
Subsets II

Pattern 2: Combination

Used when selecting elements without caring about order.

Template:

for(int i=start;i<n;i++){

    path.add(nums[i]);

    dfs(i+1,path);

    path.remove(path.size()-1);
}

Top problems:

Combinations
Combination Sum
Combination Sum II

Pattern 3: Permutations

Used when order matters.

Template:

for(int i=0;i<n;i++){

    if(used[i]) continue;

    used[i]=true;

    path.add(nums[i]);

    dfs(path,used);

    path.remove(path.size()-1);

    used[i]=false;
}

Top problems:

Permutations
Permutations II

Pattern 4: Combination Sum (Reuse Allowed)

Some problems allow reusing elements multiple times.

Template:

path.add(nums[i]);

dfs(i,target-nums[i],path);

path.remove(path.size()-1);

dfs(i+1,target,path);

Top problems:

Combination Sum
Combination Sum III

Pattern 5: Constraint Placement

Used in grid or board problems.

Examples include:

N-Queens
Sudoku Solver
Word Search

Template:

for(each possible choice){

    if(valid){

        place choice

        dfs()

        remove choice
    }
}

4. Most Asked Backtracking Problems (Interview List)

These appear frequently in FAANG and product-based interviews.

Easy

Subsets
Permutations

Medium

Combination Sum
Letter Combinations of a Phone Number
Palindrome Partitioning

Hard

N-Queens
Sudoku Solver

5. Complexity of Backtracking

Most backtracking algorithms are exponential.

Typical complexity:

O(2^n)
O(n!)

Examples:

Subsets → 2^n
Permutations → n!

Final Mental Model

When solving a recursion problem, ask these three questions:

1. Does order matter?
2. Can elements repeat?
3. Are there constraints?

Mapping:

Order matters → Permutation
Order doesn't matter → Combination
Reuse allowed → Combination Sum
Grid constraint → Placement

Building Modern Data Systems: Event-Driven Architecture, Messaging Queues, Batch Processing, ETL & ELT

Dev Cookies — Tue, 07 Oct 2025 16:06:11 +0000

A senior engineer's guide to designing scalable, resilient data platforms

🎯 Introduction: The Modern Data Platform Challenge

In today's data-driven world, building systems that can handle real-time transactions, process massive data volumes, and deliver actionable insights isn't just a nice-to-have—it's table stakes. Whether you're architecting a fintech platform processing millions of transactions daily, an e-commerce system tracking user behavior, or a logistics network coordinating shipments, you need an architecture that can scale horizontally, recover from failures gracefully, and evolve without requiring a complete rewrite.

This article walks through the architecture of a modern data platform, explaining how Event-Driven Architecture (EDA), messaging queues, batch processing, ETL, and ELT work together to create a system that's both operationally robust and analytically powerful. We'll use a fintech transaction processing platform as our reference implementation—a domain where data integrity, real-time processing, and regulatory compliance aren't optional.

By the end, you'll understand not just what these components do individually, but how they integrate to solve real engineering problems at scale.

🏗️ The Foundation: Event-Driven Architecture (EDA)

What Is EDA and Why Does It Matter?

Event-Driven Architecture is a design paradigm where system components communicate by producing and consuming events—immutable facts about state changes. Unlike request-response patterns where services wait for answers, EDA enables asynchronous, decoupled communication.

Core Principles:

Events are facts, not commands: An event like TransactionCompleted describes what happened, not what should happen next
Temporal decoupling: Producers and consumers don't need to be online simultaneously
Spatial decoupling: Services don't need to know about each other's existence
Immutability: Events represent historical facts that cannot be changed

Real-World Benefits in Fintech

In a transaction processing system, EDA solves several critical problems:

Scalability: When a payment service processes a transaction, it emits an event and moves on. Downstream services (fraud detection, accounting, notifications) consume at their own pace.
Resilience: If the notification service is down, events queue up and get processed when it recovers. No transactions are lost.
Auditability: Every state change is captured as an immutable event, creating a complete audit trail—essential for regulatory compliance.
Flexibility: Adding new consumers (e.g., a new ML-based fraud detection model) doesn't require changing existing services.

Sample Event Structure

{
  "eventId": "evt_7x9k2m4n",
  "eventType": "transaction.completed",
  "timestamp": "2025-10-07T14:32:15.234Z",
  "version": "1.0",
  "data": {
    "transactionId": "txn_abc123",
    "accountId": "acc_xyz789",
    "amount": 1250.00,
    "currency": "USD",
    "merchantId": "mch_def456",
    "paymentMethod": "credit_card",
    "status": "completed",
    "metadata": {
      "ipAddress": "203.0.113.42",
      "deviceId": "dev_mobile_001",
      "location": "US-CA-SF"
    }
  }
}

This structure includes everything downstream consumers need while remaining self-contained and versioned for schema evolution.

📮 The Nervous System: Messaging Queues

Kafka: The Event Backbone

While there are many messaging systems (RabbitMQ, AWS SQS, Google Pub/Sub), Apache Kafka has become the de facto standard for event-driven architectures at scale. Here's why:

Key Characteristics:

Distributed commit log: Events are persisted to disk, not just held in memory
High throughput: Handles millions of messages per second with horizontal scaling
Replay capability: Consumers can rewind and reprocess events from any point
Ordering guarantees: Within a partition, events maintain strict ordering
Durability: Configurable replication ensures no data loss

Topic Design in Practice

In our fintech platform, we organize events into topics based on bounded contexts:

transactions.raw          → All transaction events (unvalidated)
transactions.validated    → Validated, enriched transactions
transactions.failed       → Failed transactions for retry/investigation
payments.completed        → Successful payment confirmations
fraud.alerts              → Suspicious activity detected
accounting.journal        → Double-entry bookkeeping events

Partitioning Strategy:

Partition Key: accountId
Purpose: Ensures all events for an account go to same partition
Benefit: Maintains ordering per account, enables parallel processing

Producer Pattern

@Service
public class TransactionEventProducer {
    private final KafkaTemplate<String, TransactionEvent> kafkaTemplate;

    public void publishTransaction(Transaction txn) {
        TransactionEvent event = TransactionEvent.builder()
            .eventId(UUID.randomUUID().toString())
            .eventType("transaction.completed")
            .timestamp(Instant.now())
            .data(txn)
            .build();

        // Partition by accountId for ordering
        kafkaTemplate.send(
            "transactions.raw",
            txn.getAccountId(),
            event
        ).addCallback(
            success -> log.info("Event published: {}", event.getEventId()),
            failure -> handlePublishFailure(event, failure)
        );
    }
}

Consumer Pattern

@Service
public class FraudDetectionConsumer {

    @KafkaListener(
        topics = "transactions.validated",
        groupId = "fraud-detection-service"
    )
    public void processTransaction(
        @Payload TransactionEvent event,
        @Header(KafkaHeaders.RECEIVED_PARTITION_ID) int partition,
        @Header(KafkaHeaders.OFFSET) long offset
    ) {
        try {
            FraudScore score = fraudEngine.analyze(event.getData());

            if (score.isHighRisk()) {
                publishFraudAlert(event, score);
            }

            // Commit offset only after successful processing
        } catch (Exception e) {
            // Dead letter queue for failed processing
            dlqPublisher.send(event, e);
        }
    }
}

🔄 ETL: Extract, Transform, Load

The Traditional Data Integration Pattern

ETL represents the classic approach to data integration: extract data from sources, transform it in-flight according to business rules, and load clean, validated data into the target system.

When ETL Shines

1. Data Quality Requirements

In fintech, you can't afford dirty data in your data warehouse. ETL validates and cleanses before loading:

def transform_transaction(raw_event):
    """
    ETL transformation logic - validate, enrich, standardize
    """
    # Extract
    txn = extract_from_kafka(raw_event)

    # Transform
    validated = {
        'transaction_id': txn['transactionId'],
        'amount': validate_amount(txn['amount']),
        'currency': standardize_currency(txn['currency']),
        'merchant_id': validate_merchant(txn['merchantId']),
        'merchant_category': enrich_merchant_category(txn['merchantId']),
        'risk_score': calculate_risk_score(txn),
        'is_international': detect_international(txn),
        'processed_at': datetime.utcnow(),
        'data_quality_flags': run_quality_checks(txn)
    }

    # Only load if validation passes
    if validated['data_quality_flags']['is_valid']:
        # Load
        load_to_warehouse(validated)
    else:
        send_to_quarantine(txn, validated['data_quality_flags'])

    return validated

2. Complex Business Logic

When transformation requires multiple data sources:

-- ETL example: Enrich transactions with customer tier and spending limits
INSERT INTO warehouse.enriched_transactions
SELECT 
    t.transaction_id,
    t.amount,
    t.currency,
    c.customer_tier,
    c.monthly_limit,
    CASE 
        WHEN t.amount > c.monthly_limit * 0.8 THEN 'high_usage'
        WHEN t.amount > c.monthly_limit * 0.5 THEN 'medium_usage'
        ELSE 'normal'
    END as usage_category,
    m.merchant_name,
    m.mcc_code,
    mcc.category_description
FROM staging.raw_transactions t
JOIN dim.customers c ON t.account_id = c.account_id
JOIN dim.merchants m ON t.merchant_id = m.merchant_id
JOIN dim.mcc_codes mcc ON m.mcc_code = mcc.mcc_code
WHERE t.status = 'completed'
  AND t.processed = false;

3. Schema Enforcement

ETL enforces schema at write time, preventing invalid data from polluting your warehouse:

# Schema validation before load
TRANSACTION_SCHEMA = {
    "transaction_id": {"type": "string", "pattern": "^txn_[a-z0-9]+$"},
    "amount": {"type": "number", "minimum": 0.01, "maximum": 1000000},
    "currency": {"type": "string", "enum": ["USD", "EUR", "GBP"]},
    "timestamp": {"type": "datetime", "format": "iso8601"}
}

def validate_and_load(event):
    if not validate_schema(event, TRANSACTION_SCHEMA):
        raise ValidationError("Schema validation failed")

    load_to_warehouse(event)

ETL Pipeline Architecture

Event Source (Kafka)
       ↓
   Extractor
   (Kafka Consumer)
       ↓
  Transformation Layer
  - Validation
  - Enrichment
  - Business Rules
  - Data Quality Checks
       ↓
    Loader
    (Batch Insert)
       ↓
  Data Warehouse
  (Snowflake/Redshift)
       ↓
   BI Dashboards

🔀 ELT: Extract, Load, Transform

The Modern Cloud Data Warehouse Approach

ELT flips the script: load raw data first, transform later. This approach has gained popularity with cloud data warehouses that offer massive compute power and storage.

When ELT Excels

1. Schema-on-Read Flexibility

Load everything now, decide what you need later:

-- ELT Stage 1: Load raw JSON directly
CREATE TABLE raw.transaction_events (
    event_id STRING,
    raw_payload VARIANT,  -- JSON blob in Snowflake
    ingested_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP()
);

-- ELT Stage 2: Transform when querying
CREATE VIEW analytics.transaction_summary AS
SELECT 
    raw_payload:data:transactionId::STRING as transaction_id,
    raw_payload:data:amount::NUMBER as amount,
    raw_payload:data:currency::STRING as currency,
    raw_payload:data:metadata:location::STRING as location,
    raw_payload:timestamp::TIMESTAMP as event_time
FROM raw.transaction_events
WHERE raw_payload:eventType::STRING = 'transaction.completed';

2. Audit Trail and Reprocessing

Keep raw data immutable, transform multiple times:

-- Original transformation (deployed week 1)
CREATE TABLE analytics.transactions_v1 AS
SELECT 
    transaction_id,
    amount,
    currency
FROM raw.transaction_events;

-- Updated business logic (deployed week 4)
CREATE TABLE analytics.transactions_v2 AS
SELECT 
    transaction_id,
    amount,
    currency,
    CASE 
        WHEN amount > 10000 THEN 'large'
        WHEN amount > 1000 THEN 'medium'
        ELSE 'small'
    END as transaction_size  -- New logic
FROM raw.transaction_events;  -- Reprocess from raw

3. Exploratory Analytics

Data scientists can explore raw data without waiting for ETL pipelines:

# Data scientist exploring raw events
df = spark.read.json("s3://data-lake/transactions/raw/")

# Ad-hoc transformation for ML feature engineering
features = df.select(
    col("data.transactionId").alias("txn_id"),
    col("data.amount").alias("amount"),
    hour(col("timestamp")).alias("hour_of_day"),
    dayofweek(col("timestamp")).alias("day_of_week"),
    col("data.metadata.deviceId").alias("device")
).filter(
    col("eventType") == "transaction.completed"
)

# No ETL pipeline needed for experimentation

ELT Pipeline Architecture

Event Source (Kafka)
       ↓
   Extractor
   (Kafka Connect)
       ↓
   Data Lake (S3)
   [Raw JSON/Parquet]
       ↓
  Cloud Warehouse
  (Snowflake/BigQuery)
  [Raw Schema]
       ↓
  dbt Transformations
  (SQL-based)
       ↓
  Analytics Tables
  (Curated Views)
       ↓
  BI & ML Consumers

⚖️ ETL vs ELT: Making the Right Choice

Comparison Matrix

Dimension	ETL	ELT
Transformation Location	Before loading (in pipeline)	After loading (in warehouse)
Data Quality	Enforced at ingestion	Enforced at read/query time
Schema Management	Schema-on-write	Schema-on-read
Storage Cost	Lower (only valid data stored)	Higher (all raw data stored)
Compute Cost	Higher (dedicated pipeline infra)	Lower (leverage warehouse compute)
Flexibility	Lower (changes require pipeline updates)	Higher (transform without reingestion)
Time to Insight	Slower (validation delays)	Faster (load immediately)
Audit Trail	Transformed data only	Complete raw history
Best For	Regulated industries, strict quality needs	Exploratory analytics, rapid iteration

Decision Framework

Choose ETL when:

Data quality is non-negotiable (finance, healthcare)
Transformation logic is stable and well-defined
Reducing storage costs is critical
Compliance requires validated data only
Target system has limited compute (legacy warehouse)

Choose ELT when:

Using modern cloud data warehouses
Requirements change frequently
Need to support exploratory analytics
Want complete audit trail of raw data
Data scientists need flexible access
Time-to-insight matters more than storage cost

Hybrid Approach: The Best of Both Worlds

Most mature platforms use both:

Real-time Events
       ↓
    Kafka
       ↓
    ┌─────┴─────┐
    ↓           ↓
  ETL         ELT
(Critical)   (Exploratory)
    ↓           ↓
Operational  Data Lake
Warehouse       ↓
    ↓        Analytics
BI Dashboards  Warehouse
              ↓
          ML/Data Science

Example allocation:

ETL: Financial reports, compliance dashboards, real-time fraud detection
ELT: Customer behavior analysis, A/B testing, ML model training

🔄 Batch Processing: The Scheduled Workhorse

The Role of Batch Jobs

While event streams handle real-time data, batch processing handles periodic aggregations, reconciliations, and complex analytics that don't need to be immediate.

Common Batch Processing Patterns

1. Daily Aggregations

# Airflow DAG for daily transaction summary
@dag(
    schedule_interval="0 2 * * *",  # 2 AM daily
    start_date=datetime(2025, 1, 1),
    catchup=False
)
def daily_transaction_summary():

    @task
    def extract_daily_transactions():
        """Extract yesterday's transactions"""
        return spark.read.parquet(
            f"s3://data-lake/transactions/date={yesterday}"
        )

    @task
    def transform_and_aggregate(df):
        """Calculate daily metrics"""
        return df.groupBy("account_id", "currency").agg(
            count("transaction_id").alias("txn_count"),
            sum("amount").alias("total_amount"),
            avg("amount").alias("avg_amount"),
            max("amount").alias("max_amount"),
            countDistinct("merchant_id").alias("unique_merchants")
        )

    @task
    def load_to_warehouse(summary_df):
        """Load to analytics warehouse"""
        summary_df.write.mode("overwrite").insertInto(
            "analytics.daily_transaction_summary"
        )

    # Pipeline
    raw = extract_daily_transactions()
    summary = transform_and_aggregate(raw)
    load_to_warehouse(summary)

dag = daily_transaction_summary()

2. End-of-Month Reconciliation

def monthly_reconciliation(month, year):
    """
    Reconcile transactions against bank statements
    Critical for financial accuracy
    """
    # Extract all transactions for the month
    transactions = get_transactions(month, year)

    # Extract bank statements
    bank_statements = get_bank_statements(month, year)

    # Match and identify discrepancies
    matched, unmatched = reconcile(transactions, bank_statements)

    # Generate report
    report = {
        'total_transactions': len(transactions),
        'matched': len(matched),
        'unmatched': len(unmatched),
        'discrepancy_amount': sum(u['amount'] for u in unmatched),
        'reconciliation_rate': len(matched) / len(transactions) * 100
    }

    # Alert if reconciliation rate < 99.9%
    if report['reconciliation_rate'] < 99.9:
        send_alert(report)

    return report

3. ML Model Training

@task
def train_fraud_detection_model():
    """
    Weekly batch job to retrain fraud model
    """
    # Extract last 90 days of labeled transactions
    df = spark.sql("""
        SELECT 
            amount,
            merchant_category,
            hour_of_day,
            is_international,
            velocity_24h,
            is_fraud  -- labeled by fraud analysts
        FROM analytics.labeled_transactions
        WHERE processed_date >= current_date - 90
    """)

    # Feature engineering
    features = prepare_features(df)

    # Train model
    model = XGBClassifier()
    model.fit(features, df['is_fraud'])

    # Evaluate and deploy if better than current
    if model.score > current_model.score:
        deploy_model(model, version=f"v{datetime.now().strftime('%Y%m%d')}")

🏛️ Complete System Architecture

End-to-End Data Flow

┌─────────────────────────────────────────────────────────────────┐
│                     PRODUCTION SERVICES                          │
│  (Payment API, Account Service, Merchant Service)               │
└────────────────────────┬────────────────────────────────────────┘
                         │ Emit Events
                         ↓
┌─────────────────────────────────────────────────────────────────┐
│                      KAFKA CLUSTER                               │
│  Topics: transactions.raw, transactions.validated,               │
│          fraud.alerts, accounting.journal                        │
└──────┬──────────────────────────┬───────────────────────────────┘
       │                          │
       │ Real-time                │ Batch
       ↓                          ↓
┌─────────────────┐      ┌─────────────────┐
│  STREAM         │      │  KAFKA          │
│  PROCESSORS     │      │  CONNECT        │
│                 │      │  (CDC/S3 Sink)  │
│ - Validation    │      └────────┬────────┘
│ - Enrichment    │               │
│ - Fraud Check   │               ↓
│ - Routing       │      ┌─────────────────┐
└────────┬────────┘      │  DATA LAKE      │
         │               │  (S3/Parquet)   │
         │               └────────┬────────┘
         │                        │
         ↓                        ↓
┌─────────────────┐      ┌─────────────────┐
│  OPERATIONAL    │      │  ANALYTICS      │
│  WAREHOUSE      │      │  WAREHOUSE      │
│  (PostgreSQL)   │      │  (Snowflake)    │
│                 │      │                 │
│ ETL Pipeline    │      │ ELT Pipeline    │
│ - Validated     │      │ - Raw Load      │
│ - Enriched      │      │ - dbt Transform │
│ - Aggregated    │      │ - Star Schema   │
└────────┬────────┘      └────────┬────────┘
         │                        │
         ↓                        ↓
┌─────────────────────────────────────────┐
│         CONSUMPTION LAYER                │
│                                          │
│  ┌──────────┐  ┌──────────┐  ┌────────┐│
│  │ BI Tools │  │ ML/AI    │  │ APIs   ││
│  │ (Tableau)│  │ Platform │  │        ││
│  └──────────┘  └──────────┘  └────────┘│
└─────────────────────────────────────────┘

       ┌──────────────────────┐
       │   BATCH PROCESSING   │
       │   (Airflow/Spark)    │
       │                      │
       │ - Daily Aggregations │
       │ - Reconciliation     │
       │ - Model Training     │
       └──────────────────────┘

Data Flow Example: Transaction Journey

Let's trace a single transaction through the entire system:

T+0ms: Transaction Created

POST /api/v1/transactions
{
  "accountId": "acc_xyz789",
  "amount": 1250.00,
  "currency": "USD",
  "merchantId": "mch_def456"
}

T+5ms: Event Published to Kafka

{
  "eventType": "transaction.completed",
  "data": { /* transaction details */ }
}
// Published to: transactions.raw

T+10ms: Stream Processor Validates

# Kafka Streams processor
validated_txn = validate_transaction(raw_event)
if validated_txn.is_valid:
    publish("transactions.validated", validated_txn)
else:
    publish("transactions.failed", raw_event)

T+50ms: Multiple Consumers React

- Fraud Detection: Analyzes and scores transaction
- Accounting: Creates double-entry journal entries
- Notification: Sends confirmation to customer
- Analytics: Writes to operational warehouse (ETL)

T+2min: Loaded to Data Lake

Kafka Connect → S3 Sink
s3://data-lake/transactions/date=2025-10-07/hour=14/
  part-00001.parquet (raw ELT)

T+1hr: Batch Aggregation

-- Hourly rollup job
INSERT INTO analytics.hourly_transaction_summary
SELECT 
    date_trunc('hour', event_time) as hour,
    currency,
    count(*) as txn_count,
    sum(amount) as total_volume
FROM raw.transaction_events
WHERE event_time >= current_hour
GROUP BY 1, 2;

T+24hrs: Overnight Processing

1. Daily reconciliation batch job
2. Fraud model retraining
3. Customer spending report generation
4. Data quality checks
5. Compliance report export

🎯 Engineering Best Practices

1. Idempotency: The Golden Rule

Every event consumer must be idempotent—processing the same event multiple times produces the same result:

@Transactional
public void processPayment(TransactionEvent event) {
    // Check if already processed
    if (paymentRepository.existsByEventId(event.getEventId())) {
        log.info("Event {} already processed, skipping", event.getEventId());
        return;
    }

    // Process and record event ID
    Payment payment = createPayment(event);
    paymentRepository.save(payment);

    // Store event ID to prevent reprocessing
    processedEventRepository.save(
        new ProcessedEvent(event.getEventId(), Instant.now())
    );
}

2. Schema Registry: Contract-First Development

Use a schema registry (like Confluent Schema Registry) to enforce contracts:

{
  "type": "record",
  "name": "TransactionEvent",
  "namespace": "com.fintech.events",
  "version": "1.0",
  "fields": [
    {"name": "eventId", "type": "string"},
    {"name": "eventType", "type": "string"},
    {"name": "timestamp", "type": "long", "logicalType": "timestamp-millis"},
    {"name": "data", "type": {
      "type": "record",
      "name": "TransactionData",
      "fields": [
        {"name": "transactionId", "type": "string"},
        {"name": "amount", "type": "double"},
        {"name": "currency", "type": "string"}
      ]
    }}
  ]
}

3. Dead Letter Queues: Graceful Failure Handling

@KafkaListener(topics = "transactions.validated")
public void processTransaction(TransactionEvent event) {
    try {
        businessLogic.process(event);
    } catch (RetryableException e) {
        // Temporary failure - will retry
        throw e;
    } catch (NonRetryableException e) {
        // Permanent failure - send to DLQ
        dlqPublisher.send("transactions.dlq", event, e);
        log.error("Event {} moved to DLQ: {}", event.getEventId(), e.getMessage());
    }
}

4. Observability: Know Your System

Key Metrics to Track:

- Event lag: Time between production and consumption
- Processing rate: Events per second per consumer
- Error rate: Failed events / total events
- DLQ size: Events requiring manual intervention
- Pipeline latency: End-to-end time for data flows
- Data quality: Percentage of records passing validation

Implementation:

@Timed(value = "transaction.processing.time")
@Counted(value = "transaction.processed")
public void processTransaction(TransactionEvent event) {
    Instant start = Instant.now();
    try {
        doProcessing(event);
        meterRegistry.counter("transaction.success").increment();
    } catch (Exception e) {
        meterRegistry.counter("transaction.failure").increment();
        throw e;
    } finally {
        long duration = Duration.between(start, Instant.now()).toMillis();
        meterRegistry.timer("transaction.latency").record(duration, TimeUnit.MILLISECONDS);
    }
}

5. Data Quality Gates

def validate_data_quality(df):
    """
    Data quality checks before promoting to production tables
    """
    checks = {
        'null_check': df.filter(col("transaction_id").isNull()).count() == 0,
        'duplicate_check': df.count() == df.select("transaction_id").distinct().count(),
        'range_check': df.filter(col("amount") <= 0).count() == 0,
        'referential_integrity': check_foreign_keys(df),
        'freshness_check': max(df.select("timestamp")) >= yesterday
    }

    if not all(checks.values()):
        raise DataQualityException(f"Quality checks failed: {checks}")

    return df

6. Backward Compatibility

When evolving schemas:

✅ DO: Add optional fields
✅ DO: Deprecate fields gradually
✅ DO: Maintain version numbers
❌ DON'T: Remove required fields
❌ DON'T: Change field types
❌ DON'T: Break existing consumers

7. Cost Optimization

# Partition pruning in data lake
df = spark.read.parquet("s3://data-lake/transactions/") \
    .filter("date >= '2025-10-01'")  # Only scan October data

# Compression for storage efficiency
df.write \
    .option("compression", "snappy") \
    .partitionBy("date", "currency") \
    .parquet("s3://data-lake/transactions/")

# Materialized views for frequent queries
CREATE MATERIALIZED VIEW daily_summary AS
SELECT date, currency, sum(amount)
FROM transactions
GROUP BY 1, 2;

📊 Benefits of This Architecture

1. Scalability

Each component scales independently. High transaction volume? Add Kafka partitions and consumers. Complex analytics? Scale warehouse compute.

2. Resilience

Failed services don't lose data—events queue up. Failed pipelines can replay from any point. Multiple replicas ensure availability.

3. Flexibility

New consumers plug in without changing producers. New transformations don't require data reingestion. Business logic changes quickly.

4. Auditability

Immutable event log provides complete history. Every state change is traceable. Compliance requirements are built-in.

5. Cost Efficiency

Pay only for what you use. Cloud warehouses scale compute independently of storage. Batch jobs run on spot instances.

6. Time to Insight

Real-time streams for operational decisions. Batch jobs for deep analytics. Self-service analytics without engineering bottlenecks.

🚀 Conclusion: Building for the Future

Modern data systems aren't about choosing between real-time and batch, or ETL and ELT—they're about orchestrating these patterns to solve different problems optimally. Event-driven architecture provides the foundation for decoupled, scalable systems. Messaging queues enable reliable, asynchronous communication. ETL enforces quality where it matters. ELT provides flexibility where it's needed. Batch processing handles complex aggregations efficiently.

The fintech platform we've explored demonstrates how these pieces integrate into a cohesive whole: transactions flow through Kafka, get validated in real-time, land in both operational and analytical stores, get enriched through batch processing, and ultimately power everything from fraud detection to customer insights.

As you design your own data platforms, remember: architecture is about trade-offs, not absolutes. Understand your constraints—latency requirements, data quality needs, team capabilities, cost budgets—and choose the patterns that best fit your context. Start simple, measure everything, and evolve as you learn.

The best data platform is one that serves your business needs today while remaining flexible enough to adapt tomorrow.

Key Takeaways:

✅ Event-driven architecture enables loose coupling and independent scaling

✅ Message queues provide durability, ordering, and replay capabilities

✅ ETL enforces quality at write time; ELT optimizes for flexibility

✅ Batch processing complements real-time streams for complex analytics

✅ Idempotency, observability, and data quality are non-negotiable

✅ Hybrid approaches leverage the strengths of multiple patterns

✅ Architecture decisions should be driven by business requirements, not trends

Happy building, and may your data pipelines never have backpressure at 3 AM. 🌙

DEV Community: Dev Cookies

Low-Level Design (LLD) of a Heap (Priority Queue) in Java

Table of Contents

1. Introduction

2. What is a Heap?

3. Heap Properties

Complete Binary Tree

Heap Property

4. Types of Heap

Min Heap

Max Heap

5. Internal Representation

6. Parent/Child Formula

7. Designing Our Heap

Step 1 — Heap Skeleton

Step 2 — Resize Array

Step 3 — Insert

Heapify Up

Step 4 — Peek

Step 5 — Remove Root

Heapify Down

Swap

Build Heap

Complete Java Implementation

Time Complexity

Why Build Heap is O(n)?

Java PriorityQueue Internals

Common Interview Questions

Why use an array instead of nodes?

Why is insertion O(log n)?

Why can't we perform binary search on a heap?

Difference between Heap and BST?

When should you use a Heap?

Design Improvements for Production

Summary

Low-Level Design (LLD) of HashMap in Java — Build Your Own HashMap from Scratch

Table of Contents

1. Introduction

2. What is a HashMap?

3. Internal Architecture

4. Core Components

5. Designing Our HashMap

Step 1 — Node

Step 2 — HashMap Skeleton

Bucket Array

Step 3 — Hash Function

Why modulo?

Step 4 — Put Operation

Example

Step 5 — Get Operation

Example

Step 6 — Remove Operation

Collision Handling

Rehashing

Resize Implementation

Add Resize Check

Complete Java Implementation

Time Complexity

How Java 8 Improved HashMap

Additional Optimizations in JDK HashMap

Common Interview Questions

1. Why is the default capacity 16?

2. Why is the default load factor 0.75?

3. Why are power-of-two capacities important?

4. Why store the hash in the node?

5. What happens if hashCode() is poorly implemented?

6. Is HashMap thread-safe?

Key Design Takeaways

Summary

Parking Lot System Low-Level Design (LLD) in Java

Complete Interview Guide | SOLID Principles | Design Patterns | Production-Ready Architecture

Introduction

Problem Statement

Functional Requirements

Core Features

Optional Features

Non-Functional Requirements

Real-World Examples

High-Level Architecture

Core Components

Java `PriorityQueue` Internals

5. What happens if `hashCode()` is poorly implemented?

6. Is `HashMap` thread-safe?