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(