Parking Lot Design Using OO Design


  • 32
    P

    Ways to approach a general Design problem.

    • Use Cases Generation: Gather all the possible use cases

    • Constraints and Analysis: How many users, how much data etc.

    • Basic Design: Most basic design. Few users case.

    • Bottlenecks: Find the bottlenecks and solve them.

    • Scalability: A large number of users. 4 and 5 step will go in loop till we get a satisfactory answer

    Current Scenario

    1. Use cases for this problem.
    • Parking can be single-level or multilevel.
    • Types of vehicles that can be parked, separate spaces for each type of vehicle.
    • Entry and exit points.
    1. Constraints
    • Number of vehicles that can be accommodated of any type.
    1. Basic Design/High-Level Components
    • Vehicle/Type of vehicle.
    • Entry and Exit points.
    • Different spots for vehicles.
    1. Bottlenecks
    • Capacity breach for any type of vehicle.
    1. Scalability
    • Scalable from single-level to multi-level
    • Scalable from Bike only parking to accommodate all kinds of vehicles.

    Keeping these in minds, APIs can be designed in the language of your preference.


  • -2
    A

    @prashant3 bro iam not that much brilliant sry I can't answer it


  • 20

    A sample solution:

    1. Application controller : First object that will receive calls on application events.
    public enum ParkingLotController { //singleton facade controller
    	INSTANCE;
    	public ParkingLotController() {
    		VehicleSensorPool.INSTANCE.register(VehicleEventListenerPool.INSTANCE);
    	}
    	
    	public ParkingTicket enter(VehicleEntryEvent vehicleEntryEvent) throws SpotNotAvailableException, IllegitimateVehicleException { // app event
    		ParkingSpot parkingSpot = null;
    		Vehicle enteringVehicle = vehicleEntryEvent.getVehicle();
    		try {
    			parkingSpot = ParkingLot.addVehicle(enteringVehicle);
    			return printTicket(enteringVehicle);
    		}
    		catch(SpotNotAvailableException e) {
    			displayWaitMessage(e);
    			//very primitive retry mechanism..substitute your own here
    			//or we can use wait-notify
    			Thread.sleep(WAIT_DURATION);
    			enter(vehicleEntryEvent);
    		}
    		catch(IllegitimateVehicleException e) {
    			displayIntoleranceMessage(e);
    		}
    	}
    	
    	public ParkingBill exit(VehicleExitEvent vehicleExitEvent) { // app event
    		Vehicle exitingVehicle = ParkingLot.getVehicle(enteringVehicle);
    		ParkingLot.removeVehicle(exitingVehicle);
    		long timeVehicleKept = ParkingLot.getTimeKept(exitingVehicle);
    		return printBill(exitingVehicle, timeVehicleKept);
    	}
    	
    	private ParkingTicket printTicket(Vehicle vehicle) {
    		//..
    	}
    	
    	private ParkingBill printBill(Vehicle vehicle, long timeVehicleKept) {
                    //BillingSystem is again a facade
    		return BillingSystem.INSTANCE.printBill(vehicle, timeVehicleKept);
    	}
    }
    
    1. Event listener infrastructure : The next question is who will forward events to the controller. We have vehicle sensors at multiple points of entry and exit. These sensors are able to scan a vehicle's props such as plate, height, type etc. and notify entry and exit event listeners about entry and exit. Note that this enables a real time feel and reduces waiting for vehicles (as spots can be made async available) if slots are full.
      Sensors run on their own threads. We have the flexibility of having sensors:listeners in a m:n relationship through the use of the composite listener pool.
      Further note: SensorData is inner for enhanced encapsulation.
    public enum VehicleSensorPool {
    	INSTANCE;
    	private List<VehicleSensor> vehicleSensors;
    	public VehicleSensorPool() {
    		//init vehicleSensors, according to config
    		for(VehicleSensor vehicleSensor : vehicleSensors) {
    			new Thread(vehicleSensor).start();
    		}
    	}
    	public void register(VehicleEventListener vehicleEventListener) {
    		for(VehicleSensor vehicleSensor : vehicleSensors) {
    			vehicleSensor.addEventListener(vehicleEventListener);
    		}
    	}
    }
    
    public interface VehicleEventListener {
    	public void onVehicleEnter(Vehicle vehicle);
    	public void onVehicleExit(Vehicle vehicle);
    }
    
    public class VehicleSensor implements Runnable {
    	private class SensorData {//contains raw sensor data that the sensor must use to raise events}
    	public void run() {
    		while(true) {
    			//sense Vehicle entry and exit and notify event listeners
    			SensorData sensorData = sense(); //blocking call
    			
    			//on entry create a Vehicle object (populated with height, type, plate etc) and notify.
    			//on exit retrieve vehicle object from ParkingLot object and raise event.
    		}
    	}
    	private Vehicle createVehicleEvent(SensorData sensorData) {
    		if( //sensorData points to entry) {
    			Vehicle vehicle = createVehicle(sensorData);
    			return new VehicleEntryEvent(vehicle);
    		}
    		else { //sensorData points to exit
    			return new VehicleExitEvent(sensorData.getPlate());
    		}
    	}
    	private Vehicle createVehicle(SensorData sensorData) {
    		//series of vehicle.setXXX(sensorData.getXXX())
    	}
    }
    
    public enum VehicleEventListenerPool implements VehicleEventListener { //composite singleton
    	INSTANCE;
    	private List<VehicleEventListener> vehicleEventListeners;
    	public VehicleEventListenerPool() {
    		//init vehicleEventListeners, according to config
    	}
    	public void onVehicleEnter(VehicleEntryEvent vehicleEntryEvent) {
    		//select a listener from the pool and call its onVehicleEnter method
    	}
    	public void onVehicleExit(VehicleExitEvent vehicleExitEvent) {
    		//select a listener from the pool and call its onVehicleExit method
    	}
    }
    
    public class VehicleEventListenerImpl implements VehicleEventListener {
    	public void onVehicleEnter(VehicleEntryEvent vehicleEntryEvent) {
    		ParkingLotController.INSTANCE.enter(vehicleEntryEvent);
    	}
    	public void onVehicleExit(VehicleExitEvent vehicleExitEvent) {
    		ParkingLotController.INSTANCE.exit(vehicleExitEvent);
    	}
    }
    
    1. ParkingLot : Facade for the parking lot subsystem. Manages parkingSpot assignments. Validates vehicles to ensure that they follow parking policy (for eg max height).
      A parking spot encapsulates level, spot no and vehicle types it is suitable for. This enables a vehicle to enter through a different level(floor) and park at a completely different floor (in case there was no space available on the entry floor.)
      Validators are strategy objects to ensure flexibility around different parking policies that might arise. Spot assignment is again based on strategy objects which decide which spot goes to which vehicle based on parameters.
      Additionally, it would be easy to add timekeeping as shown. This would aid billing.
    public class Vehicle {
    	private String plate;
    	private double height;
    	private VehicleType type;
    }
    
    public enum VehicleType {
    	BIKE(100.0), BICYCLE(90.0), TRUCK(1000.0), CAR(400.0); //sample props of VehicleType
    	private int maxHeight;
    	public VehicleType(int maxHeight) {
    		this.maxHeight = maxHeight;
    	}
    	//..
    }
    
    public class ParkingSpot {
    	private int level;
    	private int height;
    	private int spotNo;
    	private boolean vacant;
    	private Set<VehicleType> suitableFor;
    	//equals() and hashCode()..
    	//..
    }
    
    public enum ParkingLot {
    	INSTANCE,
    	//..internal DSes to maintain parking spots, vehicles and assignments.
    	//strategies for validation and assignment
    	private ParkingSpotAssignmentStrategy parkingSpotAssignmentStrategy;
    	private VehicleValidationStrategy vehicleValidationStrategy;
    	public ParkingLot() {
    		//..init internal DSes to maintain parking spots, vehicles and assignments. 
    		//init strategies
    		parkingSpotAssignmentStrategy = new ParkingSpotAssignmentStrategyImpl(this);
    		vehicleValidationStrategy = new VehicleValidationStrategyImpl(this);
    	}
    	public ParkingSpot addVehicle(Vehicle vehicle) throws SpotNotAvailableException, IllegitimateVehicleException {
    		//check if vehicle is elligible for parking(we can have a Validator object) and assign ParkingSpot according to strategy
    		vehicleValidationStrategy.validate();
    		//assignment happens only after validation
    		return assign(vehicle);
    	}
    	private ParkingSpot assign(Vehicle vehicle) throws SpotNotAvailableException {
    		ParkingSpot vacantParkingSpot = parkingSpotAssignmentStrategy.assign(vehicle);
    		synchronized(vacantParkingSpot) { //so that no two vehicles are assigned the same spot
    			if(vacantParkingSpot.isVacant()) {
    				//..associate vehicle with vacantParkingSpot. Update internal DSes.	
    				//start timekeeping using a TimeKeeper object
    			}
    			else {
    				//retry
    				return assign(vehicle);
    			}
    		}
    		return vacantParkingSpot;
    	}
    	public Vehicle getVehicle(String plate) {
    		//..get vehicle by plate
    	}
    	public void removeVehicle(Vehicle vehicle) {
    		//..remove vehicle from lot. reclaim parkingSpot. Update internal DSes.
    		//stop timekeeping.
    	}
    	public void getTimeKept(Vehicle vehicle) {
    		//return time kept by TimeKeeper
    	}
    }
    
    public interface ParkingSpotAssignmentStrategy {
    	public ParkingSpot assign(Vehicle vehicle) throws SpotNotAvailableException;
    }
    
    public interface VehicleValidationStrategy {
    	public void validate(Vehicle vehicle) throws IllegitimateVehicleException;
    }
    

  • 0
    P

    @soumyadeep2007 nice one.
    Thanks for the post.


  • 0

    @prashant3 Most welcome! :)


  • 0
    R

    @soumyadeep2007 Appreciate your answer. In Interview , are they expect class diagrams or coding for this problem? just want to know how to answer design related questions, if they gave time for 30-40 mn how to approach to these kind of questions?


  • 1

    @rlmadhu There is no substitute for code on the whiteboard, that is what they want. If they ask you to do a class diagram, then do it, but its more of an adjunct. If you are asked such a question, take the initiative and get on the whiteboard and narrate your decision making. And not pseudo-code, actual code. You can obviously shorten syntax and stuff, but communicate that to the interviewer.


  • 4
    P

    @rlmadhu Interviewer judges you on the basis of your thought process.

    Eg.

    • In this case if you first started approaching the problem as mentioned in the article.
    • Then make a component diagram to explain your approach and interaction of your components.
    • Then he may ask you to write code/pseudo code for any of the component in detail.
    • He may go on to ask the different calls to other components.
    • And if you are able to write code for all components as well as interactions as in @soumyadeep2007 code. You have a higher chance of impressing the interviewer.

  • 4

    @rlmadhu honestly, I have never been asked to write the complete code of a system/oo design question in an interview.

    I have always started with clarifying questions to understand all the use cases and restrictions. Then start my design with drawing class diagrams. I usually start with small components and try to connect them together to build dependencies and associations and finally the whole system. I usually come up with new classes once I'm trying to connect pieces together.

    Then, the interviewer probably finds some parts of my design interesting and asks me to write code for a use case or two. Then I will do.

    And mostly the interview is followed by some follow up questions such as how to add a new component/use case to the system and [almost always] how I'm gonna test the application.

    For testing my design, I will start with a small component and test it alone. Try to remove the dependencies for the mentioned component/function (look up unit testing/mock/fake/stub). Then I'll test two or more components that are building a workflow together (integration testing) and finally the system as a whole (system testing).


  • 1
    R

    @yashar / @soumyadeep2007 /@prashant3 ...Thank you guys for ur comments, it is very helpful.


  • 0
    G
    This post is deleted!

  • 0
    L

    @rlmadhu I see you're interesteed in this topic. If parking lot design is the subject of your interest, you should totally check this source too. It helped me so much!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.