Maximize Amount After Two Days of Conversions

Medium

Uber

1 view

Topics:

GraphsDynamic Programming

You are given a string initialCurrency, and you start with 1.0 of initialCurrency.

You are also given four arrays with currency pairs (strings) and rates (real numbers):

pairs1[i] = [startCurrency_i, targetCurrency_i] denotes that you can convert from startCurrency_i to targetCurrency_i at a rate of rates1[i] on day 1.
pairs2[i] = [startCurrency_i, targetCurrency_i] denotes that you can convert from startCurrency_i to targetCurrency_i at a rate of rates2[i] on day 2.
Also, each targetCurrency can be converted back to its corresponding startCurrency at a rate of 1 / rate.

You can perform any number of conversions, including zero, using rates1 on day 1, followed by any number of additional conversions, including zero, using rates2 on day 2.

Return the maximum amount of initialCurrency you can have after performing any number of conversions on both days in order.

Note: Conversion rates are valid, and there will be no contradictions in the rates for either day. The rates for the days are independent of each other.

Example 1:

Input: initialCurrency = "EUR", pairs1 = [["EUR","USD"],["USD","JPY"]], rates1 = [2.0,3.0], pairs2 = [["JPY","USD"],["USD","CHF"],["CHF","EUR"]], rates2 = [4.0,5.0,6.0]

Output: 720.00000

Explanation:

To get the maximum amount of EUR, starting with 1.0 EUR:

On Day 1:
- Convert EUR to USD to get 2.0 USD.
- Convert USD to JPY to get 6.0 JPY.
On Day 2:
- Convert JPY to USD to get 24.0 USD.
- Convert USD to CHF to get 120.0 CHF.
- Finally, convert CHF to EUR to get 720.0 EUR.

Example 2:

Input: initialCurrency = "NGN", pairs1 = [["NGN","EUR"]], rates1 = [9.0], pairs2 = [["NGN","EUR"]], rates2 = [6.0]

Output: 1.50000

Explanation:

Converting NGN to EUR on day 1 and EUR to NGN using the inverse rate on day 2 gives the maximum amount.

Example 3:

Input: initialCurrency = "USD", pairs1 = [["USD","EUR"]], rates1 = [1.0], pairs2 = [["EUR","JPY"]], rates2 = [10.0]

Output: 1.00000

Explanation:

In this example, there is no need to make any conversions on either day.

Constraints:

1 <= initialCurrency.length <= 3
initialCurrency consists only of uppercase English letters.
1 <= n == pairs1.length <= 10
1 <= m == pairs2.length <= 10
pairs1[i] == [startCurrency_i, targetCurrency_i]
pairs2[i] == [startCurrency_i, targetCurrency_i]
1 <= startCurrency_i.length, targetCurrency_i.length <= 3
startCurrency_i and targetCurrency_i consist only of uppercase English letters.
rates1.length == n
rates2.length == m
1.0 <= rates1[i], rates2[i] <= 10.0
The input is generated such that there are no contradictions or cycles in the conversion graphs for either day.
The input is generated such that the output is at most 5 * 10¹⁰.

Maximize Amount After Two Days of Conversions

Medium

Uber

1 view

Topics:

GraphsDynamic Programming

You are given a string initialCurrency, and you start with 1.0 of initialCurrency.

You are also given four arrays with currency pairs (strings) and rates (real numbers):

pairs1[i] = [startCurrency_i, targetCurrency_i] denotes that you can convert from startCurrency_i to targetCurrency_i at a rate of rates1[i] on day 1.
pairs2[i] = [startCurrency_i, targetCurrency_i] denotes that you can convert from startCurrency_i to targetCurrency_i at a rate of rates2[i] on day 2.
Also, each targetCurrency can be converted back to its corresponding startCurrency at a rate of 1 / rate.

You can perform any number of conversions, including zero, using rates1 on day 1, followed by any number of additional conversions, including zero, using rates2 on day 2.

Return the maximum amount of initialCurrency you can have after performing any number of conversions on both days in order.

Note: Conversion rates are valid, and there will be no contradictions in the rates for either day. The rates for the days are independent of each other.

Example 1:

Input: initialCurrency = "EUR", pairs1 = [["EUR","USD"],["USD","JPY"]], rates1 = [2.0,3.0], pairs2 = [["JPY","USD"],["USD","CHF"],["CHF","EUR"]], rates2 = [4.0,5.0,6.0]

Output: 720.00000

Explanation:

To get the maximum amount of EUR, starting with 1.0 EUR:

On Day 1:
- Convert EUR to USD to get 2.0 USD.
- Convert USD to JPY to get 6.0 JPY.
On Day 2:
- Convert JPY to USD to get 24.0 USD.
- Convert USD to CHF to get 120.0 CHF.
- Finally, convert CHF to EUR to get 720.0 EUR.

Example 2:

Input: initialCurrency = "NGN", pairs1 = [["NGN","EUR"]], rates1 = [9.0], pairs2 = [["NGN","EUR"]], rates2 = [6.0]

Output: 1.50000

Explanation:

Converting NGN to EUR on day 1 and EUR to NGN using the inverse rate on day 2 gives the maximum amount.

Example 3:

Input: initialCurrency = "USD", pairs1 = [["USD","EUR"]], rates1 = [1.0], pairs2 = [["EUR","JPY"]], rates2 = [10.0]

Output: 1.00000

Explanation:

In this example, there is no need to make any conversions on either day.

Constraints:

1 <= initialCurrency.length <= 3
initialCurrency consists only of uppercase English letters.
1 <= n == pairs1.length <= 10
1 <= m == pairs2.length <= 10
pairs1[i] == [startCurrency_i, targetCurrency_i]
pairs2[i] == [startCurrency_i, targetCurrency_i]
1 <= startCurrency_i.length, targetCurrency_i.length <= 3
startCurrency_i and targetCurrency_i consist only of uppercase English letters.
rates1.length == n
rates2.length == m
1.0 <= rates1[i], rates2[i] <= 10.0
The input is generated such that there are no contradictions or cycles in the conversion graphs for either day.
The input is generated such that the output is at most 5 * 10¹⁰.

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:

Can the initial amount and the conversion rates be zero or negative?
What are the upper bounds for the initial amount and the two conversion rates?
If it's impossible to perform both conversions (e.g., conversion rates are zero), what should the function return?
Can the initial amount or the conversion rates be floating-point numbers?
Are the conversion rates independent, or does the second day's conversion rate depend on the amount after the first conversion?

Brute Force Solution

Approach

The brute force strategy is to explore every possible combination of actions we can take over two days. We will look at every possibility and choose the best outcome. This approach guarantees finding the maximum amount if we consider all valid conversions.

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

On the first day, consider all possible conversions of items we could make. Imagine we convert 0 items of the first type, then 1 item, then 2 items, and so on, up to converting all possible items of the first type.
For each possible number of items we convert on the first day, calculate how many of each item type we have left after the conversion.
On the second day, for each result from the first day, we again consider all possible conversions we could make, considering how many items of each type are available after day one. Again, we convert 0 items, then 1 item, then 2 items, and so on.
For each possible conversion on the second day, calculate the final amount we would have after the two days of conversions.
After exploring every single possible combination of conversions for both days, compare the final amounts from each combination.
Select the highest final amount that we found. This will be the maximum amount we can achieve after two days of conversions.

Code Implementation

def maximize_amount_after_two_days_brute_force(item_counts, conversion_rates):
    maximum_amount = 0

    # Iterate through all possible conversions on the first day
    for first_day_conversion_count in range(item_counts[0] + 1):
        remaining_item_count_after_first_conversion = [
            item_counts[0] - first_day_conversion_count,
            item_counts[1] + first_day_conversion_count * conversion_rates[0]
        ]

        # Iterate through all possible conversions on the second day
        for second_day_conversion_count in range(remaining_item_count_after_first_conversion[0] + 1):
            # Calculates result after a second conversion
            final_item_count_after_second_conversion = [
                remaining_item_count_after_first_conversion[0] - second_day_conversion_count,
                remaining_item_count_after_first_conversion[1] + second_day_conversion_count * conversion_rates[0]
            ]

            final_amount = final_item_count_after_second_conversion[1]

            # Keep track of the best final amount
            maximum_amount = max(maximum_amount, final_amount)

    return maximum_amount

Big(O) Analysis

Time Complexity

O(n^4) – The algorithm iterates through all possible conversions on day one. Assuming 'n' is the initial number of items of a type, this could be 'n' possibilities. For each of these, it iterates through all possible conversions on day two, which again is 'n' possibilities. Since we repeat this process for each item type, and assume there are two item types, the runtime will be O(n*n*n*n) = O(n^4) as we are exploring all combinations.

Space Complexity

O(1) – The brute force algorithm described explores all possible combinations of conversions. While it calculates intermediate amounts, it only needs to store a few variables to keep track of the current state of items after each conversion and the maximum amount found so far. The number of these variables does not depend on the number of items we start with. Therefore, the auxiliary space required remains constant regardless of the input size, resulting in O(1) space complexity.

Optimal Solution

Approach

The best way to tackle this problem is to figure out which conversion yields the most money each day and do it. The key is to repeatedly identify and exploit the most profitable conversion available at each step, focusing on immediate gains.

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

First, calculate how much money you would make by doing the first possible conversion on the first day.
Then, calculate how much money you would make by doing the second possible conversion on the first day.
Pick the conversion that gives you the most money on the first day and do that conversion.
After doing the first day conversion, update your starting amount to the new amount.
Repeat the same process for the second day. Calculate the gains from each available conversion using the updated starting amount.
Again, pick the conversion that gives you the most money on the second day and do that conversion.
At the end of the second day, the amount of money you have is the maximum possible amount.

Code Implementation

def maximize_amount(starting_amount, conversion_rates_day_one, conversion_rates_day_two):
   current_amount = starting_amount

   # Determine best conversion for day one
   best_conversion_day_one_amount = 0
   for rate in conversion_rates_day_one:
       potential_amount = current_amount * rate
       if potential_amount > best_conversion_day_one_amount:
           best_conversion_day_one_amount = potential_amount

   # Update the amount after day one's conversion
   current_amount = best_conversion_day_one_amount

   # Determine best conversion for day two
   best_conversion_day_two_amount = 0
   for rate in conversion_rates_day_two:
       potential_amount = current_amount * rate
       if potential_amount > best_conversion_day_two_amount:
           best_conversion_day_two_amount = potential_amount

   # Update the amount after day two's conversion
   current_amount = best_conversion_day_two_amount

   return current_amount

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates for two days. On each day, it examines each of the 'n' possible conversions to determine the most profitable one. Since this process is repeated a fixed number of times (two days), the dominant factor is the single loop through the 'n' conversions on each day. Thus, the total operations are proportional to 2 * n, which simplifies to O(n).

Space Complexity

O(1) – The algorithm's space complexity is constant because it only uses a few variables to store intermediate values and the updated amount of money. The number of conversions available is fixed (two), and the number of days is also fixed (two), therefore, the space needed does not scale with any input size, N. No auxiliary data structures like lists or hash maps are created to store intermediate results. Therefore, the algorithm uses a fixed amount of extra memory.

Edge Cases

Case	How to Handle
Empty list of conversion rates	Return 0 immediately, as no conversions can be made.
List of conversion rates contains only one element	Return the single element's value since no conversion possible.
Very large conversion rates causing integer overflow during multiplication	Use a data type with larger capacity like long or double to store intermediate results, or use modular arithmetic if appropriate for the problem.
Conversion rates are zero	Handle zero conversion rates correctly, which would result in a zero amount after conversions.
Negative conversion rates (if permitted by the problem description)	Account for negative values, potentially leading to minimizing the amount instead of maximizing.
All conversion rates are identical	The solution should still work correctly and perform the conversions as expected.
Input list is extremely large (e.g., millions of entries), potentially leading to performance issues.	Ensure algorithm has optimal time complexity, potentially using dynamic programming if applicable, and consider memory usage implications.
No profitable conversions are possible (all rates are less than or equal to 1)	The solution should still return the initial amount without performing any conversion.