Maximize Distinct Purchases Within Budget Constraints
Company: TikTok
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
##### Scenario
Given a customer budget and a list of product prices, determine the maximum number of distinct products the customer can afford.
##### Question
Design an algorithm that lists the products a customer can purchase within their budget while maximizing the count of items bought.
##### Hints
Sort prices ascending, add items greedily until the running total would exceed the budget.
Overview: This question evaluates understanding of selection and optimization under budget constraints, algorithmic efficiency, and the ability to implement correct logic for maximizing the number of distinct items purchased.
Given a non-negative integer budget and an array prices where prices[i] is the price of the i-th product, choose a subset of product indices such that the total cost does not exceed budget and the number of chosen products is maximized. If multiple subsets achieve the same maximum count, prefer the one with the smallest total cost; if still tied, return the lexicographically smallest list of indices. Each index represents a distinct product even if prices repeat. Return the chosen indices in increasing order.
Constraints
- 0 <= n <= 200000 where n = len(prices)
- 0 <= prices[i] <= 10^9
- 0 <= budget <= 10^14
- Indices are 0-based
- Return indices in increasing order
Hints
- Sort (price, index) pairs by price ascending, breaking ties by index.
- Iterate the sorted list and keep a running total; add an item if it keeps the total within budget.
- Track original indices while sorting; return chosen indices sorted ascending.