Design a subscription email scheduler with changes and renewals
Company: Stripe
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement an email notification scheduler for subscription accounts.
Inputs:
- send_schedule: a mapping whose keys include:
• "start": label to send on an account’s begin_date.
• Integer negative offsets (e.g., -
15): labels to send at end_date + offset, where end_date = begin_date + duration.
• "end": label to send on end_date.
- user_accounts: a list of objects {name: string, plan: string, account_date: int (days), duration: int (days)}.
Output:
- Emit all notifications in chronological order as lines: "<time>: [<Label>] Subscription for <name> (<plan>)" and terminate after the last message.
- When multiple notifications share the same timestamp, apply this deterministic ordering:
1) State changes (defined below) in the order: Changed, then Renewed.
2) "start" events.
3) Relative-offset events sorted by their numeric offset (more negative first).
4) "end" events.
- For ties within the same priority bucket, sort by name lexicographically.
Sub-questions:
(a) Baseline scheduling: Using only send_schedule and user_accounts, generate all scheduled notifications for each account (welcome on begin_date, each negative-offset notification relative to end_date, and expired on end_date) and merge them into the global, ordered output.
(b) Plan changes: Add a list changes1 of entries {name: string, new_plan: string, change_date: int}. At change_date, emit "[Changed] Subscription for <name> (<new_plan>)" and update the account’s plan effective immediately; any notifications at the same timestamp and all future notifications must use the updated plan.
(c) Renewals/extensions: Now allow a change list where each entry is either a plan change as above or a renewal entry {name: string, extension: int (days), change_date: int}. On a renewal, emit "[Renewed] Subscription for <name> (<current_plan>)" and extend the account’s end_date by extension days from its current end_date. Recompute all future relative-offset and end events to reflect the new end_date. If a renewal and a plan change occur for the same account on the same timestamp, apply the ordering rules above.
Constraints/expectations:
- Support up to N accounts and M change/renewal events efficiently; describe data structures and time complexity.
- Your API design is flexible (e.g., a Notifier class with send_emails(user_accounts, send_schedule, changes=None)).
- Clearly state any additional assumptions you make and ensure deterministic output under all tie cases.
Quick Answer: This question evaluates event-driven scheduling, deterministic time-based ordering, stateful account updates for plan changes and renewals, and algorithmic merging of notification streams in the Coding & Algorithms domain.
Part 1: Baseline Subscription Email Scheduling
Implement the baseline notification scheduler for subscription accounts. Given a send_schedule mapping and a list of user_accounts, generate every scheduled notification and return them in global chronological order. The send_schedule may contain 'start', 'end', and negative integer offsets. A 'start' notification is sent on account_date. A negative offset k is sent at end_date + k, where end_date = account_date + duration. An 'end' notification is sent on end_date. When multiple notifications share a timestamp, output 'start' events first, then relative-offset events sorted by numeric offset from most negative to least negative, then 'end' events. Within the same bucket, sort by account name lexicographically.
Constraints
- 0 <= len(user_accounts) <= 100000
- Account names are unique.
- 0 <= duration <= 1000000000
- account_date may be any integer day value.
- send_schedule contains at most 100 negative integer offset keys.
- Negative offset keys are strictly less than 0.
Examples
Input: ({'start': 'Welcome', -15: 'Upcoming expiration', 'end': 'Expired'}, [{'name': 'Alice', 'plan': 'Basic', 'account_date': 0, 'duration': 30}, {'name': 'Bob', 'plan': 'Pro', 'account_date': 10, 'duration': 20}])
Expected Output:
Explanation: Alice and Bob have the same end date, so their relative and end notifications tie by timestamp and are sorted by name.
Input: ({'start': 'Welcome', -10: 'Ten days left', -5: 'Five days left', 'end': 'Expired'}, [{'name': 'Ann', 'plan': 'Basic', 'account_date': 0, 'duration': 10}, {'name': 'Zoe', 'plan': 'Plus', 'account_date': 5, 'duration': 5}])
Expected Output:
Explanation: At time 0, Ann's start event comes before relative-offset events. At time 5, Zoe's start event comes before all relative-offset events.
Hints
- Convert every account notification into a sortable event tuple.
- The sort key should encode both timestamp and the required same-timestamp priority rules.
Part 2: Subscription Scheduling with Plan Changes
Extend the baseline scheduler to support plan changes. In addition to send_schedule and user_accounts, you are given changes1, a list of entries with name, new_plan, and change_date. At change_date, output '[Changed] Subscription for <name> (<new_plan>)' and update that account's plan immediately. Any scheduled notification at the same timestamp, and all future scheduled notifications, must use the updated plan. When multiple events share a timestamp, output Changed events first, then start events, then relative-offset events sorted by numeric offset from most negative to least negative, then end events. Within each bucket, sort by name lexicographically.
Constraints
- 0 <= len(user_accounts) <= 100000
- 0 <= len(changes1) <= 100000
- Account names are unique.
- Every change references an existing account.
- At most one plan change exists for the same account at the same timestamp.
- send_schedule contains at most 100 negative integer offset keys.
- Negative offset keys are strictly less than 0.
Examples
Input: ({'start': 'Welcome', -5: 'Reminder', 'end': 'Expired'}, [{'name': 'Alice', 'plan': 'Basic', 'account_date': 0, 'duration': 10}], [{'name': 'Alice', 'new_plan': 'Pro', 'change_date': 7}])
Expected Output:
Explanation: The reminder is before the plan change, while the end notification is after it.
Input: ({'start': 'Welcome', 'end': 'Expired'}, [{'name': 'Bob', 'plan': 'Basic', 'account_date': 5, 'duration': 5}], [{'name': 'Bob', 'new_plan': 'Gold', 'change_date': 5}])
Expected Output:
Explanation: The change and start happen at the same timestamp, so the change is emitted first and the start uses the new plan.
Hints
- You can still create a single global event list, but change events must be processed before scheduled notifications at the same time.
- Store the current plan for each account separately from the event list so later events see updates.
Part 3: Subscription Scheduling with Plan Changes and Renewals
Extend the scheduler to support both plan changes and renewals. Each entry in changes is either a plan change with name, new_plan, and change_date, or a renewal with name, extension, and change_date. At a plan change, emit '[Changed]' and update the plan immediately. At a renewal, emit '[Renewed]' using the account's current plan, then extend the account's current end_date by extension days. Future relative-offset and end notifications must be recomputed from the new end_date. Events already emitted before the renewal are not revoked. Events at the same timestamp as a state change are treated as future events because state changes are processed before start, relative-offset, and end notifications. Ordering at the same timestamp is: Changed events, Renewed events, start events, relative-offset events sorted by numeric offset from most negative to least negative, then end events. Within each bucket, sort by name lexicographically.
Constraints
- 0 <= len(user_accounts) <= 100000
- 0 <= len(changes) <= 100000
- Account names are unique.
- Every change or renewal references an existing account.
- At most one plan change and at most one renewal exist for the same account at the same timestamp.
- extension is a positive integer.
- send_schedule contains at most 100 negative integer offset keys.
- Negative offset keys are strictly less than 0.
Examples
Input: ({'start': 'Welcome', -5: 'Reminder', 'end': 'Expired'}, [{'name': 'Alice', 'plan': 'Basic', 'account_date': 0, 'duration': 10}], [{'name': 'Alice', 'extension': 10, 'change_date': 4}])
Expected Output:
Explanation: The renewal at time 4 moves the end date from 10 to 20, so the old reminder at 5 and old end at 10 are canceled.
Input: ({'start': 'Welcome', -2: 'Reminder', 'end': 'Expired'}, [{'name': 'Alice', 'plan': 'Basic', 'account_date': 0, 'duration': 10}], [{'name': 'Alice', 'extension': 5, 'change_date': 8}, {'name': 'Alice', 'new_plan': 'Pro', 'change_date': 8}])
Expected Output:
Explanation: Even though the renewal appears first in the input, Changed is processed before Renewed at the same timestamp. The old reminder at time 8 is canceled and recomputed for the new end date.
Hints
- A min-heap works well because renewals can create newly scheduled future events while the simulation is running.
- Use a per-account version number to invalidate old end-relative events after a renewal.