How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at TikTok.

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at TikTok during technical interviews.

Maximize products bought under budget | TikTok Coding Question

Q: Maximize products bought under budget

This question evaluates algorithmic problem-solving skills including sorting, prefix-sum accumulation, binary search, greedy selection, careful tie-breaking for lexicographic order, and complexity analysis.

Maximize products bought under budget

Company: TikTok

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Take-home Project

Given N products and M customers, for each customer find the list of distinct products they can buy without exceeding their budget such that the number of products purchased is maximized. If multiple solutions yield the same maximum count: (1) choose the set with the smallest total spend; (2) if still tied, choose the lexicographically smallest list of product_ids. You may use each product at most once per customer; assume infinite stock across customers (each customer considers the full catalog independently). Return, for each customer, (customer_id, max_count, chosen_product_ids in ascending order by price then product_id). Design an algorithm with preprocessing O(N log N) and query time O(log N) per customer (excluding output size), and implement it. Justify correctness. Input format - products: list of (product_id INT, price INT) with price >= 0 - customers: list of (customer_id INT, budget INT) with budget >= 0 Constraints - 1 ≤ N, M ≤ 200,000; 0 ≤ price, budget ≤ 1e9 - Ties on price are broken by smaller product_id Required approach - Pre-sort products by (price ASC, product_id ASC) and build prefix sums of prices and parallel array of product_ids. - For each budget B, find k = max index such that prefix_sum[k] ≤ B via binary search; output the first k product_ids in that sorted order. Example products = [(1,100),(2,100),(3,300),(4,500)] customers = [("A",500)] Output: ("A", 3, [1,2,3]) because taking the three cheapest maximizes count; total spend 500. Edge cases to handle - Budget < cheapest price → empty list. - Budget ≥ sum of all prices → all product_ids. - Many equal prices: verify lexicographic tie-break by product_id. Deliverables - Working implementation (e.g., Python) and time/space complexity analysis.

Quick Answer: This question evaluates algorithmic problem-solving skills including sorting, prefix-sum accumulation, binary search, greedy selection, careful tie-breaking for lexicographic order, and complexity analysis.

Given a catalog of products and a list of customers, determine what each customer should buy independently. Each product has a distinct product_id and a non-negative price. Each customer has a customer_id and a non-negative budget. For each customer, choose a set of distinct products whose total price does not exceed the customer's budget and whose number of products is maximized. If multiple choices buy the same maximum number of products, choose the one with the smallest total spend. If there is still a tie, choose the lexicographically smallest product_id list when products are ordered by price ascending, then product_id ascending. You may use each product at most once per customer, but stock is infinite across different customers. Return one result per customer in the same order as the input customers.

Constraints

1 <= len(products), len(customers) <= 200000
0 <= price, budget <= 1000000000
product_id values are distinct integers
Ties on product price are broken by smaller product_id
The total number of returned product IDs may be large; output construction cost is counted separately from per-customer query time

Examples

Input: ([(1, 100), (2, 100), (3, 300), (4, 500)], [(10, 500)])

Expected Output: [(10, 3, [1, 2, 3])]

Explanation: The three cheapest products cost 100 + 100 + 300 = 500, so customer 10 can buy 3 products.

Input: ([(5, 10), (2, 20)], [(1, 9)])

Expected Output: [(1, 0, [])]

Explanation: The customer's budget is smaller than the cheapest product price, so no products can be bought.

Input: ([(3, 5), (1, 0), (2, 5)], [(7, 10)])

Expected Output: [(7, 3, [1, 2, 3])]

Explanation: Sorted by price then product_id, the products are 1, 2, 3 with total cost 10, so all products are chosen.

Input: ([(5, 2), (1, 2), (3, 2), (4, 5)], [(8, 4)])

Expected Output: [(8, 2, [1, 3])]

Explanation: Any two price-2 products maximize the count with spend 4. The tie is broken by smaller product_id, so products 1 and 3 are chosen.

Input: ([(10, 8), (20, 3), (30, 3), (40, 2), (50, 10)], [(1, 1), (2, 5), (3, 15), (4, 100)])

Expected Output: [(1, 0, []), (2, 2, [40, 20]), (3, 3, [40, 20, 30]), (4, 5, [40, 20, 30, 10, 50])]

Explanation: Products sorted by price then product_id are [40, 20, 30, 10, 50] with prefix costs [2, 5, 8, 16, 26]. Each budget chooses the longest affordable prefix.

Input: ([(7, 0), (2, 0), (5, 1)], [(9, 0), (10, 1)])

Expected Output: [(9, 2, [2, 7]), (10, 3, [2, 7, 5])]

Explanation: A zero budget can still buy all zero-price products. Equal zero prices are ordered by product_id.

Hints

For any fixed count k, the cheapest possible way to buy k products is to take the first k products after sorting by price, then product_id.
Build prefix sums of the sorted prices. For a customer budget B, binary search for the largest k such that prefix_sums[k] <= B.

Quick Overview

This question evaluates algorithmic problem-solving skills including sorting, prefix-sum accumulation, binary search, greedy selection, careful tie-breaking for lexicographic order, and complexity analysis.