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 role is this question designed for?

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

Minimum Sum of Weekly Maximum Costs | Salesforce Coding Question

Quick Overview

This question tests dynamic programming skills applied to array partitioning, specifically minimizing an objective function over contiguous subarrays. It evaluates the ability to recognize optimal substructure and formulate recurrences for partition-based optimization problems, a common pattern in algorithm interviews for software engineering roles.

Minimum Sum of Weekly Maximum Costs

Company: Salesforce

Role: Software Engineer

Category: Coding & Algorithms

Interview Round: Onsite

## Minimum Sum of Weekly Maximum Costs You are scheduling a marketing campaign rollout. You are given an integer array `costs`, where `costs[i]` is the cost of running the `i`-th campaign, and an integer `weeks` giving the number of weeks over which the campaigns must be run. You must partition the campaigns into exactly `weeks` **contiguous** groups (one group per week), where: - The campaigns assigned to each week form a contiguous slice of the original array (you may not reorder campaigns). - Every week is assigned **at least one** campaign. - Together the groups cover all campaigns, in order, with no gaps or overlaps. The cost charged for a single week equals the **maximum** campaign cost among the campaigns scheduled in that week. The total cost is the **sum** of the per-week maxima. Return the minimum possible total cost over all valid partitions. ### Example ``` Input: costs = [2, 5, 4, 3, 7, 1, 6, 8], weeks = 3 Output: 15 ``` One optimal partition is `[2]`, `[5]`, `[4, 3, 7, 1, 6, 8]`: - Week 1 max = `2` - Week 2 max = `5` - Week 3 max = `8` - Total = `2 + 5 + 8 = 15` No valid partition into 3 contiguous non-empty groups yields a smaller sum. ### Constraints - `1 <= weeks <= len(costs) <= 1000` - `1 <= costs[i] <= 10^6` - It is guaranteed that `weeks <= len(costs)`, so a valid partition always exists. ### Input / Output Format - **Input:** an integer array `costs` and an integer `weeks`. - **Output:** a single integer — the minimum achievable sum of the per-week maximum costs.

Quick Answer: This question tests dynamic programming skills applied to array partitioning, specifically minimizing an objective function over contiguous subarrays. It evaluates the ability to recognize optimal substructure and formulate recurrences for partition-based optimization problems, a common pattern in algorithm interviews for software engineering roles.

You are scheduling a marketing campaign rollout. You are given an integer array `costs`, where `costs[i]` is the cost of running the `i`-th campaign, and an integer `weeks` giving the number of weeks over which the campaigns must be run. You must partition the campaigns into exactly `weeks` **contiguous** groups (one group per week), where: - The campaigns assigned to each week form a contiguous slice of the original array (you may not reorder campaigns). - Every week is assigned **at least one** campaign. - Together the groups cover all campaigns, in order, with no gaps or overlaps. The cost charged for a single week equals the **maximum** campaign cost among the campaigns scheduled in that week. The total cost is the **sum** of the per-week maxima. Return the minimum possible total cost over all valid partitions. ### Example ``` Input: costs = [2, 5, 4, 3, 7, 1, 6, 8], weeks = 3 Output: 15 ``` One optimal partition is `[2]`, `[5]`, `[4, 3, 7, 1, 6, 8]`: - Week 1 max = `2` - Week 2 max = `5` - Week 3 max = `8` - Total = `2 + 5 + 8 = 15` No valid partition into 3 contiguous non-empty groups yields a smaller sum. ### Constraints - `1 <= weeks <= len(costs) <= 1000` - `1 <= costs[i] <= 10^6` - It is guaranteed that `weeks <= len(costs)`, so a valid partition always exists.

Constraints

1 <= weeks <= len(costs) <= 1000
1 <= costs[i] <= 10^6
weeks <= len(costs), so a valid partition always exists

Examples

Input: ([2, 5, 4, 3, 7, 1, 6, 8], 3)

Expected Output: 15

Explanation: Partition [2],[5],[4,3,7,1,6,8] gives maxima 2+5+8 = 15, the minimum over all valid 3-way contiguous splits.

Input: ([5], 1)

Expected Output: 5

Explanation: A single campaign in a single week: the only partition, max = 5.

Input: ([1, 2, 3, 4], 4)

Expected Output: 10

Explanation: weeks == len(costs): every campaign is its own week, so the total is just the sum 1+2+3+4 = 10.

Input: ([7, 2, 5, 10, 8], 2)

Expected Output: 17

Explanation: Best split keeps the global max (10) in a group with 8 while a separate group's max is 7, e.g. [7,2,5]+[10,8] = 7+10 = 17.

Input: ([1, 1, 1, 1], 2)

Expected Output: 2

Explanation: All values equal, so any 2-way split yields max 1 per week: 1+1 = 2.

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

Expected Output: 10

Explanation: One week means one group covering everything; its max is 10.

Input: ([4, 3, 2, 1], 2)

Expected Output: 5

Explanation: Split [4,3,2]+[1] gives maxima 4+1 = 5, the minimum over all 2-way splits.

Input: ([1000000, 999999, 1, 2, 3], 3)

Expected Output: 1000004

Explanation: Putting both huge values in one group hides 999999 under 1000000. Optimal partition [1000000,999999],[1],[2,3] gives maxima 1000000+1+3 = 1000004.

Hints

Because groups must be contiguous and ordered, the only choice is where the cut points fall. Think about a DP over (number of weeks used, number of campaigns consumed so far).
Let dp[j][i] be the minimum total cost of partitioning the first i campaigns into exactly j weeks. Transition: dp[j][i] = min over m < i of dp[j-1][m] + max(costs[m..i-1]).
As you move the split point m downward from i-1, maintain a running maximum of costs[m..i-1] so each transition is O(1). Base case dp[0][0] = 0; you can roll the j dimension to keep memory at O(n).

Quick Overview