Maximize Distinct Purchases Within Budget Constraints
Company: TikTok
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Take-home Project
##### 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.
Quick Answer: 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
Solution
from typing import List
def maximize_purchases(prices: List[int], budget: int) -> List[int]:
indexed = [(p, i) for i, p in enumerate(prices)]
# Sort by price, then by index to ensure deterministic tie-breaking
indexed.sort(key=lambda x: (x[0], x[1]))
total = 0
chosen = [] # store original indices
for price, idx in indexed:
if total + price <= budget:
total += price
chosen.append(idx)
# else skip; later items are not cheaper due to sorting
# Return indices in increasing order as required
chosen.sort()
return chosen
Explanation
Sorting items by (price, index) ensures that greedily taking items in that order yields the maximum count within budget. This also minimizes total cost for that count because the chosen set is the set of the cheapest possible items. Ties on equal prices are broken by index to ensure lexicographically smallest indices among equal-cost optimal solutions. Finally, the result is returned as indices in increasing order.
Time complexity: O(n log n). Space complexity: O(n).
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.