Deployment Window Scheduler: Allowed Minus Freeze Windows, Time Zones, Filters
Company: Stripe
Role: Software Engineer
Category: Software Engineering Fundamentals
Difficulty: hard
Interview Round: Online Assessment
Implement a scheduler that computes when a service may be deployed. Time is measured as `minute_of_week`, an integer in `[0, 10079]`; a week has 10080 minutes.
The entry point receives:
- `part`: the string `"part1"` or `"part2"`;
- `inputCsv`: an array of strings, each string one comma-separated record.
It returns the deployable windows as a two-dimensional array `[[start, end], ...]`.
### Clarifying Questions
- Is `end` inclusive (the last deployable minute) or exclusive, and how is a window's length measured as a result?
- Should overlapping or touching windows be merged, so that the output contains only disjoint windows?
- In what order must the output windows appear?
- Can `inputCsv` contain a header row, blank lines or malformed records, and how should they be treated?
- Can a record have `start > end`, for example a window meant to run past the end of the week?
### Part 1 — Allowed windows minus freeze windows
Every record has the form `start,end,type`, where `type` is `allowed` or `freeze`. Return all deployable windows: the time covered by allowed windows, minus the time covered by freeze windows.
```hint Normalize before subtracting
Records of the same type can overlap one another. Decide what shape each list should be in before you subtract, so that a single pass can cut freeze time out of allowed time.
```
#### What This Part Should Cover
- Parsing the records and separating the two window types.
- Normalizing each list, and a subtraction that handles partial overlap, full containment, a freeze splitting one allowed window in two, and a freeze spanning several allowed windows.
- A consistent interval convention and a well-defined output order.
### Part 2 — Time zones, lead time, minimum length and a result cap
The input format changes. The first record is `utc_now,lead_time,min_continuous_minutes,k`. Every following record has the form `start,end,type,timezone_offset`, where `start` and `end` are local times, converted to UTC with `utc = local - offset`.
Compute the deployable windows on the UTC timeline as in Part 1, then return only windows that satisfy all of the following:
- the window starts at or after `utc_now + lead_time`;
- the window is at least `min_continuous_minutes` long;
- no more than `k` windows are returned.
```hint Order the pipeline
Conversion, subtraction and three filters now interact. Work out which steps must run before the others so that the start-time and length checks see the final shape of each window.
```
#### Clarifying Questions for this Part
- What unit is `timezone_offset` in: minutes, like the timeline, or hours?
- If a converted time falls below 0 or above 10079, does it wrap around the week, and is a window that crosses the week boundary split in two?
- A window that begins before `utc_now + lead_time` but ends after it: should it be dropped, or trimmed to start at `utc_now + lead_time`?
- Can `utc_now + lead_time` exceed 10079, and should the search then continue into the following week?
- When more than `k` windows qualify, which ones are kept: the earliest by start time?
#### What This Part Should Cover
- Converting every record, allowed and freeze alike, to UTC before combining them, with a stated policy for week wrap-around.
- The order of conversion, subtraction and filtering, and the chosen semantics of each filter.
- Selecting at most `k` results deterministically.
### What a Strong Answer Covers
- Clean decomposition into parsing, normalization, subtraction and filtering, with every ambiguous rule isolated so it can be changed in one place.
- Correct interval arithmetic with no off-by-one errors under the chosen end convention.
- Time and space complexity for n records, and awareness that the fixed 10080-minute domain allows a simpler alternative.
- Targeted tests for edge cases: touching and nested windows, empty results, wrap-around, and `k` larger than the number of qualifying windows.
### Follow-up Questions
- If windows may cross the end of the week into the start of the next, how would you represent them so that a crossing window counts as one continuous window for the length check?
- How would you answer many queries of the form "earliest window starting at or after time T with at least M continuous minutes" without recomputing everything for each query?
- If freeze windows are added and removed while the service runs, what data structure would you maintain instead of recomputing from scratch?
- How would a daylight-saving change inside the week affect the single-offset-per-record model?
Overview: Implement a deployment-window scheduler over the 10080 minutes of a week: subtract freeze windows from allowed windows, then convert local times to UTC and keep only windows that start after a lead time, meet a minimum length and fit a cap of k results. Tests interval arithmetic, parsing and handling of an underspecified spec.
Read the full Stripe Software Engineer interview experience this question came from
Community answers
Answer by navida
W = 10080 # minutes in a week; times are half-open [start, end)
---------- parsing (bad records are skipped in one place) ----------
def parse(input_csv, n_fields):
rows = []
for line in input_csv:
f = [x.strip() for x in line.split(",")]
if len(f) != n_fields:
continue # blank line, header, malformed
try:
nums = [int(x) for x in f[:2]] + ([int(f[3])] if n_fields == 4 else [])
except ValueError:
continue # e.g. header "start,end,type"
kind = f[2].lower()
if kind in ("allowed", "freeze"):
rows.append((kind, *nums))
return rows
---------- interval helpers ----------
def to_pieces(start, end):
"""[start, end) inside one week; start > end wraps past the week end -> two pieces."""
start, end = start % W, end % W if end != W else W
if start < end:
return [(start, end)]
if start > end:
return [(start, W), (0, end)] if end > 0 else [(start, W)]
return [] # start == end: empty
def merge(iv):
out = []
for s, e in sorted(iv):
if out and s <= out[-1][1]: # overlapping or touching
out[-1][1] = max(out[-1][1], e)
else:
out.append([s, e])
return out
def subtract(A, B): # both merged and sorted
res, j = [], 0
for s, e in A:
while j < len(B) and B[j][1] <= s:
j += 1
cur, k = s, j
while k < len(B) and B[k][0] < e:
if B[k][0] > cur:
res.append([cur, B[k][0]])
cur = max(cur, B[k][1])
k += 1
if cur < e:
res.append([cur, e])
return res
def deployable(records): # records: (kind, start, end) in UTC
allowed = merge([p for k, s, e in records if k == "allowed" for p in to_pieces(s, e)])
freeze = merge(
Answer by duykhanh.eric
edge case needed to check for code
1.freezes
2.freeze fully covers an allowed window
3.freeze splits allowed into two
4.overlapping freezes that need merging
5.window wraps across week boundary
6.lead time trims or filters
7.time zone conversion sanity check (e.g., UTC vs UTC+X)