FastPrepMinimum Variance Sum Split
Problems/Minimum Variance Sum Split

Minimum Variance Sum Split

Airbnb logoAirbnb● MediumINTERNPHONE SCREEN

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported in an Airbnb software engineer intern technical round in Beijing in 2021. The report only names the task: divide an array so that the sum of the variances is as small as possible. It was one of two coding rounds, said to be at a medium to hard level.

The report gives no other rules, interface, limits or examples. It does not say how many parts to make. Here, the array is split into exactly k groups of neighboring elements, k is an input, a group's variance is the average squared distance from the group's mean, and the answer is the smallest total variance as a decimal number. The limits and examples are our own.

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

You are given an integer array nums and an integer k. Split nums into exactly k groups. Each group is a non-empty run of neighboring elements, and every element belongs to exactly one group.

The variance of a group is the average of the squared differences between its numbers and the group's mean. For a group of m numbers with mean avg, it is the sum of (x - avg) * (x - avg) over the group's numbers x, divided by m. A group with one number has variance 0.

Return the smallest possible sum of the variances of the k groups.

An answer is accepted if it differs from the correct answer by at most 10-9, or by a relative error of at most 10-9 when the correct answer is larger than 1.

Function

minVarianceSum(nums: int[], k: int) → double

Examples

Example 1

nums = [1,2,10,11]k = 2return = 0.5

The best split is [1,2] and [10,11]. The first group has mean 1.5, and both numbers are 0.5 away from it, so its variance is (0.25 + 0.25) / 2 = 0.25. The second group also has variance 0.25. The total is 0.5.

Any other split puts a small and a large number together, which gives a much bigger variance.

Example 2

nums = [0,10,0,10]k = 2return = 22.22222222222222

There are three ways to make two groups:

  • [0] and [10,0,10]: the second group has mean 20/3 and variance 200/9, so the total is 200/9, about 22.2222.
  • [0,10] and [0,10]: each group has mean 5 and variance 25, so the total is 50.
  • [0,10,0] and [10]: the same as the first way by symmetry, 200/9.

The smallest total is 200/9 = 22.22222222222222. Splitting into the two halves [0,10] and [0,10] is the worst choice, because each half still holds both a 0 and a 10.

Example 3

nums = [3,1,4,1,5]k = 1return = 2.56

With k = 1, the whole array is one group. Its mean is 14 / 5 = 2.8. The squared differences are 0.04, 3.24, 1.44, 3.24 and 4.84, which add up to 12.8. The variance is 12.8 / 5 = 2.56.

Constraints

  • 1 <= k <= nums.length <= 200
  • -104 <= nums[i] <= 104

More Airbnb Phone Screen questions

  • Read Across Sound TracksPHONE SCREEN · Seen Nov 2026
  • Text JustificationPHONE SCREEN · Seen Nov 2026
  • Decode and Store StringsPHONE SCREEN · Seen Oct 2026
  • Print Sentences as TablePHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
  • Detonate Bombs with Chain ReactionsPHONE SCREEN · Seen Aug 2026
  • Smallest Common RegionPHONE SCREEN · Seen Aug 2026
  • Longest Chain BookingPHONE SCREEN · Seen Aug 2026
  • Nested List Iterator with RemovePHONE SCREEN · Seen Jul 2026
  • Parse Query StringPHONE SCREEN · Seen May 2026
  • Pacific Atlantic Water FlowPHONE SCREEN · Seen May 2023

Similar questions at other companies

  • Best Improvement Period of at Least K IntervalsAmazon · PHONE SCREEN
  • Maximum Subarray SumCapital One · PHONE SCREEN · ONSITE INTERVIEWCapital One interview questions
  • Largest All-One Square Area and CountNVIDIA · PHONE SCREENNVIDIA interview questions
  • Minimum Cost to Merge StonesGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
  • Maximum Game Score with Fixed Forward JumpsStripe · OAStripe interview questions
  • Maximum Apples from Two Disjoint Fixed-Length SegmentsMarshall Wace · OAMarshall Wace interview questions
  • Maximum Non-Decreasing Array LengthVisa · OAVisa interview questions
  • Maximize CollaborationTikTok · OATikTok interview questions
  • Maximum Sum RectangleDeloitte · OADeloitte interview questions
  • Maximum Subarray Sum with One DeletionServiceNow · PHONE SCREENServiceNow interview questions

Interview reports that mention this question

  • Airbnb Intern Phone Interviews: 21 Experiences (Part 7 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 OA and Phone Screens: 17 Experiences (Part 6 of 7)
  • Airbnb Intern OA and Onsite Rounds: 16 Experiences (Part 5 of 7)
  • Airbnb Intern OA, Diplomacy Game: 19 Experiences (Part 4 of 7)
All Airbnb interview questionsSee Airbnb hiring insights
Saved
class Solution {
    public double minVarianceSum(int[] nums, int k) {
      // Write your code here.
    }
}
Checking account…