Object-Oriented Design (OOD) Interview Patterns: LRU Cache, Parking Lot & More
OOD interviews ask you to design a system using classes, interfaces, and design patterns. They test whether you can translate requirements into clean, extensible object models. Common at companies like Amazon and Microsoft.
The SOLID Principles
- Single Responsibility: each class has one reason to change
- Open/Closed: open for extension, closed for modification (use interfaces)
- Liskov Substitution: subclasses can replace their base class without breaking behavior
- Interface Segregation: don’t force clients to implement interfaces they don’t use
- Dependency Inversion: depend on abstractions, not concrete implementations
Pattern 1: LRU Cache (Doubly Linked List + Hash Map)
class Node:
def __init__(self, key=0, val=0):
self.key = key
self.val = val
self.prev = self.next = None
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.map = {} # key → node
self.head = Node() # dummy head (most recent)
self.tail = Node() # dummy tail (least recent)
self.head.next = self.tail
self.tail.prev = self.head
def _remove(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def _add_to_front(self, node):
node.next = self.head.next
node.prev = self.head
self.head.next.prev = node
self.head.next = node
def get(self, key):
if key not in self.map:
return -1
node = self.map[key]
self._remove(node)
self._add_to_front(node)
return node.val
def put(self, key, val):
if key in self.map:
self._remove(self.map[key])
node = Node(key, val)
self.map[key] = node
self._add_to_front(node)
if len(self.map) > self.capacity:
lru = self.tail.prev
self._remove(lru)
del self.map[lru.key]
Pattern 2: Parking Lot Design
from enum import Enum
from abc import ABC, abstractmethod
class VehicleSize(Enum):
COMPACT = 1
REGULAR = 2
LARGE = 3
class Vehicle(ABC):
@abstractmethod
def get_size(self) -> VehicleSize: pass
class Car(Vehicle):
def get_size(self): return VehicleSize.REGULAR
class Motorcycle(Vehicle):
def get_size(self): return VehicleSize.COMPACT
class Truck(Vehicle):
def get_size(self): return VehicleSize.LARGE
class ParkingSpot:
def __init__(self, spot_size: VehicleSize):
self.size = spot_size
self.vehicle = None
def can_fit(self, vehicle: Vehicle) -> bool:
return self.vehicle is None and vehicle.get_size().value ParkingSpot:
for floor in self.floors:
for spot in floor:
if spot.can_fit(vehicle):
spot.park(vehicle)
return spot
return None # lot full
def available_spots(self) -> int:
return sum(1 for floor in self.floors for spot in floor if spot.is_available())
Pattern 3: Elevator System
from enum import Enum
from collections import defaultdict
class Direction(Enum):
UP = "UP"
DOWN = "DOWN"
IDLE = "IDLE"
class Elevator:
def __init__(self, id, num_floors):
self.id = id
self.current_floor = 0
self.direction = Direction.IDLE
self.requests = set() # floors to stop at
def add_request(self, floor): self.requests.add(floor)
def step(self):
if not self.requests: self.direction = Direction.IDLE; return
target = min(self.requests) if self.direction == Direction.UP else max(self.requests)
if self.current_floor target:
self.current_floor -= 1; self.direction = Direction.DOWN
if self.current_floor in self.requests:
self.requests.remove(self.current_floor)
class ElevatorSystem:
def __init__(self, num_elevators, num_floors):
self.elevators = [Elevator(i, num_floors) for i in range(num_elevators)]
def request(self, floor, direction):
# Assign to closest idle or same-direction elevator
best = min(self.elevators,
key=lambda e: abs(e.current_floor - floor))
best.add_request(floor)
Common OOD Interview Problems
| Problem | Key Classes | Design Pattern |
|---|---|---|
| LRU Cache | Node, Cache | Doubly linked list + HashMap |
| Parking Lot | Vehicle, ParkingSpot, Lot | Strategy (vehicle sizes), Polymorphism |
| Elevator System | Elevator, ElevatorSystem | State machine, Observer |
| Library Management | Book, Member, Loan | Repository pattern |
| Chess Game | Piece, Board, Player | Strategy (move validation) |
| File System | File, Directory, Path | Composite pattern |
| ATM Machine | Card, Account, Transaction | State machine |
Interview Tips
- Clarify requirements before designing: “Should the parking lot support reserved spots? EV charging? Multiple entry gates?”
- Start with the nouns (entities → classes) and verbs (behaviors → methods)
- Use abstract base classes or interfaces for extensibility (Strategy pattern)
- Think about encapsulation: expose a clean public API, hide implementation details
- Consider thread safety for concurrent access to shared state
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “How do you implement an LRU cache with O(1) get and put operations?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Use a doubly linked list for ordering (most recently used at head, LRU at tail) combined with a hash map for O(1) lookup. get(key): find node via hash map, move to head, return value. put(key, val): if key exists, update and move to head; if new, add node at head and map it; if at capacity, remove tail node and its hash map entry before adding the new one. Both operations are O(1) because the hash map gives direct node access and linked list operations are constant time.” }
},
{
“@type”: “Question”,
“name”: “How do you design a parking lot system using OOD principles?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Key classes: Vehicle (abstract, with get_size()), Car/Motorcycle/Truck (concrete vehicles), ParkingSpot (with size, vehicle, can_fit(), park(), leave()), ParkingFloor (list of spots), ParkingLot (list of floors, park(), leave(), available_spots()). Apply SOLID: Vehicle is open for extension (add ElectricCar) without modifying Vehicle base class. ParkingSpot's can_fit() encapsulates size comparison logic. A ParkingLot can also implement a ticket system by adding a Ticket class with entry time for billing.” }
},
{
“@type”: “Question”,
“name”: “What is the difference between composition and inheritance in OOD?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Inheritance ("is-a"): subclass inherits behavior. Car is-a Vehicle. Use when the subclass truly is a specialized form of the parent. Risk: tight coupling — changes to parent break subclasses. Composition ("has-a"): class contains instances of other classes. ParkingLot has-a list of ParkingFloors. Use when combining behaviors from unrelated classes, or when you need flexibility to swap implementations at runtime (Strategy pattern). The rule of thumb: prefer composition over inheritance — it leads to more maintainable, testable code.” }
}
]
}