Suppose you are given 2 unordered lists of Amazon products with product id, price and a gift coupon worth S amount.
Can you write a function to find 1 product from each list which can best utilize the gift coupon (not more than the value)?
You can write a function in the programming language of your choice.
Input: (a: 10, b: 2, c: 5, d: 8) (x: 20, y: 15, z: 10), S: 16
Result: => (c: 5, z: 10)
Return null if no price < S.
这道题要求你从两组无序商品中各选一个商品，使两者价格之和不超过优惠券金额 S，并且尽量接近 S。核心思路是先把其中一组商品按价格整理出来，再在另一组中遍历每个价格，利用哈希表或二分查找快速寻找不超过剩余额度的最佳匹配，从而得到最优组合。示例中 S=16，(5, 10) 正好等于 15，是满足条件且最接近上限的答案。如果找不到任何合法组合，则返回 null。
正文完
