LLD Framework, HashMap Internals & LRU Intuition

The LLD interview framework ▶ 1:18:37 – 1:41:07

Five steps to follow for any "Design X" question: Requirements → Entities → Relationships → Code → Edge cases & extensions.

The problem

In an LLD round (usually 45–60 minutes) you get a one-line prompt: "Design a parking lot", "Design a rate limiter", "Design an LRU cache", "Design an elevator", "Design a vending machine", "Design a notification system". Many candidates jump straight into code because they "know" the problem, and they fail. These rounds are highly interactive. The interviewer is grading how you think: first principles or jumping to solutions, whether you look for edge cases, how clearly you explain, and whether your comments and names are clean.

The checklist

Step 1 in detail: functional vs non-functional

• Functional requirement (FR): a feature the system must have. Without it, the system is wrong. Example: "park a vehicle", "issue a ticket".
• Non-functional requirement (NFR): a quality. Without it the feature still works, but badly: slow, unsafe under concurrency, hard to extend. Examples: thread safety, performance, clean code, SOLID, extensibility, loose coupling.

Step 2 in detail: class or enum?

• Entity = a class = state (fields) + behaviour (methods). User, Order, ParkingLot (it can park_vehicle() and unpark_vehicle()).
• Enum = a fixed set of readable names with no real behaviour. Use enums for types and states: VehicleType.CAR / TRUCK / MOTORCYCLE / VAN, SlotType.SMALL / MEDIUM / LARGE / HANDICAPPED, vending-machine states IDLE / DISPENSING / RETURNING_CHANGE. Use them instead of magic numbers like 0 = car, 1 = truck.
• Interface = a contract for behaviour that can vary (payment method, pricing strategy).

Step 3 in detail: why relationships matter

A relationship turns into a field. You can only write vehicle inside Ticket if you have decided "a Ticket has a Vehicle". Relationships also tell you about lifecycle: if A is deleted, does B die too (composition) or survive (aggregation)? This was a student's answer in class. To find a relationship, ask a plain question: "Does a parking lot hold floors, or do floors hold lots?" Not everything must be linked directly. ParkingLot and Payment are only related through ExitGate, so Payment is like a "grandchild" of the lot.

classDiagram
  class ParkingLot {
    +id
    +address
    +floors
    +entrance_gates
    +exit_gates
  }
  class ParkingFloor {
    +slots
    +display_board
  }
  class ParkingSlot {
    +slot_type
    +is_free
  }
  class EntranceGate {
    +issue_ticket()
  }
  class ExitGate {
    +process_payment()
  }
  class Ticket {
    +vehicle
    +entry_time
  }
  class Vehicle {
    +number
    +vehicle_type
  }
  ParkingLot o-- ParkingFloor
  ParkingFloor o-- ParkingSlot
  ParkingLot o-- EntranceGate
  ParkingLot o-- ExitGate
  EntranceGate --> Ticket
  Ticket --> Vehicle
  ExitGate --> Payment
  Car --|> Vehicle
  Truck --|> Vehicle
  Motorcycle --|> Vehicle

This is a sketch of the parking-lot diagram the teacher showed. In the interview you will usually have only a code editor, so you say these relationships out loud or type them as comments. You do not draw them.

A tiny skeleton you can type in the first 10 minutes

from abc import ABC
from dataclasses import dataclass, field
from enum import Enum


# Step 2: enums for "types" (no behaviour, just readable names)
class VehicleType(Enum):
    CAR = "car"
    TRUCK = "truck"
    MOTORCYCLE = "motorcycle"


class SlotType(Enum):
    SMALL = "small"
    MEDIUM = "medium"
    LARGE = "large"


# Step 2: entities = classes (state + behaviour); Step 3: relationships become fields
class Vehicle(ABC):                        # Car IS-A Vehicle (inheritance)
    def __init__(self, number: str, vehicle_type: VehicleType):
        self.number = number
        self.vehicle_type = vehicle_type


class Car(Vehicle):
    def __init__(self, number: str):
        super().__init__(number, VehicleType.CAR)


@dataclass
class ParkingSlot:
    slot_id: int
    slot_type: SlotType
    vehicle: Vehicle | None = None         # a slot HAS-A (maybe) vehicle

    def is_free(self) -> bool:
        return self.vehicle is None


@dataclass
class ParkingFloor:
    number: int
    slots: list[ParkingSlot] = field(default_factory=list)   # floor HAS slots


@dataclass
class ParkingLot:
    address: str
    floors: list[ParkingFloor] = field(default_factory=list)  # lot HAS floors


# usage
lot = ParkingLot("MG Road", [ParkingFloor(0, [ParkingSlot(1, SlotType.MEDIUM)])])
slot = lot.floors[0].slots[0]
slot.vehicle = Car("KA-01-1234")
print(slot.is_free(), slot.vehicle.vehicle_type.name)   # False CAR

Course roadmap: the LLD problems to practise ▶ 1:47:41 – 2:02:50

About 15 problems that cover around 80% of LLD interviews. Each one teaches a different modelling skill.

HashMap and LRU cache are "starter" questions. They lean more on data structures than on LLD, but you will meet one of them in roughly 1 out of 10 interviews. Social-media design was left out on purpose: as LLD it is mostly CRUD, and the interesting part (friend suggestions) is an HLD or data-structures problem.

LLD of HashMap ▶ 2:02:50 – 2:42:48

A key-value store that uses a hash function to turn any key into an array index, so lookups are O(1) on average.

The problem

We want lookup by a unique key to be very fast, ideally O(1), even with millions of entries. Interviewers ask this to see whether you know what happens "under the hood". The teacher's claim: 80% of engineers cannot write one.

Why arrays are the secret

An array jumps to any index in O(1) with simple arithmetic: address(arr[i]) = base + i × size_of_element. This is called direct addressing. If keys were always small integers 0..n-1, we could store value at arr[key] and be done (4 → "Ajay", 3 → "Pradeep", 2 → "Upasana"). Real keys are not like that. They are big numbers like 981111, names, or whole documents.

Building it step by step

1. Hash function: a formula that takes a key and returns an index in 0 … table_size - 1. Typically index = hash(key) % capacity. A good hash function is deterministic (same input, same output), spreads keys evenly, and is fast.
2. Collision: with more keys than slots, two keys will sometimes land on the same index. With 4 slots and 10 keys, this is guaranteed.
3. Chaining: each slot (a bucket) holds the head of a linked list. A colliding key is added to that chain. The bucket array is an array of Entry references, much like an adjacency list in graphs.
4. Worst case: every key hashes to the same bucket. That gives one long chain, and lookup becomes O(n).
5. Load factor (α): α = number of elements / table size, which is the average chain length. 8 items in 4 buckets gives α = 2. 14 items in 4 buckets gives α = 3.5.
6. Rehashing (resizing): when α passes a threshold (0.75, chosen from experiments), the table is "too small". Double the capacity (4 → 8 → 16 …), go through every entry, and re-place it using the new % capacity. For example, capacity 16 × 0.75 = 12, so Java's HashMap resizes when the 13th element is inserted.

Python code

The Entry node stores key, value, a cached hash and next. MyHashMap holds the bucket array, capacity, size and load factor. No dict is used for storage.

from typing import Any, Optional


class Entry:
    """One node in a bucket's chain (a singly linked list)."""
    def __init__(self, key: Any, value: Any, h: int, nxt: Optional["Entry"] = None):
        self.key = key
        self.value = value
        self.hash = h          # cached hash: no need to recompute it while resizing
        self.next = nxt


class MyHashMap:
    DEFAULT_CAPACITY = 16
    LOAD_FACTOR = 0.75

    def __init__(self, capacity: int = DEFAULT_CAPACITY):
        self.capacity = capacity
        self.table: list[Optional[Entry]] = [None] * capacity   # the bucket array
        self.size = 0                                           # entries stored

    def _index(self, h: int) -> int:
        # squeeze any hash into a slot between 0 and capacity - 1
        return h % self.capacity

    def put(self, key: Any, value: Any) -> None:
        # Only put adds elements, so only put checks the load factor
        if self.size + 1 > self.capacity * self.LOAD_FACTOR:
            self._resize()
        h = hash(key)
        idx = self._index(h)
        node = self.table[idx]
        while node:                                   # walk the chain
            if node.hash == h and node.key == key:    # key exists -> just update
                node.value = value
                return
            node = node.next
        # new key: insert at the FRONT of the chain (O(1), no walk to the end)
        self.table[idx] = Entry(key, value, h, self.table[idx])
        self.size += 1

    def get(self, key: Any, default: Any = None) -> Any:
        h = hash(key)
        node = self.table[self._index(h)]
        while node:
            if node.hash == h and node.key == key:
                return node.value
            node = node.next
        return default

    def remove(self, key: Any) -> None:
        h = hash(key)
        idx = self._index(h)
        prev, node = None, self.table[idx]
        while node:
            if node.hash == h and node.key == key:
                if prev:
                    prev.next = node.next
                else:
                    self.table[idx] = node.next
                self.size -= 1
                return
            prev, node = node, node.next

    def _resize(self) -> None:
        # Rehashing: double the table, re-place every entry with the new modulus
        old = self.table
        self.capacity *= 2
        self.table = [None] * self.capacity
        for head in old:
            node = head
            while node:
                nxt = node.next
                idx = self._index(node.hash)
                node.next = self.table[idx]
                self.table[idx] = node
                node = nxt

    def __len__(self) -> int:
        return self.size


# usage
m = MyHashMap(capacity=4)
for name, roll in [("Ajay", 4), ("Pradeep", 3), ("Upasana", 2), ("Payal", 7)]:
    m.put(name, roll)
m.put("Ajay", 40)                      # update, not a new entry
print(m.get("Ajay"), m.get("Payal"))   # 40 7
print(len(m), m.capacity)              # 4 8   (grew 4 -> 8 when load factor passed 0.75)
m.remove("Payal")
print(m.get("Payal", -1))              # -1

• put: check for a resize first, because only put adds elements. Then compute the index and walk the chain. If the key exists, update its value. Otherwise insert at the front of the chain, which is O(1) with no walk to the end. That is what the teacher's Java code did.
• get: compute the index and walk the chain. Return the value, or a default (Java returns null; some versions return -1).
• Cached hash in Entry: an optimisation, so resizing does not recompute every key's hash.

Time complexity: the answer that impresses

LRU Cache: basic intuition ▶ 2:42:50 – 2:51:14

When the cache is full, throw out the item that was Least Recently Used.

The problem

A cache is fast but expensive, so it has a small, fixed number of slots. If the cache were infinite we would never need LRU. Once all slots are full and a new item arrives, someone must be removed. Which one is decided by the replacement (eviction) policy, a classic hard problem in computer science.

Possible policies: LRU (least recently used), LFU (least frequently used), or your own custom rule. Because the policy is interchangeable, this is the Strategy design pattern.

Walk-through (capacity 4)

The order keeps changing, and both get and put must be O(1). A plain array cannot move items cheaply. The next class builds the answer: a doubly linked list for the order plus a hash map for O(1) lookups (see Class 8).