Amazon frequently offers product bundles to customers, where multiple related products are combined and sold together at a discounted price. The goal is to create attractive bundle offers that maximize potential revenue.
Given two equally sized arrays, A and B, where A represents the individual selling prices of a set of products, and B represents the individual selling prices of another set of related products. The size of these arrays, N, represents the number of products in each set.
Amazon wants to identify the top K most lucrative product bundle combinations by combining one product from set A and one product from set B. The revenue generated from a bundle is calculated as the sum of the individual product prices in the bundle.
A = [1, 2, 3, 4]
B = [2, 7, 1, 2]
This problem asks for the top K largest sums formed by picking one element from A and one element from B. A practical solution is to sort the arrays and use a max heap (priority queue) to efficiently explore the largest pair sums without generating all N² combinations. The key idea is to always expand from the current best candidates, which keeps the solution efficient for online assessment settings.
