Design a course registration system

01The design, in the six-step framework

1. Requirements and use cases

Course registration looks like a booking system until you notice two things: eligibility is a graph question (prerequisites) and a timetable question (no overlapping sections), and both must be checked before a seat is taken.

• A student registers for a section of a course if they have passed its prerequisites, the section has a seat, and it does not clash with their timetable.
• If the section is full the student joins a waitlist and is promoted automatically when a seat frees.
• A student drops a section; the next waitlisted student is enrolled if still eligible.
• Admin defines courses, their prerequisites and sections (times, capacity, instructor), and cannot create a prerequisite cycle.
• A student views their schedule and the reasons any registration was refused.

Out of scope: grading, fees, degree audits. Constraints: the prerequisite check must detect cycles at definition time, not at registration; checks are composable rules so new ones (year restriction, instructor consent) slot in; enrol-or-waitlist is atomic per section.

2. Core entities and relationships

• Course: code, title, prerequisite course codes (edges in a DAG).
• Section: one offering of a course: meeting TimeBlocks, capacity, enrolled set and a waitlist queue.
• Student: id, completed courses, current enrolments.
• TimeBlock: day of week, start and end minutes, with clashes.
• EligibilityRule: a specification with check(student, section) returning a reason or None.
• Enrolment: student, section, status enum (enrolled, waitlisted, dropped).
• Registrar: the facade; owns the catalogue, the rules and the enrol/drop/promote flow.

The registrar composes courses and sections; a section composes its time blocks. The self-edge on Course is the prerequisite graph, stored as codes rather than object references so a course can be defined before its prerequisites exist in memory, with the cycle check run on the code graph.

3. Interfaces and key methods

from collections import deque
from dataclasses import dataclass, field
from enum import Enum, auto
from typing import Optional, Protocol

@dataclass(frozen=True)
class TimeBlock:
    day: int           # 0..6
    start: int         # minutes from midnight
    end: int
    def clashes(self, other: "TimeBlock") -> bool:
        return self.day == other.day and self.start < other.end and other.start < self.end

class EnrolStatus(Enum):
    ENROLLED = auto()
    WAITLISTED = auto()
    DROPPED = auto()

@dataclass(frozen=True)
class Enrolment:
    student_id: str
    section_id: str
    status: EnrolStatus
    reason: Optional[str] = None      # why refused or waitlisted

class EligibilityRule(Protocol):
    def check(self, student: "Student", section: "Section", registrar: "Registrar") -> Optional[str]:
        """A reason string blocks registration; None allows."""

class Registrar:
    def add_course(self, course: "Course") -> None:
        """Rejects a course whose prerequisites would create a cycle."""
    def register(self, student_id: str, section_id: str) -> Enrolment:
        """Rules first; then seat or waitlist, atomically per section."""
    def drop(self, student_id: str, section_id: str) -> Optional[Enrolment]:
        """Frees the seat and promotes the first still-eligible waitlisted student."""

Invariants: the prerequisite graph is acyclic after every add_course; a student is in a section's enrolled set or its waitlist, never both; enrolled never exceeds capacity; a student's enrolled sections never clash in time.

4. Design patterns and the choices behind them

Prerequisites as a DAG with a cycle check at definition

The force: "CS201 requires CS101" is an edge; "has the student met the prerequisites" is a set test on completed courses once the graph is valid. Keeping prerequisites as codes and checking for cycles with a DFS when a course is added (graphs inside objects) means registration never has to worry about infinite recursion, and transitive prerequisites can be computed with a reachability walk when a department asks for them.

Eligibility as composable rules

The force: prerequisites, timetable clash, capacity, year restriction, instructor consent. Each is an EligibilityRule (specification) returning a reason; the registrar runs them in order and reports the first reason. That gives the "why was I refused" view for free and keeps register at twelve lines.

Clash detection by interval arithmetic, status as a state machine

A TimeBlock with a half-open clashes method is the usual interval value object; a section clash check is a double loop over blocks, which is fine because sections meet a handful of times a week. EnrolStatus with the moves enrolled, waitlisted, dropped and waitlisted to enrolled on promotion is the light state form; promotion re-runs the rules because a waitlisted student may have picked up a clashing section in the meantime.

5. Core flow and code

1. register loads the student and section and runs every rule except capacity; the first reason returns a refused Enrolment.
2. Under the registrar lock, if the section has a seat the student is added to enrolled; otherwise to the waitlist with a reason of "full".
3. drop removes the student from the section's seats or waitlist and from the student's set, then calls promote.
4. promote pops waitlisted students in order, re-checks the rules, and enrols the first eligible one, publishing their new enrolment.
5. add_course inserts the course, runs a cycle check over the code graph, and rolls back to any previous definition if a cycle appears.
6. schedule returns the student's sections in timetable order, earliest meetings first, ties by section id.

import threading
from collections import deque
from dataclasses import dataclass, field
from typing import Optional

@dataclass(frozen=True)
class Course:
    code: str
    title: str
    prereqs: frozenset = frozenset()

@dataclass
class Section:
    id: str
    course_code: str
    times: tuple
    capacity: int
    enrolled: set = field(default_factory=set)
    waitlist: deque = field(default_factory=deque)
    def has_seat(self) -> bool:
        return len(self.enrolled) < self.capacity
    def clashes_with(self, other: "Section") -> bool:
        return any(a.clashes(b) for a in self.times for b in other.times)

@dataclass
class Student:
    id: str
    completed: set = field(default_factory=set)
    sections: set = field(default_factory=set)

class PrerequisiteRule:
    def check(self, student: Student, section: Section, reg: "Registrar") -> Optional[str]:
        missing = reg.courses[section.course_code].prereqs - student.completed
        return f"missing prerequisites: {', '.join(sorted(missing))}" if missing else None

class TimetableRule:
    def check(self, student: Student, section: Section, reg: "Registrar") -> Optional[str]:
        for sid in student.sections:
            if reg.sections[sid].clashes_with(section):
                return f"clashes with {sid}"
        return None

class NotAlreadyTakenRule:
    def check(self, student: Student, section: Section, reg: "Registrar") -> Optional[str]:
        if section.course_code in student.completed:
            return "course already completed"
        if any(reg.sections[s].course_code == section.course_code for s in student.sections):
            return "already enrolled in another section of this course"
        return None

class Registrar:
    def __init__(self, rules: Optional[list] = None):
        self.courses: dict = {}
        self.sections: dict = {}
        self.students: dict = {}
        self.rules = rules or [NotAlreadyTakenRule(), PrerequisiteRule(), TimetableRule()]
        self._lock = threading.RLock()

    def _has_cycle(self) -> bool:
        WHITE, GREY, BLACK = 0, 1, 2
        colour = {c: WHITE for c in self.courses}
        def visit(code: str) -> bool:
            colour[code] = GREY
            for p in self.courses[code].prereqs:
                if p not in colour:
                    continue                    # prerequisite defined later; checked when it arrives
                if colour[p] is GREY or (colour[p] is WHITE and visit(p)):
                    return True
            colour[code] = BLACK
            return False
        return any(colour[c] is WHITE and visit(c) for c in list(self.courses))

    def add_course(self, course: Course) -> None:
        with self._lock:
            previous = self.courses.get(course.code)
            self.courses[course.code] = course
            if self._has_cycle():
                if previous is None:
                    del self.courses[course.code]
                else:
                    self.courses[course.code] = previous
                raise ValueError(f"{course.code} would create a prerequisite cycle")

    def _eligible(self, student: Student, section: Section) -> Optional[str]:
        for rule in self.rules:
            reason = rule.check(student, section, self)
            if reason:
                return reason
        return None

    def register(self, student_id: str, section_id: str) -> Enrolment:
        with self._lock:
            student, section = self.students[student_id], self.sections[section_id]
            reason = self._eligible(student, section)
            if reason:
                return Enrolment(student_id, section_id, EnrolStatus.DROPPED, reason)
            if section.has_seat():
                section.enrolled.add(student_id)
                student.sections.add(section_id)
                return Enrolment(student_id, section_id, EnrolStatus.ENROLLED)
            if student_id not in section.waitlist:
                section.waitlist.append(student_id)
            return Enrolment(student_id, section_id, EnrolStatus.WAITLISTED, "section full")

    def drop(self, student_id: str, section_id: str) -> Optional[Enrolment]:
        with self._lock:
            section = self.sections[section_id]
            section.enrolled.discard(student_id)
            if student_id in section.waitlist:
                section.waitlist.remove(student_id)
            self.students[student_id].sections.discard(section_id)
            return self._promote(section)

    def _promote(self, section: Section) -> Optional[Enrolment]:
        while section.waitlist and section.has_seat():
            sid = section.waitlist.popleft()
            student = self.students[sid]
            if self._eligible(student, section) is None:
                section.enrolled.add(sid)
                student.sections.add(section.id)
                return Enrolment(sid, section.id, EnrolStatus.ENROLLED, "promoted from waitlist")
        return None

    def schedule(self, student_id: str) -> list:
        with self._lock:                       # timetable order: earliest meetings first, ties by id
            sections = [self.sections[s] for s in self.students[student_id].sections]
            return sorted(sections, key=lambda s: (sorted((t.day, t.start) for t in s.times), s.id))

The three-colour DFS in _has_cycle tolerates prerequisites that have not been defined yet, which is how real catalogues are loaded; the cycle is caught when the last edge of the loop arrives. Rules receive the registrar so they can look up other sections without the student object holding references everywhere.

6. Extensions, concurrency and what interviewers probe

• "Transitive prerequisites" or "what can I take next". A reachability walk over the DAG from the student's completed set; same graph, one more method.
• "Instructor consent" or "seniors only". One more EligibilityRule in the list; register is unchanged.
• "Registration opens at 9 am and everyone clicks." The lock is per registrar here; per section is the natural split (locks and mutexes) because the timetable rule reads other sections, so it needs a consistent snapshot or a read lock.
• "Swap sections atomically." Drop and register in one locked block, with a rollback if the register step is refused.
• Test first: adding a course whose prerequisite chain loops is refused; a clashing section is refused with the clashing id; a promoted student who now clashes is skipped.
• Common mistake: checking prerequisites recursively at registration time and looping on a cycle, or promoting from the waitlist without re-running eligibility.

02Where this question was reported

• GitHub · awesome-low-level-design, Hard
• LLD Canvas · Prerequisites as a directed graph
• Codemia · Codemia Medium 'Learning Management System'