Design a Parking Lot

package com.androidinterview.parkinglot.model;

import java.time.Duration;

// What the exit gate hands back. The amount is a long of minor units, never a
// double, because money in floating point is a rounding bug in waiting.
public record ParkingReceipt(String ticketId, Duration stay, long amountMinor) {}

package com.androidinterview.parkinglot.model;

import java.time.Duration;

public record ParkingReceipt(String ticketId, Duration stay, long amountMinor) {}

package com.androidinterview.parkinglot.model;

import java.util.concurrent.atomic.AtomicReference;

// One bay. It owns exactly one fact, whether it is occupied and by whom.
//
// The occupant is an AtomicReference because two cars can reach the last bay
// at the same moment. Claiming is a compare and set from empty, so one call
// wins and the other is told to look elsewhere. A real system would hold this
// in a database row and claim it with a conditional update instead.
public final class ParkingSpot {

    private final String id;
    private final int floor;
    private final SpotSize size;
    // Walking distance from the entrance in metres, used by nearest first.
    private final int distance;

    private final AtomicReference<Vehicle> occupant = new AtomicReference<>();

    public ParkingSpot(String id, int floor, SpotSize size, int distance) {
        this.id = id;
        this.floor = floor;
        this.size = size;
        this.distance = distance;
    }

    public String id() {
        return id;
    }

    public int floor() {
        return floor;
    }

    public SpotSize size() {
        return size;
    }

    public int distance() {
        return distance;
    }

    public boolean isFree() {
        return occupant.get() == null;
    }

    public boolean fits(Vehicle vehicle) {
        return size.accepts(vehicle.type().requiredSize);
    }

    // The only way to take a bay. True for exactly one of two racing callers.
    public boolean claim(Vehicle vehicle) {
        return fits(vehicle) && occupant.compareAndSet(null, vehicle);
    }

    public void release() {
        occupant.set(null);
    }
}

package com.androidinterview.parkinglot.model;

import java.util.concurrent.atomic.AtomicReference;

public final class ParkingSpot {

    private final String id;
    private final int floor;
    private final SpotSize size;
    private final int distance;

    private final AtomicReference<Vehicle> occupant = new AtomicReference<>();

    public ParkingSpot(String id, int floor, SpotSize size, int distance) {
        this.id = id;
        this.floor = floor;
        this.size = size;
        this.distance = distance;
    }

    public String id() {
        return id;
    }

    public int floor() {
        return floor;
    }

    public SpotSize size() {
        return size;
    }

    public int distance() {
        return distance;
    }

    public boolean isFree() {
        return occupant.get() == null;
    }

    public boolean fits(Vehicle vehicle) {
        return size.accepts(vehicle.type().requiredSize);
    }

    public boolean claim(Vehicle vehicle) {
        return fits(vehicle) && occupant.compareAndSet(null, vehicle);
    }

    public void release() {
        occupant.set(null);
    }
}

package com.androidinterview.parkinglot.model;

// Ordered small to large. The declaration order is the fitting rule, so a bay
// takes any vehicle needing its own size or less.
public enum SpotSize {
    SMALL,
    MEDIUM,
    LARGE;

    public boolean accepts(SpotSize required) {
        return ordinal() >= required.ordinal();
    }
}

package com.androidinterview.parkinglot.model;

public enum SpotSize {
    SMALL,
    MEDIUM,
    LARGE;

    public boolean accepts(SpotSize required) {
        return ordinal() >= required.ordinal();
    }
}

package com.androidinterview.parkinglot.model;

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

// The proof that a bay belongs to this driver. It carries the bay id so exit
// never searches the lot, and the entry time so the fee is a pure function of
// the ticket and the clock.
public record Ticket(String id, Vehicle vehicle, String spotId, Instant issuedAt) {

    public static Ticket issue(Vehicle vehicle, ParkingSpot spot, Instant now) {
        return new Ticket(UUID.randomUUID().toString(), vehicle, spot.id(), now);
    }
}

package com.androidinterview.parkinglot.model;

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

public record Ticket(String id, Vehicle vehicle, String spotId, Instant issuedAt) {

    public static Ticket issue(Vehicle vehicle, ParkingSpot spot, Instant now) {
        return new Ticket(UUID.randomUUID().toString(), vehicle, spot.id(), now);
    }
}

package com.androidinterview.parkinglot.model;

// A value, so a record. The plate is the identity, and it is also how we spot
// a driver scanning in twice.
public record Vehicle(String plate, VehicleType type) {}

package com.androidinterview.parkinglot.model;

public record Vehicle(String plate, VehicleType type) {}

package com.androidinterview.parkinglot.model;

// The type carries the bay size it needs, so nothing else ever switches over
// vehicle types. Adding a bus is one line here and nothing anywhere else.
public enum VehicleType {
    MOTORCYCLE(SpotSize.SMALL),
    CAR(SpotSize.MEDIUM),
    TRUCK(SpotSize.LARGE);

    public final SpotSize requiredSize;

    VehicleType(SpotSize requiredSize) {
        this.requiredSize = requiredSize;
    }
}

package com.androidinterview.parkinglot.model;

public enum VehicleType {
    MOTORCYCLE(SpotSize.SMALL),
    CAR(SpotSize.MEDIUM),
    TRUCK(SpotSize.LARGE);

    public final SpotSize requiredSize;

    VehicleType(SpotSize requiredSize) {
        this.requiredSize = requiredSize;
    }
}

package com.androidinterview.parkinglot.service;

import java.time.Clock;
import java.time.Duration;
import java.util.List;
import java.util.Map;
import java.util.Optional;
import java.util.concurrent.ConcurrentHashMap;
import java.util.stream.Collectors;

import com.androidinterview.parkinglot.model.ParkingReceipt;
import com.androidinterview.parkinglot.model.ParkingSpot;
import com.androidinterview.parkinglot.model.SpotSize;
import com.androidinterview.parkinglot.model.Ticket;
import com.androidinterview.parkinglot.model.Vehicle;
import com.androidinterview.parkinglot.strategy.FeeStrategy;
import com.androidinterview.parkinglot.strategy.SpotAllocationStrategy;

// The one door into the system. Gates, kiosks and the app talk to this class
// and nothing else, which is what leaves allocation and pricing free to change.
//
// It owns the bays and the open tickets. It owns no rules at all.
public final class ParkingLot {

    private final List<ParkingSpot> spots;
    private final Map<String, ParkingSpot> spotsById;
    private final SpotAllocationStrategy allocation;
    private final FeeStrategy fees;
    private final Clock clock;

    private final Map<String, Ticket> openTickets = new ConcurrentHashMap<>();
    private final Map<String, String> ticketIdByPlate = new ConcurrentHashMap<>();

    public ParkingLot(
            List<ParkingSpot> spots, SpotAllocationStrategy allocation, FeeStrategy fees, Clock clock) {
        this.spots = List.copyOf(spots);
        this.spotsById = this.spots.stream().collect(Collectors.toMap(ParkingSpot::id, spot -> spot));
        this.allocation = allocation;
        this.fees = fees;
        this.clock = clock;
    }

    // Entry. Empty means the lot is full for this size of vehicle, which is an
    // ordinary Tuesday and not an exceptional case.
    //
    // The plate is claimed first, and the allocation runs inside that claim.
    // computeIfAbsent runs the function at most once per absent key, so two
    // barriers reading the same plate at the same moment produce one bay and
    // one ticket, and the second reader gets the ticket the first one issued.
    // A get followed by a put would be check then act, and the loser's bay
    // would be orphaned for good. A full lot returns null from the function, so
    // nothing is recorded against the plate and the next attempt tries again.
    public Optional<Ticket> enter(Vehicle vehicle) {
        String ticketId = ticketIdByPlate.computeIfAbsent(vehicle.plate(), plate ->
                allocation.allocate(spots, vehicle)
                        .map(spot -> {
                            Ticket ticket = Ticket.issue(vehicle, spot, clock.instant());
                            openTickets.put(ticket.id(), ticket);
                            return ticket.id();
                        })
                        .orElse(null));
        return Optional.ofNullable(ticketId).map(openTickets::get);
    }

    // The lost ticket path. The plate index is what makes it possible.
    public Optional<Ticket> openTicketFor(String plate) {
        return Optional.ofNullable(ticketIdByPlate.get(plate)).map(openTickets::get);
    }

    // Exit. Removing the ticket comes first and is atomic, so of two barriers
    // scanning the same ticket only one gets a value and the other is told it
    // is already closed. Freeing the bay before that would let a double scan
    // hand the same space to two drivers, so the bay is released last.
    public ParkingReceipt exit(String ticketId) {
        Ticket ticket = openTickets.remove(ticketId);
        if (ticket == null) {
            throw new IllegalStateException("no open ticket " + ticketId);
        }
        ticketIdByPlate.remove(ticket.vehicle().plate());

        Duration stay = Duration.between(ticket.issuedAt(), clock.instant());
        long amount = fees.feeFor(ticket.vehicle(), stay);
        spotsById.get(ticket.spotId()).release();
        return new ParkingReceipt(ticket.id(), stay, amount);
    }

    // What the sign at the entrance shows. Counted on demand, because a lot
    // has a few thousand bays and a cached counter is one more thing to keep
    // correct for no gain.
    public Map<SpotSize, Long> availability() {
        return spots.stream()
                .filter(ParkingSpot::isFree)
                .collect(Collectors.groupingBy(ParkingSpot::size, Collectors.counting()));
    }
}

package com.androidinterview.parkinglot.service;

import java.time.Clock;
import java.time.Duration;
import java.util.List;
import java.util.Map;
import java.util.Optional;
import java.util.concurrent.ConcurrentHashMap;
import java.util.stream.Collectors;

import com.androidinterview.parkinglot.model.ParkingReceipt;
import com.androidinterview.parkinglot.model.ParkingSpot;
import com.androidinterview.parkinglot.model.SpotSize;
import com.androidinterview.parkinglot.model.Ticket;
import com.androidinterview.parkinglot.model.Vehicle;
import com.androidinterview.parkinglot.strategy.FeeStrategy;
import com.androidinterview.parkinglot.strategy.SpotAllocationStrategy;

public final class ParkingLot {

    private final List<ParkingSpot> spots;
    private final Map<String, ParkingSpot> spotsById;
    private final SpotAllocationStrategy allocation;
    private final FeeStrategy fees;
    private final Clock clock;

    private final Map<String, Ticket> openTickets = new ConcurrentHashMap<>();
    private final Map<String, String> ticketIdByPlate = new ConcurrentHashMap<>();

    public ParkingLot(
            List<ParkingSpot> spots, SpotAllocationStrategy allocation, FeeStrategy fees, Clock clock) {
        this.spots = List.copyOf(spots);
        this.spotsById = this.spots.stream().collect(Collectors.toMap(ParkingSpot::id, spot -> spot));
        this.allocation = allocation;
        this.fees = fees;
        this.clock = clock;
    }

    public Optional<Ticket> enter(Vehicle vehicle) {
        String ticketId = ticketIdByPlate.computeIfAbsent(vehicle.plate(), plate ->
                allocation.allocate(spots, vehicle)
                        .map(spot -> {
                            Ticket ticket = Ticket.issue(vehicle, spot, clock.instant());
                            openTickets.put(ticket.id(), ticket);
                            return ticket.id();
                        })
                        .orElse(null));
        return Optional.ofNullable(ticketId).map(openTickets::get);
    }

    public Optional<Ticket> openTicketFor(String plate) {
        return Optional.ofNullable(ticketIdByPlate.get(plate)).map(openTickets::get);
    }

    public ParkingReceipt exit(String ticketId) {
        Ticket ticket = openTickets.remove(ticketId);
        if (ticket == null) {
            throw new IllegalStateException("no open ticket " + ticketId);
        }
        ticketIdByPlate.remove(ticket.vehicle().plate());

        Duration stay = Duration.between(ticket.issuedAt(), clock.instant());
        long amount = fees.feeFor(ticket.vehicle(), stay);
        spotsById.get(ticket.spotId()).release();
        return new ParkingReceipt(ticket.id(), stay, amount);
    }

    public Map<SpotSize, Long> availability() {
        return spots.stream()
                .filter(ParkingSpot::isFree)
                .collect(Collectors.groupingBy(ParkingSpot::size, Collectors.counting()));
    }
}

package com.androidinterview.parkinglot.strategy;

import java.time.Duration;
import java.util.Map;

import com.androidinterview.parkinglot.model.Vehicle;
import com.androidinterview.parkinglot.model.VehicleType;

// The other rule that changes, and the one an interviewer will change on you
// halfway through. A new price list is a new lambda, not an edit to the lot.
@FunctionalInterface
public interface FeeStrategy {

    long feeFor(Vehicle vehicle, Duration stay);

    // What a real car park does. A free grace period so a wrong turn is not
    // charged, then whole hours rounded up at a rate per vehicle type.
    static FeeStrategy hourly(Duration grace, Map<VehicleType, Long> ratePerHour) {
        return (vehicle, stay) -> {
            if (stay.compareTo(grace) <= 0) {
                return 0L;
            }
            // Integer ceiling division keeps floating point away from money.
            // toMinutes drops the seconds first, so two hours and one second
            // bills two hours. That rounds down in the customer's favour, on
            // purpose.
            long hours = (Math.max(1, stay.toMinutes()) + 59) / 60;
            return hours * ratePerHour.get(vehicle.type());
        };
    }

    static FeeStrategy standard() {
        return hourly(
                Duration.ofMinutes(15),
                Map.of(
                        VehicleType.MOTORCYCLE, 2000L,
                        VehicleType.CAR, 4000L,
                        VehicleType.TRUCK, 8000L));
    }
}

package com.androidinterview.parkinglot.strategy;

import java.time.Duration;
import java.util.Map;

import com.androidinterview.parkinglot.model.Vehicle;
import com.androidinterview.parkinglot.model.VehicleType;

@FunctionalInterface
public interface FeeStrategy {

    long feeFor(Vehicle vehicle, Duration stay);

    static FeeStrategy hourly(Duration grace, Map<VehicleType, Long> ratePerHour) {
        return (vehicle, stay) -> {
            if (stay.compareTo(grace) <= 0) {
                return 0L;
            }
            long hours = (Math.max(1, stay.toMinutes()) + 59) / 60;
            return hours * ratePerHour.get(vehicle.type());
        };
    }

    static FeeStrategy standard() {
        return hourly(
                Duration.ofMinutes(15),
                Map.of(
                        VehicleType.MOTORCYCLE, 2000L,
                        VehicleType.CAR, 4000L,
                        VehicleType.TRUCK, 8000L));
    }
}

package com.androidinterview.parkinglot.strategy;

import java.util.Comparator;
import java.util.List;
import java.util.Optional;

import com.androidinterview.parkinglot.model.ParkingSpot;
import com.androidinterview.parkinglot.model.Vehicle;

// Where a car goes is the rule most likely to change, so it lives behind an
// interface with more than one real implementation.
//
// The strategy claims the bay as well as choosing it. If it only returned a
// suggestion, every caller would have to check the bay was still free and then
// take it, and that gap is the race.
public interface SpotAllocationStrategy {

    Optional<ParkingSpot> allocate(List<ParkingSpot> spots, Vehicle vehicle);

    // The default. Shortest walk for the driver.
    static SpotAllocationStrategy nearestFirst() {
        return ordered(Comparator.comparingInt(ParkingSpot::distance));
    }

    // Smallest bay that holds the car, so a motorcycle never eats the last
    // truck bay. Same seam, different sort.
    static SpotAllocationStrategy bestFit() {
        return ordered(Comparator.comparing(ParkingSpot::size).thenComparingInt(ParkingSpot::distance));
    }

    // Sort the free bays, then walk them claiming until one claim wins. A bay
    // taken between the sort and the claim simply fails and we move on.
    // Sorting a few thousand bays per car is microseconds. If it ever mattered
    // you would keep a free list per size, and the claim would still decide.
    private static SpotAllocationStrategy ordered(Comparator<ParkingSpot> order) {
        return (spots, vehicle) -> spots.stream()
                .filter(spot -> spot.isFree() && spot.fits(vehicle))
                .sorted(order)
                .filter(spot -> spot.claim(vehicle))
                .findFirst();
    }
}

package com.androidinterview.parkinglot.strategy;

import java.util.Comparator;
import java.util.List;
import java.util.Optional;

import com.androidinterview.parkinglot.model.ParkingSpot;
import com.androidinterview.parkinglot.model.Vehicle;

public interface SpotAllocationStrategy {

    Optional<ParkingSpot> allocate(List<ParkingSpot> spots, Vehicle vehicle);

    static SpotAllocationStrategy nearestFirst() {
        return ordered(Comparator.comparingInt(ParkingSpot::distance));
    }

    static SpotAllocationStrategy bestFit() {
        return ordered(Comparator.comparing(ParkingSpot::size).thenComparingInt(ParkingSpot::distance));
    }

    private static SpotAllocationStrategy ordered(Comparator<ParkingSpot> order) {
        return (spots, vehicle) -> spots.stream()
                .filter(spot -> spot.isFree() && spot.fits(vehicle))
                .sorted(order)
                .filter(spot -> spot.claim(vehicle))
                .findFirst();
    }
}

package com.androidinterview.parkinglot.model

import java.util.concurrent.atomic.AtomicReference

// One bay. It owns exactly one fact, whether it is occupied and by whom.
//
// The occupant is an AtomicReference because two cars can reach the last bay
// at the same moment. Claiming is a compare and set from empty, so one call
// wins and the other looks elsewhere. A real system would hold this in a
// database row and claim it with a conditional update instead.
class ParkingSpot(
    val id: String,
    val floor: Int,
    val size: SpotSize,
    // Walking distance from the entrance in metres, used by nearest first.
    val distance: Int,
) {
    private val occupant = AtomicReference<Vehicle?>(null)

    val isFree: Boolean get() = occupant.get() == null

    fun fits(vehicle: Vehicle): Boolean = size >= vehicle.type.requiredSize

    // The only way to take a bay. True for exactly one of two racing callers.
    fun claim(vehicle: Vehicle): Boolean = fits(vehicle) && occupant.compareAndSet(null, vehicle)

    fun release() = occupant.set(null)
}

package com.androidinterview.parkinglot.model

import java.util.concurrent.atomic.AtomicReference

class ParkingSpot(
    val id: String,
    val floor: Int,
    val size: SpotSize,
    val distance: Int,
) {
    private val occupant = AtomicReference<Vehicle?>(null)

    val isFree: Boolean get() = occupant.get() == null

    fun fits(vehicle: Vehicle): Boolean = size >= vehicle.type.requiredSize

    fun claim(vehicle: Vehicle): Boolean = fits(vehicle) && occupant.compareAndSet(null, vehicle)

    fun release() = occupant.set(null)
}

package com.androidinterview.parkinglot.model

import java.time.Duration
import java.time.Instant
import java.util.UUID

// The proof that a bay belongs to this driver. It carries the bay id so exit
// never searches the lot, and the entry time so the fee is a pure function of
// the ticket and the clock.
data class Ticket(val id: String, val vehicle: Vehicle, val spotId: String, val issuedAt: Instant) {
    companion object {
        fun issue(vehicle: Vehicle, spot: ParkingSpot, now: Instant) =
            Ticket(UUID.randomUUID().toString(), vehicle, spot.id, now)
    }
}

// Money is a Long of minor units, never a Double, because floating point money
// is a rounding bug that has not happened yet.
data class ParkingReceipt(val ticketId: String, val stay: Duration, val amountMinor: Long)

package com.androidinterview.parkinglot.model

import java.time.Duration
import java.time.Instant
import java.util.UUID

data class Ticket(val id: String, val vehicle: Vehicle, val spotId: String, val issuedAt: Instant) {
    companion object {
        fun issue(vehicle: Vehicle, spot: ParkingSpot, now: Instant) =
            Ticket(UUID.randomUUID().toString(), vehicle, spot.id, now)
    }
}

data class ParkingReceipt(val ticketId: String, val stay: Duration, val amountMinor: Long)

package com.androidinterview.parkinglot.model

// Enums compare by declaration order, and that ordering is the whole fitting
// rule. A bay takes any vehicle needing its own size or less.
enum class SpotSize { SMALL, MEDIUM, LARGE }

// The type carries the bay size it needs, so nothing else ever switches over
// vehicle types. Adding a bus is one line here and nothing anywhere else.
enum class VehicleType(val requiredSize: SpotSize) {
    MOTORCYCLE(SpotSize.SMALL),
    CAR(SpotSize.MEDIUM),
    TRUCK(SpotSize.LARGE),
}

// A value, so a data class. equals and hashCode come free, which is why the
// plate can be a map key without writing anything.
data class Vehicle(val plate: String, val type: VehicleType)

package com.androidinterview.parkinglot.model

enum class SpotSize { SMALL, MEDIUM, LARGE }

enum class VehicleType(val requiredSize: SpotSize) {
    MOTORCYCLE(SpotSize.SMALL),
    CAR(SpotSize.MEDIUM),
    TRUCK(SpotSize.LARGE),
}

data class Vehicle(val plate: String, val type: VehicleType)

package com.androidinterview.parkinglot.service

import java.time.Clock
import java.time.Duration
import java.util.concurrent.ConcurrentHashMap

import com.androidinterview.parkinglot.model.ParkingReceipt
import com.androidinterview.parkinglot.model.ParkingSpot
import com.androidinterview.parkinglot.model.SpotSize
import com.androidinterview.parkinglot.model.Ticket
import com.androidinterview.parkinglot.model.Vehicle
import com.androidinterview.parkinglot.strategy.FeeStrategy
import com.androidinterview.parkinglot.strategy.SpotAllocationStrategy

// The one door into the system. Gates, kiosks and the app talk to this and to
// nothing else, which is what leaves allocation and pricing free to change.
// It owns the bays and the open tickets. It owns no rules.
//
// The clock has no default on purpose. Whoever wires the lot up chooses it,
// and a test hands in a fixed one.
class ParkingLot(
    private val spots: List<ParkingSpot>,
    private val allocation: SpotAllocationStrategy,
    private val fees: FeeStrategy,
    private val clock: Clock,
) {
    private val spotsById = spots.associateBy { it.id }
    private val openTickets = ConcurrentHashMap<String, Ticket>()
    // The value type is nullable only so the computeIfAbsent lambda in enter
    // can answer no bay. The map never holds a null.
    private val ticketIdByPlate = ConcurrentHashMap<String, String?>()

    // Entry. Null means full for this size of vehicle, an ordinary Tuesday.
    //
    // The plate is claimed first and the allocation runs inside that claim.
    // computeIfAbsent runs the lambda at most once per absent key, so two
    // barriers reading one plate at the same moment produce one bay and one
    // ticket, and the second reader gets the ticket the first one issued. A
    // get then a put would be check then act, and the loser's bay would be
    // orphaned for good. A full lot returns null from the lambda, so nothing is
    // recorded against the plate and the next attempt tries again.
    fun enter(vehicle: Vehicle): Ticket? {
        val ticketId = ticketIdByPlate.computeIfAbsent(vehicle.plate) {
            allocation.allocate(spots, vehicle)?.let { spot ->
                Ticket.issue(vehicle, spot, clock.instant()).also { openTickets[it.id] = it }.id
            }
        }
        return ticketId?.let { openTickets[it] }
    }

    // The lost ticket path. The plate index is what makes it possible.
    fun openTicketFor(plate: String): Ticket? = ticketIdByPlate[plate]?.let { openTickets[it] }

    // Exit. The remove comes first and is atomic, so of two barriers scanning
    // the same ticket only one gets a value. Freeing the bay first would let a
    // double scan hand the same space to two drivers, so the bay is released
    // last.
    fun exit(ticketId: String): ParkingReceipt {
        val ticket = checkNotNull(openTickets.remove(ticketId)) { "no open ticket $ticketId" }
        ticketIdByPlate.remove(ticket.vehicle.plate)

        val stay = Duration.between(ticket.issuedAt, clock.instant())
        val amount = fees.feeFor(ticket.vehicle, stay)
        spotsById.getValue(ticket.spotId).release()
        return ParkingReceipt(ticket.id, stay, amount)
    }

    // What the sign shows. Counted on demand, because a cached counter is one
    // more thing to keep correct for no gain.
    fun availability(): Map<SpotSize, Int> =
        spots.filter { it.isFree }.groupingBy { it.size }.eachCount()
}

package com.androidinterview.parkinglot.service

import java.time.Clock
import java.time.Duration
import java.util.concurrent.ConcurrentHashMap

import com.androidinterview.parkinglot.model.ParkingReceipt
import com.androidinterview.parkinglot.model.ParkingSpot
import com.androidinterview.parkinglot.model.SpotSize
import com.androidinterview.parkinglot.model.Ticket
import com.androidinterview.parkinglot.model.Vehicle
import com.androidinterview.parkinglot.strategy.FeeStrategy
import com.androidinterview.parkinglot.strategy.SpotAllocationStrategy

class ParkingLot(
    private val spots: List<ParkingSpot>,
    private val allocation: SpotAllocationStrategy,
    private val fees: FeeStrategy,
    private val clock: Clock,
) {
    private val spotsById = spots.associateBy { it.id }
    private val openTickets = ConcurrentHashMap<String, Ticket>()
    private val ticketIdByPlate = ConcurrentHashMap<String, String?>()

    fun enter(vehicle: Vehicle): Ticket? {
        val ticketId = ticketIdByPlate.computeIfAbsent(vehicle.plate) {
            allocation.allocate(spots, vehicle)?.let { spot ->
                Ticket.issue(vehicle, spot, clock.instant()).also { openTickets[it.id] = it }.id
            }
        }
        return ticketId?.let { openTickets[it] }
    }

    fun openTicketFor(plate: String): Ticket? = ticketIdByPlate[plate]?.let { openTickets[it] }

    fun exit(ticketId: String): ParkingReceipt {
        val ticket = checkNotNull(openTickets.remove(ticketId)) { "no open ticket $ticketId" }
        ticketIdByPlate.remove(ticket.vehicle.plate)

        val stay = Duration.between(ticket.issuedAt, clock.instant())
        val amount = fees.feeFor(ticket.vehicle, stay)
        spotsById.getValue(ticket.spotId).release()
        return ParkingReceipt(ticket.id, stay, amount)
    }

    fun availability(): Map<SpotSize, Int> =
        spots.filter { it.isFree }.groupingBy { it.size }.eachCount()
}

package com.androidinterview.parkinglot.strategy

import com.androidinterview.parkinglot.model.ParkingSpot
import com.androidinterview.parkinglot.model.Vehicle

// One method, so a fun interface, and every policy below is a lambda instead
// of a class. Null means full for this vehicle, which is a real answer in
// Kotlin and needs no Optional.
//
// The strategy claims the bay as well as choosing it. Returning a suggestion
// would leave every caller to check then take, and that gap is the race.
fun interface SpotAllocationStrategy {
    fun allocate(spots: List<ParkingSpot>, vehicle: Vehicle): ParkingSpot?
}

// Sort the free bays, then take the first one we actually win. A bay claimed
// by someone else between the sort and the claim just fails compareAndSet.
// Sorting a few thousand bays per car is microseconds. If it ever mattered you
// would keep a free list per size, and the claim would still decide.
private fun ordered(order: Comparator<ParkingSpot>) = SpotAllocationStrategy { spots, vehicle ->
    spots.filter { it.isFree && it.fits(vehicle) }
        .sortedWith(order)
        .firstOrNull { it.claim(vehicle) }
}

// The default, shortest walk for the driver.
val nearestFirst = ordered(compareBy { it.distance })

// Smallest bay that holds the car, so a motorcycle never eats the last truck
// bay. Same seam, different sort.
val bestFit = ordered(compareBy({ it.size }, { it.distance }))

package com.androidinterview.parkinglot.strategy

import com.androidinterview.parkinglot.model.ParkingSpot
import com.androidinterview.parkinglot.model.Vehicle

fun interface SpotAllocationStrategy {
    fun allocate(spots: List<ParkingSpot>, vehicle: Vehicle): ParkingSpot?
}

private fun ordered(order: Comparator<ParkingSpot>) = SpotAllocationStrategy { spots, vehicle ->
    spots.filter { it.isFree && it.fits(vehicle) }
        .sortedWith(order)
        .firstOrNull { it.claim(vehicle) }
}

val nearestFirst = ordered(compareBy { it.distance })

val bestFit = ordered(compareBy({ it.size }, { it.distance }))

package com.androidinterview.parkinglot.strategy

import java.time.Duration

import com.androidinterview.parkinglot.model.Vehicle
import com.androidinterview.parkinglot.model.VehicleType

// The rule an interviewer will change on you halfway through. Behind a fun
// interface, a new price list is a new lambda and the lot is untouched.
fun interface FeeStrategy {
    fun feeFor(vehicle: Vehicle, stay: Duration): Long
}

// What a real car park does. A free grace period so a wrong turn is not
// charged, then whole hours rounded up at a rate per vehicle type.
fun hourly(
    grace: Duration = Duration.ofMinutes(15),
    rates: Map<VehicleType, Long> = mapOf(
        VehicleType.MOTORCYCLE to 2_000L,
        VehicleType.CAR to 4_000L,
        VehicleType.TRUCK to 8_000L,
    ),
) = FeeStrategy { vehicle, stay ->
    if (stay <= grace) {
        0L
    } else {
        // Integer ceiling division keeps floating point away from money.
        // toMinutes drops the seconds first, so two hours and one second bills
        // two hours. That rounds down in the customer's favour, on purpose.
        val hours = (stay.toMinutes().coerceAtLeast(1) + 59) / 60
        hours * rates.getValue(vehicle.type)
    }
}

package com.androidinterview.parkinglot.strategy

import java.time.Duration

import com.androidinterview.parkinglot.model.Vehicle
import com.androidinterview.parkinglot.model.VehicleType

fun interface FeeStrategy {
    fun feeFor(vehicle: Vehicle, stay: Duration): Long
}

fun hourly(
    grace: Duration = Duration.ofMinutes(15),
    rates: Map<VehicleType, Long> = mapOf(
        VehicleType.MOTORCYCLE to 2_000L,
        VehicleType.CAR to 4_000L,
        VehicleType.TRUCK to 8_000L,
    ),
) = FeeStrategy { vehicle, stay ->
    if (stay <= grace) {
        0L
    } else {
        val hours = (stay.toMinutes().coerceAtLeast(1) + 59) / 60
        hours * rates.getValue(vehicle.type)
    }
}