Ramp·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Apr 2026

Summary

Interviewed for a Software Engineer role at Ramp and got hit with a dynamic programming scheduling problem that looked deceptively simple at first glance. The core challenge was figuring out how to optimally spend a limited number of day-off conversions to maximize streak bonuses on top of base wages.

Questions Asked (1)

Given a schedule of workdays and days off over n consecutive days, a fixed wage per day worked, a streak bonus earned when two consecutive days are both worked, and a budget of at most k conversions from day-off to workday, find the maximum total earnings possible.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

Took me an embarrassingly long time to realize the streak bonus structure is what makes this non-trivial.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as maximizing earnings over n days with at most k flips from off to work, where each workday gives a fixed wage and each adjacent pair of workdays gives a streak bonus. Use dynamic programming with states (day index, flips used, whether previous day was worked) to compute the optimal earnings, then optimize to O(nk) time and O(k) space. Discuss trade-offs between DP and greedy approaches, noting that greedy fails due to the interaction between flips and streak bonuses.

Pro tip: Emphasize that the streak bonus makes this a weighted interval scheduling variant, and mention that you can reduce space by keeping only the previous day's DP states. Also, clarify that flips are only from off to work, not vice versa, and that you can flip at most k days.

1. Clarify the problem and constraints

Restate the problem: given a binary schedule of n days (1=work, 0=off), a fixed wage W per workday, a streak bonus B for each pair of consecutive workdays, and at most k flips from 0 to 1, maximize total earnings. Confirm that flips are only 0→1 and that you can flip at most k days.

2. Define the DP state and recurrence

Let dp[i][j][s] be the max earnings for the first i days using exactly j flips, where s=1 if day i is worked (after flips) and s=0 otherwise. Recurrence: if day i is off, dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1]); if day i is worked, dp[i][j][1] = W + max(dp[i-1][j][0], dp[i-1][j][1] + B) plus flip cost if original day was off.

3. Optimize space and time

Observe that dp[i] depends only on dp[i-1], so reduce space to O(k) by keeping two arrays for s=0 and s=1. Time complexity is O(nk). Mention that if k is large, you can cap k at the number of off days.

4. Handle edge cases and initialization

Initialize dp[0][0][0]=0, dp[0][0][1]=-inf, and for j>0, dp[0][j][*]=-inf. At the end, answer is max over j≤k and s of dp[n][j][s]. Consider cases where n=0, k=0, or all days already worked.

5. Discuss alternative approaches and trade-offs

Mention that a greedy approach (e.g., flipping days that create the most streaks) may fail because flips interact. Compare with a min-cost max-flow formulation or a DP with state compression. Highlight that DP is optimal and efficient for typical constraints.

Key Points to Mention

Dynamic programming with state (day, flips used, previous day worked)
Time complexity O(nk) and space optimization to O(k)
Streak bonus only applies when two consecutive days are both worked
Flips are only from off to work, and at most k flips allowed
Edge cases: k=0, all days off, all days worked, n=0
Trade-offs: greedy vs DP, and why greedy fails due to non-local effects

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.