FastPrepSplit a Number into Non-Decreasing Groups
Problems/Split a Number into Non-Decreasing Groups

Split a Number into Non-Decreasing Groups

Expedia logoExpedia● MediumINTERNOAONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Three Expedia SDE intern reports from late 2020 name this task. Two are entries, one from an online test and one from a video-call interview. The third is a post that lists it in its online test.

The entries give only the title, and the post describes the task in a single line. A separate card for that title gives the rule (k groups, none empty, whose sizes never go down), the answer modulo 10^9 + 7, and limits of at most 1000 items with K no larger than N. Here, the function takes one n and one k per call instead of several test cases. The rule, the modulus and the limits follow the card.

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

You have n identical items and want to split all of them into exactly k groups. Every group must get at least one item, and the groups are listed so that their sizes never decrease: size[0] <= size[1] <= ... <= size[k-1].

Since the items are identical, a split is fully described by its list of group sizes. For example, with n = 5 and k = 2 the splits are [1,4] and [2,3]; [4,1] is not allowed because the sizes go down.

Return the number of different splits. The number can be very large, so return it modulo 10^9 + 7.

Function

countPartitions(n: int, k: int) → int

Examples

Example 1

n = 7k = 3return = 4

The ways to write 7 as 3 group sizes that never decrease are [1,1,5], [1,2,4], [1,3,3] and [2,2,3]. Orders such as [5,1,1] are not counted again, because the sizes must not go down. The answer is 4.

Example 2

n = 9k = 4return = 6

The 6 ways are [1,1,1,6], [1,1,2,5], [1,1,3,4], [1,2,2,4], [1,2,3,3] and [2,2,2,3].

Example 3

n = 300k = 25return = 185796306

The exact count is 125,144,186,672,314, which is larger than 10^9 + 7, so the answer is that count modulo 10^9 + 7: 185796306.

Constraints

  • 1 <= n <= 1000
  • 1 <= k <= n

More Expedia Onsite Interview questions

  • Scramble StringONSITE INTERVIEW · Seen Sep 2026
  • Smallest Sufficient TeamONSITE INTERVIEW · Seen Sep 2026
  • Check Anagram Pairs Index by IndexONSITE INTERVIEW · Seen Oct 2025
  • Fresh Oranges Left After Rotting StopsONSITE INTERVIEW · Seen Oct 2025
  • Longest Increasing SubsequenceONSITE INTERVIEW · Seen Oct 2025
  • Lowest Common Ancestor with Repeated and Missing ValuesONSITE INTERVIEW · Seen Oct 2025
  • Shortest Substring with Exactly K OnesONSITE INTERVIEW · Seen Oct 2025
  • Middle Element of a Linked ListONSITE INTERVIEW · Seen Nov 2024
  • Minimum in a Rotated Sorted ArrayONSITE INTERVIEW · Seen Sep 2024
  • Mirror Image Binary TreesONSITE INTERVIEW · Seen Sep 2024

Similar questions at other companies

  • Dice-Walk Winning ProbabilityGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
  • Integer BreakAmazon · ONSITE INTERVIEW
  • Knight Probability in ChessboardGoldman Sachs · ONSITE INTERVIEWGoldman Sachs interview questions
  • Frog Paths Without Long RunsSusquehanna International Group (SIG) · OASusquehanna International Group (SIG) interview questions
  • Count Lucky TicketsThe D.E. Shaw Group · OAThe D.E. Shaw Group interview questions
  • Count Staircases with Strictly Increasing StepseBay · ONSITE INTERVIEWeBay interview questions
  • Maximum Score with Prime JumpsMicrosoft · OAMicrosoft interview questions
  • Count Divisible Power SumsGoodScore · ONSITE INTERVIEW
  • Jump Game with Prime-Step RuleUber · OAUber interview questions
  • Count Shipment SchedulesMorgan Stanley · OAMorgan Stanley interview questions

Expedia interview experiences

  • Expedia Intern Final Round in 2021: 28 Experiences (Part 4 of 6)
  • Expedia Intern Finals Before 2020: 14 Experiences (Part 6 of 6)
  • Expedia Intern Final Round in 2020: 24 Experiences (Part 5 of 6)
  • Expedia Intern Final Round in 2022: 15 Experiences (Part 3 of 6)
  • Expedia Intern Final Round in 2023: 17 Experiences (Part 2 of 6)
  • Expedia SWE Intern Final Round: 126 Experiences (Part 1 of 6)
All Expedia interview questionsSee Expedia hiring insights
Saved
class Solution {
    public int countPartitions(int n, int k) {
        // Write your code here.
    }
}
Checking account…