FastPrepMinimum Starting Coins to Buy All Products
Problems/Minimum Starting Coins to Buy All Products

Minimum Starting Coins to Buy All Products

Microsoft logoMicrosoft● HardINTERNOA

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: According to a review of a Microsoft software engineering student position, a medium-hard question on an online take-home test asked for the fewest coins to start with so that n products can all be bought. It gave one array of expected costs and another cost array that the author abbreviates as WC.

The review does not give the buying rule, the order, limits or the return type. We read WC as worst case and set the rule ourselves. To buy a product you must hold at least its worst-case amount. You then pay its expected amount, which is never more than the worst case. You choose the order, and you return the smallest start as a 64-bit integer. There are 1 to 10^4 products with amounts from 1 to 10^9. The question the author met may have used a different rule, for example a start that must work for every order.

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

You want to buy n products, each exactly once, in any order you choose. For product i:

  • worstCase[i] is the number of coins you must be holding to buy it, and
  • expected[i] is the number of coins you actually pay for it. It is never more than worstCase[i].

You start with some coins and never get any more. Return the smallest number of starting coins that lets you buy all n products, if you pick the best order.

Function

minimumStartingCoins(worstCase: int[], expected: int[]) → long

Examples

Example 1

worstCase = [5,8,4]expected = [3,2,4]return = 9

The three products cost 3 + 2 + 4 = 9 coins in total, so at least 9 coins are needed. 9 is enough. Buy product 1 first: it needs 8, you have 9, pay 2, 7 left. Then product 0: it needs 5, you have 7, pay 3, 4 left. Then product 2: it needs 4, you have 4, pay 4, 0 left.

Example 2

worstCase = [10,3]expected = [1,3]return = 10

Start with 10 and buy product 0 first: it needs 10, you have 10, pay 1, 9 left. Then product 1: it needs 3, you have 9, pay 3, 6 left. Fewer than 10 coins cannot work, because product 0 alone needs 10 on hand. So the answer is 10.

Example 3

worstCase = [6,9]expected = [1,8]return = 10

Start with 10 and buy product 0 first: it needs 6, you have 10, pay 1, 9 left. Then product 1: it needs 9, you have 9, pay 8, 1 left. 9 coins are not enough in either order: product 0 first leaves 8, which is less than the 9 product 1 needs, and product 1 first leaves 1, which is less than the 6 product 0 needs. The answer is 10.

Constraints

  • 1 <= worstCase.length == expected.length <= 10^4
  • 1 <= expected[i] <= worstCase[i] <= 10^9

More Microsoft Online Assessment questions

  • Minimum Cost to Process Priority TasksOA · Seen Nov 2026
  • Most Visited Sprint MarkerOA · Seen Nov 2026
  • Maximum Escape Game ScoreOA · Seen Nov 2026
  • Count Subarrays with a Perfect-Square ProductOA · Seen Nov 2026
  • Maximum Interactive Team SizeOA · Seen Nov 2026
  • Maximize Pipeline Throughput Under a Scaling BudgetOA · Seen Nov 2026
  • Minimum Cost K-Capable ModelsOA · Seen Nov 2026
  • Find Available Meeting RoomsOA · Seen Oct 2026
  • Maximum Sum of a K-StarOA · Seen Oct 2026
  • Capacity to Ship Packages Within DaysOA · ONSITE INTERVIEW · Seen Oct 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 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
  • Maximum Easy Tasks After RearrangingIBM · OAIBM interview questions

Interview reports that mention this question

  • Microsoft Explore and Student SWE: 12 Experiences (Part 6 of 6)

Microsoft interview experiences

  • Microsoft SWE Intern, Early 2025: 41 Experiences (Part 5 of 6)
  • Microsoft SWE Intern, Mid 2025: 42 Experiences (Part 4 of 6)
  • Microsoft SWE Intern, Late 2025: 47 Experiences (Part 3 of 6)
  • Microsoft SWE Intern, Early 2026: 54 Experiences (Part 2 of 6)
  • Microsoft SWE Intern Interviews: 244 Experiences (Part 1 of 6)
All Microsoft interview questionsSee Microsoft hiring insights
Saved
class Solution {
    public long minimumStartingCoins(int[] worstCase, int[] expected) {
        // Write your code here.
    }
}
Checking account…