Disk Clustering
Updated
Problem statement
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.length1 <= clusterCount <= n <= 1051 <= 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 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)