Amazon Online Assessment 2021 (OA) - Find Lowest Price

Think of a video game that's been around for ten whole years. To celebrate, the game creators decide to throw an epic virtual party. But this party is VIP only—just for the gamers who have been playing and supporting the game for the last five years. They're the ones who get the VIP passes to some seriously cool in-game items on sale.

Now, here's the game: these special items have different kinds of sale stickers on them. Players have to use their math skills to figure out the cheapest way to grab all the items they want. Every item's price has to be rounded to the nearest number before they add it up to see how much virtual cash they need.

The sale stickers are like power-ups:

The "Fixed Price" power-up (Type 0) changes the item's price to a lower one that's already set. The "Percent Off" power-up (Type 1) knocks off a chunk of the price based on a percentage. The "Cash Off" power-up (Type 2) takes a set amount of virtual cash off the item's price. The players have to be smart and pick the best power-ups to get their total cost as low as possible. It's like a mini-game puzzle inside the big celebration, and everyone's trying to score the best loot for the least amount of virtual coins.

Relevant Amazon OA Problems:

Input

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

Output

the total amount paid for all listed products, discounted to privileged members' pricing

Examples

Example 1:

Input:

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

Output: 35

Explanation:

The total price to purchase the three items is 5+15+15=35.

Constraints

1 <= n, m, d <= 1000