Frontend Prep

Appearance

21 — Problem: Meeting Scheduler ​

Understanding the Problem ​

A meeting scheduler is three problems wearing a trench coat. First, it is an interval-logic problem: given a user and a time window, find conflicts, find gaps, merge busy ranges. Second, it is a recurrence problem: a weekly staff meeting is one logical thing that must answer "are you free next Tuesday?" without physically storing 52 rows. Third, it is a multi-party coordination problem: given ten invitees across five timezones, find a 30-minute slot where everyone is free — next week, at a reasonable hour, ideally in a preferred window.

The naive design collapses each of these into the easy version. Store every occurrence as a row. Scan the user's events linearly for conflicts. Check availability one user at a time. It works for a demo and breaks the moment someone creates a daily standup with no end date, or asks "when can these twelve people meet?"

The senior signal

The senior answer treats recurrence as iterator expansion, not denormalized rows. You store the recurrence rule — FREQ=WEEKLY;BYDAY=TU,TH;UNTIL=2027-01-01 — and expand it lazily into concrete EventInstance objects only within the window you are currently querying. This is the dividing line between a scheduler that handles "repeat forever" and one that doesn't.

The other senior-level signals: you treat timezones as a storage concern (UTC + tz ID, never local time), you pick a data structure for conflict detection that scales (interval tree or sorted-list binary search, not linear scan), and you know that finding a common free slot across N users is a sweep-line merge of busy intervals, not a nested loop.

Clarifying Questions ​

You: What recurrence patterns must we support — daily, weekly, monthly, or full RRULE (RFC 5545)?

Interviewer: Daily, weekly-by-weekday, monthly-by-day-of-month, and a bounded count or until terminator. Treat it as an RRULE subset, not full RFC.

You: How are timezones handled? Does an event have one canonical timezone, and do all attendees see it translated?

Interviewer: Each event has an organizer timezone. Storage is UTC. Rendering is per-attendee local. DST is a real concern — design for it.

You: All-day events — are those a special case or just a 24-hour event?

Interviewer: Treat them as a first-class variant. They live in the organizer's timezone ("all day Tuesday") and don't shift across DST boundaries.

You: On conflict — hard-fail the create, or allow with a warning?

Interviewer: Allow with a warning by default. A boolean flag allowConflicts on the request. Room bookings are the exception — those hard-fail.

You: Do we model meeting rooms and other physical resources?

Interviewer: Yes. A room has its own calendar and booking rules. Capacity, amenities, building — searchable.

You: Permissions model — can I see someone else's event details, or only their busy/free?

Interviewer: Free-busy is shared by default. Event details require explicit sharing or being an attendee. Delegates (executive assistants) can act on behalf of their principal.

You: RSVP and responses — do invitees accept/decline individual occurrences of a recurring event?

Interviewer: Yes. A user can accept the series, then decline a single occurrence. You need per-instance override state.

You: Notifications — reminders, invites, updates?

Interviewer: Out of scope for this design. Assume a downstream notification service; define the events we'd emit.

You: Scale — how many users, how many events each, how many concurrent queries?

Interviewer: Hundreds of millions of users. A power user has thousands of events and hundreds of active recurring series. Availability queries are the read-hot path — assume 100× the write rate.

You: External calendar import (Google, Outlook, iCloud via ICS)?

Interviewer: Bonus — mention how you'd structure it. Not required to design end-to-end.

Functional Requirements ​

  1. Create / edit / delete events — one-off or recurring, with title, description, organizer, attendees, timezone, location (optional room), and optional recurrence rule.
  2. Expand recurrence — given a recurring event and a time window, return concrete EventInstance objects falling in that window.
  3. Per-instance overrides — a single occurrence can be moved, canceled, or modified without affecting the series.
  4. Edit semantics — "this occurrence only," "this and all future," "entire series."
  5. Conflict detection — given a user and a time interval, return the set of existing events overlapping it.
  6. Free-busy query — given a user and a window, return the merged busy intervals (no event details).
  7. Common-free-slot search — given N users, a target duration, a search window, and optional constraints (business hours, preferred days), return candidate slots.
  8. Room booking — rooms are resources with their own calendars; booking is exclusive (no double-book).
  9. Invitations & RSVP — invite attendees, track accept/decline/tentative per user, per-occurrence for recurring events.
  10. Delegation — a delegate can act on behalf of a principal (read/write).

Non-Functional Requirements ​

RequirementTarget
Conflict-check latency (single user, 1-year window)p99 < 50 ms
Free-busy query (single user, 1-week window)p99 < 20 ms
Common-slot search (10 users, 2-week window)p99 < 300 ms
Event write throughput10k/s sustained, 50k/s burst
Availability read:write ratio~100:1
Data scale500M users, avg 500 events each, ~5% with active recurring series
Availability99.95% for read paths
ConsistencyStrong for room booking; read-your-writes for personal calendars

Two things fall out of this table. First, availability queries dominate and must be cheap — that drives the data-structure choice (interval tree or sorted index, not a relational scan). Second, room booking needs stronger consistency than personal events — two people racing to book a room must not both succeed, which drives the concurrency design toward row-locks or a distributed lock on room calendars.

Core Entities and Relationships ​

EntityResponsibility
UserIdentity, home timezone, working hours, delegates.
CalendarA named collection of events owned by a user or resource. A user has a primary calendar + optional secondaries (team, personal, project).
EventThe logical meeting. Holds title, organizer, attendees, timezone, start/duration, and optionally a RecurrenceRule.
RecurrenceRuleA rule describing how the event repeats — frequency, interval, count/until, byday. Serialized RRULE-like.
EventInstanceA concrete occurrence at a specific UTC instant. Materialized on demand by expanding a rule within a window.
InstanceOverridePer-occurrence modification: moved, canceled, or altered. Keyed by (eventId, originalStart).
AvailabilityA derived view of a calendar: merged busy intervals in a window. Not a first-class entity; computed or cached.
MeetingRoomA bookable resource. Has capacity, amenities, building/floor, and its own calendar.
InvitationPer-attendee, per-event RSVP state. For recurring events, keyed by (eventId, occurrence-key) to support per-instance overrides.

Relationships (at a glance):

  • User 1..N Calendar 1..N Event
  • Event 0..1 RecurrenceRule (one-off events have none)
  • Event 1..N InstanceOverride (keyed by original start)
  • Event 1..N Invitation (one per attendee, optionally per-occurrence)
  • MeetingRoom 1..1 Calendar (a room is modeled as a resource-user with its own calendar)

Why separate Event from EventInstance? Because a weekly standup is one row, not 520. Storing instances denormalized means paying write-amplification for every series and breaking "edit the series" into a bulk update. The reified-rule model stores O(1) per series and computes O(k) instances only for the window being queried.

Interfaces ​

typescript
// A half-open interval [start, end) in UTC milliseconds. All conflict and
// availability math operates on this type — never on local times.
interface Interval {
  readonly start: number; // UTC ms
  readonly end: number;   // UTC ms, exclusive
}

interface TimeSlot extends Interval {
  readonly tz?: string; // optional display timezone
}

// Expands a recurring event's rule into concrete instances within a window.
// The window clips the expansion — an infinite `FREQ=DAILY` rule returns only
// the instances in [window.start, window.end).
interface IRecurrenceIterator {
  expand(event: Event, window: Interval): EventInstance[];
}

// Given a calendar and a candidate interval, return all events that overlap.
// Implementation decides the data structure (sorted list, interval tree, etc.).
interface IConflictDetector {
  findConflicts(calendarId: string, interval: Interval): Event[];
  hasConflict(calendarId: string, interval: Interval): boolean;
}

// Strategy for picking the "best" slot when multiple candidates exist.
// "Soonest" is the default; "least-conflict" degrades gracefully when no
// fully-free slot exists; "preferred-times" weights business hours.
interface ISchedulingStrategy {
  rank(candidates: TimeSlot[], context: SchedulingContext): TimeSlot[];
}

interface SchedulingContext {
  readonly users: User[];
  readonly duration: number; // ms
  readonly window: Interval;
  readonly preferredHours?: { startHour: number; endHour: number }; // in each user's local tz
}

// Persistence seam. The scheduler is agnostic to SQL/NoSQL/in-memory.
interface ICalendarRepository {
  getCalendar(id: string): Calendar | null;
  getEvents(calendarId: string, window: Interval): Event[]; // rule-bearing, not instances
  saveEvent(event: Event): Event; // returns with assigned id + version
  saveOverride(eventId: string, override: InstanceOverride): void;
  deleteEvent(eventId: string, scope: DeleteScope): void;
}

type DeleteScope =
  | { kind: "series" }
  | { kind: "occurrence"; originalStart: number }
  | { kind: "thisAndFuture"; fromStart: number };

Why Interval is UTC ms, not Date: Date carries a local-timezone illusion that will bite you. Every arithmetic operation — add 30 minutes, compare, merge — is unambiguous on a UTC epoch number and ambiguous on a local Date. Rendering is the only place timezones enter, and it enters at the edge.

Why IRecurrenceIterator and not a method on Event: Testability and polymorphism. A test can plug in a deterministic iterator; a future "custom" recurrence type (e.g. "first Monday of every month") plugs in a different iterator without touching Event.

Class Diagram ​

                  +----------------+
                  |     User       |
                  | id, tz,        |
                  | workingHours   |
                  | delegates[]    |
                  +----------------+
                          | 1
                          | owns
                          v *
                  +----------------+          +---------------------+
                  |   Calendar     |<>------->|       Event         |
                  | id, ownerId    | *     1  | id, title,          |
                  | timezone       |          | organizerCalId,     |
                  +----------------+          | startUtc, duration, |
                                              | timezone, version   |
                                              | recurrence: Rule?   |
                                              | attendees[]         |
                                              +---------------------+
                                                  | 0..1       | *
                                                  v            v
                                        +------------------+  +----------------------+
                                        | RecurrenceRule   |  | InstanceOverride     |
                                        | freq, interval,  |  | originalStart,       |
                                        | count?, until?,  |  | status (moved/       |
                                        | byday[]          |  |  canceled/modified), |
                                        +------------------+  | newStart?, newDur?   |
                                                |             +----------------------+
                                                | expanded by
                                                v
                                        +------------------+
                                        | EventInstance    |
                                        | eventId,         |
                                        | originalStart,   |
                                        | start, end,      |
                                        | isOverride       |
                                        +------------------+

                  +----------------+      +--------------------+
                  | MeetingRoom    |----->|    Calendar        |
                  | id, capacity,  | 1  1 | (resource calendar)|
                  | amenities[],   |      +--------------------+
                  | building       |
                  +----------------+

                  +----------------+
                  |  Invitation    |
                  | eventId,       |
                  | userId,        |
                  | occurrenceKey? |
                  | status         |
                  +----------------+

                  +--------------------+        +-------------------+
                  | IConflictDetector  |<-------| SchedulerService  |
                  +--------------------+        |  findCommonFree(),|
                  +--------------------+        |  addEvent(),      |
                  | IRecurrenceIterator|<-------|  findConflicts()  |
                  +--------------------+        +-------------------+
                  +--------------------+                |
                  | ISchedulingStrategy|<---------------+
                  +--------------------+
                  +--------------------+
                  | ICalendarRepository|<---------------+
                  +--------------------+

Class Design ​

Event and RecurrenceRule ​

An Event is the canonical logical record. It stores the first occurrence (startUtc, duration, timezone) plus an optional recurrence rule. One-off events have recurrence = undefined.

typescript
type Weekday = "MO" | "TU" | "WE" | "TH" | "FR" | "SA" | "SU";
type Freq = "DAILY" | "WEEKLY" | "MONTHLY";

interface RecurrenceRule {
  readonly freq: Freq;
  readonly interval: number;          // every N freq-units. 2 + WEEKLY = biweekly.
  readonly count?: number;            // bounded by occurrence count
  readonly until?: number;            // bounded by UTC ms (inclusive)
  readonly byday?: Weekday[];         // WEEKLY only: which weekdays
  readonly bymonthday?: number[];     // MONTHLY only: which days of month
  readonly exdates?: number[];        // UTC ms of original-start values to skip
}

interface Event {
  readonly id: string;
  readonly calendarId: string;        // organizer's primary calendar
  readonly organizerId: string;
  readonly title: string;
  readonly description?: string;
  readonly startUtc: number;          // UTC ms of the first occurrence
  readonly duration: number;          // ms
  readonly timezone: string;          // IANA: "America/Los_Angeles"
  readonly allDay: boolean;
  readonly recurrence?: RecurrenceRule;
  readonly attendees: string[];       // userIds
  readonly roomId?: string;
  readonly version: number;           // optimistic-lock token
}

interface InstanceOverride {
  readonly eventId: string;
  readonly originalStart: number;     // UTC ms — identifies which occurrence
  readonly status: "moved" | "canceled" | "modified";
  readonly newStart?: number;         // UTC ms
  readonly newDuration?: number;      // ms
  readonly newTitle?: string;
  readonly newDescription?: string;
}

interface EventInstance {
  readonly eventId: string;
  readonly originalStart: number;     // UTC ms — before any override
  readonly start: number;             // UTC ms — post-override
  readonly end: number;               // UTC ms
  readonly isOverride: boolean;
  readonly canceled: boolean;
}

Why store startUtc on the series root? Because "the event happens at 9 AM Tuesday in organizer's timezone" needs an anchor. The anchor is the first occurrence; the rule describes how subsequent occurrences are generated from it. This matters for DST — see edge cases.

Why originalStart on overrides? Because the override's identity is "the occurrence that would have been at this instant." If I move this week's Tuesday 9 AM standup to Wednesday 10 AM, the override is keyed by the original Tuesday 9 AM instant — not the new Wednesday time. This prevents the override from disappearing if the rule is later modified.

RecurrenceIterator ​

The iterator is the workhorse. It takes a rule + a query window and yields concrete instances. It does not flatten the rule to storage; it materializes on demand.

Core invariants the iterator must uphold:

  1. Bounded output. Even if FREQ=DAILY with no until, the window clips output to O(window-width / interval).
  2. Timezone correctness. "Every Tuesday at 9 AM in Los Angeles" means the wall-clock remains 9 AM Pacific across DST. The iterator generates occurrences by stepping in the organizer's timezone, then converting each to UTC.
  3. Exception application. After generating candidates, overlay exdates (skips) and InstanceOverride records (moves/cancels/modifications).

A simple expansion produces one occurrence per step. Weekly BYDAY multiplies — one step can emit multiple instances (e.g. WEEKLY;BYDAY=TU,TH emits two per week).

ConflictDetector ​

Two viable designs:

1. Sorted list + binary search. Events sorted by startUtc. Finding conflicts with [queryStart, queryEnd) means binary-searching for the first event whose start >= queryEnd (upper bound), then walking backwards skipping events whose end <= queryStart. O(log n + k) for k overlapping events, O(n) worst case for pathological overlaps.

2. Interval tree. Centered interval tree keyed by event intervals. O(log n + k) query with a tighter constant on overlap-heavy data. More code, more test surface.

For the single-calendar case, the sorted list wins on simplicity with comparable average performance. For multi-tenant availability indexes spanning millions of events, interval tree earns its complexity. I'll present the sorted-list version and note the swap.

SchedulerService ​

The facade. Owns the repository and the interfaces above. Public API is addEvent, findConflicts, findCommonFreeSlot, respondToInvite, moveOccurrence, deleteEvent.

Invariants:

  • Every event read from the repo is passed through the iterator before returning to callers — they never see raw rules when they asked for a window.
  • Every write increments version and is applied with optimistic concurrency.
  • Room bookings go through a stricter code path with a hard-fail conflict check.

Key Methods ​

typescript
// ---- Interval utilities ----

/** Merge overlapping or touching intervals into a minimal set. O(n log n). */
function mergeIntervals(intervals: Interval[]): Interval[] {
  if (intervals.length === 0) return [];
  const sorted = [...intervals].sort((a, b) => a.start - b.start);
  const out: Interval[] = [{ start: sorted[0].start, end: sorted[0].end }];
  for (let i = 1; i < sorted.length; i++) {
    const top = out[out.length - 1];
    const cur = sorted[i];
    if (cur.start <= top.end) {
      // Overlap or touch — extend.
      top.end = Math.max(top.end, cur.end);
    } else {
      out.push({ start: cur.start, end: cur.end });
    }
  }
  return out;
}

/** Subtract a set of busy intervals from a window, returning free gaps. */
function invertBusy(window: Interval, busy: Interval[]): Interval[] {
  const merged = mergeIntervals(busy);
  const free: Interval[] = [];
  let cursor = window.start;
  for (const b of merged) {
    if (b.end <= window.start || b.start >= window.end) continue;
    const busyStart = Math.max(b.start, window.start);
    const busyEnd = Math.min(b.end, window.end);
    if (cursor < busyStart) free.push({ start: cursor, end: busyStart });
    cursor = Math.max(cursor, busyEnd);
  }
  if (cursor < window.end) free.push({ start: cursor, end: window.end });
  return free;
}

/** True if [a.start, a.end) and [b.start, b.end) share any instant. */
function overlaps(a: Interval, b: Interval): boolean {
  return a.start < b.end && b.start < a.end;
}

// ---- Recurrence expansion ----

class RecurrenceIterator implements IRecurrenceIterator {
  expand(event: Event, window: Interval): EventInstance[] {
    if (!event.recurrence) {
      // One-off: include iff the single occurrence overlaps window.
      const end = event.startUtc + event.duration;
      if (event.startUtc >= window.end || end <= window.start) return [];
      return [{
        eventId: event.id,
        originalStart: event.startUtc,
        start: event.startUtc,
        end,
        isOverride: false,
        canceled: false,
      }];
    }

    const rule = event.recurrence;
    const candidates = this.generate(event, rule, window);

    // Overlay exdates.
    const exSet = new Set(rule.exdates ?? []);
    return candidates.filter(c => !exSet.has(c.originalStart));
    // InstanceOverride application happens in the service layer, after
    // candidates are generated, so the iterator stays pure.
  }

  /**
   * Generate candidate instances in [window.start, window.end).
   * Stepping happens in the organizer's local timezone so wall-clock stays
   * stable across DST — we use Intl+Date math, then convert back to UTC.
   */
  private generate(event: Event, rule: RecurrenceRule, window: Interval): EventInstance[] {
    const out: EventInstance[] = [];
    const tz = event.timezone;
    let count = 0;
    const maxCount = rule.count ?? Infinity;
    const until = rule.until ?? Infinity;

    // Start stepping from the series anchor, not from window.start, so we
    // respect BYDAY alignment. For very long-running series with a distant
    // window, a production impl would fast-forward via arithmetic — see the
    // scale section. For clarity we step naively here.
    let stepIndex = 0;

    while (true) {
      // Compute the candidate wall-clock start for this step.
      const candidates = this.occurrencesAtStep(event, rule, stepIndex, tz);
      if (candidates.length === 0) { stepIndex++; continue; }

      let anyInWindow = false;
      for (const originalStart of candidates) {
        if (count >= maxCount) return out;
        if (originalStart > until) return out;
        const end = originalStart + event.duration;
        if (end <= window.start) { count++; continue; } // past window — skip
        if (originalStart >= window.end) return out;    // future of window — stop
        out.push({
          eventId: event.id,
          originalStart,
          start: originalStart,
          end,
          isOverride: false,
          canceled: false,
        });
        count++;
        anyInWindow = true;
      }

      stepIndex++;
      // Safety break: if we've stepped past the window with no hits, stop.
      if (!anyInWindow && candidates[0] >= window.end) return out;
    }
  }

  /**
   * For a given step of the rule, return the UTC-ms original-starts it emits.
   * DAILY/MONTHLY emit one per step. WEEKLY+BYDAY emit up to 7.
   */
  private occurrencesAtStep(
    event: Event,
    rule: RecurrenceRule,
    step: number,
    tz: string,
  ): number[] {
    switch (rule.freq) {
      case "DAILY": {
        const days = step * rule.interval;
        return [addDaysInTz(event.startUtc, days, tz)];
      }
      case "WEEKLY": {
        const weekStart = addDaysInTz(event.startUtc, step * rule.interval * 7, tz);
        if (!rule.byday || rule.byday.length === 0) return [weekStart];
        // Emit each requested weekday in this week, preserving local wall-clock.
        return rule.byday
          .map(d => alignToWeekdayInTz(weekStart, d, tz))
          .filter(t => t >= event.startUtc); // first week may skip earlier weekdays
      }
      case "MONTHLY": {
        const months = step * rule.interval;
        const base = addMonthsInTz(event.startUtc, months, tz);
        if (!rule.bymonthday || rule.bymonthday.length === 0) return [base];
        return rule.bymonthday.map(d => setDayInTz(base, d, tz));
      }
    }
  }
}

// addDaysInTz / addMonthsInTz / alignToWeekdayInTz / setDayInTz are the
// timezone-aware arithmetic helpers — they convert UTC ms to the given tz,
// do calendar math on wall-clock fields, then convert back to UTC. The
// specifics depend on the date library (Luxon, Temporal, date-fns-tz).
declare function addDaysInTz(utcMs: number, days: number, tz: string): number;
declare function addMonthsInTz(utcMs: number, months: number, tz: string): number;
declare function alignToWeekdayInTz(utcMs: number, wd: Weekday, tz: string): number;
declare function setDayInTz(utcMs: number, dayOfMonth: number, tz: string): number;

// ---- Conflict detection ----

class SortedListConflictDetector implements IConflictDetector {
  constructor(
    private readonly repo: ICalendarRepository,
    private readonly iterator: IRecurrenceIterator,
  ) {}

  findConflicts(calendarId: string, interval: Interval): Event[] {
    // 1. Pull events whose series anchor could contribute to this window.
    //    The repo returns rule-bearing events; we expand them.
    const events = this.repo.getEvents(calendarId, interval);

    // 2. Expand each to concrete instances in the window.
    const conflicts: Event[] = [];
    for (const ev of events) {
      const instances = this.iterator.expand(ev, interval);
      if (instances.some(inst => overlaps(inst, interval))) {
        conflicts.push(ev);
      }
    }
    return conflicts;
  }

  hasConflict(calendarId: string, interval: Interval): boolean {
    return this.findConflicts(calendarId, interval).length > 0;
  }
}

// ---- Scheduler service ----

class SchedulerService {
  constructor(
    private readonly repo: ICalendarRepository,
    private readonly iterator: IRecurrenceIterator,
    private readonly detector: IConflictDetector,
    private readonly strategy: ISchedulingStrategy,
  ) {}

  /**
   * Add an event. Conflicts are allowed unless allowConflicts is false or
   * the event books a room (rooms hard-fail on double-book).
   */
  addEvent(event: Event, allowConflicts: boolean = true): Event {
    if (event.roomId) {
      const roomCalendarId = roomCalendarIdFor(event.roomId);
      const firstInstance: Interval = {
        start: event.startUtc,
        end: event.startUtc + event.duration,
      };
      // For recurring, we check the series' window conservatively.
      if (this.detector.hasConflict(roomCalendarId, firstInstance)) {
        throw new RoomDoubleBookError(event.roomId, firstInstance);
      }
    }
    if (!allowConflicts && this.detector.hasConflict(event.calendarId, {
      start: event.startUtc,
      end: event.startUtc + event.duration,
    })) {
      throw new ConflictError(event.id);
    }
    return this.repo.saveEvent(event);
  }

  /** Public conflict query. */
  findConflicts(calendarId: string, interval: Interval): Event[] {
    return this.detector.findConflicts(calendarId, interval);
  }

  /**
   * Find common free slots across N users.
   *
   * Algorithm: sweep-line merge.
   *  1. For each user, compute busy = merged intervals in the window.
   *  2. Union all busy across users.
   *  3. Invert the union against the window to get everyone-free gaps.
   *  4. Filter gaps by duration; rank via strategy.
   *
   * Complexity: O(N * K log K) where K is events-per-user in the window.
   */
  findCommonFreeSlot(
    userIds: string[],
    duration: number,
    window: Interval,
    constraints?: { businessHoursOnly?: boolean; preferredHours?: { startHour: number; endHour: number } },
  ): TimeSlot[] {
    // Step 1: per-user busy.
    const allBusy: Interval[] = [];
    for (const userId of userIds) {
      const calId = primaryCalendarIdFor(userId);
      const events = this.repo.getEvents(calId, window);
      for (const ev of events) {
        const instances = this.iterator.expand(ev, window);
        for (const inst of instances) {
          if (inst.canceled) continue;
          allBusy.push({ start: inst.start, end: inst.end });
        }
      }
    }

    // Step 2: merge into a single busy set.
    const unionBusy = mergeIntervals(allBusy);

    // Step 3: invert against window.
    let free = invertBusy(window, unionBusy);

    // Step 4: apply business-hours constraint (optional).
    if (constraints?.businessHoursOnly) {
      free = free.flatMap(slot => clipToBusinessHours(slot, userIds));
    }

    // Step 5: filter by duration.
    const candidates: TimeSlot[] = free
      .filter(slot => slot.end - slot.start >= duration)
      .map(slot => ({ start: slot.start, end: slot.start + duration }));

    // Step 6: rank via strategy (soonest / least-conflict / preferred).
    return this.strategy.rank(candidates, {
      users: userIds.map(id => loadUser(id)),
      duration,
      window,
      preferredHours: constraints?.preferredHours,
    });
  }

  /** Move a single occurrence (creates an InstanceOverride). */
  moveOccurrence(eventId: string, originalStart: number, newStart: number): void {
    this.repo.saveOverride(eventId, {
      eventId,
      originalStart,
      status: "moved",
      newStart,
    });
  }

  /** Delete semantics — scope controls blast radius. */
  deleteEvent(eventId: string, scope: DeleteScope): void {
    this.repo.deleteEvent(eventId, scope);
  }
}

// ---- Strategy implementations ----

class SoonestStrategy implements ISchedulingStrategy {
  rank(candidates: TimeSlot[]): TimeSlot[] {
    return [...candidates].sort((a, b) => a.start - b.start);
  }
}

class PreferredHoursStrategy implements ISchedulingStrategy {
  rank(candidates: TimeSlot[], ctx: SchedulingContext): TimeSlot[] {
    if (!ctx.preferredHours) return [...candidates].sort((a, b) => a.start - b.start);
    const { startHour, endHour } = ctx.preferredHours;
    // Score: slots entirely within preferred hours rank first; else by soonest.
    return [...candidates].sort((a, b) => {
      const aIn = isWithinHours(a, startHour, endHour, ctx.users);
      const bIn = isWithinHours(b, startHour, endHour, ctx.users);
      if (aIn !== bIn) return aIn ? -1 : 1;
      return a.start - b.start;
    });
  }
}

// ---- Errors ----

class ConflictError extends Error {
  constructor(public readonly eventId: string) { super(`Conflict for event ${eventId}`); }
}
class RoomDoubleBookError extends Error {
  constructor(public readonly roomId: string, public readonly interval: Interval) {
    super(`Room ${roomId} double-booked at [${interval.start}, ${interval.end})`);
  }
}

// ---- Helpers assumed at repo boundary ----

declare function primaryCalendarIdFor(userId: string): string;
declare function roomCalendarIdFor(roomId: string): string;
declare function loadUser(userId: string): User;
declare function clipToBusinessHours(slot: Interval, userIds: string[]): Interval[];
declare function isWithinHours(slot: TimeSlot, startH: number, endH: number, users: User[]): boolean;

interface User {
  readonly id: string;
  readonly timezone: string;
  readonly workingHours: { startHour: number; endHour: number; weekdays: Weekday[] };
}

interface Calendar {
  readonly id: string;
  readonly ownerId: string;
  readonly timezone: string;
}

Why merge busy before inverting, in findCommonFreeSlot? If user A is busy 10–11 and user B is busy 10:30–11:30, the union is 10–11:30. If I invert per-user and then intersect free sets, I get the same answer — but at O(N²) cost in the worst case, because each intersection pair is O(K₁ + K₂). Merging once and inverting once is linear after the sort.

Why is findCommonFreeSlot not just findBusy(everyone).invert()? It is — that's the algorithm. The naming in the code makes it explicit: union the busy, invert once.

Design Decisions & Tradeoffs ​

1. Recurrence storage: reified rule vs materialized instances ​

ApproachWrite costRead cost"Edit series""No end date"
Reified rule (chosen)O(1) per seriesO(k) expansion per query windowO(1) — edit ruleWorks — expansion clips to window
Materialized instancesO(N) per series (N = occurrences)O(1) lookup per instanceO(N) — bulk updateExplodes — need a cap
Hybrid (materialize near-future)O(window/interval)O(1) in window, O(k) outsideO(near-future) + rule editWorks with warm window

The reified rule is the default because "repeat weekly forever" is a first-class user intent and materializing is incompatible with it. The hybrid is a scale optimization, not a semantic one — precompute the next 90 days into an availability index for hot-path reads, fall back to expansion outside that window.

2. Conflict detection: sorted list vs interval tree ​

Per-calendar event counts for active users are typically small (hundreds to low thousands active in a given year). Sorted list with binary search is O(log n + k) and the constants are tiny. Interval tree wins when overlap density is high or n is large — a free-busy index aggregating across an entire organization's calendars, for instance.

Rule of thumb in the interview: "For a personal calendar, sorted list. For an organization-wide aggregation index, interval tree. Either way, never linear scan on the hot path."

3. Exception handling: per-instance overrides ​

Rather than editing the series for "I need to move next week's standup," we persist an InstanceOverride keyed by the original start instant. On expansion, the iterator produces the candidate, and the service layer overlays overrides — canceling, relocating, or mutating fields per-instance.

The alternative — splitting the series at the modification point — loses the "this is the same weekly standup" identity, breaks attendee RSVP state, and complicates "edit all" operations.

4. Timezone: UTC storage, tz-aware rendering, tz-aware recurrence stepping ​

All timestamps stored in UTC epoch milliseconds. Event.timezone is the organizer's IANA name. Two separate concerns:

  • Rendering — always "UTC + viewer's tz" at the edge.
  • Recurrence stepping — must happen in the organizer's tz so "9 AM Tuesday in LA" stays 9 AM across DST. Stepping in UTC means the Tuesday 9 AM meeting becomes 8 AM half the year.

This is why occurrencesAtStep takes a tz parameter and uses tz-aware arithmetic helpers.

5. Availability index: derived view, not source of truth ​

The source of truth is Event. Availability is a projection: "given this calendar in this window, here are the merged busy intervals." We cache it in a per-user interval-tree-backed KV entry for hot windows (next 7/30/90 days), invalidated on event write.

Caching is an optimization; correctness must not depend on the cache being present. Every read falls back to expansion if the cache is cold.

Patterns Used ​

PatternWhereWhy
IteratorRecurrenceIterator.expandLazy generation of instances. The interface makes "custom recurrence type" a swap, not a rewrite.
StrategyISchedulingStrategy (Soonest, LeastConflict, PreferredHours)Ranking policy varies per caller / per feature flag without touching the slot-finding core.
CompositeEvent with optional RecurrenceRule; series vs instance treated polymorphically for overlap checks.Callers see a uniform "has this event in this window" signature whether it's one-off or recurring.
VisitorConflict check across different event types (event-on-event, event-on-room, event-on-external-import) — each subtype accepts the visitor.Adding a new event kind (e.g. "tentative hold") doesn't scatter instanceof across the codebase.
ObserverInvitation-response updates propagating to organizer, to calendar views, to the notification service.Decouples RSVP state-change from the N downstream reactions.
RepositoryICalendarRepositoryPersistence seam — swap Postgres for DynamoDB for in-memory without touching service logic.
FacadeSchedulerServiceSingle entry point for callers; hides iterator/detector/strategy wiring.

Concurrency Considerations ​

1. Concurrent event additions on the same calendar ​

Two clients adding a meeting at overlapping times should both succeed by default (we allow conflicts) — that's a product decision, not a concurrency one. But each individual event must be atomic: either it's saved with its version=1 or it isn't.

Mechanism: optimistic concurrency on the event row. Reads include version; writes do UPDATE ... WHERE id = ? AND version = ?. On conflict, retry with the fresh version. Save-new uses a DB-generated id so there's nothing to collide on.

2. Concurrent acceptance of the same room ​

Rooms hard-fail on double-book. Two users racing to book Room 7 at 10 AM must serialize — one wins, one gets RoomDoubleBookError.

Mechanism: scoped serialization. Options, in increasing complexity:

  • Row-lock on the room calendar — SELECT ... FOR UPDATE on the calendar row during the conflict check and insert. Works within a single DB.
  • Distributed lock (Redis SETNX with TTL) on roomId — required if the scheduler is sharded or if the DB doesn't support row locks across partitions.
  • Unique constraint on (roomId, startUtc) — works for one-off events, breaks for recurring (the constraint doesn't know about expansion).

The pragmatic answer: row-lock on the room's calendar for the duration of the check-and-insert transaction. For recurring room bookings, check all expanded instances in the window before committing.

3. Recurrence-modification races ​

The subtle one. Two admins act on the same series concurrently:

  • Admin A: deleteEvent(eventId, { kind: "occurrence", originalStart: T }) — delete one instance.
  • Admin B: deleteEvent(eventId, { kind: "series" }) — delete the whole series.

Both succeed if we aren't careful — the per-occurrence override is persisted, then the series is wiped, orphaning the override. The converse is worse: B deletes the series, A then writes an override on a phantom event.

Mechanism: treat series-level operations as an exclusive lock on the event row. Any thisAndFuture or series write bumps version; any per-occurrence write reads the current version and conflicts out if the series has changed under it. Alternatively, a compare-and-set on event existence — WHERE id = ? AND version = ? for overrides too.

4. Availability cache invalidation ​

A write invalidates cached availability for every attendee — that's an N-fanout write. For a meeting with 50 attendees, publishing an invalidation to 50 cache keys is linear but tractable. Lossy invalidation (TTL-only, no active purge) is acceptable if the cache is short-lived (seconds) and reads tolerate slight staleness.

Scale & Extensibility ​

Availability index — per-user interval tree ​

For the hot window (next 90 days), maintain a per-user interval tree of merged busy intervals. Flush to a KV store keyed by userId:windowBucket. Reads hit the cache; writes append to an invalidation queue.

Why 90 days? It's the practical ceiling for most scheduling flows (meeting-booking, interviews, leave). Beyond that, expansion on demand is fast enough because the far-future event density is low.

Materialized near-future instances + on-demand far-future ​

For recurring series, pre-expand into an availability index for the next 90 days. A write to the series invalidates and re-materializes. Queries beyond 90 days fall back to the iterator.

Tradeoff: write amplification for recurring events. Mitigated by bounding the materialization window and by bulk-materializing on write rather than lazily.

Delegated calendars ​

A user can grant read or write delegation to another user (principal → delegate). Delegation is a join table; authorization checks accept either "I am the owner" or "I am an active delegate." The service layer mediates: the delegate's actions are attributed to the principal on the event but audited under the delegate's identity.

Timezone-aware scheduling across users ​

Free-busy is UTC-uniform — finding common free across timezones is just sweep-line on UTC. Business-hours constraint is the tricky one: "between 9 AM and 5 PM for everyone" means clipping to each user's local business hours, intersected in UTC.

Resource booking with amenities ​

A MeetingRoom has capacity, amenities (projector, whiteboard, VC), building, and floor. Room search is a filter (capacity, amenities) plus an availability query. The availability-query code is unchanged — rooms are resources with calendars. Amenity search sits in a separate rooms index.

Free-busy sharing without exposing details ​

Users can share "busy" without exposing titles or attendees. The API has two shapes:

  • getEvents(calendarId, window) — full details, requires read-share.
  • getFreeBusy(calendarId, window) — merged intervals only, default-public.

Calendar imports (ICS) ​

Accept RFC 5545 ICS blobs. Parse VEVENT + VTIMEZONE + RRULE into our Event + RecurrenceRule types. The RRULE subset we support covers 95% of real-world rules; the long tail (BYMONTH, BYSETPOS combinations) is best-effort with fallback to instance materialization.

One-way vs two-way sync: one-way (external → us) is straightforward. Two-way sync (external ↔ us) requires ETags/sync tokens and conflict resolution — that's its own system.

Edge Cases ​

  1. DST "spring forward" — At 2 AM PST on the DST transition day, local time jumps to 3 AM. An event scheduled for 2:30 AM local on that day has no UTC instant. We must either reject on write or snap forward to 3:00 AM. Either is defensible; pick and document.

  2. DST "fall back" — Local clock 1:30 AM occurs twice. An event at 1:30 AM local is ambiguous. Resolve by storing the dtstart in UTC (which disambiguates) and rendering with a tz-aware library that knows the transition. Never infer from wall-clock.

  3. Recurring event "moved" to a new weekday — A weekly Tuesday meeting where one occurrence is moved to Wednesday. The move is an InstanceOverride with status=moved, newStart on Wednesday. Future occurrences remain on Tuesday.

  4. "This and all future" edit of a recurring series — Split the series at the modification point. Two options: (a) truncate the original series with until = pivotTime - 1, create a new series from pivotTime with the new rule; (b) keep one series with a "rule change at pivot" marker. Option (a) is simpler and more common in real systems.

  5. Series-delete vs occurrence-delete on an invited calendar — If I'm invited to a series and decline one occurrence, my decline is per-instance. If the organizer deletes the whole series, my per-instance declines are orphaned — the invite record is gone. Cascade-delete per-instance invitations on series delete.

  6. Mixed-response RSVP to recurring — Invitee accepts the series, then declines three specific occurrences. Store the series-level RSVP (accepted) and three per-instance declined overrides. Expansion reports per-instance status merged with series-level default.

  7. Room double-book via race — Covered above. Row-lock on the room calendar during check-and-insert.

  8. Event spans DST boundary — A 3-hour meeting starting 1 AM on the fall-back day actually lasts 4 wall-clock hours (1 AM occurs twice). The duration is stored in ms so the UTC-ms end is correct; rendering should show the actual end wall-clock, which may be a different hour than users expect. Document the convention.

  9. Back-to-back events with no gap — Event A ends at 10:00, event B starts at 10:00. Not a conflict — overlaps uses half-open intervals (a.start < b.end && b.start < a.end). A scheduling UI may want to flag "no buffer"; the conflict engine should not.

  10. Zero-duration events — An event with duration = 0 is a point in time. Half-open intervals make this a non-overlap with everything. Either reject on write or treat as a "marker" that never conflicts. Typically we reject — zero-duration meetings are a bug, not a feature.

  11. Past-event edits — Editing an event that has already occurred is usually allowed (it happens — corrections, notes). Moving it to a future time effectively creates a new event; organize this in the UI, not the API.

  12. Invitation to a series that expires — The series ends by until; invitations beyond that are moot. Expansion naturally prunes them.

  13. Attendee in a different timezone from organizer — All math is UTC. The attendee sees the event translated to their tz. DST rules apply independently per tz — an event stable at 9 AM LA local will show as 5 PM London in winter and 6 PM London in summer, because the two zones' DST transitions are offset by a few weeks.

  14. Leap seconds — Ignore. UTC-ms does not represent leap seconds, and JavaScript's Date doesn't either. Accept the blur.

  15. Very long recurrences — FREQ=DAILY;COUNT=10000 expanded in a 1-year window is fine (365 instances). Expanded in a 10-year window with no further clamping is 3650. The iterator's generation loop is bounded by window OR count OR until — whichever comes first.

Follow-up Questions ​

Q: How do you find the optimal meeting time for 10 people across 3 timezones?

Compute union of busy intervals across all 10 attendees using sweep-line (as in findCommonFreeSlot). Invert against the search window to get everyone-free gaps. Intersect each gap with the set of business-hour windows (one per attendee's tz), keeping only sub-intervals inside every attendee's business hours. Filter by target duration. Rank by strategy — typically earliest slot that's in everyone's core hours.

Q: How do you handle timezones correctly?

Three rules: (1) Store UTC plus IANA tz name — never a numeric offset, offsets change. (2) Do recurrence arithmetic in the organizer's tz, not UTC, so wall-clock stays stable across DST. (3) Render at the edge in the viewer's tz. Errors in scheduling systems almost always trace to violating one of these.

Q: How do you implement "this and all future occurrences" edit?

Truncate the original series by setting until = pivotInstant - 1. Create a new series starting at the pivot with the edited rule. Migrate per-instance overrides that fall on or after the pivot to reference the new series. Migrate attendee RSVPs the same way.

Q: How do you scale availability queries to millions of users?

Per-user availability index: a KV entry per user per window-bucket (e.g. week-keyed) holding merged busy intervals. Writes fan out invalidations to affected buckets. Reads hit the cache; misses expand from events and repopulate. Beyond the warm window, fall back to on-demand expansion. Hot users get dedicated cache nodes; cold users share.

Q: How do you reconcile with external calendars (Google/Outlook import)?

For one-way import: parse ICS/CalDAV into our types, tag the events with a source identifier, periodically re-pull and reconcile by stable UID. For two-way sync: ETags on each external calendar resource, sync tokens for incremental pulls, and a conflict policy (external-wins, local-wins, last-writer-wins per field). Two-way is a separate subsystem, not a bolt-on.

Q: How do you implement "find me a conference room with a projector that holds 12 people"?

Two-phase: (1) filter rooms by static attributes (capacity ≥ 12, amenities includes "projector") — that's an indexed query on the rooms table. (2) For each matching room, run an availability query over the desired window. Rank by availability, proximity to the organizer's building, and size (closest to 12, not wildly over). Cache the static filter result; recompute availability each call.

Q: How do you find the next free 30-minute slot today?

A cheap special case of findCommonFreeSlot with one user, a window of [now, endOfDay], and duration 30 min. Hits the availability index directly — no expansion needed if today is inside the warm window. First gap ≥ 30 min wins. Short-circuits before enumerating all gaps.

Q: How do you handle a user who is invited to a recurring meeting but wants to decline only the July 4th occurrence?

Store an Invitation override keyed by (eventId, userId, originalStart) with status = declined. Series-level invitation remains accepted. Expansion for this user overlays the occurrence-level override on the series-level status.

Q: How would you support travel-time between back-to-back meetings in different locations?

Add a location field on Event (we have roomId already). The conflict engine gains a rule: "event A at location X followed by event B at location Y requires a travel-gap ≥ travelTime(X, Y)." Implement as a secondary check after basic overlap — flag as a conflict when the gap is insufficient. Travel time comes from a maps service, cached per (X, Y) pair.

Q: How would you handle "hold" events — tentative blocks that release if real meetings take their place?

A new event kind HOLD that participates in availability but is automatically released when a conflicting real event is created in its window. The scheduler checks for HOLD events on conflict and cancels them inline (emitting an event so downstream integrations see the release). This is a Visitor-pattern use case — HOLD events accept a different conflict-visitor than regular events.

SDE2 vs SDE3 — How the Bar Rises ​

AxisSDE2 (expected)SDE3 (expected)
Recurrence storageStores rule, expands on read, bounds expansion by window.Adds materialized near-future index, explains the write-amp tradeoff, covers edit-series semantics (thisAndFuture = truncate + new series).
Timezone correctnessStores UTC + tz name, renders per viewer.Articulates why recurrence must step in organizer's tz (wall-clock stability across DST), handles DST spring-forward/fall-back explicitly, rejects or snaps invalid instants with a documented policy.
Conflict-detection structureSorted list + binary search, O(log n + k).Names the interval-tree alternative, gives the crossover point (organization-wide aggregation), and identifies the hot-path cache (per-user availability index).
Modification semantics depthSupports delete-occurrence, delete-series.Handles per-instance overrides with original-start keys, thisAndFuture split, cascade on RSVP, race between series-delete and occurrence-edit with optimistic versioning.
Multi-user scheduling algorithmNested loop over users, flags conflicts.Sweep-line merge of busy intervals across users, business-hours intersection per-tz, ranking strategy, O(N · K log K) complexity analysis.
ExtensibilityClean class split (Event, Instance, Service).Explicit interfaces for iterator/detector/strategy/repository; identifies what swaps when (piece for interval tree; materialized index for reified rule; Visitor for new event kinds); scopes out two-way external sync.
ConcurrencyOptimistic versioning on events.Room double-book race covered with row-lock or distributed lock; recurrence-modification race solved with version-guarded overrides; availability-cache invalidation fanout.
ScopingAnswers what was asked.Names what's out of scope (notifications, two-way sync, CRDT for collaborative edit) and why, so the interviewer doesn't spend time chasing them.

The senior signal on this problem is that you treat each sub-problem (recurrence, timezone, multi-party, concurrency) as a separable design decision with tradeoffs, not a feature checkbox. You can say "I'd do X, and here's where X breaks, and here's the version of Y I'd switch to when it does." That's the bar.

Frontend interview preparation reference.