Minimum Starting Coins to Buy All Products
Updated
Problem statement
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, andexpected[i]is the number of coins you actually pay for it. It is never more thanworstCase[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[]) → longExamples
Example 1
worstCase = [5,8,4]expected = [3,2,4]return = 9The 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 = 10Start 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 = 10Start 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^41 <= 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 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)