Derive vs Track State

TL;DR: Prefer deriving state from a single source of truth over maintaining redundant copies. Every redundant piece of state is a bug waiting to happen — two values that should agree but eventually won't.

Single Source of Truth

One of the most common mistakes in LLD interviews is tracking state in multiple places. A candidate designs a Movie Booking system with a reservations list AND a separate bookedSeats set. Now there are two representations of the same truth, and they can get out of sync.

The principle is simple: if you can compute a value from existing data, don't store it separately. Every redundant copy of state is a consistency risk. When you add a reservation but forget to update the booked seats set — or update the set but the reservation creation fails halfway through — your system is in an inconsistent state.

This doesn't mean you should never cache derived values. But in an LLD interview, where you're writing in-memory code without performance constraints, the derived approach is almost always better. It's simpler, safer, and demonstrates that you understand data integrity.

Derive, Don't Duplicate

Movie Booking: Reservations ARE Seat State

// BAD: Tracking seat state in two places
class BookingSystem {
    private List<Reservation> reservations;
    private Set<String> bookedSeats;  // REDUNDANT — duplicates info in reservations

    public void book(String seatId, String userId) {
        if (bookedSeats.contains(seatId)) {
            throw new IllegalStateException("Seat already booked");
        }
        reservations.add(new Reservation(seatId, userId));
        bookedSeats.add(seatId);  // Must keep in sync — what if this line is missed?
    }

    public void cancel(String seatId) {
        reservations.removeIf(r -> r.getSeatId().equals(seatId));
        bookedSeats.remove(seatId);  // Must keep in sync with reservations
    }
}

// GOOD: Derive seat availability from the reservations list
class BookingSystem {
    private final Map<String, Reservation> reservationsBySeat = new HashMap<>();

    public void book(String seatId, String userId) {
        if (reservationsBySeat.containsKey(seatId)) {
            throw new IllegalStateException("Seat already booked");
        }
        reservationsBySeat.put(seatId, new Reservation(seatId, userId));
    }

    public void cancel(String seatId) {
        if (reservationsBySeat.remove(seatId) == null) {
            throw new IllegalArgumentException("No reservation for this seat");
        }
    }

    public boolean isSeatAvailable(String seatId) {
        return !reservationsBySeat.containsKey(seatId);
    }

    public Set<String> getBookedSeats() {
        return Collections.unmodifiableSet(reservationsBySeat.keySet());
    }
}

// BAD: Redundant state
class BookingSystem {
    std::vector<Reservation> reservations;
    std::unordered_set<std::string> bookedSeats;  // duplicates reservation info
};

// GOOD: Single source of truth
class BookingSystem {
    std::unordered_map<std::string, Reservation> reservationsBySeat;

public:
    void book(const std::string& seatId, const std::string& userId) {
        if (reservationsBySeat.count(seatId)) {
            throw std::runtime_error("Seat already booked");
        }
        reservationsBySeat.emplace(seatId, Reservation(seatId, userId));
    }

    void cancel(const std::string& seatId) {
        if (reservationsBySeat.erase(seatId) == 0) {
            throw std::invalid_argument("No reservation for this seat");
        }
    }

    bool isSeatAvailable(const std::string& seatId) const {
        return reservationsBySeat.find(seatId) == reservationsBySeat.end();
    }
};

# BAD: Redundant state
class BookingSystem:
    def __init__(self):
        self._reservations: list[Reservation] = []
        self._booked_seats: set[str] = set()  # duplicates reservation info

# GOOD: Single source of truth
class BookingSystem:
    def __init__(self):
        self._reservations_by_seat: dict[str, Reservation] = {}

    def book(self, seat_id: str, user_id: str) -> None:
        if seat_id in self._reservations_by_seat:
            raise ValueError("Seat already booked")
        self._reservations_by_seat[seat_id] = Reservation(seat_id, user_id)

    def cancel(self, seat_id: str) -> None:
        if self._reservations_by_seat.pop(seat_id, None) is None:
            raise ValueError("No reservation for this seat")

    def is_seat_available(self, seat_id: str) -> bool:
        return seat_id not in self._reservations_by_seat

    def get_booked_seats(self) -> set[str]:
        return set(self._reservations_by_seat.keys())

One data structure. One place to update. No sync bugs.

Rate Limiter: Derive Token Count From Elapsed Time

A token bucket rate limiter refills tokens over time. A naive approach runs a background thread that adds tokens every second. A better approach derives the current token count from the last request time.

// BAD: Background thread to refill tokens
class RateLimiter {
    private int tokens;
    private final int maxTokens;
    // Requires a background thread calling refill() every second
    // Thread synchronization, timer management, resource cleanup...
}

// GOOD: Derive tokens from elapsed time
class RateLimiter {
    private final int maxTokens;
    private final double refillRate;  // tokens per second
    private double currentTokens;
    private Instant lastRefillTime;

    public RateLimiter(int maxTokens, double refillRate) {
        this.maxTokens = maxTokens;
        this.refillRate = refillRate;
        this.currentTokens = maxTokens;
        this.lastRefillTime = Instant.now();
    }

    public synchronized boolean tryConsume() {
        refill();
        if (currentTokens >= 1) {
            currentTokens -= 1;
            return true;
        }
        return false;
    }

    private void refill() {
        Instant now = Instant.now();
        double elapsed = Duration.between(lastRefillTime, now).toMillis() / 1000.0;
        currentTokens = Math.min(maxTokens, currentTokens + elapsed * refillRate);
        lastRefillTime = now;
    }
}

// GOOD: Derive tokens from elapsed time
class RateLimiter {
    int maxTokens;
    double refillRate;
    double currentTokens;
    TimePoint lastRefillTime;

public:
    RateLimiter(int maxTokens, double refillRate)
        : maxTokens(maxTokens), refillRate(refillRate),
          currentTokens(maxTokens), lastRefillTime(Clock::now()) {}

    bool tryConsume() {
        refill();
        if (currentTokens >= 1.0) {
            currentTokens -= 1.0;
            return true;
        }
        return false;
    }

private:
    void refill() {
        auto now = Clock::now();
        double elapsed = std::chrono::duration<double>(now - lastRefillTime).count();
        currentTokens = std::min(static_cast<double>(maxTokens),
                                 currentTokens + elapsed * refillRate);
        lastRefillTime = now;
    }
};

# GOOD: Derive tokens from elapsed time
class RateLimiter:
    def __init__(self, max_tokens: int, refill_rate: float):
        self._max_tokens = max_tokens
        self._refill_rate = refill_rate  # tokens per second
        self._current_tokens = float(max_tokens)
        self._last_refill_time = time.monotonic()

    def try_consume(self) -> bool:
        self._refill()
        if self._current_tokens >= 1.0:
            self._current_tokens -= 1.0
            return True
        return False

    def _refill(self) -> None:
        now = time.monotonic()
        elapsed = now - self._last_refill_time
        self._current_tokens = min(
            self._max_tokens,
            self._current_tokens + elapsed * self._refill_rate
        )
        self._last_refill_time = now

No background thread. No timer. No resource cleanup. The token count is always correct because it's derived from elapsed time at the moment you need it.

File System: Derive Path by Walking Parent Pointers

// BAD: Storing the full path as a field
class FileNode {
    private String name;
    private String fullPath;  // "/home/user/docs/file.txt" — must be updated on every rename or move
    private FileNode parent;
}

// GOOD: Derive the path when needed
class FileNode {
    private String name;
    private FileNode parent;

    public String getPath() {
        if (parent == null) {
            return "/" + name;
        }
        return parent.getPath() + "/" + name;
    }
}

// GOOD: Derive the path when needed
class FileNode {
    std::string name;
    FileNode* parent;

public:
    std::string getPath() const {
        if (parent == nullptr) {
            return "/" + name;
        }
        return parent->getPath() + "/" + name;
    }
};

# GOOD: Derive the path when needed
class FileNode:
    def __init__(self, name: str, parent: "FileNode | None" = None):
        self._name = name
        self._parent = parent

    def get_path(self) -> str:
        if self._parent is None:
            return "/" + self._name
        return self._parent.get_path() + "/" + self._name

If you store fullPath, every rename or move operation must update the path of the node AND all its descendants. If you derive it, renaming is just changing the name field. The path is always correct because it's computed from the current tree structure.

Interview tip: When you catch yourself adding a field that duplicates information already present in your data structures, pause and say "I can derive this from [source] instead of tracking it separately." This is one of the strongest signals of design maturity an interviewer can see.

Tell, Don't Ask

The single source of truth principle extends to how callers interact with your objects. Objects should manage their own state and expose behavior — not getters for callers to make decisions.

Interview tip: Follow the "Tell, Don't Ask" principle. Instead of asking if (account.getBalance() > amount) then calling account.setBalance(...), tell the object: account.withdraw(amount) and let it enforce its own rules internally. This keeps validation logic inside the class that owns the state, eliminating an entire category of bugs where callers forget to check preconditions.

The Compartment example below demonstrates this well: callers don't check isOccupied() and then flip a boolean — they call occupy() and the compartment enforces its own constraints.

Intrinsic vs. Relational State

Not all state should be derived. The question is: "Is this a property of the entity itself, or a relationship managed by the system?"

Intrinsic State: Lives ON the Entity

Some state is physically tied to an entity. An Amazon Locker compartment is either physically occupied or it isn't — that's a fact about the compartment itself, not about the system's bookkeeping.

// Intrinsic: occupied is a physical property of the compartment
class Compartment {
    private final Size size;
    private boolean occupied;
    private String pickupCode;

    public void occupy(String code) {
        if (occupied) throw new IllegalStateException("Already occupied");
        this.occupied = true;
        this.pickupCode = code;
    }

    public void release() {
        this.occupied = false;
        this.pickupCode = null;
    }

    public boolean isOccupied() { return occupied; }
}

class Compartment {
    Size size;
    bool occupied = false;
    std::string pickupCode;

public:
    explicit Compartment(Size size) : size(size) {}

    void occupy(const std::string& code) {
        if (occupied) throw std::runtime_error("Already occupied");
        occupied = true;
        pickupCode = code;
    }

    void release() {
        occupied = false;
        pickupCode.clear();
    }

    bool isOccupied() const { return occupied; }
};

class Compartment:
    def __init__(self, size: Size):
        self._size = size
        self._occupied = False
        self._pickup_code: str | None = None

    def occupy(self, code: str) -> None:
        if self._occupied:
            raise ValueError("Already occupied")
        self._occupied = True
        self._pickup_code = code

    def release(self) -> None:
        self._occupied = False
        self._pickup_code = None

    @property
    def is_occupied(self) -> bool:
        return self._occupied

This is correct. The compartment manages its own occupied state because physical presence is intrinsic to the compartment.

Relational State: Lives ON the Orchestrator

A parking spot's assignment to a vehicle is a relationship managed by the parking lot system. The spot itself doesn't know or care what's parked in it — the system tracks that mapping.

// Relational: spot assignment is tracked by the system, not the spot
class ParkingLot {
    private final Set<Integer> occupiedSpotIds;
    private final Map<String, Ticket> activeTickets;

    public boolean isSpotAvailable(int spotId) {
        return !occupiedSpotIds.contains(spotId);
    }
}

class ParkingLot {
    std::unordered_set<int> occupiedSpotIds;
    std::unordered_map<std::string, Ticket> activeTickets;

public:
    bool isSpotAvailable(int spotId) const {
        return occupiedSpotIds.find(spotId) == occupiedSpotIds.end();
    }
};

class ParkingLot:
    def __init__(self):
        self._occupied_spot_ids: set[int] = set()
        self._active_tickets: dict[str, Ticket] = {}

    def is_spot_available(self, spot_id: int) -> bool:
        return spot_id not in self._occupied_spot_ids

Both the locker approach and the parking lot approach are correct. The deciding question is whether the state is a property of the entity or a relationship managed by the system:

System	State	Where it lives	Why
Amazon Locker	Compartment occupied	ON the Compartment	Physical presence is intrinsic — a compartment holds a package
Parking Lot	Spot occupied	ON the ParkingLot	Assignment is relational — the system decides which car goes where
Movie Booking	Seat reserved	ON the BookingSystem	Reservation is relational — it links a user to a seat for a showtime
File System	File locked	ON the FileNode	Lock is intrinsic — the file itself is either locked or not

Interview tip: When deciding where state lives, ask yourself: "If I delete the orchestrator and just look at this entity in isolation, does this state still make sense?" A compartment is occupied whether or not a LockerSystem exists. A parking spot's assignment to a car only makes sense in the context of the parking lot system.

Quick Recap

Concept	What it means	Why it matters
Derive over track	Compute values from existing data instead of storing redundant copies	Eliminates sync bugs — one source of truth can't contradict itself
Single source of truth	One authoritative data structure for each piece of state	Every redundant copy is a consistency risk
Intrinsic state	A property of the entity itself (compartment is occupied)	Lives on the entity because it describes the entity's physical state
Relational state	A relationship managed by the system (spot is assigned to car)	Lives on the orchestrator because it describes system-level bookkeeping