FastPrep
Problem · Array

Maximum Products by Budget

Learn this problem
● MediumMicrosoftINTERNOA
See Microsoft hiring insights

Problem statement

Alex is shopping at Ozone Galleria Mall, where each cubicle sells products at a fixed price. The cubicles are arranged from left to right in non-decreasing order of price.

You are given an array of n integers, prices, where prices[i] is the price at the ith cubicle, and a list of queries. Each query contains:

  • pos: Alex's 1-based initial position
  • amount: the amount of money Alex has

For each query, Alex visits every cubicle from position pos through n. He may buy at most one product from each visited cubicle. Return the maximum number of products he can buy without spending more than amount.

Function

maximumProducts(prices: int[], queries: int[][]) → int[]

Examples

Example 1

prices = [3,4,5,5,7]queries = [[2,10],[1,24],[5,5]]return = [2,5,0]

  1. pos = 2, amount = 10: Alex visits cubicles 2 through 5 and can buy at most 2 products. He can choose any of the following pairs:

    • Cubicles 2 and 3: 4 + 5 = 9 (<= 10)
    • Cubicles 2 and 4: 4 + 5 = 9 (<= 10)
    • Cubicles 3 and 4: 5 + 5 = 10 (<= 10)

    The answer is 2.

  2. pos = 1, amount = 24: Alex visits all cubicles and can buy from all of them because the total cost is 3 + 4 + 5 + 5 + 7 = 24 (<= 24).

    The answer is 5.

  3. pos = 5, amount = 5: Alex can visit only cubicle 5, but cannot buy its product because the price 7 exceeds the available amount 5.

    The answer is 0.

More Microsoft problems

drafts saved locally
public int[] maximumProducts(int[] prices, int[][] queries) {
  // write your code here
}
prices[3,4,5,5,7]
queries[[2,10],[1,24],[5,5]]
expected[2,5,0]
checking account