Hudson Software Engineer Interview Experience — An OA on Budgeted Item Purchases

Input:

prices[]: An array of length n, where prices[i] is the price of item i.

queries[]: A two-dimensional array whose elements are [start_i, budget_i]. Each query means that only items with indices greater than or equal to start_i may be purchased, with a total budget of budget_i.

Rules:

Each item may be purchased at most once. The order or positions of the items do not matter; they do not have to be contiguous. The goal is to buy as many items as possible without exceeding the budget.

Output:

For each query, return the maximum number of items that can be purchased.

Greedy approach for a single query:

Sort the prices in the eligible range from lowest to highest. Buy the cheapest items in order until buying the next item would exceed the budget. This gives the maximum number of items, by the classic exchange argument.