These are the notes for Low-Level Design (LLD) episode 60, the second half of the parking lot machine-coding problem. In episode 59 we built the model: spot types, vehicle types, floors, spots, tickets, gates and a display board. Now we make that model work on a busy Saturday. We answer four questions, each with the obvious code first and its real failure: which spot should a vehicle get (a spot allocation strategy, the nearest spot strategy, and availability tracking with a TreeSet), how much it pays (a pricing strategy: hourly vs flat pricing, with the integer-division billing bug), how it pays (payment as a Payment strategy: UPI, card, cash) and where its ticket is (the ticket lifecycle ACTIVE → PAID → EXITED). Then the hardest one: concurrent spot booking, where eight gates book at the same moment and the fix is synchronized allocation. Finally the whole thing runs together in a running demo.
How the code was run: every program was saved as Main.java in a fresh folder and run with javac Main.java && java -cp . Main on OpenJDK 21. Every output below is the real output, pasted exactly, including exceptions. The race program's "no lock" line changes from run to run (that is the bug), so three real runs are shown. The mall and its tariff (Rs 10, 30 and 60 an hour, Rs 100 flat) are made up for teaching.
1. The problem: part 1's lot on a Saturday
Part 1 gave us a model where every rule has an owner. A quick reminder of the pieces we keep:
VehicleTypeis an enum (a type with a fixed list of values) withBIKE, CAR, TRUCK.SpotTypeis an enum withSMALL, COMPACT, LARGE. A spot fits a vehicle when the spot is at least as big: aLARGEspot fits anything, aSMALLspot fits only a bike.- A
Spothas an id likeC1, a type, and now also a distance (metres from the gate) and a free flag. - In part 1 the lot gave a vehicle the first free spot that fits, in list order.
That was enough to pass part 1's tests. On a real Saturday it has four problems, and this episode fixes them in order:
| Problem | What goes wrong | Fixed by |
|---|---|---|
| Bikes take the big spots near the gate | Cars and trucks are turned away while bike spots sit empty | Spot allocation strategy: nearest spot strategy |
| 2 h 59 min is billed as 2 h | The mall loses an hour's fee on every such visit | Pricing strategy that rounds up started hours |
| One driver pays twice, another leaves without paying | Nothing knows where a ticket is in its life | Ticket lifecycle (a small state machine) |
| Two gates, one last spot | Both gates print a ticket for spot C1 | Synchronized allocation |
Clarifying questions for part 2 (episode 55 taught us to ask before coding):
| Question | Our assumption |
|---|---|
| Which spot should a vehicle get? | The smallest spot type that fits, and inside that type the nearest to the gate |
| How is a stay billed? | Per started hour, minimum one hour; some nights a flat price per visit |
| How can a driver pay? | UPI, card or cash (cash gives change); more methods later |
| Can a ticket be paid twice, or used to exit twice? | No: every wrong move is refused with an exception |
| Do several gates work at the same time? | Yes: 8 gates, so booking must be safe when gates act at once |
2. The real-life idea: Saturday rush, part 2
It's Saturday at the mall basement again. The first two riders on bikes are waved into the compact and large spots near the gate, because those were "first". A car arrives: nothing left that fits, though both bike spots are empty. A family parks for 2 hours 59 minutes and the machine charges 2 hours. One driver pays twice by mistake; another simply drives out without paying. And at 6 pm, with one free spot left, two gates print a ticket for spot C1 at the same moment.
A well-run mall solves each of these with its own rule book, and each rule book becomes one interface in our design:
| At the mall | In the design |
|---|---|
| The usher's rule: "bikes to the bike row, nearest first" | SpotAllocationStrategy (NearestFit, FirstFree) |
| The board of free spots the usher keeps up to date | Availability tracking: a TreeSet of free spots per SpotType |
| The rate card at the gate: Rs 30 an hour, or Rs 100 on a concert night | PricingStrategy (HourlyPricing, FlatPricing) |
| The pay counter that takes UPI, a card, or cash and gives change | PaymentMethod, the Payment strategy (Upi, Card, Cash) |
| The stamp on the paper slip: unstamped, stamped PAID, torn at the exit | The ticket lifecycle: ACTIVE → PAID → EXITED |
| Only one attendant may write on the spot board at a time | synchronized: one gate at a time inside the booking code |
Each rule book can be swapped without touching the others: a new rate card does not change how spots are chosen. That is the Strategy pattern from episode 34: a family of interchangeable algorithms behind one interface.
3. Spot allocation: who decides which spot?
Spot allocation means choosing which free spot a vehicle gets. Different malls want different rules (nearest to the gate, nearest to the lift, fill floor 1 first), so we don't hard-code one. We make the choice a strategy:
interface SpotAllocationStrategy { Optional<Spot> pick(VehicleType v); void release(Spot s); }
- An interface is a contract: a list of methods a class promises to have. Any class that
implementsit can be plugged in. picktakes a vehicle type and maybe returns a spot. "Maybe" isOptional<Spot>: a box that either holds aSpotor is empty. It forces the caller to handle "no spot", instead of getting a surprisenull.releasegives a spot back when its vehicle leaves.
Our test: a compact spot C1 5 metres from the gate, a large one L1 at 8 m, and two small ones, S1 at 20 m and S2 at 12 m. Two bikes arrive, then a car, then a truck.
4. The obvious way: first free spot (and how it breaks)
This is the video's program. HEAD (the first six lines) is shared with the next program.
import java.util.*;
enum VehicleType { BIKE, CAR, TRUCK }
enum SpotType { SMALL, COMPACT, LARGE; boolean fits(VehicleType v) { return ordinal() >= v.ordinal(); } }
class Spot { final String id; final SpotType type; final int distance; boolean free = true; // metres to the gate
Spot(String id, SpotType type, int distance) { this.id = id; this.type = type; this.distance = distance; } }
interface SpotAllocationStrategy { Optional<Spot> pick(VehicleType v); void release(Spot s); }
class FirstFree implements SpotAllocationStrategy { // the obvious way: scan the list in order
private final List<Spot> spots;
FirstFree(List<Spot> spots) { this.spots = spots; }
public Optional<Spot> pick(VehicleType v) { // O(n): looks at every spot in the worst case
for (Spot s : spots)
if (s.free && s.type.fits(v)) { s.free = false; return Optional.of(s); }
return Optional.empty();
}
public void release(Spot s) { s.free = true; }
}
public class Main { public static void main(String[] args) {
List<Spot> spots = List.of(new Spot("C1", SpotType.COMPACT, 5), new Spot("L1", SpotType.LARGE, 8),
new Spot("S1", SpotType.SMALL, 20), new Spot("S2", SpotType.SMALL, 12));
SpotAllocationStrategy strategy = new FirstFree(spots);
for (String v : "BIKE BIKE CAR TRUCK".split(" ")) // four vehicles arrive, in this order
System.out.println(v + " -> " + strategy.pick(VehicleType.valueOf(v)).map(s -> s.id).orElse("NONE"));
}}
Output:
BIKE -> C1
BIKE -> L1
CAR -> NONE
TRUCK -> NONE
Read it line by line:
SpotType.fitsusesordinal(), an enum value's position in its list (SMALLis 0,COMPACT1,LARGE2;BIKE0,CAR1,TRUCK2). "Spot position ≥ vehicle position" means "the spot is big enough".FirstFree.pickwalks the list in order and takes the first spot that is free and fits. In the worst case it looks at every spot: O(n). Big-O notation describes how the work grows with the input size n; O(n) means "in step with n": twice the spots, twice the work.- In
main,List.of(...)makes a fixed list."BIKE BIKE CAR TRUCK".split(" ")cuts the string into four words, andVehicleType.valueOf(v)turns the word"CAR"into the enum valueCAR. strategy.pick(...).map(s -> s.id).orElse("NONE"): if the Optional holds a spot,mapturns it into the spot's id; if it is empty,orElsegives"NONE".s -> s.idis a lambda: a short unnamed function, here "given s, return s.id".
Why it failed
The first bike got C1, because C1 was first in the list and a compact spot fits a bike. The second bike got L1. Now the car and the truck find nothing, while both small spots are still empty. First-fit gave a big spot to a small vehicle while a small spot was free. The list order decided, not the sizes.
5. The nearest spot strategy and availability tracking
The fix is a smarter strategy. Our nearest spot strategy has two rules:
- Try the smallest spot type that fits first (a bike tries
SMALL, thenCOMPACT, thenLARGE). - Inside that type, take the spot nearest the gate.
Picture three queues of free spots, one per type, each sorted by distance:
SMALL : S2 (12 m), S1 (20 m) <- a bike takes the front: S2
COMPACT : C1 (5 m)
LARGE : L1 (8 m)
Keeping this list of free spots always up to date (remove a spot when it is taken, add it back when it is released) is called availability tracking. Then nobody has to scan every spot to find a free one: the answer is already waiting at the front of a queue.
The tool: TreeSet
A TreeSet is a Java set that keeps itself sorted all the time. Inside it is a balanced tree, so finding the smallest element, removing it and adding a new one are all O(log n). O(log n) means the work grows like the number of times you can halve n: for 10,000 spots it is about 14 steps, for a million about 20. A set holds each element at most once.
A Comparator tells a sorted collection how to order its elements. Comparator.comparingInt(s -> s.distance) means "order spots by their distance, smallest first".
An EnumMap is a Map (a table from keys to values) whose keys are the values of one enum. It is fast (inside it is just an array indexed by ordinal()) and always lists keys in the enum's order.
A small program to see these tools on their own:
import java.util.*;
enum SpotType { SMALL, COMPACT, LARGE }
public class Main {
public static void main(String[] args) {
TreeSet<Integer> distances = new TreeSet<>(List.of(20, 12, 35, 5));
System.out.println("kept sorted: " + distances);
System.out.println("first(): " + distances.first() + " (looks, does not remove)");
System.out.println("pollFirst(): " + distances.pollFirst() + " (removes it)");
distances.add(8);
System.out.println("after add(8): " + distances);
System.out.println("add(12) again: " + distances.add(12) + " (a set keeps no duplicates)");
Map<SpotType, Integer> freeCount = new EnumMap<>(SpotType.class);
freeCount.put(SpotType.LARGE, 1); freeCount.put(SpotType.SMALL, 2); freeCount.put(SpotType.COMPACT, 1);
System.out.println("EnumMap order: " + freeCount + " (the enum's order, always)");
for (int n : new int[]{ 16, 1_000, 10_000, 1_000_000 })
System.out.println("n = " + n + ": about " + (int) Math.ceil(Math.log(n) / Math.log(2)) + " steps (log2 n)");
}
}
Output:
kept sorted: [5, 12, 20, 35]
first(): 5 (looks, does not remove)
pollFirst(): 5 (removes it)
after add(8): [8, 12, 20, 35]
add(12) again: false (a set keeps no duplicates)
EnumMap order: {SMALL=2, COMPACT=1, LARGE=1} (the enum's order, always)
n = 16: about 4 steps (log2 n)
n = 1000: about 10 steps (log2 n)
n = 10000: about 14 steps (log2 n)
n = 1000000: about 20 steps (log2 n)
first() only looks; pollFirst() looks and removes, which is exactly "take the nearest free spot".
NearestFit
The video's program: the same HEAD, a new strategy, and the same main with NearestFit passed in.
import java.util.*;
enum VehicleType { BIKE, CAR, TRUCK }
enum SpotType { SMALL, COMPACT, LARGE; boolean fits(VehicleType v) { return ordinal() >= v.ordinal(); } }
class Spot { final String id; final SpotType type; final int distance; boolean free = true; // metres to the gate
Spot(String id, SpotType type, int distance) { this.id = id; this.type = type; this.distance = distance; } }
interface SpotAllocationStrategy { Optional<Spot> pick(VehicleType v); void release(Spot s); }
class NearestFit implements SpotAllocationStrategy { // smallest type that fits, nearest first
private final Map<SpotType, TreeSet<Spot>> free = new EnumMap<>(SpotType.class); // availability tracking
NearestFit(List<Spot> spots) {
for (SpotType t : SpotType.values()) // one sorted set of free spots per type
free.put(t, new TreeSet<Spot>(Comparator.comparingInt(s -> s.distance)));
for (Spot s : spots) free.get(s.type).add(s);
}
public Optional<Spot> pick(VehicleType v) {
for (SpotType t : SpotType.values()) // SMALL, then COMPACT, then LARGE
if (t.fits(v) && !free.get(t).isEmpty())
return Optional.of(free.get(t).pollFirst()); // nearest free spot of that type: O(log n)
return Optional.empty();
}
public void release(Spot s) { free.get(s.type).add(s); } // back into its set: O(log n)
}
public class Main { public static void main(String[] args) {
List<Spot> spots = List.of(new Spot("C1", SpotType.COMPACT, 5), new Spot("L1", SpotType.LARGE, 8),
new Spot("S1", SpotType.SMALL, 20), new Spot("S2", SpotType.SMALL, 12));
SpotAllocationStrategy strategy = new NearestFit(spots);
for (String v : "BIKE BIKE CAR TRUCK".split(" ")) // four vehicles arrive, in this order
System.out.println(v + " -> " + strategy.pick(VehicleType.valueOf(v)).map(s -> s.id).orElse("NONE"));
}}
Output:
BIKE -> S2
BIKE -> S1
CAR -> C1
TRUCK -> L1
- The field
freemaps eachSpotTypeto aTreeSetof its free spots, sorted by distance.new TreeSet<Spot>(...)names the element type so that the lambdas -> s.distanceknowssis aSpot. - The constructor makes one empty set per type, then puts every spot into its type's set.
picktriesSMALL, thenCOMPACT, thenLARGE(the order ofSpotType.values()). For the first type that fits and has a free spot,pollFirst()removes and returns the nearest one: O(log n).releaseputs a spot back into its set: O(log n).
Bike gets S2 (the nearer small spot), bike gets S1, car gets C1, truck gets L1. Everybody parks. And main didn't change at all: only the strategy we passed in. That is the payoff of making allocation a strategy.
| Strategy | Picks | Work per pick | Result on our test |
|---|---|---|---|
FirstFree |
First free spot that fits, in list order | O(n) scan | Car and truck turned away |
NearestFit |
Smallest type that fits, then nearest | O(log n) per type (3 types) | Everyone parks |
Expert note. In this episode's video both small spots happen to have different distances. If two spots of one type had the same distance, a TreeSet sorted only by distance would treat them as the same element and silently keep only one. Section 13 (Common mistakes) shows this for real; the fix is a tie-breaker: Comparator.comparingInt(Spot::distance).thenComparing(Spot::id). (Spot::id is a method reference, a shorter way to write the lambda s -> s.id().)
6. Pricing: hourly vs flat
A pricing strategy turns a ticket (vehicle type, entry time, exit time) into an amount.
- Hourly pricing charges a rate for every hour or part of an hour. In our made-up mall: Rs 10 an hour for a bike, Rs 30 for a car, Rs 60 for a truck.
- Flat pricing charges one fixed price per visit, however long you stay, say Rs 100 on a concert night.
Hourly vs flat pricing is exactly the kind of choice that changes from night to night, so pricing is a strategy too: interface PricingStrategy { int price(...); }.
The billing bug: integer division
The obvious way: hours = minutes / 60. But when you divide two whole-number types (int or long) in Java, you get integer division: the fraction is thrown away, not rounded. 179 / 60 is 2, not 2.98. The driver who stayed 2 h 59 min pays for 2 hours.
Parking is billed per started hour, so we round up. The classic trick: add 59 first, then divide. (179 + 59) / 60 = 238 / 60 = 3. Any leftover minute (1 to 59) pushes the total over the next multiple of 60, while an exact number of hours (like 120 minutes) is not pushed over: (120 + 59) / 60 = 179 / 60 = 2.
Two Java time types do the clock maths:
LocalDateTimeis a date and a time of day without a time zone, like 14 Nov 2026, 10:00.LocalDateTime.of(2026, 11, 14, 10, 0)makes one.Durationis an amount of time.Duration.between(in, out)is the time fromintoout;.toMinutes()gives it in whole minutes.
The video's program:
import java.time.*;
enum VehicleType { BIKE, CAR, TRUCK }
interface PricingStrategy { int price(VehicleType v, LocalDateTime in, LocalDateTime out); } // in rupees
class HourlyPricing implements PricingStrategy { // a rate for every hour or part of an hour
private final int[] ratePerHour = { 10, 30, 60 }; // bike, car, truck (our mall's made-up tariff)
public int price(VehicleType v, LocalDateTime in, LocalDateTime out) {
long minutes = Duration.between(in, out).toMinutes();
long hours = (minutes + 59) / 60; // started hours: round UP
return (int) Math.max(1, hours) * ratePerHour[v.ordinal()];
}
}
class FlatPricing implements PricingStrategy { // one price per visit, e.g. a concert night
private final int amount; FlatPricing(int amount) { this.amount = amount; }
public int price(VehicleType v, LocalDateTime in, LocalDateTime out) { return amount; }
}
public class Main {
public static void main(String[] args) {
LocalDateTime in = LocalDateTime.of(2026, 11, 14, 10, 0), out = LocalDateTime.of(2026, 11, 14, 12, 59);
long minutes = Duration.between(in, out).toMinutes();
System.out.println("parked " + minutes + " min, naive hours = minutes / 60 = " + (minutes / 60));
PricingStrategy hourly = new HourlyPricing(), flat = new FlatPricing(100);
System.out.println("hourly, car: Rs " + hourly.price(VehicleType.CAR, in, out));
System.out.println("hourly, bike: Rs " + hourly.price(VehicleType.BIKE, in, out));
System.out.println("flat, truck: Rs " + flat.price(VehicleType.TRUCK, in, out));
}
}
Output:
parked 179 min, naive hours = minutes / 60 = 2
hourly, car: Rs 90
hourly, bike: Rs 30
flat, truck: Rs 100
HourlyPricingkeeps one rate per vehicle type in an array and picks it withv.ordinal()(bike 0, car 1, truck 2).Math.max(1, hours)sets a minimum charge of one hour: a car that leaves after 0 minutes still pays for one hour.(int)is a cast: it converts thelongresult to anint(safe here, the numbers are small).- 179 minutes: naive hours say 2. Hourly car: Rs 90 (3 started hours × Rs 30). Hourly bike: Rs 30 (3 × Rs 10). Flat truck: Rs 100, however long it stayed.
Here is the rounding rule on its edges, which is where billing bugs hide:
public class Main {
public static void main(String[] args) {
int rate = 30;
for (long minutes : new long[]{0, 1, 59, 60, 61, 179, 180}) {
long naive = minutes / 60, up = (minutes + 59) / 60, billed = Math.max(1, up);
System.out.println(minutes + " min: naive " + naive + " h, rounded up " + up + " h, billed " + billed + " h = Rs " + billed * rate);
}
}
}
Output:
0 min: naive 0 h, rounded up 0 h, billed 1 h = Rs 30
1 min: naive 0 h, rounded up 1 h, billed 1 h = Rs 30
59 min: naive 0 h, rounded up 1 h, billed 1 h = Rs 30
60 min: naive 1 h, rounded up 1 h, billed 1 h = Rs 30
61 min: naive 1 h, rounded up 2 h, billed 2 h = Rs 60
179 min: naive 2 h, rounded up 3 h, billed 3 h = Rs 90
180 min: naive 3 h, rounded up 3 h, billed 3 h = Rs 90
One minute into the second hour starts it (61 min → 2 hours). The minimum charge turns 0 hours into 1.
Extension: a Clock you can control (testability)
HourlyPricing takes the entry and exit times as parameters, which makes it easy to test: we just pass in 10:00 and 12:59. But somewhere, real code must ask "what time is it now?". If it calls LocalDateTime.now() directly, a test would have to wait 61 real minutes to check the 61-minute bill.
The fix is to inject the clock: give the object a java.time.Clock in its constructor (this is dependency injection: an object receives the things it depends on instead of creating them). A Clock is Java's source of "now". In production you pass the real clock, Clock.systemDefaultZone(). In a test you pass:
Clock.fixed(instant, zone): a clock that always says the same moment; it never moves.Clock.offset(clock, duration): the same clock, moved forward by a duration.
An Instant is one exact point on the world's timeline, and a ZoneId names a time zone (here "Asia/Kolkata"), which is needed to turn a LocalDateTime into an Instant and back. LocalDateTime.now(clock) asks the given clock instead of the computer's.
import java.time.*;
enum VehicleType { BIKE, CAR, TRUCK }
interface PricingStrategy { int price(VehicleType v, long minutes); }
class PayDesk { // reads "now" from a Clock it is given
private final Clock clock;
private final PricingStrategy pricing;
PayDesk(Clock clock, PricingStrategy pricing) { this.clock = clock; this.pricing = pricing; }
LocalDateTime now() { return LocalDateTime.now(clock); }
int bill(VehicleType v, LocalDateTime entry) {
long minutes = Duration.between(entry, now()).toMinutes();
return pricing.price(v, minutes);
}
}
public class Main {
public static void main(String[] args) {
int[] rate = { 10, 30, 60 };
PricingStrategy hourly = (v, min) -> (int) Math.max(1, (min + 59) / 60) * rate[v.ordinal()];
ZoneId zone = ZoneId.of("Asia/Kolkata");
LocalDateTime entry = LocalDateTime.of(2026, 11, 14, 10, 0);
Clock atEntry = Clock.fixed(entry.atZone(zone).toInstant(), zone); // a clock that never moves
for (int minutes : new int[]{ 0, 60, 61, 179 }) {
Clock later = Clock.offset(atEntry, Duration.ofMinutes(minutes)); // the same clock, moved on
PayDesk desk = new PayDesk(later, hourly);
System.out.println("exit at " + desk.now().toLocalTime() + " (" + minutes + " min): car pays Rs "
+ desk.bill(VehicleType.CAR, entry));
}
PayDesk real = new PayDesk(Clock.systemDefaultZone(), hourly); // production: the real clock
System.out.println("real clock gives a LocalDateTime: " + (real.now() != null));
}
}
Output:
exit at 10:00 (0 min): car pays Rs 30
exit at 11:00 (60 min): car pays Rs 30
exit at 11:01 (61 min): car pays Rs 60
exit at 12:59 (179 min): car pays Rs 90
real clock gives a LocalDateTime: true
The quiz case (61 minutes → Rs 60) is now a test that runs in a millisecond, gives the same answer every time, and needs no waiting. The mini project goes one step further with a small clock class whose time a test can move forward.
7. Payment: the Payment strategy
Payment is the step where the driver hands over the amount the pricing strategy worked out. There are many ways to pay, and new ones keep appearing, so payment is a strategy too: the Payment strategy.
interface PaymentMethod { String pay(int amount); }
Upidescribes a payment from a UPI id (UPI is a phone-based bank payment method).Carddescribes a payment by the card whose last four digits it holds.Cashholds the amount handed over; it refuses too little money (anIllegalArgumentException) and works out the change.
The code that collects the money knows only PaymentMethod. A new method, like a wallet, is one more class; nothing else changes (practice question 4 does it).
8. The ticket lifecycle
The ticket lifecycle is the list of states a ticket moves through, in order:
ACTIVE ──pay()──▶ PAID ──exit()──▶ EXITED
(parked) (paid) (barrier opened; final)
Paying twice, exiting without paying, and exiting twice are all moves this lifecycle does not allow. So each action first checks the current state and refuses a wrong move. This is a small state machine (episode 37): a fixed set of states plus the allowed moves (transitions) between them; anything else is refused.
The video's program:
enum State { ACTIVE, PAID, EXITED } // the ticket lifecycle, in order
interface PaymentMethod { String pay(int amount); } // the Payment strategy
class Upi implements PaymentMethod { private final String id; Upi(String id) { this.id = id; }
public String pay(int amount) { return "Rs " + amount + " by UPI from " + id; } }
class Card implements PaymentMethod { private final String last4; Card(String last4) { this.last4 = last4; }
public String pay(int amount) { return "Rs " + amount + " by card ending " + last4; } }
class Cash implements PaymentMethod {
private final int given; Cash(int given) { this.given = given; }
public String pay(int amount) {
if (given < amount) throw new IllegalArgumentException("Rs " + given + " is less than Rs " + amount);
return "Rs " + amount + " in cash, change Rs " + (given - amount); } }
class Ticket {
final int id, amount; private State state = State.ACTIVE;
Ticket(int id, int amount) { this.id = id; this.amount = amount; }
void pay(PaymentMethod m) { // ACTIVE -> PAID
require(State.ACTIVE, "pay"); System.out.println(id + ": " + m.pay(amount)); state = State.PAID; }
void exit() { // PAID -> EXITED
require(State.PAID, "exit"); state = State.EXITED; System.out.println(id + ": barrier up"); }
private void require(State s, String what) { // only the allowed next step
if (state != s) throw new IllegalStateException("can't " + what + " ticket " + id + ", it's " + state); }
}
public class Main { public static void main(String[] args) {
Ticket t1 = new Ticket(1, 90), t2 = new Ticket(2, 30), t3 = new Ticket(3, 60);
t1.pay(new Upi("asha@upi")); t1.exit();
t2.pay(new Cash(50)); t2.exit();
t3.pay(new Card("4242"));
t1.exit(); // ticket 1 tries to leave again
}}
Output:
1: Rs 90 by UPI from asha@upi
1: barrier up
2: Rs 30 in cash, change Rs 20
2: barrier up
3: Rs 60 by card ending 4242
Exception in thread "main" java.lang.IllegalStateException: can't exit ticket 1, it's EXITED
at Ticket.require(Main.java:20)
at Ticket.exit(Main.java:18)
at Main.main(Main.java:27)
enum Statelists the states, so no misspelt state like"payed"can exist.TicketstartsACTIVE.payrequiresACTIVE, pays, and moves toPAID.exitrequiresPAIDand moves toEXITED.requireis the guard: if the ticket is not in the state the action needs, it throws anIllegalStateException("the object is not in a state where this call is allowed").- An exception is Java's way of stopping normal flow because something should not happen. Uncaught, it prints its message and the stack trace: the chain of method calls, with line numbers, that led there (
requireat line 20, called byexitat line 18, called bymainat line 27).
Ticket 1 pays Rs 90 by UPI and exits. Ticket 2 pays Rs 30 with a Rs 50 note: change Rs 20. Ticket 3 pays Rs 60 by card. Then ticket 1 tries to exit again: can't exit ticket 1, it's EXITED. The lifecycle refused it. Here the exception is the fix working, not a bug.
Cash also refuses too little money, for real:
interface PaymentMethod { String pay(int amount); }
class Cash implements PaymentMethod {
private final int given; Cash(int given) { this.given = given; }
public String pay(int amount) {
if (given < amount) throw new IllegalArgumentException("Rs " + given + " is less than Rs " + amount);
return "Rs " + amount + " in cash, change Rs " + (given - amount); } }
public class Main {
public static void main(String[] args) {
System.out.println(new Cash(100).pay(90));
System.out.println(new Cash(20).pay(30)); // a Rs 20 note for a Rs 30 bill
}
}
Output:
Rs 90 in cash, change Rs 10
Exception in thread "main" java.lang.IllegalArgumentException: Rs 20 is less than Rs 30
at Cash.pay(Main.java:5)
at Main.main(Main.java:10)
Notice the two exception types: too little cash is a bad argument (IllegalArgumentException); a ticket in the wrong state is a bad state (IllegalStateException).
9. Two gates at once: concurrent spot booking
Now the hardest problem: concurrent spot booking. "Concurrent" means "at the same time". Each gate's software runs as its own thread: a separate line of execution inside the same program, running at the same time as the others and sharing the same objects in memory. Eight gates are eight threads, all touching one set of spots.
Here is what goes wrong with one free spot:
Gate A: is C1 free? yes
Gate B: is C1 free? yes <- A has not marked it taken yet
Gate A: take C1, print ticket
Gate B: take C1, print ticket <- two tickets, one spot
This pattern is called check-then-act: you check a condition, then act on it, but between the check and the act another thread changes the world, so your check is stale by the time you act. A bug whose result depends on the exact timing of threads is a race condition (episode 46): the threads "race", and the winner changes from run to run.
The fix: synchronized
The fix is a lock: a token only one thread can hold at a time; others wait until it is free. In Java every object has a built-in lock, and the keyword synchronized uses it:
- A
synchronizedmethod: only one thread at a time may be inside any synchronized method of the same object. The others wait at the door. - A
synchronized (x) { ... }block: the same, using objectx's lock, for just those lines.
With the check and the take inside one synchronized method, they become one indivisible (also called atomic) step: no other gate can slip in between them. This is synchronized allocation.
The tools in the race program
- A thread pool is a fixed group of worker threads that run the tasks you hand them, reusing the same threads.
Executors.newFixedThreadPool(8)makes one with 8 threads: our 8 gates. ExecutorServiceis Java's interface for such a pool.submit(task)hands it a task and returns at once.- A
Future<Integer>is a receipt for a task's result that will exist later.f.get()waits until the task is done and returns its result. shutdown()tells the pool to accept no new tasks and let its threads finish.Thread.sleep(1)pauses the current thread for 1 millisecond. It stands for "printing the ticket takes a moment", and it widens the gap between the check and the act. It can throwInterruptedException(another thread asked this one to stop), which Java makes us catch.- A
HashSetis a set with fast add and lookup; here it collects the different spot numbers handed out. () -> safe ? lot.bookSafe() : lot.bookUnsafe()is a lambda with no parameters: the task each car runs.
The video's program:
import java.util.*;
import java.util.concurrent.*;
class Lot {
private final boolean[] taken = new boolean[10]; // 10 spots
int bookUnsafe() { return book(); } // no lock
synchronized int bookSafe() { return book(); } // one thread at a time
private int book() { // check-then-act
for (int i = 0; i < taken.length; i++)
if (!taken[i]) { printTicket(); taken[i] = true; return i; } // check ... then act
return -1; // full
}
private static void printTicket() { try { Thread.sleep(1); } catch (InterruptedException e) { } }
}
public class Main {
static void rush(String name, boolean safe) throws Exception {
Lot lot = new Lot();
ExecutorService gates = Executors.newFixedThreadPool(8); // 8 gates working at the same time
List<Future<Integer>> cars = new ArrayList<>();
for (int c = 0; c < 40; c++) cars.add(gates.submit(() -> safe ? lot.bookSafe() : lot.bookUnsafe())); // 40
int tickets = 0; Set<Integer> spots = new HashSet<>();
for (Future<Integer> f : cars) { int s = f.get(); if (s >= 0) { tickets++; spots.add(s); } }
gates.shutdown();
System.out.println(name + ": " + tickets + " tickets for " + spots.size() + " different spots");
}
public static void main(String[] args) throws Exception {
rush("no lock ", false); rush("synchronized", true);
}
}
Three real runs of the same program, one after another:
run 1
no lock : 40 tickets for 5 different spots
synchronized: 10 tickets for 10 different spots
run 2
no lock : 40 tickets for 7 different spots
synchronized: 10 tickets for 10 different spots
run 3
no lock : 40 tickets for 6 different spots
synchronized: 10 tickets for 10 different spots
The video doesn't quote the "no lock" numbers, because they change every run. Here they were 5, 7 and 6 different spots, and every run printed 40 tickets. (Three runs just before these all happened to print 6: a race can also repeat by chance, which is one more reason you can't trust a few runs.) Why?
- 8 threads start almost together. All 8 check
taken[0]: it is stillfalsefor every one of them, because each sleeps 1 ms (printing the ticket) before marking it taken. So all 8 get spot 0. - When they wake up they all set
taken[0] = trueand pick up the next cars; those all seetaken[1]free, and so on. Roughly 8 cars share each spot, so 40 cars need only about 40 / 8 = 5 spots before the lot even looks full. Thread start-up timing varies, so sometimes the groups are smaller and more spots get used (7 in run 2). - Result: far more tickets than spots, many cars sent to the same spot.
- Synchronized: one thread at a time inside
bookSafe, so each check-and-take finishes before the next starts. Exactly 10 tickets for 10 different spots, every time. The other 30 cars get-1(full).
A race can hide
The 1 ms sleep makes the race easy to see. Remove it (printTicket() does nothing) and run three times:
no lock : 10 tickets for 10 different spots
synchronized: 10 tickets for 10 different spots
no lock : 10 tickets for 10 different spots
synchronized: 10 tickets for 10 different spots
no lock : 10 tickets for 10 different spots
synchronized: 10 tickets for 10 different spots
In these three runs the unsafe version looked correct, because the gap between check and act became tiny. The bug is still there; it just shows up rarely, for example on a busy server at the worst moment. A test passing does not prove code is thread-safe. You make it safe by design: put check-and-take under one lock.
The lock must be shared
synchronized locks one object. If every gate locks its own object, nobody waits for anybody:
import java.util.*;
import java.util.concurrent.*;
class Gate { // one object PER gate
static final boolean[] taken = new boolean[10]; // but the spots are shared by all gates
synchronized int book() { // locks THIS gate only
for (int i = 0; i < taken.length; i++)
if (!taken[i]) { pause(); taken[i] = true; return i; }
return -1;
}
static void pause() { try { Thread.sleep(1); } catch (InterruptedException e) { } }
}
public class Main {
public static void main(String[] args) throws Exception {
ExecutorService pool = Executors.newFixedThreadPool(8);
List<Future<Integer>> cars = new ArrayList<>();
for (int c = 0; c < 40; c++) { Gate g = new Gate(); cars.add(pool.submit(() -> g.book())); }
int tickets = 0; Set<Integer> spots = new HashSet<>();
for (Future<Integer> f : cars) { int s = f.get(); if (s >= 0) { tickets++; spots.add(s); } }
pool.shutdown();
System.out.println("tickets " + (tickets > spots.size() ? "> " : "= ") + "spots: " + tickets + " vs " + spots.size());
}
}
Output (one run; the numbers change from run to run):
tickets > spots: 40 vs 5
Each car gets a new Gate object, so each thread holds a different lock, while all of them share the static taken array (a static field belongs to the class, so there is one copy shared by every object). The rule: the lock must belong to the object that owns the shared data, here the one ParkingLot.
10. How much to lock: coarse vs fine-grained
Coarse-grained locking means one lock for a big piece of state, here the whole lot. Fine-grained locking means several smaller locks, each for a smaller piece (one per spot type, one per floor, one per ticket), so unrelated work doesn't wait.
- One lock for the whole lot is simple and always correct. The cost is that gates wait for each other, but a check-and-take takes only microseconds (millionths of a second), so for a mall that's fine.
- Finer locks, one per spot type or per floor, mean a bike and a truck never wait for each other. They are harder to get right (practice question 3 shows a per-type version).
- Keep slow work outside the lock. Printing a ticket or waiting for a payment app while holding the lock makes every gate wait for that slow work.
Real measurement of the last point: 8 gates, 40 cars, printing takes 5 ms.
import java.util.*;
import java.util.concurrent.*;
class Lot {
private final boolean[] taken = new boolean[40];
private static void printTicket() { try { Thread.sleep(5); } catch (InterruptedException e) { } } // slow: 5 ms
synchronized int bookSlow() { // prints the ticket INSIDE the lock
int s = take(); printTicket(); return s;
}
int bookFast() { // locks only check-and-take
int s; synchronized (this) { s = take(); }
printTicket(); return s; // prints OUTSIDE the lock
}
private int take() { for (int i = 0; i < taken.length; i++) if (!taken[i]) { taken[i] = true; return i; } return -1; }
}
public class Main {
static long rush(boolean slow) throws Exception {
Lot lot = new Lot(); ExecutorService gates = Executors.newFixedThreadPool(8);
long start = System.nanoTime();
List<Future<Integer>> cars = new ArrayList<>();
for (int c = 0; c < 40; c++) cars.add(gates.submit(() -> slow ? lot.bookSlow() : lot.bookFast()));
for (Future<Integer> f : cars) f.get();
gates.shutdown();
return (System.nanoTime() - start) / 1_000_000;
}
public static void main(String[] args) throws Exception {
long slow = rush(true), fast = rush(false);
System.out.println("printing inside the lock: " + slow + " ms");
System.out.println("printing outside the lock: " + fast + " ms");
System.out.println("inside at least 200 ms (40 x 5 ms, one at a time)? " + (slow >= 200));
}
}
Output (one of three runs; the times change from run to run, and the other two runs gave 219 / 28 ms and 229 / 32 ms):
printing inside the lock: 217 ms
printing outside the lock: 33 ms
inside at least 200 ms (40 x 5 ms, one at a time)? true
(System.nanoTime() reads a timer in nanoseconds, billionths of a second; dividing by 1,000,000 gives milliseconds.) Inside the lock, the 40 prints happen strictly one at a time: at least 40 × 5 = 200 ms. Outside, up to 8 print at once.
Interview answer: start with one coarse lock, measure, and split it only if you must.
11. The running demo: everything together
Now all the parts in one program, folded to fit the screen. A running demo is a short main that drives the whole design end to end, so the interviewer sees it work (episode 55: always finish a machine-coding round with one).
The video's program:
import java.time.*; import java.util.*; enum VehicleType { BIKE, CAR, TRUCK } enum State { ACTIVE, PAID, EXITED }
enum SpotType { SMALL, COMPACT, LARGE; boolean fits(VehicleType v) { return ordinal() >= v.ordinal(); } }
record Spot(String id, SpotType type, int distance) {} interface PaymentMethod { String pay(int amount); }
interface PricingStrategy { int price(VehicleType v, long minutes); }
class Ticket { int id; VehicleType v; Spot spot; LocalDateTime in; State state = State.ACTIVE; // one visit
Ticket(int id, VehicleType v, Spot s, LocalDateTime in) { this.id = id; this.v = v; spot = s; this.in = in; } }
class ParkingLot {
final TreeSet<Spot> free = new TreeSet<>(Comparator.comparing(Spot::type).thenComparingInt(Spot::distance));
private final PricingStrategy pricing; private int nextId = 1; // free: smallest type first, then nearest
ParkingLot(List<Spot> spots, PricingStrategy pricing) { free.addAll(spots); this.pricing = pricing; }
synchronized Ticket enter(VehicleType v, LocalDateTime now) { // one gate at a time
for (Spot s : free) if (s.type().fits(v)) { free.remove(s); return new Ticket(nextId++, v, s, now); }
throw new IllegalStateException("full for " + v); }
synchronized String pay(Ticket t, PaymentMethod m, LocalDateTime now) { // ACTIVE -> PAID
if (t.state != State.ACTIVE) throw new IllegalStateException("ticket " + t.id + " is " + t.state);
t.state = State.PAID; return m.pay(pricing.price(t.v, Duration.between(t.in, now).toMinutes())); }
synchronized void exit(Ticket t) { // PAID -> EXITED, spot freed
if (t.state != State.PAID) throw new IllegalStateException("pay first: " + t.id + " is " + t.state);
t.state = State.EXITED; free.add(t.spot); } }
public class Main { public static void main(String[] args) {
PricingStrategy hourly = (v, min) -> (int) Math.max(1, (min + 59) / 60) * new int[]{ 10, 30, 60 }[v.ordinal()];
var spots = List.of(new Spot("C1", SpotType.COMPACT, 5), new Spot("S1", SpotType.SMALL, 12));
ParkingLot lot = new ParkingLot(spots, hourly); LocalDateTime ten = LocalDateTime.of(2026, 11, 14, 10, 0);
Ticket car = lot.enter(VehicleType.CAR, ten), bike = lot.enter(VehicleType.BIKE, ten);
System.out.println("car -> " + car.spot.id() + ", bike -> " + bike.spot.id());
System.out.println("car pays " + lot.pay(car, amount -> "Rs " + amount + " by UPI", ten.plusMinutes(130)));
lot.exit(car); System.out.println("car left, free: " + lot.free);
lot.exit(bike); }} // the bike tries to leave without paying
Output:
car -> C1, bike -> S1
car pays Rs 90 by UPI
car left, free: [Spot[id=C1, type=COMPACT, distance=5]]
Exception in thread "main" java.lang.IllegalStateException: pay first: 2 is ACTIVE
at ParkingLot.exit(Main.java:18)
at Main.main(Main.java:28)
What is new here:
Spotis a record: a short class whose only job is to carry values. Java writes the constructor, the accessor methodsid(),type(),distance(),equals,hashCodeandtoStringfor you; that is why a spot prints asSpot[id=C1, type=COMPACT, distance=5].- One
TreeSetof free spots, sorted by type first, then distance:Comparator.comparing(Spot::type).thenComparingInt(Spot::distance). Enums compare byordinal(), soSMALLspots come first. Walking this set and taking the first spot that fits gives the same smallest-then-nearest order asNearestFit, in a single set. (The walk is O(n) in the worst case;NearestFit's per-type sets stay O(log n).) enter,payandexitare allsynchronized: one gate at a time inside the lot.entertakes the first free spot that fits, removes it fromfreeand issues aTicket; if none fits it throwsfull for <type>.paychecks the state, prices the stay, and pays.exitchecks the ticket was paid and puts the spot back intofree: that is the release.PricingStrategyhas exactly one abstract method, so it is a functional interface, and any lambda with the right shape can be one.(v, min) -> ...is hourly pricing written in one line. The paymentamount -> "Rs " + amount + " by UPI"is aPaymentMethodwritten as a lambda the same way.var spots = ...lets Java work out the variable's type from the right-hand side (List<Spot>).
The car parks in C1 and the bike in S1 at 10:00. At 12:10 (130 minutes, 3 started hours) the car pays Rs 90 by UPI and leaves; C1 is free again. Then the bike tries to leave without paying: pay first: 2 is ACTIVE.
The cleaner version: final fields
To keep the lines short, the video's Ticket declares int id; VehicleType v; Spot spot; LocalDateTime in; as ordinary fields. That means any code could later write car.in = ... and change when the car arrived. In a real codebase, fields that are set once and must never change are final: a final field must be set in the constructor and can never be assigned again. Only state should change.
The cleaner version, unfolded, with final fields and one more improvement: pay sets PAID only after the payment succeeds, so a refused payment leaves the ticket ACTIVE. It also reads the free set through a synchronized method instead of touching the field from outside.
import java.time.*;
import java.util.*;
enum VehicleType { BIKE, CAR, TRUCK }
enum State { ACTIVE, PAID, EXITED }
enum SpotType {
SMALL, COMPACT, LARGE;
boolean fits(VehicleType v) { return ordinal() >= v.ordinal(); }
}
record Spot(String id, SpotType type, int distance) {}
interface PaymentMethod { String pay(int amount); }
interface PricingStrategy { int price(VehicleType v, long minutes); }
class Ticket { // one visit
final int id; // final: set once, in the constructor, never changed
final VehicleType vehicle;
final Spot spot;
final LocalDateTime entry;
State state = State.ACTIVE; // the only field that is meant to change
Ticket(int id, VehicleType vehicle, Spot spot, LocalDateTime entry) {
this.id = id; this.vehicle = vehicle; this.spot = spot; this.entry = entry;
}
}
class ParkingLot {
private final TreeSet<Spot> free = // smallest type first, then nearest
new TreeSet<>(Comparator.comparing(Spot::type).thenComparingInt(Spot::distance));
private final PricingStrategy pricing;
private int nextId = 1;
ParkingLot(List<Spot> spots, PricingStrategy pricing) { free.addAll(spots); this.pricing = pricing; }
synchronized Ticket enter(VehicleType v, LocalDateTime now) {
for (Spot s : free)
if (s.type().fits(v)) { free.remove(s); return new Ticket(nextId++, v, s, now); }
throw new IllegalStateException("full for " + v);
}
synchronized String pay(Ticket t, PaymentMethod m, LocalDateTime now) { // ACTIVE -> PAID
if (t.state != State.ACTIVE) throw new IllegalStateException("ticket " + t.id + " is " + t.state);
int amount = pricing.price(t.vehicle, Duration.between(t.entry, now).toMinutes());
String receipt = m.pay(amount); // if the payment throws, the ticket stays ACTIVE
t.state = State.PAID;
return receipt;
}
synchronized void exit(Ticket t) { // PAID -> EXITED
if (t.state != State.PAID) throw new IllegalStateException("pay first: " + t.id + " is " + t.state);
t.state = State.EXITED;
free.add(t.spot); // the release
}
synchronized String freeSpots() { return free.toString(); }
}
public class Main {
public static void main(String[] args) {
int[] rate = { 10, 30, 60 };
PricingStrategy hourly = (v, min) -> (int) Math.max(1, (min + 59) / 60) * rate[v.ordinal()];
ParkingLot lot = new ParkingLot(
List.of(new Spot("C1", SpotType.COMPACT, 5), new Spot("S1", SpotType.SMALL, 12)), hourly);
LocalDateTime ten = LocalDateTime.of(2026, 11, 14, 10, 0);
Ticket car = lot.enter(VehicleType.CAR, ten), bike = lot.enter(VehicleType.BIKE, ten);
System.out.println("car -> " + car.spot.id() + ", bike -> " + bike.spot.id());
System.out.println("car pays " + lot.pay(car, amount -> "Rs " + amount + " by UPI", ten.plusMinutes(130)));
lot.exit(car);
System.out.println("car left, free: " + lot.freeSpots());
// car.entry = ten.minusHours(5); // would not compile: cannot assign a value to final variable entry
lot.exit(bike); // the bike tries to leave without paying
}
}
Output:
car -> C1, bike -> S1
car pays Rs 90 by UPI
car left, free: [Spot[id=C1, type=COMPACT, distance=5]]
Exception in thread "main" java.lang.IllegalStateException: pay first: 2 is ACTIVE
at ParkingLot.exit(Main.java:47)
at Main.main(Main.java:67)
Same behaviour. And if you remove the // from the line car.entry = ten.minusHours(5);, the compiler refuses it:
Main.java:66: error: cannot assign a value to final variable entry
car.entry = ten.minusHours(5);
^
1 error
An object whose fields can't change after it is built is called immutable; a Ticket is now immutable except for its lifecycle state, which only ParkingLot changes. Immutable data is also safer with threads: no thread can see it half-changed.
12. The class diagram, and interview follow-ups
ParkingLot (one object, made in main)
├─uses──▶ SpotAllocationStrategy ── FirstFree · NearestFit (TreeSet per SpotType)
├─uses──▶ PricingStrategy ── HourlyPricing · FlatPricing
├─issues▶ Ticket ── State: ACTIVE ──pay──▶ PAID ──exit──▶ EXITED
└─takes─▶ PaymentMethod ── Upi · Card · Cash
enter / pay / exit are synchronized: one gate at a time
Read it as: the ParkingLot is one object, made in main (part 1's lesson: no singleton). It uses an allocation strategy and a pricing strategy, each with interchangeable implementations. It issues tickets that move ACTIVE → PAID → EXITED, and takes any payment method. enter, pay and exit are synchronized, so many gates can work at once safely.
What the interviewer asks next:
| Follow-up | Answer |
|---|---|
| Lost ticket | Add a LOST state and a fixed penalty price (practice question 1) |
| Night rates, weekend rates | A PricingStrategy that splits the stay into parts and prices each, or wraps another strategy (practice question 2) |
| Nearest to which gate? | Each spot gets a distance per gate, and each gate keeps its own sorted set of free spots |
| Electric-vehicle (EV) charging | A new spot type for charging spots; pricing adds the energy used |
| Many lots in one app | Store lots and tickets behind repositories (episode 45): objects that hide where data is stored |
| One lock is too slow | Finer locking: a lock per floor or per spot type; slow work outside the lock |
| Testing time-based prices | Inject a Clock; use Clock.fixed and Clock.offset in tests (section 6) |
13. Common mistakes
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| First free spot for everyone | CAR -> NONE, TRUCK -> NONE |
Bikes took the big spots | NearestFit: smallest type first, then nearest |
hours = minutes / 60 |
parked 179 min, naive hours = minutes / 60 = 2 |
Integer division drops the fraction | (minutes + 59) / 60 |
| Forgetting the minimum charge | 0 minutes billed Rs 0 | (0 + 59) / 60 is 0 |
Math.max(1, hours) |
| No ticket lifecycle | Double exits and free rides, silently | Nothing tracks the ticket's state | Check the state on every action; with it you see java.lang.IllegalStateException: can't exit ticket 1, it's EXITED |
| Paying twice | java.lang.IllegalStateException: ticket 1 is PAID |
That's the guard working | Show "already paid" to the driver |
| Cash less than the bill | java.lang.IllegalArgumentException: Rs 20 is less than Rs 30 |
Bad argument | Ask for more money; ticket stays ACTIVE |
Marking PAID before the payment succeeds |
A refused payment still opens the barrier | State changed too early | Pay first, then move to PAID |
| Check-then-act without a lock | no lock : 40 tickets for 5 different spots |
Race condition | synchronized booking |
| Locking a different object per gate | tickets > spots: 40 vs 5 |
Each thread holds its own lock | Lock the one object that owns the spots |
| Slow work inside the lock | printing inside the lock: 217 ms |
Lock held too long | Lock only check-and-take |
TreeSet sorted only by distance |
add S2 (12 m): false, one spot vanishes |
Equal comparator result = same element | Add a tie-breaker: .thenComparing(Spot::id) |
TreeSet with no Comparator |
java.lang.ClassCastException: class Spot cannot be cast to class java.lang.Comparable |
It doesn't know how to order spots | Pass a Comparator, or make Spot Comparable |
Assigning a final field |
error: cannot assign a value to final variable entry |
Set-once data | Good: the compiler protects it |
The ones not already shown above, run for real.
Paying twice (and a full lot), with the video's ParkingLot and one compact spot:
import java.time.*; import java.util.*; enum VehicleType { BIKE, CAR, TRUCK } enum State { ACTIVE, PAID, EXITED }
enum SpotType { SMALL, COMPACT, LARGE; boolean fits(VehicleType v) { return ordinal() >= v.ordinal(); } }
record Spot(String id, SpotType type, int distance) {} interface PaymentMethod { String pay(int amount); }
interface PricingStrategy { int price(VehicleType v, long minutes); }
class Ticket { int id; VehicleType v; Spot spot; LocalDateTime in; State state = State.ACTIVE; // one visit
Ticket(int id, VehicleType v, Spot s, LocalDateTime in) { this.id = id; this.v = v; spot = s; this.in = in; } }
class ParkingLot {
final TreeSet<Spot> free = new TreeSet<>(Comparator.comparing(Spot::type).thenComparingInt(Spot::distance));
private final PricingStrategy pricing; private int nextId = 1; // free: smallest type first, then nearest
ParkingLot(List<Spot> spots, PricingStrategy pricing) { free.addAll(spots); this.pricing = pricing; }
synchronized Ticket enter(VehicleType v, LocalDateTime now) { // one gate at a time
for (Spot s : free) if (s.type().fits(v)) { free.remove(s); return new Ticket(nextId++, v, s, now); }
throw new IllegalStateException("full for " + v); }
synchronized String pay(Ticket t, PaymentMethod m, LocalDateTime now) { // ACTIVE -> PAID
if (t.state != State.ACTIVE) throw new IllegalStateException("ticket " + t.id + " is " + t.state);
t.state = State.PAID; return m.pay(pricing.price(t.v, Duration.between(t.in, now).toMinutes())); }
synchronized void exit(Ticket t) { // PAID -> EXITED, spot freed
if (t.state != State.PAID) throw new IllegalStateException("pay first: " + t.id + " is " + t.state);
t.state = State.EXITED; free.add(t.spot); } }
public class Main { public static void main(String[] args) {
PricingStrategy hourly = (v, min) -> (int) Math.max(1, (min + 59) / 60) * new int[]{ 10, 30, 60 }[v.ordinal()];
ParkingLot lot = new ParkingLot(List.of(new Spot("C1", SpotType.COMPACT, 5)), hourly);
LocalDateTime ten = LocalDateTime.of(2026, 11, 14, 10, 0);
Ticket car = lot.enter(VehicleType.CAR, ten);
try { lot.enter(VehicleType.TRUCK, ten); } catch (IllegalStateException e) { System.out.println(e); }
System.out.println(lot.pay(car, a -> "Rs " + a + " by UPI", ten.plusMinutes(45)));
System.out.println(lot.pay(car, a -> "Rs " + a + " by UPI", ten.plusMinutes(46))); // pays again
}}
Output:
java.lang.IllegalStateException: full for TRUCK
Rs 30 by UPI
Exception in thread "main" java.lang.IllegalStateException: ticket 1 is PAID
at ParkingLot.pay(Main.java:15)
at Main.main(Main.java:27)
The truck finds no spot (full for TRUCK; we caught and printed the exception, and println(e) prints its type and message). The car pays Rs 30 for 45 minutes, then tries again: ticket 1 is PAID.
Two spots at the same distance:
import java.util.*;
class Spot { final String id; final int distance;
Spot(String id, int distance) { this.id = id; this.distance = distance; } }
public class Main {
public static void main(String[] args) {
TreeSet<Spot> byDistance = new TreeSet<>(Comparator.comparingInt((Spot s) -> s.distance));
System.out.println("add S1 (12 m): " + byDistance.add(new Spot("S1", 12)));
System.out.println("add S2 (12 m): " + byDistance.add(new Spot("S2", 12))); // same distance!
System.out.println("free small spots: " + byDistance.size());
TreeSet<Spot> fixed = new TreeSet<>(Comparator.comparingInt((Spot s) -> s.distance).thenComparing(s -> s.id));
fixed.add(new Spot("S1", 12)); fixed.add(new Spot("S2", 12));
System.out.println("with a tie-breaker on id: " + fixed.size());
}
}
Output:
add S1 (12 m): true
add S2 (12 m): false
free small spots: 1
with a tie-breaker on id: 2
A TreeSet decides "same element" by the comparator, not by equals: if the comparator says 0 (equal distances), the second spot is treated as a duplicate and add returns false. That spot is now invisible to the allocator forever. thenComparing(s -> s.id) breaks the tie, and both stay.
A TreeSet that can't sort:
import java.util.*;
class Spot { final String id; final int distance;
Spot(String id, int distance) { this.id = id; this.distance = distance; } }
public class Main {
public static void main(String[] args) {
TreeSet<Spot> free = new TreeSet<>(); // no Comparator, and Spot is not Comparable
free.add(new Spot("S1", 12));
}
}
Output:
Exception in thread "main" java.lang.ClassCastException: class Spot cannot be cast to class java.lang.Comparable (Spot is in unnamed module of loader 'app'; java.lang.Comparable is in module java.base of loader 'bootstrap')
at java.base/java.util.TreeMap.compare(TreeMap.java:1604)
at java.base/java.util.TreeMap.addEntryToEmptyMap(TreeMap.java:811)
at java.base/java.util.TreeMap.put(TreeMap.java:820)
at java.base/java.util.TreeMap.put(TreeMap.java:569)
at java.base/java.util.TreeSet.add(TreeSet.java:259)
at Main.main(Main.java:7)
With no Comparator, a TreeSet expects its elements to be Comparable (an interface for classes that know their own natural order, like Integer or String). Spot isn't, so the very first add throws a ClassCastException (Java tried to treat an object as a type it isn't).
Mini project: a thread-safe, fully pluggable parking lot
Goal: put every part of both episodes behind its interface and run a whole day.
ParkingLottakes aSpotAllocationStrategy(NearestFit, with the tie-breaker), aPricingStrategy(HourlyPricing) and aClock.enteris synchronized on the lot: check-and-take is one step. 20 cars rush in at 8 gates at once.paylocks only the ticket (fine-grained), so a slow payment at one counter doesn't stop the gates. If the payment throws, the ticket staysACTIVE.exitis synchronized on the lot because it releases a spot. (Lock order is always lot, then ticket, andpaynever takes the lot's lock, so two threads can never wait for each other forever: that would be a deadlock.)- A
TestClock(aClockwhose time a test can move forward) makes the bills exact. Its time field isvolatile, which makes a write by one thread visible to other threads straight away.
import java.time.*;
import java.util.*;
import java.util.concurrent.*;
enum VehicleType { BIKE, CAR, TRUCK }
enum SpotType {
SMALL, COMPACT, LARGE;
boolean fits(VehicleType v) { return ordinal() >= v.ordinal(); }
}
enum State { ACTIVE, PAID, EXITED }
record Spot(String id, SpotType type, int distance) {}
// ---------- allocation ----------
interface SpotAllocationStrategy { Optional<Spot> pick(VehicleType v); void release(Spot s); }
class NearestFit implements SpotAllocationStrategy { // not thread-safe: the lot locks around it
private final Map<SpotType, TreeSet<Spot>> free = new EnumMap<>(SpotType.class);
NearestFit(List<Spot> spots) {
for (SpotType t : SpotType.values())
free.put(t, new TreeSet<>(Comparator.comparingInt(Spot::distance).thenComparing(Spot::id)));
for (Spot s : spots) free.get(s.type()).add(s);
}
public Optional<Spot> pick(VehicleType v) {
for (SpotType t : SpotType.values())
if (t.fits(v) && !free.get(t).isEmpty()) return Optional.of(free.get(t).pollFirst());
return Optional.empty();
}
public void release(Spot s) { free.get(s.type()).add(s); }
public String toString() { return free.toString(); }
}
// ---------- pricing ----------
interface PricingStrategy { int price(VehicleType v, long minutes); }
class HourlyPricing implements PricingStrategy {
private final int[] ratePerHour = { 10, 30, 60 }; // made-up tariff
public int price(VehicleType v, long minutes) {
return (int) Math.max(1, (minutes + 59) / 60) * ratePerHour[v.ordinal()];
}
}
// ---------- payment ----------
interface PaymentMethod { String pay(int amount); }
class Upi implements PaymentMethod {
private final String id; Upi(String id) { this.id = id; }
public String pay(int amount) { return "Rs " + amount + " by UPI from " + id; }
}
class Card implements PaymentMethod {
private final String last4; Card(String last4) { this.last4 = last4; }
public String pay(int amount) { return "Rs " + amount + " by card ending " + last4; }
}
class Cash implements PaymentMethod {
private final int given; Cash(int given) { this.given = given; }
public String pay(int amount) {
if (given < amount) throw new IllegalArgumentException("Rs " + given + " is less than Rs " + amount);
return "Rs " + amount + " in cash, change Rs " + (given - amount);
}
}
// ---------- ticket ----------
class Ticket {
final int id; final VehicleType vehicle; final Spot spot; final LocalDateTime entry;
private State state = State.ACTIVE;
Ticket(int id, VehicleType vehicle, Spot spot, LocalDateTime entry) {
this.id = id; this.vehicle = vehicle; this.spot = spot; this.entry = entry;
}
synchronized State state() { return state; }
synchronized void require(State s, String action) {
if (state != s) throw new IllegalStateException("can't " + action + " ticket " + id + ", it's " + state);
}
synchronized void moveTo(State from, State to, String action) { // the only way the state changes
require(from, action);
state = to;
}
}
// ---------- a clock a test can move ----------
class TestClock extends Clock {
private volatile Instant now; private final ZoneId zone;
TestClock(Instant start, ZoneId zone) { now = start; this.zone = zone; }
void advance(Duration d) { now = now.plus(d); }
public Instant instant() { return now; }
public ZoneId getZone() { return zone; }
public Clock withZone(ZoneId z) { return new TestClock(now, z); }
}
// ---------- the lot ----------
class ParkingLot {
private final SpotAllocationStrategy allocation;
private final PricingStrategy pricing;
private final Clock clock;
private int nextId = 1;
ParkingLot(SpotAllocationStrategy allocation, PricingStrategy pricing, Clock clock) {
this.allocation = allocation; this.pricing = pricing; this.clock = clock;
}
synchronized Optional<Ticket> enter(VehicleType v) { // check-and-take as ONE step
return allocation.pick(v).map(s -> new Ticket(nextId++, v, s, LocalDateTime.now(clock)));
}
int amountDue(Ticket t) { // pure maths: no lock needed
return pricing.price(t.vehicle, Duration.between(t.entry, LocalDateTime.now(clock)).toMinutes());
}
String pay(Ticket t, PaymentMethod m) { // locks the TICKET, not the lot
synchronized (t) { // fine-grained: other gates keep working
t.require(State.ACTIVE, "pay");
String receipt = m.pay(amountDue(t)); // may throw: then the ticket stays ACTIVE
t.moveTo(State.ACTIVE, State.PAID, "pay");
return receipt;
}
}
synchronized void exit(Ticket t) {
t.moveTo(State.PAID, State.EXITED, "exit");
allocation.release(t.spot);
}
synchronized String free() { return allocation.toString(); }
}
public class Main {
public static void main(String[] args) throws Exception {
List<Spot> spots = List.of(
new Spot("S1", SpotType.SMALL, 20), new Spot("S2", SpotType.SMALL, 12),
new Spot("C1", SpotType.COMPACT, 5), new Spot("C2", SpotType.COMPACT, 9), new Spot("C3", SpotType.COMPACT, 15),
new Spot("L1", SpotType.LARGE, 8), new Spot("L2", SpotType.LARGE, 25));
ZoneId zone = ZoneId.of("Asia/Kolkata");
TestClock clock = new TestClock(LocalDateTime.of(2026, 11, 14, 10, 0).atZone(zone).toInstant(), zone);
ParkingLot lot = new ParkingLot(new NearestFit(spots), new HourlyPricing(), clock);
// 1. Saturday rush: 20 cars at 8 gates, all at once
ExecutorService gates = Executors.newFixedThreadPool(8);
List<Future<Optional<Ticket>>> rush = new ArrayList<>();
for (int i = 0; i < 20; i++) rush.add(gates.submit(() -> lot.enter(VehicleType.CAR)));
List<Ticket> cars = new ArrayList<>();
for (Future<Optional<Ticket>> f : rush) f.get().ifPresent(cars::add);
gates.shutdown();
cars.sort(Comparator.comparingInt(t -> t.id));
System.out.println("rush: " + cars.size() + " cars parked, " + (20 - cars.size()) + " turned away");
for (Ticket t : cars) System.out.print(" #" + t.id + "->" + t.spot.id());
System.out.println();
// 2. a bike and a truck arrive
Ticket bike = lot.enter(VehicleType.BIKE).orElseThrow();
System.out.println("bike -> " + bike.spot.id());
System.out.println("truck -> " + lot.enter(VehicleType.TRUCK).map(t -> t.spot.id()).orElse("NONE (lot full for trucks)"));
// 3. 61 minutes later the cars pay and leave
clock.advance(Duration.ofMinutes(61));
PaymentMethod[] methods = { new Upi("asha@upi"), new Card("4242"), new Cash(100), new Cash(60), new Upi("ravi@upi") };
for (int i = 0; i < cars.size(); i++) {
Ticket t = cars.get(i);
System.out.println(" #" + t.id + " " + lot.pay(t, methods[i]));
lot.exit(t);
}
System.out.println("free now: " + lot.free());
System.out.println("truck -> " + lot.enter(VehicleType.TRUCK).map(t -> t.spot.id()).orElse("NONE"));
// 4. the lifecycle refuses wrong moves
try { lot.exit(bike); } catch (IllegalStateException e) { System.out.println("refused: " + e.getMessage()); }
try { lot.pay(cars.get(0), new Upi("asha@upi")); } catch (IllegalStateException e) { System.out.println("refused: " + e.getMessage()); }
clock.advance(Duration.ofMinutes(120)); // bike stayed 181 minutes in all
try { lot.pay(bike, new Cash(20)); } catch (IllegalArgumentException e) { System.out.println("refused: " + e.getMessage() + ", ticket still " + bike.state()); }
System.out.println("bike pays " + lot.pay(bike, new Cash(50)));
lot.exit(bike);
System.out.println("bike left at " + LocalDateTime.now(clock).toLocalTime());
}
}
Output:
rush: 5 cars parked, 15 turned away
#1->C1 #2->C2 #3->C3 #4->L1 #5->L2
bike -> S2
truck -> NONE (lot full for trucks)
#1 Rs 60 by UPI from asha@upi
#2 Rs 60 by card ending 4242
#3 Rs 60 in cash, change Rs 40
#4 Rs 60 in cash, change Rs 0
#5 Rs 60 by UPI from ravi@upi
free now: {SMALL=[Spot[id=S1, type=SMALL, distance=20]], COMPACT=[Spot[id=C1, type=COMPACT, distance=5], Spot[id=C2, type=COMPACT, distance=9], Spot[id=C3, type=COMPACT, distance=15]], LARGE=[Spot[id=L1, type=LARGE, distance=8], Spot[id=L2, type=LARGE, distance=25]]}
truck -> L1
refused: can't exit ticket 6, it's ACTIVE
refused: can't pay ticket 1, it's EXITED
refused: Rs 20 is less than Rs 40, ticket still ACTIVE
bike pays Rs 40 in cash, change Rs 10
bike left at 13:01
What happened:
- 20 cars at 8 gates, 7 spots, 2 of them small (no car fits): exactly 5 cars parked, 15 turned away. Because
enteris synchronized, ticket numbers and spots are handed out together, so ticket 1 always gets the nearest compactC1, and so on, whichever thread wins. The program was run twice; the output was the same. - The bike gets
S2, the nearer small spot. The truck finds both large spots taken by cars. - At 11:01 (61 minutes) every car pays Rs 60 (2 started hours) by four different methods and leaves; the spots go back into their sets, nearest first. Now the truck gets
L1. - The lifecycle refuses the bike's exit without paying and ticket 1's second payment. A Rs 20 note for the bike's Rs 40 bill (181 minutes = 4 started hours × Rs 10) is refused and the ticket stays ACTIVE; then Rs 50 works, with Rs 10 change.
f.get().ifPresent(cars::add)adds the ticket to the list only if the Optional holds one.orElseThrow()takes the value out of an Optional, or throws if it is empty.
Practice
1. Add a LOST state: a driver who lost the slip reports it, pays a fixed penalty of Rs 200 (made up), then exits. A ticket that has already exited can't be reported lost.
Answer
enum State { ACTIVE, LOST, PAID, EXITED }
class Ticket {
static final int LOST_PENALTY = 200; // made-up fixed penalty, in rupees
final int id; private final int amount; private State state = State.ACTIVE;
Ticket(int id, int amount) { this.id = id; this.amount = amount; }
void reportLost() { require(State.ACTIVE, "report lost"); state = State.LOST; } // ACTIVE -> LOST
int amountDue() { return state == State.LOST ? LOST_PENALTY : amount; }
void pay() { // ACTIVE -> PAID, or LOST -> PAID
if (state != State.ACTIVE && state != State.LOST)
throw new IllegalStateException("can't pay ticket " + id + ", it's " + state);
System.out.println(id + ": paid Rs " + amountDue()); state = State.PAID;
}
void exit() { require(State.PAID, "exit"); state = State.EXITED; System.out.println(id + ": barrier up"); }
private void require(State s, String what) {
if (state != s) throw new IllegalStateException("can't " + what + " ticket " + id + ", it's " + state);
}
}
public class Main {
public static void main(String[] args) {
Ticket t1 = new Ticket(1, 90), t2 = new Ticket(2, 90);
t1.pay(); t1.exit(); // normal visit
t2.reportLost(); t2.pay(); t2.exit(); // lost slip: the penalty instead
t2.reportLost(); // too late: already EXITED
}
}
Output:
1: paid Rs 90
1: barrier up
2: paid Rs 200
2: barrier up
Exception in thread "main" java.lang.IllegalStateException: can't report lost ticket 2, it's EXITED
at Ticket.require(Main.java:15)
at Ticket.reportLost(Main.java:6)
at Main.main(Main.java:23)
The lifecycle grows one state and two transitions: ACTIVE → LOST and LOST → PAID. Nothing outside Ticket changes.
2. Write a weekend PricingStrategy that charges double on Saturday and Sunday, reusing HourlyPricing for the base price.
Answer
WeekendPricing wraps another PricingStrategy and changes its result. An object that wraps another of the same interface to add behaviour is the Decorator pattern. getDayOfWeek() gives a DayOfWeek, an enum of the seven days.
import java.time.*;
enum VehicleType { BIKE, CAR, TRUCK }
interface PricingStrategy { int price(VehicleType v, LocalDateTime in, LocalDateTime out); }
class HourlyPricing implements PricingStrategy {
private final int[] ratePerHour = { 10, 30, 60 };
public int price(VehicleType v, LocalDateTime in, LocalDateTime out) {
long hours = (Duration.between(in, out).toMinutes() + 59) / 60;
return (int) Math.max(1, hours) * ratePerHour[v.ordinal()];
}
}
class WeekendPricing implements PricingStrategy { // wraps another strategy
private final PricingStrategy weekday; private final int factor;
WeekendPricing(PricingStrategy weekday, int factor) { this.weekday = weekday; this.factor = factor; }
public int price(VehicleType v, LocalDateTime in, LocalDateTime out) {
DayOfWeek d = in.getDayOfWeek();
boolean weekend = d == DayOfWeek.SATURDAY || d == DayOfWeek.SUNDAY;
return weekday.price(v, in, out) * (weekend ? factor : 1);
}
}
public class Main {
public static void main(String[] args) {
PricingStrategy pricing = new WeekendPricing(new HourlyPricing(), 2);
LocalDateTime fri = LocalDateTime.of(2026, 11, 13, 10, 0), sat = LocalDateTime.of(2026, 11, 14, 10, 0);
System.out.println(fri.getDayOfWeek() + ", car 2 h: Rs " + pricing.price(VehicleType.CAR, fri, fri.plusHours(2)));
System.out.println(sat.getDayOfWeek() + ", car 2 h: Rs " + pricing.price(VehicleType.CAR, sat, sat.plusHours(2)));
}
}
Output:
FRIDAY, car 2 h: Rs 60
SATURDAY, car 2 h: Rs 120
3. Make NearestFit thread-safe on its own (without relying on the lot's lock). Then write a fine-grained version with one lock per spot type. Test both with 8 gates and 40 vehicles on 12 spots.
Answer
The coarse version adds synchronized to pick and release. The fine-grained version locks only the one TreeSet it touches; pollFirst() returns null on an empty set, so "check and take" is a single call inside the lock. The map itself is filled in the constructor and never changed afterwards, so reading it without a lock is safe.
import java.util.*;
import java.util.concurrent.*;
enum VehicleType { BIKE, CAR, TRUCK }
enum SpotType { SMALL, COMPACT, LARGE; boolean fits(VehicleType v) { return ordinal() >= v.ordinal(); } }
record Spot(String id, SpotType type, int distance) {}
interface SpotAllocationStrategy { Optional<Spot> pick(VehicleType v); void release(Spot s); }
class SafeNearestFit implements SpotAllocationStrategy { // coarse: one lock for the whole strategy
private final Map<SpotType, TreeSet<Spot>> free = new EnumMap<>(SpotType.class);
SafeNearestFit(List<Spot> spots) {
for (SpotType t : SpotType.values())
free.put(t, new TreeSet<>(Comparator.comparingInt(Spot::distance).thenComparing(Spot::id)));
for (Spot s : spots) free.get(s.type()).add(s);
}
public synchronized Optional<Spot> pick(VehicleType v) {
for (SpotType t : SpotType.values())
if (t.fits(v) && !free.get(t).isEmpty()) return Optional.of(free.get(t).pollFirst());
return Optional.empty();
}
public synchronized void release(Spot s) { free.get(s.type()).add(s); }
}
class PerTypeNearestFit implements SpotAllocationStrategy { // fine-grained: one lock per SpotType
private final Map<SpotType, TreeSet<Spot>> free = new EnumMap<>(SpotType.class);
PerTypeNearestFit(List<Spot> spots) {
for (SpotType t : SpotType.values())
free.put(t, new TreeSet<>(Comparator.comparingInt(Spot::distance).thenComparing(Spot::id)));
for (Spot s : spots) free.get(s.type()).add(s); // the map itself never changes after this
}
public Optional<Spot> pick(VehicleType v) {
for (SpotType t : SpotType.values()) {
if (!t.fits(v)) continue;
TreeSet<Spot> set = free.get(t);
synchronized (set) { // lock only this type's set
Spot s = set.pollFirst(); // null if empty: check and take in one call
if (s != null) return Optional.of(s);
}
}
return Optional.empty();
}
public void release(Spot s) { TreeSet<Spot> set = free.get(s.type()); synchronized (set) { set.add(s); } }
}
public class Main {
static void rush(String name, SpotAllocationStrategy strategy) throws Exception {
ExecutorService gates = Executors.newFixedThreadPool(8);
List<Future<Optional<Spot>>> results = new ArrayList<>();
VehicleType[] kinds = VehicleType.values();
for (int i = 0; i < 40; i++) { VehicleType v = kinds[i % 3]; results.add(gates.submit(() -> strategy.pick(v))); }
int tickets = 0; Set<String> ids = new HashSet<>();
for (Future<Optional<Spot>> f : results) { Optional<Spot> s = f.get(); if (s.isPresent()) { tickets++; ids.add(s.get().id()); } }
gates.shutdown();
System.out.println(name + ": " + tickets + " tickets for " + ids.size() + " different spots");
}
public static void main(String[] args) throws Exception {
List<Spot> spots = new ArrayList<>();
for (int i = 1; i <= 4; i++) {
spots.add(new Spot("S" + i, SpotType.SMALL, 10 + i));
spots.add(new Spot("C" + i, SpotType.COMPACT, 20 + i));
spots.add(new Spot("L" + i, SpotType.LARGE, 30 + i));
}
rush("one lock ", new SafeNearestFit(spots));
rush("lock per type", new PerTypeNearestFit(spots));
}
}
Output:
one lock : 12 tickets for 12 different spots
lock per type: 12 tickets for 12 different spots
40 vehicles, 12 spots: both versions hand out exactly 12 tickets for 12 different spots. With per-type locks a bike taking a small spot never waits for a truck taking a large one. (Practice: try removing synchronized from SafeNearestFit and run it a few times.)
4. Add a Wallet payment method with a balance. Which existing classes change?
Answer
None. Wallet is one new class implementing PaymentMethod; checkout knows only the interface.
interface PaymentMethod { String pay(int amount); }
class Upi implements PaymentMethod { private final String id; Upi(String id) { this.id = id; }
public String pay(int amount) { return "Rs " + amount + " by UPI from " + id; } }
class Wallet implements PaymentMethod { // the new method: one new class, nothing else changes
private int balance; Wallet(int balance) { this.balance = balance; }
public String pay(int amount) {
if (balance < amount) throw new IllegalStateException("wallet has Rs " + balance + ", needs Rs " + amount);
balance -= amount;
return "Rs " + amount + " from wallet, Rs " + balance + " left";
}
}
public class Main {
static void checkout(int amount, PaymentMethod m) { System.out.println(m.pay(amount)); } // knows only the interface
public static void main(String[] args) {
Wallet w = new Wallet(100);
checkout(60, new Upi("asha@upi"));
checkout(60, w);
checkout(60, w); // only Rs 40 left
}
}
Output:
Rs 60 by UPI from asha@upi
Rs 60 from wallet, Rs 40 left
Exception in thread "main" java.lang.IllegalStateException: wallet has Rs 40, needs Rs 60
at Wallet.pay(Main.java:7)
at Main.checkout(Main.java:13)
at Main.main(Main.java:18)
5. A truck enters at 09:30 and leaves at 09:30 the same day (it turned round at the barrier). What does HourlyPricing charge, and which line decides it?
Answer
Rs 60. The stay is 0 minutes, (0 + 59) / 60 = 0 hours, and Math.max(1, hours) raises it to the one-hour minimum: 1 × Rs 60. (The edge-case table in section 6 shows 0 minutes → 1 hour, run for real.)
6. Why is release in NearestFit O(log n) and not O(1)?
Answer
Putting a spot back into a TreeSet must find its sorted place in the tree, which takes about log₂ n steps. That is the price of having the nearest spot always at the front (an O(log n) pollFirst instead of an O(n) scan).
7. In the race program, why does bookSafe give 10 tickets but bookUnsafe 40, when both call the same book()?
Answer
book() is check-then-act with a 1 ms gap between the check (!taken[i]) and the act (taken[i] = true). Without a lock, other threads check during that gap and see the spot as free. synchronized makes the whole book() one indivisible step per thread, so the next check always sees the previous take.
Quick quiz
HourlyPricing: car Rs 30 per started hour, minimum 1 hour. Entry 10:00, exit 11:01, hours = (minutes + 59) / 60. What does the car pay? (a) Rs 30 (b) Rs 60 (c) Rs 31 (d) Rs 90
Answer
(b) Rs 60. 61 minutes: (61 + 59) / 60 = 120 / 60 = 2 started hours, so 2 × 30 = Rs 60. One minute into the second hour starts it. (The Clock program in section 6 prints exactly this: exit at 11:01 (61 min): car pays Rs 60.)
Interview questions
- How do you choose a spot? Behind a
SpotAllocationStrategyinterface. The default is nearest fit: the smallest spot type that fits, then the nearest spot inside it. First-fit wastes big spots on small vehicles. - How do you find a free spot fast? Availability tracking: keep only the free spots, one
TreeSetper spot type sorted by distance. Take the nearest withpollFirst()and give it back withadd, both O(log n). Remember a tie-breaker in the comparator. - How do you bill per started hour?
(minutes + 59) / 60, with a minimum of one hour. Plainminutes / 60uses integer division and drops the part hour. - Hourly or flat pricing: where does that choice live? In a
PricingStrategypassed to the lot. Event nights getFlatPricing; nothing else changes. Weekend or night rates are new strategies (or wrappers). - How do you add a new payment method? One new class implementing
PaymentMethod. The lot only knows the interface (Strategy pattern): new behaviour is added by new code, not by editing old code. - What stops paying twice or leaving without paying? The ticket lifecycle
ACTIVE → PAID → EXITED: every action checks the current state and throwsIllegalStateExceptionon a wrong move. Change toPAIDonly after the payment succeeds. - Two gates book the last spot at the same moment. What happens, and how do you fix it? Check-then-act race: both see it free, both take it. Make check-and-take one indivisible step: a
synchronizedmethod on the one lot object (or a lock per spot type, or an atomic "take" likepollFirstinside a lock). - Isn't one lock for the whole lot slow? Booking is microseconds, so start coarse; measure; split per floor or per type only if needed. Keep slow work (printing, payment calls) outside the lock.
- How do you test time-based pricing? Pass times in, or inject a
Clockand useClock.fixed/Clock.offsetin tests. Never callLocalDateTime.now()with no argument deep inside the logic. - Should
ParkingLotbe a singleton? No (part 1): one object made inmainand passed in; tests can make a fresh lot each time.
Glossary
| Term | Meaning, with an example |
|---|---|
| Parking lot (LLD problem) | A classic machine-coding problem: model spots, vehicles, tickets and gates, then allocation, pricing and payment |
| Machine-coding round | An interview round where you design and code a small working system in about 60-120 minutes |
| Spot allocation | Choosing which free spot a vehicle gets |
| Spot allocation strategy | An interface for that choice, so the rule can be swapped: SpotAllocationStrategy with pick and release |
First-fit (FirstFree) |
Take the first free spot that fits, in list order; wastes big spots on small vehicles |
Nearest spot strategy (NearestFit) |
Smallest spot type that fits, then the spot nearest the gate: a bike gets S2 (12 m) before C1 |
| Availability tracking | Keeping an always-up-to-date collection of free spots, so finding one needs no scan |
| Release | Giving a spot back to the free collection when its vehicle leaves |
| Pricing strategy | An interface that turns a stay into an amount: PricingStrategy.price(...) |
| Hourly pricing | A rate for every started hour: car Rs 30 × 3 hours = Rs 90 (made-up tariff) |
| Flat pricing | One fixed price per visit, however long: Rs 100 on a concert night |
| Hourly vs flat pricing | Two interchangeable PricingStrategy classes, chosen per night |
| Started hour | Any part of an hour counts as a whole hour: 61 minutes = 2 started hours |
| Minimum charge | The least you pay: Math.max(1, hours) bills 0 minutes as 1 hour |
| Payment | The step where the driver pays the amount due, by some method |
| Payment strategy | Payment methods behind one interface: PaymentMethod with Upi, Card, Cash |
| UPI | A phone-based bank payment method; here just one PaymentMethod class |
| Change | Cash handed over minus the bill: Rs 50 for Rs 30 gives Rs 20 |
| Ticket lifecycle | The states a ticket moves through: ACTIVE → PAID → EXITED |
| State | Where an object is in its life right now: a ticket is PAID |
| Transition | An allowed move from one state to another: pay() moves ACTIVE to PAID |
| State machine | A fixed set of states plus the allowed transitions; everything else is refused (episode 37) |
Guard (require) |
A check at the start of an action that refuses it in the wrong state |
| Concurrent | Happening at the same time: 8 gates booking at once |
| Concurrent spot booking | Several gates (threads) booking spots from the same lot at the same moment |
| Thread | A separate line of execution in the same program, sharing its objects: each gate runs as one |
| Thread pool | A fixed group of reusable worker threads that run submitted tasks: Executors.newFixedThreadPool(8) |
| ExecutorService | Java's interface for a thread pool: submit a task, shutdown when done |
| Executors | A Java class with factory methods that build thread pools |
| Future | A receipt for a result that will exist later; get() waits for it |
| Thread.sleep | Pauses the current thread: Thread.sleep(1) waits 1 ms |
| InterruptedException | Thrown when a sleeping or waiting thread is asked to stop; Java makes you handle it |
| Race condition | A bug whose result depends on the timing of threads: 40 tickets for 5 spots one run, 7 the next |
| Check-then-act | Checking a condition, then acting on it, while another thread can change things in between |
| Stale check | A check whose answer is out of date by the time you act on it |
| Lock | A token only one thread can hold at a time; others wait for it |
| synchronized | Java's built-in lock: only one thread at a time inside synchronized code of the same object |
| synchronized block | synchronized (x) { ... }: lock object x for just those lines |
| Synchronized allocation | Booking a spot inside a synchronized method, so check-and-take is one step |
| Atomic, indivisible | Happening as one step that no other thread can see half-done or split |
| Coarse-grained locking | One lock for a big piece of state: the whole lot |
| Fine-grained locking | Several small locks for smaller pieces: one per spot type, per floor, or per ticket |
| Deadlock | Two threads each waiting forever for a lock the other holds; avoided by always locking in the same order |
| volatile | A field modifier that makes one thread's write visible to other threads at once |
| static field | A field that belongs to the class, one copy shared by all objects |
| Running demo | A short main that drives the whole design end to end to show it works |
| Strategy pattern | Interchangeable algorithms behind one interface (episode 34) |
| Decorator pattern | An object that wraps another of the same interface to add behaviour: WeekendPricing wraps HourlyPricing |
| Repository | An object that hides where data is stored (episode 45) |
| Interface | A contract: methods a class promises to have: class Upi implements PaymentMethod |
| Functional interface | An interface with exactly one abstract method, so a lambda can implement it: PricingStrategy |
| Lambda | A short unnamed function: s -> s.id, (v, min) -> ... |
| Method reference | A shorter lambda that names an existing method: Spot::type means s -> s.type() |
| Enum | A type with a fixed list of values: enum State { ACTIVE, PAID, EXITED } |
| ordinal() | An enum value's position in its list: CAR.ordinal() is 1 |
| values() / valueOf() | SpotType.values() lists all values in order; VehicleType.valueOf("CAR") turns text into a value |
| Record | A short class that only carries values; Java writes the constructor, accessors, equals, hashCode, toString: record Spot(String id, SpotType type, int distance) |
| final field | A field set once in the constructor and never changed: final LocalDateTime entry |
| Immutable | An object whose data can't change after it is built |
| var | Lets Java infer a local variable's type: var spots = List.of(...) |
| Optional | A box that holds a value or is empty: pick returns Optional<Spot> |
| map / orElse / orElseThrow / ifPresent | Optional helpers: transform the value, give a default, take it or throw, act only if present |
| List.of | Makes a fixed (unchangeable) list: List.of(c1, l1) |
| Map | A table from keys to values |
| EnumMap | A fast Map whose keys are one enum's values, kept in the enum's order |
| Set | A collection that holds each element at most once |
| HashSet | A set with fast add and lookup, in no particular order |
| TreeSet | A set that keeps itself sorted; first, pollFirst, add, remove in O(log n) |
| first() / pollFirst() | first() returns the smallest element; pollFirst() returns and removes it (or null if empty) |
| Comparator | An object that orders two elements: Comparator.comparingInt(s -> s.distance) |
| comparingInt / comparing / thenComparing | Build a comparator from a key, and add a tie-breaker key |
| Tie-breaker | A second sort key used when the first is equal: spot id after distance |
| Comparable | An interface for classes with a natural order (Integer, String) |
| ClassCastException | Thrown when an object is used as a type it isn't: a Spot as a Comparable |
| Big-O notation | How work grows with the input size n |
| O(1) | Work that doesn't grow with n |
| O(n) | Work that grows in step with n: FirstFree scanning every spot |
| O(log n) | Work that grows like the number of halvings of n: about 14 steps for 10,000 spots |
| Integer division | Dividing whole-number types drops the fraction: 179 / 60 is 2 |
| (minutes + 59) / 60 | The round-up trick for started hours: (179 + 59) / 60 is 3 |
| Cast | Converting a value to another type: (int) hours |
| long | Java's 64-bit whole-number type; toMinutes() returns one |
| Math.max | The larger of two numbers: Math.max(1, 0) is 1 |
| LocalDateTime | A date and time of day without a time zone: LocalDateTime.of(2026, 11, 14, 10, 0) |
| Duration | An amount of time: Duration.between(in, out).toMinutes() |
| Instant | One exact point on the world's timeline |
| ZoneId | A time zone's name: ZoneId.of("Asia/Kolkata") |
| DayOfWeek | An enum of the seven days: SATURDAY |
| Clock | Java's source of "now"; pass one in so tests can control time |
| Clock.fixed | A clock that always returns the same moment |
| Clock.offset | A clock that is another clock moved by a duration |
| Dependency injection | Giving an object what it depends on (a clock, a strategy) instead of letting it create it |
| Testability | How easily code can be checked by fast, repeatable tests |
| System.nanoTime | A timer in nanoseconds, used to measure how long something took |
| Exception | Java's way of stopping normal flow because something should not happen |
| IllegalStateException | Thrown when the object is in the wrong state for the call: can't exit ticket 1, it's EXITED |
| IllegalArgumentException | Thrown when a method gets a bad argument: Rs 20 is less than Rs 30 |
| Stack trace | The chain of method calls, with line numbers, printed with an uncaught exception |
| Singleton | A class allowed only one object, reached through a global method; part 1 showed why the lot should not be one |
| Accessor | A method that returns a field's value: a record's id() |
| equals / hashCode | The methods Java uses to decide whether two objects are "the same" in hash-based collections |
| String.split | Cuts a string into pieces: "BIKE CAR".split(" ") gives ["BIKE", "CAR"] |
| Abstract method | A method declared without a body, which an implementing class must provide |
| Balanced tree | The structure inside a TreeSet: a tree kept shallow, so any element is about log₂ n steps away |
| Millisecond, microsecond, nanosecond | A thousandth, a millionth, a billionth of a second |
| Clock.systemDefaultZone | The real clock of the computer, in its default time zone: what production code passes in |
| TestClock | The mini project's own Clock subclass whose time a test moves forward with advance |
| EV (electric vehicle) | A vehicle that charges from the mains; a follow-up adds charging spots and energy-based pricing |
Summary
- First free spot let two bikes take the compact and large spots:
CAR -> NONE,TRUCK -> NONE. - A SpotAllocationStrategy made the rule swappable; NearestFit (smallest type that fits, then nearest) parked everyone, and
maindidn't change. - Availability tracking with one TreeSet of free spots per type gives the nearest free spot in O(log n); add a tie-breaker to the comparator.
minutes / 60is integer division: 179 minutes billed as 2 hours. (minutes + 59) / 60 rounds up to started hours;Math.max(1, …)sets the minimum.- Pricing (
HourlyPricing,FlatPricing) and payment (Upi,Card,Cash) are strategies; a new rate card or a wallet is one new class. Inject a Clock to test time. - The ticket lifecycle ACTIVE → PAID → EXITED refuses wrong moves:
can't exit ticket 1, it's EXITED,pay first: 2 is ACTIVE. - Check-then-act across 8 gates is a race condition: 40 tickets for a handful of spots, different every run. synchronized makes check-and-take one step: exactly 10 tickets for 10 spots, every time.
- Start with one coarse lock on the one lot object; go fine-grained only if you measure a need; keep slow work outside the lock.
Next episode: Design an Elevator System, part 1: elevators, floors, buttons, requests, directions and a state machine.