Maximize pay by flipping k rest days
Company: Adobe
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given integers BasePay and Bonus, a binary string schedule of length n where '1' means work and '0' means rest, and an integer k, you may change up to k zeros to ones. Pay rules: each workday earns BasePay; if day i and day i-1 are both workdays, you earn an additional Bonus for day i. Return the maximum total pay achievable after up to k flips. Describe your algorithm and analyze its time and space complexity.
Overview: This question evaluates algorithm design and optimization skills in string processing and combinatorial decision-making, testing how to maximize weighted sequences of workdays under a limited number of flips.
Choose up to k rest days to work to maximize base pay plus adjacent-work bonuses.
Constraints
- schedule contains 0/1
Examples
Input: (10, 5, '1010', 1)
Expected Output: 40
Explanation: Flip one rest day to connect work streak.
Input: (10, 5, '000', 2)
Expected Output: 25
Explanation: Choose two adjacent workdays.
Hints
- Dynamic programming over day, flips used, and whether the previous day is worked.
Community answers
Answer by ghost_writer
n = len(schedule)
total_ones = schedule.count('1')
zeroes_count = n - total_ones
flips = min(k, zeroes_count)
bonus_pairs = 0
blocks = []
start = 0
while start < n:
end = start
while end < n and schedule[end] == schedule[start]:
end += 1
blocks.append((schedule[start], end - start))
if schedule[start] == '1':
bonus_pairs += end - start - 1
start = end
gaps = sorted(length for idx, (ch, length) in enumerate(blocks) if ch == '0' and 0 < idx < len(blocks) - 1 and blocks[idx-1][0] == '1' and blocks[idx+1][0] == '1')
remaining = flips
for g in gaps:
if remaining >= g:
bonus_pairs += g + 1
remaining -= g
else:
break
if remaining > 0:
bonus_pairs += remaining if total_ones > 0 else max(0,remaining - 1)
return (total_ones + flips) BasePay + bonus_pairs Bonus