Paypal VO 面试真题解析：Shopping Cart Billing 折扣定价问题

Shopping Cart Billing

An e-commerce company is currently celebrating ten years in business. They are having a sale to honor their privileged members, those who have been using their services for the past five years. They receive the best discounts indicated by any discount tags attached to the product. Determine the minimum cost to purchase all products listed. As each potential price is calculated, truncate it to its integer part before adding it to the total. Return the cost to purchase all items as an integer.

There are three types of discount tags:

• Type 0: discounted price, the item is sold for a given price.
• Type 1: percentage discount, the customer is given a fixed percentage discount from the retail price.
• Type 2: fixed discount, the customer is given a fixed amount off from the retail price.

Example

products = [['10', 'd0', 'd1'], ['15', 'EMPTY', 'EMPTY'], ['20', 'd1', 'EMPTY']]
discounts = [['d0', '1', '27'], ['d1', '2', '5']]

The products array elements are in the form [‘price’, ‘tag1’, ‘tag2’, …, ‘tagm-1’]. There may be zero or more discount codes associated with a product. Discount tags in the products array may be ‘EMPTY’, which is the same as a null value. The discounts array elements are in the form [‘tag’, ‘type’, ‘amount’].

• If a privileged member buys product 1 listed at a price of 10 with two discounts available:
• Under discount d0 of type 1, the discounted price is 10 – 10 * 0.27 = 7.30, round to 7.
• Under discount d1 of type 2, the discounted price is 10 – 5 = 5.
• The price to purchase product 1 is the lower of the two, or 5 in this case.
• The second product is priced at 15 because there are no discounts available.
• The third product is priced at 20. Using discount tag d1 of type 2, the discounted price is 20 – 5 = 15.
• The total price to purchase the three items is 5 + 15 + 15 = 35.

Notes: Not all items will have the maximum number of tags. Empty tags may not exist in input, or they may be filled with the string EMPTY. These are equivalent as demonstrated in the example.

Function Description

Complete the function findLowestPrice in the editor below.

findLowestPrice has the following parameter(s):

• products[n][m]: a 2D array of product descriptors as strings: price followed by up to m-1 discount tags
• discounts[d][3]: a 2D array of tag descriptors as strings: tag, type, amount

Returns

int: the total amount paid for all listed products, discounted to privileged members’ pricing

这道题的核心是先把每个折扣标签整理成哈希表，再遍历每个商品的所有可用标签，分别计算会员价并取最小值。需要注意三种折扣类型：type 0 表示直接售价，type 1 是按百分比折扣，type 2 是固定金额减免；每次计算出的价格都要先向下取整，再累加到总价中。商品可能没有任何有效折扣，空标签用 EMPTY 表示，直接忽略即可。整体思路非常适合用字典 / 映射做快速查找，时间复杂度主要取决于商品数量和每个商品的标签数。