Find Partition Cost
Updated
Problem statement
The database specialists at Amazon are engaged in segmenting their sequence of interconnected servers. There exists a consecutive sequence of m servers, indexed from 0 to m - 1 (0-based), where the expense metric linked to the server with index j is given in the list expense[j]. These servers must be divided into precisely p separate, non-empty server segments.
The expense of a server segment from server x to server y (inclusive) is expense[x] + expense[y], so a segment with one server pays its expense twice. The aggregate expense accounts for the sum of partitioning costs for all server segments.
Given m servers, a list expense, and an integer p, determine both the least and greatest achievable total expense of these operations and return them as a list of length 2: [minimum expense, maximum expense].
Note: Splitting a list means dividing it into consecutive subsequences where each item belongs strictly to one segment. For a list [10, 20, 30, 40, 50], a valid segmentation would be [[10], [20, 30], [40, 50]], while [[10, 20], [20, 30], [40, 50]] and [[10, 30], [20, 40, 50]] would be deemed incorrect.
Function
getLargestNumber(expense: int[], p: int) → int[]Examples
Example 1
expense = [1, 2, 3, 2, 5]p = 3return = [14, 18]A segment from server x to server y (0-based, inclusive) costs expense[x] + expense[y]. The 6 ways to make 3 segments cost: [1], [2], [3, 2, 5]: 2 + 4 + 8 = 14; [1], [2, 3], [2, 5]: 2 + 5 + 7 = 14; [1], [2, 3, 2], [5]: 2 + 4 + 10 = 16; [1, 2], [3], [2, 5]: 3 + 6 + 7 = 16; [1, 2], [3, 2], [5]: 3 + 5 + 10 = 18; [1, 2, 3], [2], [5]: 4 + 4 + 10 = 18. The minimum is 14 and the maximum is 18, so return [14, 18].
Example 2
expense = [1, 2, 3, 4]p = 2return = [8, 12]The 3 ways to make 2 segments cost: [1], [2, 3, 4]: (1 + 1) + (2 + 4) = 8; [1, 2], [3, 4]: (1 + 2) + (3 + 4) = 10; [1, 2, 3], [4]: (1 + 3) + (4 + 4) = 12. The minimum is 8 and the maximum is 12, so return [8, 12].
Constraints
1 <= m <= 10^5, wheremis the length ofexpense1 <= expense[i] <= 10^41 <= p <= m
More Amazon interview questions
- LRU Cache for Query ResultsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Maximal SquareONSITE INTERVIEW · Seen Nov 2026
- Serialize and Deserialize a Binary TreeONSITE INTERVIEW · Seen Nov 2026
- Course SchedulePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Course Schedule IIPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Diagonal Traversal of a Binary TreeONSITE INTERVIEW · Seen Nov 2026
- Minimum Time to Spread Through a GridPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Consistent-Hash Packet RouterPHONE SCREEN · Seen Nov 2026
- Count Connected ComponentsPHONE SCREEN · Seen Nov 2026
- Maximize K-Element AND with an Increment BudgetOA · Seen Nov 2026
Similar questions at other companies
- Maximum Game Score with Fixed Forward JumpsStripe · OAStripe interview questions
- 0/1 KnapsackConfluent · OAConfluent interview questions
- Minimum Cost to Tile a Strip with Widths 1, 2, and 3Infosys · OAInfosys interview questions
- Maximum Escape Game ScoreMicrosoft · OAMicrosoft interview questions
- Maximum Subarray SumStraive · OA
- Longest Increasing Price SubsequenceOpenAI · OAOpenAI interview questions
- Lowest-Cost Shirt Color ScheduleElevenLabs · OAElevenLabs interview questions
- Maximum Game Board ScoreJP Morgan Chase · OAJP Morgan Chase interview questions
- API Bandwidth AllocationArista Networks · OAArista Networks interview questions
- Maximum Points by Deleting ElementsIBM · OAIBM interview questions