FastPrepDisk Clustering
Problems/Disk Clustering

Disk Clustering

Airbnb logoAirbnb● HardINTERNOA

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported in an Airbnb software engineer intern online assessment in early 2025, as the only problem in a 60-minute test. The task was to split a row of sector sizes into a set number of back-to-back clusters, where each cluster costs its first plus its last value, and to return both the smallest and the largest total cost.

The photo of the task was cut off near the end. It shows the rules and the worked example for the smallest cost, but not the limits or the function signature. Here, there are up to 10^5 sectors with sizes from 1 to 10^9, and the two totals come back as long values because they can pass the int range.

Our version is about 95% the same as the reported question.

A hard disk has n sectors in a row. sectorCost[i] is the size stored in sector i.

You must split the disk into exactly clusterCount clusters. Each cluster is a block of back-to-back sectors, no cluster is empty, and every sector belongs to exactly one cluster.

A cluster that runs from sector x to sector y costs sectorCost[x] + sectorCost[y]. A cluster with only one sector has x == y, so it costs twice that sector's size. The cost of a split is the sum of the costs of all its clusters.

Return an array of two numbers. The first is the smallest possible cost of a split, and the second is the largest possible cost.

Function

clusterCosts(sectorCost: int[], clusterCount: int) → long[]

Examples

Example 1

sectorCost = [1,2,3,2,5]clusterCount = 3return = [14,18]

For the smallest cost, split the disk as [1], [2], [3, 2, 5]. The costs are 1 + 1 = 2, 2 + 2 = 4 and 3 + 5 = 8, so the total is 14. For the largest cost, split it as [1, 2, 3], [2], [5]. The costs are 1 + 3 = 4, 2 + 2 = 4 and 5 + 5 = 10, so the total is 18. No other split goes below 14 or above 18.

Example 2

sectorCost = [4,1,3,6]clusterCount = 2return = [14,19]

With 2 clusters there are 3 places to cut. [4], [1, 3, 6] costs 8 + 7 = 15. [4, 1], [3, 6] costs 5 + 9 = 14. [4, 1, 3], [6] costs 7 + 12 = 19. The smallest is 14 and the largest is 19.

Example 3

sectorCost = [10,4,8]clusterCount = 1return = [18,18]

With 1 cluster, the whole disk is one block. Its cost is 10 + 8 = 18, so both the smallest and the largest cost are 18.

Constraints

  • n == sectorCost.length
  • 1 <= clusterCount <= n <= 105
  • 1 <= sectorCost[i] <= 109

More Airbnb Online Assessment questions

  • Task Management SystemOA · Seen Nov 2026
  • Recipe Management SystemOA · Seen Nov 2026
  • Progressive Banking SystemOA · Seen Nov 2026
  • Credit Accounts with Scheduled TransfersOA · Seen Oct 2026
  • Parcel Attribute Store with TTLOA · Seen Oct 2026
  • Parcel Event TrackingOA · Seen Oct 2026
  • Median Home Price by CityOA · Seen Sep 2026
  • In-Memory File SystemOA · Seen Sep 2026
  • Worker Management (Promotion Track), Part 4: Full-Shift Double PayOA · Seen Sep 2026
  • Worker Management (Promotion Track), Part 3: Promotions and SalaryOA · Seen Sep 2026

Similar questions at other companies

  • Maximize K-Element AND with an Increment BudgetAmazon · OA
  • Delete and Freeze GameRubrik · OARubrik interview questions
  • Most Segments That Sort the ArrayRippling · OARippling interview questions
  • Most Items Within Budget from a Start IndexHudson River Trading · OAHudson River Trading interview questions
  • Luna and the Colorful SocksPhonePe · OAPhonePe interview questions
  • Minimum Starting Coins to Buy All ProductsMicrosoft · OAMicrosoft interview questions
  • Minimum Swaps to Sort a Ternary Array After UpdatesGoogle · OAGoogle interview questions
  • Get Max EfficiencySalesforce · OASalesforce interview questions
  • Finding a Hidden Benchmark ValueSamsung · OASamsung interview questions
  • Catch Fish with Reusable BaitsSusquehanna International Group (SIG) · OASusquehanna International Group (SIG) interview questions

Interview reports that mention this question

  • Airbnb SWE Intern OA / Interviews: 122 Experiences (Part 1 of 7)

Airbnb interview experiences

  • Airbnb SWE OA: Four-Level Banking System: 1 Experience
  • Airbnb Campus and Full-Time SWE OA / Interviews: 9 Experiences
  • Airbnb Intern Phone Interviews: 21 Experiences (Part 7 of 7)
  • Airbnb Intern OA and Phone Screens: 17 Experiences (Part 6 of 7)
  • Airbnb Intern OA and Onsite Rounds: 16 Experiences (Part 5 of 7)
All Airbnb interview questionsSee Airbnb hiring insights
Saved
class Solution {
    public long[] clusterCosts(int[] sectorCost, int clusterCount) {
      // Write your code here.
    }
}
Checking account…