How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Ramp.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Ramp during technical interviews.

Maximize Earnings by Converting Days Off into Workdays

Quick Overview

This question evaluates a candidate's skill in dynamic programming and constrained optimization, specifically deciding which state transitions to modify under a limited budget of changes. It falls under coding and algorithms interviews, testing practical application of greedy or DP reasoning over sequential data with adjacency-based bonuses rather than pure conceptual knowledge.

Company: Ramp

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

## Maximize Earnings by Converting Days Off into Workdays An employee is planning a work schedule for `n` consecutive days. For day `i` you are given whether it is originally a **workday** or a **day off**. The pay rules are: - On every day the employee actually works, they earn a fixed amount `wage` dollars. - On a workday, the employee additionally earns `bonus` dollars **if and only if** the immediately preceding day was also a workday (a "streak" bonus). Day `0` can never earn the streak bonus because it has no preceding day. The employee may convert **at most `k`** of the original days off into workdays. (Workdays cannot be converted into days off, and converting a day off is optional.) Return the **maximum total earnings** the employee can achieve over the `n` days after performing at most `k` such conversions. ### Input - An integer `n` — the number of days. - An integer `k` — the maximum number of days off that may be converted to workdays (`0 <= k <= n`). - An integer `wage` — dollars earned for each day worked. - An integer `bonus` — extra dollars earned on a workday whose previous day was also worked. - An array `schedule` of length `n` where `schedule[i] == 1` means day `i` is originally a workday and `schedule[i] == 0` means day `i` is originally a day off. ### Output - A single integer: the maximum total earnings achievable. ### Constraints - `1 <= n <= 100000` - `0 <= k <= n` - `0 <= wage <= 10^4` - `0 <= bonus <= 10^4` - `schedule[i] ∈ {0, 1}` - The answer can exceed 32-bit range; use 64-bit integers. ### Example 1 ``` n = 5 k = 2 wage = 10 bonus = 5 schedule = [1, 0, 0, 1, 0] Output: 55 ``` Explanation: Convert the days off at indices `1` and `2`, making the schedule `[1, 1, 1, 1, 0]`. There are `4` workdays earning `4 * 10 = 40`. The consecutive-work pairs are `(0,1)`, `(1,2)`, `(2,3)`, contributing `3 * 5 = 15` in streak bonuses. Total `40 + 15 = 55`. No other choice of at most `2` conversions yields more. ### Example 2 ``` n = 4 k = 0 wage = 7 bonus = 3 schedule = [1, 1, 0, 1] Output: 24 ``` Explanation: No conversions are allowed (`k = 0`). The worked days are indices `0`, `1`, `3`, earning `3 * 7 = 21`. The only pair of adjacent worked days is `(0, 1)`, contributing one streak bonus of `3`. Total `21 + 3 = 24`. This confirms the model: `wage` is paid once per worked day, and `bonus` is paid once for each pair of adjacent worked days.

Quick Answer: This question evaluates a candidate's skill in dynamic programming and constrained optimization, specifically deciding which state transitions to modify under a limited budget of changes. It falls under coding and algorithms interviews, testing practical application of greedy or DP reasoning over sequential data with adjacency-based bonuses rather than pure conceptual knowledge.

An employee is planning a work schedule for `n` consecutive days. For day `i` you are given whether it is originally a **workday** or a **day off**. The pay rules are: - On every day the employee actually works, they earn a fixed amount `wage` dollars. - On a workday, the employee additionally earns `bonus` dollars **if and only if** the immediately preceding day was also a workday (a "streak" bonus). Day `0` can never earn the streak bonus because it has no preceding day. The employee may convert **at most `k`** of the original days off into workdays. (Workdays cannot be converted into days off, and converting a day off is optional.) Return the **maximum total earnings** the employee can achieve over the `n` days after performing at most `k` such conversions. ### Input - An integer `n` — the number of days. - An integer `k` — the maximum number of days off that may be converted to workdays (`0 <= k <= n`). - An integer `wage` — dollars earned for each day worked. - An integer `bonus` — extra dollars earned on a workday whose previous day was also worked. - An array `schedule` of length `n` where `schedule[i] == 1` means day `i` is originally a workday and `schedule[i] == 0` means day `i` is originally a day off. ### Output - A single integer: the maximum total earnings achievable. ### Constraints - `1 <= n <= 100000` - `0 <= k <= n` - `0 <= wage <= 10^4` - `0 <= bonus <= 10^4` - `schedule[i] in {0, 1}` - The answer can exceed 32-bit range; use 64-bit integers. ### Example 1 ``` n = 5, k = 2, wage = 10, bonus = 5, schedule = [1, 0, 0, 1, 0] Output: 55 ``` Convert the days off at indices `1` and `2`, making the schedule `[1, 1, 1, 1, 0]`. Four workdays earn `4 * 10 = 40`; the consecutive-work pairs `(0,1),(1,2),(2,3)` contribute `3 * 5 = 15`. Total `55`. ### Example 2 ``` n = 4, k = 0, wage = 7, bonus = 3, schedule = [1, 1, 0, 1] Output: 24 ``` No conversions allowed. Worked days `0,1,3` earn `3 * 7 = 21`; the only adjacent worked pair `(0,1)` adds `3`. Total `24`.

Constraints

1 <= n <= 100000
0 <= k <= n
0 <= wage <= 10^4
0 <= bonus <= 10^4
schedule[i] in {0, 1}
The answer may exceed 32-bit range; use 64-bit integers.

Examples

Input: (5, 2, 10, 5, [1, 0, 0, 1, 0])

Expected Output: 55

Explanation: Convert indices 1 and 2 -> [1,1,1,1,0]. 4 workdays = 40, pairs (0,1),(1,2),(2,3) = 15. Total 55.

Input: (4, 0, 7, 3, [1, 1, 0, 1])

Expected Output: 24

Explanation: No conversions. Worked days 0,1,3 = 21, only adjacent pair (0,1) adds 3. Total 24.

Input: (1, 1, 10, 5, [0])

Expected Output: 10

Explanation: Convert the single day off. It earns wage = 10; day 0 can never earn the streak bonus.

Input: (1, 0, 10, 5, [1])

Expected Output: 10

Explanation: Single workday, no conversions possible; earns wage = 10, no bonus (no preceding day).

Input: (3, 3, 10, 5, [0, 0, 0])

Expected Output: 40

Explanation: Budget covers all days off. Work all 3 = 30, pairs (0,1),(1,2) = 10. Total 40.

Input: (5, 1, 10, 5, [1, 0, 0, 0, 1])

Expected Output: 35

Explanation: Only 1 conversion. Best is a day off adjacent to a worked day (index 1 or 3): worked {0,1,4} = 30 plus one pair = 5. Total 35 (converting the isolated index 2 would give only 30).

Input: (4, 2, 10, 0, [0, 1, 0, 0])

Expected Output: 30

Explanation: bonus = 0, so only wage matters. Base worked {1} = 10; convert 2 of the 3 days off for +20. Total 30.

Input: (4, 4, 0, 5, [0, 0, 0, 0])

Expected Output: 15

Explanation: wage = 0, so only streak bonuses matter. Work all 4 -> pairs (0,1),(1,2),(2,3) = 3 * 5 = 15.

Input: (6, 2, 1, 100, [1, 0, 0, 0, 0, 1])

Expected Output: 204

Explanation: With only 2 conversions in a length-4 interior gap you cannot bridge both ends. Best is two conversions forming a chain attached to a worked day (e.g. work {0,1,2,5}): 4 workdays = 4, pairs (0,1),(1,2) = 200. Total 204.

Hints

A worked day always contributes `wage`; a bonus is earned once for every pair of adjacent worked days. So total = wage * (#worked days) + bonus * (#adjacent worked pairs).
Greedy on 'most valuable conversion first' fails because the streak bonus is created by two adjacent days working together — the marginal value of a conversion depends on its neighbors, which other conversions can change.
Do a DP over days. Track two things at each day: how many conversions you have used so far, and whether the current day ends up worked or not.
State: dp[i][j][worked]. A day that is originally a workday must stay worked; a day off may be left off, or worked at the cost of one conversion. Add the streak bonus only when transitioning worked -> worked. Keep just the previous day's rows to get O(k) memory.

Quick Overview