Hotel stay email schedule with booking changes: Frontier Interview's solution

Question: Hotel stay email schedule with booking changes

Companies: Stripe

Difficulty: Medium

Problem statement

A hotel wants to send each guest a set of emails around their stay. Write the code that produces the full email schedule.

Input

reservations: a list of objects with guest_name (string, unique), room_type (string), check_in_day (integer) and stay_length (integer number of nights, 0 or more).
touchpoints: a map from a timing key to an email label. A key is one of:
- "start": the check-in day.
- "end": the check-out day, which is check_in_day + stay_length.
- A signed integer string such as "-3" or "+1": that many days from the check-in day.

Part 1. Implement build_schedule(reservations, touchpoints) -> List[str]. Return one line per (reservation, touchpoint) pair, formatted "<day>: [<label>] <guest_name>" and sorted by day. When several emails fall on the same day, keep reservations in input order and, within one reservation, touchpoints in the order given.

Part 2. Some room types have their own touchpoints. Add an optional room_touchpoints map from room type to a touchpoint map. A guest's touchpoints are the defaults plus their room type's entries. On a key collision the room type's label wins.

Part 3. Bookings change. Implement build_schedule_with_changes(reservations, touchpoints, changes). Each change has a day, a guest_name, and an action of "cancel" or "modify". A modify may carry a new check_in_day, stay_length or room_type. Emails dated before the change day were already sent and stay in the schedule. From the change day on, only emails for the new booking are sent, and none after a cancellation. Ignore changes for unknown or already cancelled guests.

Constraints

Up to 10^4 reservations and 20 touchpoints each.
Days are integers and may be negative after applying an offset.

Example

reservations = [
  {"guest_name": "Ana", "room_type": "suite",  "check_in_day": 10, "stay_length": 3},
  {"guest_name": "Ben", "room_type": "double", "check_in_day": 4,  "stay_length": 6},
]
touchpoints = {"-2": "Prepare", "start": "Welcome", "end": "Thank you"}

Part 1:
2: [Prepare] Ben
4: [Welcome] Ben
8: [Prepare] Ana
10: [Welcome] Ana
10: [Thank you] Ben
13: [Thank you] Ana

Example with changes

changes = [
  {"day": 9, "guest_name": "Ana", "action": "modify", "check_in_day": 12},
  {"day": 3, "guest_name": "Ben", "action": "cancel"},
]

Part 3:
2: [Prepare] Ben
8: [Prepare] Ana
10: [Prepare] Ana
12: [Welcome] Ana
15: [Thank you] Ana

Interviewers usually reveal the parts one at a time.

Reconstructed from the reported question; details may differ from what interviewers ask.

Approach

This is a generate-then-sort problem. It is the same shape as Stripe's
well-known invoice reminder question, set in a hotel. Every
(reservation, touchpoint) pair produces exactly one email, and the email's
day depends only on that pair. So you expand every pair into a row
(day, label, guest), sort by day, and format.

Resolving a touchpoint key to a day. For check-in day c and stay
length s:

"start" resolves to c.
"end" resolves to c + s, the check-out day.
A signed integer such as "-3" or "+1" resolves to c + offset.

Put this in one helper. Every later part reuses it.

Ordering. Sort by day. Ties need a rule, so state it before you code.
Here, ties keep generation order: reservations in input order, then
touchpoints in the order they were given. Tag every row with an increasing
sequence number and sort by (day, seq). The sort key is then unique, and
the output is deterministic even in a language whose sort is not stable.

A brute force that loops over every day from the minimum to the maximum and
checks every reservation runs in O(D * R * T). That is a trap when check-in
days are far apart. Generating rows directly avoids any dependence on the
range of days.

Part 2: per-room-type touchpoints. Suites get extra emails, and some
room types replace a default email. Merge the default touchpoint map with
that room type's map, with the room type winning on a key collision, and
then expand as before. Nothing else changes.

Part 3: changes and cancellations. A change arrives on day d and moves
or cancels a booking. Emails before d were already sent and cannot be
taken back. Emails on or after d must follow the new booking. Model each
guest as a list of versions. Each version is active on a half-open window
[from, until) of send days. A change on day d closes the current version
at d and opens a new one at d. A cancellation opens an empty version. An
email generated from a version is kept only if its day falls in that
version's window. Invariant: the windows of one guest's versions partition
the timeline, so each send day has exactly one booking state.

Code

from typing import Dict, List, Optional, Tuple

Reservation = Dict[str, object]


def touchpoint_day(key: str, check_in: int, stay: int) -> int:
    """'start' = check-in, 'end' = check-out, '-3' / '+1' = offset from check-in."""
    if key == "start":
        return check_in
    if key == "end":
        return check_in + stay
    return check_in + int(key)  # int() accepts "+1" and "-3"


def emails_for(res: Reservation, touchpoints: Dict[str, str],
               room_touchpoints: Optional[Dict[str, Dict[str, str]]] = None
               ) -> List[Tuple[int, str]]:
    # Part 2: a room type's own entries override or extend the defaults.
    merged = dict(touchpoints)
    if room_touchpoints:
        merged.update(room_touchpoints.get(str(res["room_type"]), {}))
    check_in, stay = int(res["check_in_day"]), int(res["stay_length"])
    return [(touchpoint_day(k, check_in, stay), label)
            for k, label in merged.items()]


def build_schedule(reservations: List[Reservation], touchpoints: Dict[str, str],
                   room_touchpoints: Optional[Dict[str, Dict[str, str]]] = None
                   ) -> List[str]:
    """Part 1 and 2: every email, sorted by day; ties keep input order."""
    rows: List[Tuple[int, int, str]] = []
    seq = 0
    for res in reservations:
        for day, label in emails_for(res, touchpoints, room_touchpoints):
            rows.append((day, seq, f"{day}: [{label}] {res['guest_name']}"))
            seq += 1
    rows.sort()  # (day, seq) is unique, so the sort is stable by construction
    return [line for *_, line in rows]


def build_schedule_with_changes(reservations: List[Reservation],
                                touchpoints: Dict[str, str],
                                changes: List[Dict[str, object]]) -> List[str]:
    """Part 3: changes arrive on a given day. Emails before that day were already
    sent and stay; from that day on, the new booking (or nothing) applies."""
    NEG, POS = -10**18, 10**18
    # Each guest gets a list of versions: (active_from, active_until, booking or None).
    versions: Dict[str, List[Tuple[int, int, Optional[Reservation]]]] = {}
    order: List[str] = []
    for res in reservations:
        name = str(res["guest_name"])
        versions[name] = [(NEG, POS, res)]
        order.append(name)
    for ch in sorted(changes, key=lambda c: int(c["day"])):  # stable for same day
        name, day = str(ch["guest_name"]), int(ch["day"])
        hist = versions.get(name)
        if not hist or hist[-1][2] is None:
            continue  # unknown or already cancelled
        start, _, cur = hist[-1]
        hist[-1] = (start, day, cur)
        if ch["action"] == "cancel":
            hist.append((day, POS, None))
        else:
            new = dict(cur)
            for f in ("check_in_day", "stay_length", "room_type"):
                if f in ch:
                    new[f] = ch[f]
            hist.append((day, POS, new))

    rows: List[Tuple[int, int, str]] = []
    seq = 0
    for name in order:
        for lo, hi, res in versions[name]:
            if res is None:
                continue
            for day, label in emails_for(res, touchpoints):
                if lo <= day < hi:
                    rows.append((day, seq, f"{day}: [{label}] {name}"))
                    seq += 1
    rows.sort()
    return [line for *_, line in rows]

Complexity

Let R be reservations, T touchpoints per reservation (after the room-type
merge), and E = R * T emails.

touchpoint_day: O(1).
build_schedule (Parts 1 and 2): O(E log E) time to sort, O(E) space.
The merge in Part 2 adds O(T) per reservation.
build_schedule_with_changes (Part 3): O(C log C) to sort C changes, plus
O((R + C) * T) rows and O(((R + C) * T) log((R + C) * T)) to sort them.
Space is O(R + C + E).
If the output is consumed day by day, a min-heap that holds one cursor per
reservation streams the emails in O(E log R) time with O(R) extra space.

Test cases

Touchpoints {"-2": "Prepare", "start": "Welcome", "end": "Thank you"}.
Reservations Ana (suite, check-in 10, 3 nights) and Ben (double, check-in 4,
6 nights).

Part 1: ["2: [Prepare] Ben", "4: [Welcome] Ben", "8: [Prepare] Ana", "10: [Welcome] Ana", "10: [Thank you] Ben", "13: [Thank you] Ana"].
Day 10 is a tie. Ana comes first because she is first in the input.
Part 2 with {"suite": {"+1": "Spa offer", "end": "Suite farewell"}}:
Ana also gets "11: [Spa offer] Ana", and her day-13 email becomes
"13: [Suite farewell] Ana". Ben is unchanged.
No reservations, or an empty touchpoint map, gives [].
Stay length 0 with start and end gives two emails on the same day, in
touchpoint order: ["1: [A] Z", "1: [B] Z"].
A negative offset larger than the check-in day gives a negative send day.
It is still listed. Clamping it to day 0 is a policy question to ask.
Part 3 with Ben cancelling on day 3 and Ana moving check-in to 12 on day 9:
["2: [Prepare] Ben", "8: [Prepare] Ana", "10: [Prepare] Ana", "12: [Welcome] Ana", "15: [Thank you] Ana"]. Ben's day-2 email was already
sent. Ana's day-8 email was already sent, and the new booking schedules
another reminder on day 10.
Part 3 with no changes equals the Part 1 output.
A change for an unknown guest, or for a booking that was already
cancelled, is ignored.

Follow-ups

Per-room-type touchpoints (Part 2 above). Merge the maps before
expanding. Ask whether a room-type map replaces the defaults entirely or
only overrides some keys.
Modifications and cancellations (Part 3 above). The versioned windows
keep emails already sent and regenerate the rest. Clarify whether a
reminder for the new dates that falls on the change day itself should
still be sent. Here it is, because the window starts at d inclusive.
Repeating touchpoints, such as "every day during the stay". Expand
daily:start..end into one row per day. For long stays, generate lazily
with a heap so you never build every row in memory.
Real dates and time zones. Replace integer days with dates and send at
9 a.m. in the hotel's local time. Compute in local time, convert to UTC for
the queue, and be careful with DST transitions.
Running as a service. Store pending emails in a table keyed by
(reservation_id, touchpoint, version) with an idempotency key. A
scheduler sends rows that are due. A change bumps the version and deletes
unsent rows from older versions, so a retry never sends an email twice.

Interviewer expectations

Mid-level (L4)

Asks how ties are ordered and what the "end" day means, then codes a
correct generate-and-sort.
Puts key parsing in one helper, so "start", "end" and signed offsets
are not special-cased in several places.
Walks through the example by hand and handles empty inputs.

Senior (L5)

Gets Parts 1 and 2 done quickly and cleanly. Part 2 is a merge, not a
rewrite.
Models Part 3 correctly. Emails already sent are immutable, and the new
booking drives everything from the change day on. Names the boundary rule.
States complexity, and mentions streaming with a heap when the output is
large.

Staff (L6+)

Frames the problem as a schedule derived from booking state plus the
passage of time, and keeps the code shaped so new rules are data.
Brings up idempotent sending, versioned schedules, time zones, and what
happens when a change races with a send.
Weighs precomputing rows against computing due emails on each scheduler
tick, and explains when each fits.