FastPrepFind Partition Cost
Problems/Find Partition Cost

Find Partition Cost

Amazon logoAmazon● MediumNEW GRADOA

Updated Nov 2026

QuestionFunctionExamplesConstraints

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, where m is the length of expense
  • 1 <= expense[i] <= 10^4
  • 1 <= 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

Interview reports that mention this question

  • Amazon New Grad OA Problems: Every Task We Have (Part 3 of 5)

Amazon interview experiences

  • Amazon Experienced SDE Onsite Questions: 1 Experience
  • Amazon SDE Onsite Interview Questions: 9 Experiences
  • Amazon SDE II and L5 FDE Interview Questions: 4 Experiences
  • Amazon Full-Time OA Problems, Earlier Reports (Part 5 of 5)
  • Amazon Full-Time OA Problems, Recent Reports (Part 4 of 5)
See Amazon hiring insights
Saved
class Solution {
    public int[] getLargestNumber(int[] expense, int p) {
      // write your code here
    }

}
Checking account…