OOD Interview Patterns: LRU Cache, Parking Lot & Elevator System

By /

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

  • Databricks Interview Guide
  • Lyft Interview Guide
  • Uber Interview Guide
  • LinkedIn Interview Guide
  • Atlassian Interview Guide
  • Apple Interview Guide
    • Scroll to Top