Quick Overview

Maximize schedule earnings by changing at most k days off into working days, balancing fixed daily pay with bonuses for consecutive working days.

Maximize Earnings by Adding Working Days

Company: Citadel

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Implement `maximum_earnings(schedule, k, pay, bonus)`. `schedule` is a string of `0` and `1`, where `1` means a working day and `0` means a day off. You may change at most `k` zeroes into ones; existing working days cannot become days off. Each working day earns `pay`. It also earns `bonus` if the immediately preceding day in this schedule is a working day after all changes. The first day has no preceding day within the schedule. Return the maximum total earnings over the full schedule. For this interface, `k` is a nonnegative integer and `pay` and `bonus` are nonnegative integers in the same monetary unit. Represent these integers and the returned total using the decimal strings described below. You may use fewer changes than `k`, and cannot change more days off than exist. An empty schedule earns zero. No maximum schedule length or payment bound is specified. ### Exact integer representation This console represents integer values as canonical decimal strings so they retain their exact values in every supported language. This is an input/output representation convention; it does not impose a maximum integer magnitude. - `k`, `pay`, and `bonus` are strings representing nonnegative integers. `schedule` remains the binary schedule string described above. - Return the maximum earnings as a canonical decimal string. An empty schedule returns `"0"`. - A canonical nonnegative decimal string is `"0"` or a sequence of ASCII digits beginning with `1` through `9`. It has no sign, leading zeroes, or whitespace. - Earnings are exact integer amounts in the stated monetary unit. Do not use rounding, fixed-width overflow, or a remainder modulo another number. ### Examples ```text maximum_earnings("101", "1", "10", "5") -> "40" ``` Changing the middle day gives three working days and two adjacent working-day pairs: 30 in base pay and 10 in bonuses. ```text maximum_earnings("000", "2", "10", "5") -> "25" ``` Two adjacent working days earn 20 in base pay and one bonus of 5. Separate working days would earn no adjacency bonus.

Overview: Maximize schedule earnings by changing at most k days off into working days, balancing fixed daily pay with bonuses for consecutive working days.

Read the full Citadel Software Engineer interview experience this question came from

Implement `maximum_earnings(schedule, k, pay, bonus)`. `schedule` is a string of `0` and `1`, where `1` means a working day and `0` means a day off. You may change at most `k` zeroes into ones; existing working days cannot become days off. Each working day earns `pay`. It also earns `bonus` if the immediately preceding day in this schedule is a working day after all changes. The first day has no preceding day within the schedule. Return the maximum total earnings over the full schedule. For this interface, `k` is a nonnegative integer and `pay` and `bonus` are nonnegative integers in the same monetary unit. Represent these integers and the returned total using the decimal strings described below. You may use fewer changes than `k`, and cannot change more days off than exist. An empty schedule earns zero. No maximum schedule length or payment bound is specified. ### Exact integer representation This console represents integer values as canonical decimal strings so they retain their exact values in every supported language. This is an input/output representation convention; it does not impose a maximum integer magnitude. - `k`, `pay`, and `bonus` are strings representing nonnegative integers. `schedule` remains the binary schedule string described above. - Return the maximum earnings as a canonical decimal string. An empty schedule returns `"0"`. - A canonical nonnegative decimal string is `"0"` or a sequence of ASCII digits beginning with `1` through `9`. It has no sign, leading zeroes, or whitespace. - Earnings are exact integer amounts in the stated monetary unit. Do not use rounding, fixed-width overflow, or a remainder modulo another number. ### Examples ```text maximum_earnings("101", "1", "10", "5") -> "40" ``` Changing the middle day gives three working days and two adjacent working-day pairs: 30 in base pay and 10 in bonuses. ```text maximum_earnings("000", "2", "10", "5") -> "25" ``` Two adjacent working days earn 20 in base pay and one bonus of 5. Separate working days would earn no adjacency bonus.

Constraints

  • schedule is any finite binary string, including empty.
  • k, pay and bonus are canonical nonnegative decimal strings with no maximum magnitude specified.
  • Change at most k zeroes to ones; earnings cover all resulting working days and immediate-predecessor pairs.
  • Return a canonical nonnegative decimal string; an empty schedule earns "0".

Examples

Input: ('101', '1', '10', '5')

Expected Output: '40'

Explanation: Source example: bridge the middle gap for three days and two adjacency bonuses.

Input: ('000', '2', '10', '5')

Expected Output: '25'

Explanation: Source example: choose two adjacent working days.

Hints

  1. The first schedule position has no preceding day in the schedule.
  2. An allowance larger than the number of days off does not permit additional changes.

Loading coding console...

Show the approach

Approach

Nonnegative pay and bonus mean that using min(k,number_of_zeroes) changes cannot reduce the optimum. If no working day exists, place the changed days consecutively, giving max(0,used-1) adjacent pairs. Otherwise each changed day can extend an existing working component and earn one additional pair. Finishing an internal zero-gap joins two existing components and earns one extra pair beyond that per-change contribution. No other change can join two components. Each gap contributes exactly one extra pair if fully filled, so sorting gap lengths and finishing the shortest affordable gaps maximizes the number of joins; exchanging a chosen longer gap for an unchosen shorter one never costs more or loses a join. Any unused allowance after those joins can extend remaining components without an additional join. The exact maximum pair count is initial_pairs+used+completed_gaps. Multiply the resulting day and pair counts by the arbitrary-precision amounts and add. Clamp k against the materialized zero count before converting to a native index type; never narrow unbounded k first. All numeric values use the exact decimal representation in the public statement. Input arrays/strings must be materialized by the host; container indices and lengths use their native representable types, while mathematical values and sums use arbitrary precision. No additional problem-domain magnitude bound is imposed. Python parses decimal chunks of at most nine digits, avoiding its configurable whole-string conversion limit. Python also renders the result in nine-digit chunks so a valid very long result is not restricted by the default decimal-output limit.

Time complexity:
O(n + g log g) native count work for g internal gaps, plus exact decimal parsing and arbitrary-precision monetary arithmetic/output costs.
Space complexity:
O(g) gap lengths plus the storage required for arbitrary-precision amounts and output.