Stripe Software Engineer Interview Experience — A Fresh OA on Deployment Window Scheduling

Fresh OA!

The question was to build a deployment time window scheduler. Time is represented uniformly as minutes within a week, in the range 0 to 10079: 0 means Monday 00:00, 60 means Monday 01:00, and 10079 means Sunday 23:59. All intervals are left-closed, right-open [start, end).

There are two kinds of windows in the input:

• allowed: times when deployment is permitted
• freeze: times when deployment is forbidden

The final deployable time must satisfy: it falls within at least one allowed interval, and it must not fall within any freeze interval.

Part 1: Compute the deployable windows

The input is a number of lines in the format: start,end,type

You need to return all the maximal contiguous deployable intervals within the week, sorted by start time.

For example:
540,600,allowed
570,585,freeze

This means:
Allowed for deployment: [540, 600)
Frozen: [570, 585)

So the final result is:
540 570
585 600

Essentially this is: the union of all allowed intervals minus the union of all freeze intervals. A few other things to watch for:

• Multiple allowed intervals can overlap
• Multiple freeze intervals can overlap
• Adjacent deployable intervals need to be merged
• Intervals are left-closed, right-open

The natural approach is a sweep line / difference map: sort all the time points, and maintain the current count of active allowed and freeze intervals.

Part 2: Time zones, lead time, and minimum deployment duration

Part 2 adds a few conditions on top of Part 1.

The first line of input is: utc_now,lead_time_minutes,min_continuous_minutes,k

Meaning:

• utc_now: the current UTC time
• lead_time_minutes: deployment can only start at the earliest this many minutes after the current time
• min_continuous_minutes: a single deployment needs at least this many continuous minutes
• k: return at most the next k deployable windows

After that, each window line's format becomes: start,end,type,timezone_offset_minutes

The start and end on each line are minutes within the week in local time, and need to be converted to UTC first:

UTC = local_time - timezone_offset

After conversion the result still needs to fall within a single week, so it can wrap across week boundaries — you need to take mod 10080 and split any wrapped window into two segments.

For example:
1020,0,10,5
540,600,allowed,-480
550,565,freeze,-480

Because the offset is -480:

UTC = local - (-480) = local + 480

Which gives:
allowed: [1020,1080)
freeze: [1030,1045)

Subtracting freeze:
[1020,1030)
[1045,1080)

Then apply:

• Earliest start time: utc_now + lead_time
• Each window's length must be at least min_continuous_minutes
• Return at most k windows

Here the two windows have lengths 10 and 35, both of which satisfy the 10-minute minimum, so both are returned.

e.g.

Part 1

Input format

When part == "part1", each line of inputCsv is in the format: start,end,type

Where:

• start, end are minutes within the week
• type is allowed or freeze
• Intervals are left-closed, right-open [start, end)

Test Case 1: Basic freeze cut

part = "part1"
inputCsv = [
  "540,600,allowed",
  "570,585,freeze"
]

Output:

[
  [540, 570],
  [585, 600]
]

Part 2

Input format

When part == "part2", the first line of inputCsv is in the format: utc_now,lead_time_minutes,min_continuous_minutes,k

Each subsequent line is in the format: start,end,type,timezone_offset_minutes

Time zone conversion formula: UTC time = local time - timezone_offset_minutes

Finally return windows where:

• The start time is not earlier than utc_now + lead_time_minutes
• The length is at least min_continuous_minutes
• Sorted by UTC start time
• At most k windows returned

Test Case 1: The problem's sample

part = "part2"
inputCsv = [
  "1020,0,10,5",
  "540,600,allowed,-480",
  "550,565,freeze,-480"
]

Converted to UTC:

allowed: [1020,1080)
freeze:  [1030,1045)

Output:

[
  [1020, 1030],
  [1045, 1080]
]