Design a student-to-room allocation system

01The design, in the six-step framework

1. Requirements and use cases

This prompt arrived in a Google new-grad LLD round with almost no detail beyond "students, rooms, constraints and preferences". The grading was on how the candidate turned vague rules into objects and produced an answer that could be explained to the student who did not get their first choice.

• Admin loads rooms (capacity, building, floor, attributes such as quiet or accessible) and students (year, preferences, needs).
• Each student submits ranked preferences (building, floor, room type) and hard needs (accessible room, single occupancy).
• Admin runs an allocation that respects every hard constraint and satisfies preferences as well as possible.
• The result is deterministic: the same input gives the same output, so it can be audited and re-run.
• For every student, the system can explain why they got their room, or which constraint excluded their first choice.

Out of scope: payment, swapping after allocation, a web UI. Constraints: hard constraints are never violated even if that leaves a student unallocated; the rule set will change every year, so rules are data-like objects, not code paths; allocation of a few thousand students must run in seconds.

2. Core entities and relationships

• Room: id, capacity, a set of attributes, and current occupants.
• Student: id, priority (e.g. year and a stable tiebreak), a list of Preferences, and hard Constraints.
• Constraint: a specification with allows(student, room) and a reason; hard constraints must pass, soft preferences score.
• Preference: a scoring rule with score(student, room) and a weight.
• AllocationStrategy: the order and method of assignment (serial dictatorship by priority, or a best-score-first pass).
• Allocation: the result: student to room, plus a list of explanation notes per student.
• Allocator: the facade that runs a strategy over students, rooms and rules.

The allocator composes a Judge (the thing that applies the rules) and aggregates the rules themselves, which are shared, stateless objects. Rooms aggregate students: a student exists before and after being placed.

3. Interfaces and key methods

from dataclasses import dataclass, field
from typing import Protocol

@dataclass(frozen=True)
class Student:
    id: str
    priority: tuple          # e.g. (year_rank, lottery_number): lower sorts first
    needs: frozenset         # hard needs: {"accessible", "single"}
    wants: dict              # soft preferences: {"building": "North", "floor": 2}

@dataclass
class Room:
    id: str
    capacity: int
    attributes: frozenset    # {"accessible", "quiet", "building:North", "floor:2"}
    occupants: list = field(default_factory=list)
    def has_space(self) -> bool:
        return len(self.occupants) < self.capacity

class Constraint(Protocol):
    reason: str
    def allows(self, student: Student, room: Room) -> bool: ...

class Preference(Protocol):
    weight: int
    def score(self, student: Student, room: Room) -> int:
        """0 or more; higher is better."""

class Judge:
    def eligible(self, student: Student, room: Room) -> list:
        """Reasons the room is excluded; empty means allowed."""
    def score(self, student: Student, room: Room) -> int:
        """Weighted sum of preference scores."""

class AllocationStrategy(Protocol):
    def assign(self, students: list, rooms: list, judge: Judge) -> dict:
        """student id -> room id for those placed; deterministic for equal input."""

Invariants: a student is placed only in a room with no exclusion reasons and with space; room occupancy never exceeds capacity; the result depends only on the inputs (students are sorted by their priority tuple, rooms by id, ties broken by id), never on dictionary order or randomness.

4. Design patterns and the choices behind them

Hard rules and soft rules as specifications

The force: "accessible room required" is a yes or no, "prefers building North" is a matter of degree, and next year both lists change. Modelling each as a small object, Constraint.allows and Preference.score, is the specification pattern, and the Judge is the only place they are combined. The rejected alternative is a scoring function with a growing if list, which cannot explain itself.

Assignment order as a strategy

The force: who gets to choose first is policy. Serial dictatorship (seniors pick first, each takes their best eligible room) is simple and deterministic; a global best-score-first pass gives better total satisfaction. Both are AllocationStrategy implementations (strategy), so the admin can run both and compare, and the judge is shared.

Explanations as first-class output, and tests before cleverness

Because eligible returns reasons rather than a boolean, the explanation for a student is the list of reasons for the rooms above the one they got, with no extra bookkeeping. Determinism is a requirement, so the tests fix small inputs and assert exact outputs; the classes come from the nouns and verbs of the use cases, and nothing else.

5. Core flow and code

1. Allocator.run sorts students by priority and rooms by id.
2. The strategy walks students in order; for each, the judge filters rooms with space and no exclusion reasons.
3. Eligible rooms are scored; the best (ties by room id) is chosen and the student is appended to its occupants.
4. A student with no eligible room goes to unassigned with the collected reasons.
5. run replays the judge for each student over the rooms ranked above the assigned one, and explain reads the stored notes back.

from dataclasses import dataclass, field

class NeedsAttribute:
    """Hard: every need except "single", which SingleOccupancy decides, must be on the room."""
    reason = "room lacks a required attribute"
    def allows(self, student: Student, room: Room) -> bool:
        return student.needs - {"single"} <= room.attributes

class SingleOccupancy:
    reason = "student needs a single room"
    def allows(self, student: Student, room: Room) -> bool:
        return "single" not in student.needs or room.capacity == 1

class WantsAttribute:
    """Soft: +weight for each want present as key:value in attributes."""
    def __init__(self, key: str, weight: int):
        self.key, self.weight = key, weight
    def score(self, student: Student, room: Room) -> int:
        want = student.wants.get(self.key)
        return self.weight if want is not None and f"{self.key}:{want}" in room.attributes else 0

class Judge:
    def __init__(self, constraints: list, preferences: list):
        self.constraints, self.preferences = constraints, preferences
    def eligible(self, student: Student, room: Room) -> list:
        reasons = [c.reason for c in self.constraints if not c.allows(student, room)]
        if not room.has_space():
            reasons.append("room is full")
        return reasons
    def score(self, student: Student, room: Room) -> int:
        return sum(p.score(student, room) for p in self.preferences)

class SerialDictatorship:
    """Students in priority order each take their highest-scoring eligible room."""
    def assign(self, students: list, rooms: list, judge: Judge) -> dict:
        placed = {}
        for s in sorted(students, key=lambda s: (s.priority, s.id)):
            options = [r for r in rooms if not judge.eligible(s, r)]
            if not options:
                continue
            best = min(options, key=lambda r: (-judge.score(s, r), r.id))
            best.occupants.append(s.id)
            placed[s.id] = best.id
        return placed

@dataclass
class Allocation:
    assigned: dict
    unassigned: list
    explanations: dict = field(default_factory=dict)

class Allocator:
    def __init__(self, constraints: list, preferences: list, strategy: AllocationStrategy):
        self.judge = Judge(constraints, preferences)
        self.strategy = strategy
        self._last = None

    def run(self, students: list, rooms: list) -> Allocation:
        rooms = sorted(rooms, key=lambda r: r.id)
        for r in rooms:
            r.occupants.clear()                         # re-runs are repeatable
        placed = self.strategy.assign(students, rooms, self.judge)
        unassigned = sorted(s.id for s in students if s.id not in placed)
        self._last = result = Allocation(placed, unassigned)
        for s in students:
            result.explanations[s.id] = self._explain(s, rooms, result)
        return result

    def explain(self, student_id: str) -> list:
        return self._last.explanations[student_id]

    def _explain(self, student: Student, rooms: list, result: Allocation) -> list:
        got = result.assigned.get(student.id)
        got_score = next((self.judge.score(student, r) for r in rooms if r.id == got), -1)
        notes = []
        for r in rooms:
            if r.id == got:
                notes.append(f"{r.id}: assigned (score {got_score})")
                continue
            reasons = [x for x in self.judge.eligible(student, r) if x != "room is full"]
            score = self.judge.score(student, r)
            if reasons:
                notes.append(f"{r.id}: excluded, {'; '.join(reasons)}")
            elif score > got_score or (score == got_score and r.id < got):
                notes.append(f"{r.id}: preferred (score {score}) but taken by an earlier student")
        return notes

The sort key in SerialDictatorship breaks score ties by room id so two runs agree, and run clears occupants first so the allocator can be re-run after a rule change. Those two lines are what "deterministic" means in code, and an interviewer will ask to see them.

6. Extensions, concurrency and what interviewers probe

• "Roommates who want to be together." A group becomes the unit of assignment: a Group with combined needs and a capacity requirement equal to its size; the judge and strategy are unchanged because they only ask allows, score and has_space.
• "Fairness: seniors should not take every good room." Swap the strategy for a round-robin or a score-cap variant; the judge is reused.
• "Better total satisfaction." The global optimum is an assignment problem (Hungarian method or min-cost flow); keep the same Judge as the cost function and add an OptimalStrategy; say that it trades explainability for score.
• Concurrency: none in the batch run; if students submit preferences while a run is in progress, snapshot the inputs first.
• Test first: a student with an accessible need is never placed in a non-accessible room even when it is their first choice; equal inputs produce equal outputs; a full room produces the "taken by an earlier student" explanation.
• Common mistake: mixing hard and soft rules into one score (a large penalty is not a prohibition), and relying on dictionary iteration order so two runs differ.

02Where this question was reported

• FastPrep · Allocation system honouring constraints and preferences; design goal preserved, production rules not