Apply Discount to Prices

Medium

Amazon

8 views

Topics:

Strings

A sentence is a string of single-space separated words where each word can contain digits, lowercase letters, and the dollar sign '$'. A word represents a price if it is a sequence of digits preceded by a dollar sign.

For example, "$100", "$23", and "$6" represent prices while "100", "$", and "$1e5" do not.

You are given a string sentence representing a sentence and an integer discount. For each word representing a price, apply a discount of discount% on the price and update the word in the sentence. All updated prices should be represented with exactly two decimal places.

Return a string representing the modified sentence.

Note that all prices will contain at most 10 digits.

Example 1:

Input: sentence = "there are $1 $2 and 5$ candies in the shop", discount = 50
Output: "there are $0.50 $1.00 and 5$ candies in the shop"
Explanation: 
The words which represent prices are "$1" and "$2". 
- A 50% discount on "$1" yields "$0.50", so "$1" is replaced by "$0.50".
- A 50% discount on "$2" yields "$1". Since we need to have exactly 2 decimal places after a price, we replace "$2" with "$1.00".

Example 2:

Input: sentence = "1 2 $3 4 $5 $6 7 8$ $9 $10$", discount = 100
Output: "1 2 $0.00 4 $0.00 $0.00 7 8$ $0.00 $10$"
Explanation: 
Applying a 100% discount on any price will result in 0.
The words representing prices are "$3", "$5", "$6", and "$9".
Each of them is replaced by "$0.00".

Constraints:

1 <= sentence.length <= 10⁵
sentence consists of lowercase English letters, digits, ' ', and '$'.
sentence does not have leading or trailing spaces.
All words in sentence are separated by a single space.
All prices will be positive numbers without leading zeros.
All prices will have at most 10 digits.
0 <= discount <= 100

Apply Discount to Prices

Medium

Amazon

8 views

Topics:

Strings

A sentence is a string of single-space separated words where each word can contain digits, lowercase letters, and the dollar sign '$'. A word represents a price if it is a sequence of digits preceded by a dollar sign.

For example, "$100", "$23", and "$6" represent prices while "100", "$", and "$1e5" do not.

You are given a string sentence representing a sentence and an integer discount. For each word representing a price, apply a discount of discount% on the price and update the word in the sentence. All updated prices should be represented with exactly two decimal places.

Return a string representing the modified sentence.

Note that all prices will contain at most 10 digits.

Example 1:

Input: sentence = "there are $1 $2 and 5$ candies in the shop", discount = 50
Output: "there are $0.50 $1.00 and 5$ candies in the shop"
Explanation: 
The words which represent prices are "$1" and "$2". 
- A 50% discount on "$1" yields "$0.50", so "$1" is replaced by "$0.50".
- A 50% discount on "$2" yields "$1". Since we need to have exactly 2 decimal places after a price, we replace "$2" with "$1.00".

Example 2:

Input: sentence = "1 2 $3 4 $5 $6 7 8$ $9 $10$", discount = 100
Output: "1 2 $0.00 4 $0.00 $0.00 7 8$ $0.00 $10$"
Explanation: 
Applying a 100% discount on any price will result in 0.
The words representing prices are "$3", "$5", "$6", and "$9".
Each of them is replaced by "$0.00".

Constraints:

1 <= sentence.length <= 10⁵
sentence consists of lowercase English letters, digits, ' ', and '$'.
sentence does not have leading or trailing spaces.
All words in sentence are separated by a single space.
All prices will be positive numbers without leading zeros.
All prices will have at most 10 digits.
0 <= discount <= 100

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the data types and possible ranges for the prices and the discount? Can they be negative or non-integer?
If the discount results in a price with many decimal places, how should I handle the rounding or truncation of the resulting price?
Can the list of prices be empty or null?
If the discount is greater than 100%, what should the resulting price be? Should I return 0, a negative value, or throw an error?
Is the original list of prices allowed to be modified, or should I create a new list to store the discounted prices?

Brute Force Solution

Approach

The brute force method for applying a discount to a list of prices involves going through each price individually. For each price, we will calculate the discounted amount and subtract it from the original price to find the final discounted price.

Here's how the algorithm would work step-by-step:

Take the first price from the list.
Calculate the discount amount by multiplying the price by the discount percentage.
Subtract the discount amount from the original price to find the discounted price.
Store the discounted price in a new list of final prices.
Repeat the process (steps 1-4) for each remaining price in the original list until all prices have been discounted.
You now have a new list containing all the discounted prices.

Code Implementation

def apply_discount_brute_force(prices, discount_percentage):
    discounted_prices = []

    # Iterate through each original price to apply discount
    for original_price in prices:

        # Calculate the discount amount based on percentage
        discount_amount = original_price * (discount_percentage / 100)

        # Determine the final discounted price
        final_price = original_price - discount_amount

        # Add the discounted price to the result
        discounted_prices.append(final_price)

    return discounted_prices

Big(O) Analysis

Time Complexity

O(n) – The described solution iterates through each price in the list once to apply the discount. The input size, denoted as n, represents the number of prices in the list. For each price, a fixed number of operations (multiplication and subtraction) are performed. Therefore, the time complexity scales linearly with the number of prices, resulting in O(n) time complexity.

Space Complexity

O(N) – The algorithm creates a new list to store the discounted prices. In the worst-case scenario, the size of this list will be equal to the number of prices in the original list. Therefore, the algorithm uses auxiliary space proportional to the number of prices, N, where N is the number of prices in the input list. Hence, the space complexity is O(N).

Optimal Solution

Approach

The best way to solve this problem is to efficiently apply a discount to each price. We'll look at each price individually, figure out the discount amount, and then subtract that from the original price to get the final price. This avoids recalculating discounts or doing unnecessary work.

Here's how the algorithm would work step-by-step:

Take the first price in the list.
Calculate the amount of the discount by finding the percentage of the price that the discount represents.
Subtract the discount amount from the original price. This gives you the final, discounted price.
Store this final price in a new list or modify the original list.
Move on to the next price in the list.
Repeat the process of calculating the discount and subtracting it until you have processed all the prices.
Once all prices have been adjusted, you will have a list of the discounted prices.

Code Implementation

def apply_discount_to_prices(prices, discount):
    discounted_prices = []

    # Iterate through each price to apply the discount
    for original_price in prices:
        # Calculate the discount amount
        discount_amount = (discount / 100) * original_price

        # Subtract the discount from the original price
        final_price = original_price - discount_amount

        # Store the final price
        discounted_prices.append(final_price)

    # Return the list of discounted prices
    return discounted_prices

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through each price in the list once to apply the discount. The input size, n, represents the number of prices in the list. For each price, a fixed number of operations (multiplication and subtraction) are performed. Therefore, the time complexity is directly proportional to the number of prices, resulting in O(n) time complexity.

Space Complexity

O(N) – The plain English description indicates that a new list (or modification of the original list in-place, which we will assume is done via creating a copy first and then overwritting at the end) is used to store the final discounted prices. Where N is the number of prices in the input list, this results in an auxiliary list of size N. Other than this list and the discount percentage, no other significant auxiliary space is used. Therefore, the auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
Null prices array	Throw IllegalArgumentException or return null/empty list, depending on requirements/contract
Empty prices array	Return an empty list since there are no prices to discount
Null discount value	Throw IllegalArgumentException or return the original prices array unmodified, depending on requirements/contract
Discount value outside the range 0-100 (e.g., negative or > 100)	Throw IllegalArgumentException or return original prices, handling it as an invalid discount.
Large prices array (potential performance issues)	Ensure algorithm has O(n) time complexity to handle large input efficiently, avoiding nested loops
Prices contain very large numbers (potential integer overflow)	Use data types like long or double to prevent integer overflow during calculations if necessary
Floating point precision issues when applying the discount	Use BigDecimal for precise calculations or round the result to a certain number of decimal places to avoid representation errors
Prices array contains negative values	Throw IllegalArgumentException or assume prices should not be negative and handle them appropriately (e.g., treat as zero, or return an error).