Software Engineer · Onsite · Coding

Uber — Software Engineer

Level: Unknown Level

Round: Onsite · Type: Coding · Difficulty: 7/10 · Duration: 60 min · Interviewer: Neutral

Topics: Graph Algorithms, Currency Exchange, Bidirectional Graphs, Maximum Conversion Rate

Location: Mountain View, CA

Interview date: 2026-01-20

Summary

I had a take-home assignment to implement a currency converter with a method to find the best exchange rate between two currencies, considering bidirectional exchange rates and intermediate conversions. The task involved handling invalid currency pairs and cases where no conversion path exists.

Details

Currency Exchange – Maximum Conversion Rate

Problem Overview

You are given a collection of currency pairs along with their exchange rates (for example, GBP → USD = 109.0). Using this information, determine the best possible exchange rate from a source currency (from) to a target currency (to).

---

Assumptions & Rules

• Exchange rates are bidirectional If the rate from currency A to B is r, then the rate from B to A is 1 / r.
• Multiple conversions are allowed You may convert through intermediate currencies. The final exchange rate is calculated by multiplying all rates along the chosen path.
• Objective Find the maximum achievable exchange value from from to to using any valid conversion path.
• Invalid cases
  • If either currency does not exist, or
  • If no conversion path connects from to to, return -1.

---

Required Implementation

Implement a class named CurrencyConverter with the following methods:

java CurrencyConverter(String[] fromArr, String[] toArr, double[] rateArr)

• Initializes the converter using currency pairs and their exchange rates.

java double getBestRate(String from, String to)

• Returns the maximum exchange rate obtainable when converting from from currency to to currency.
• Returns -1 if the conversion is not possible.

---

Constraints

• 1 ≤ fromArr.length = toArr.length = rateArr.length ≤ 1000
• 0 < rateArr[i] ≤ 10^3
• Currency names:
  • Consist only of English letters
  • Length is between 1 and 10 characters

---

Example

Input

`text ["CurrencyConverter", "getBestRate", "getBestRate", "getBestRate", "getBestRate"]

[ [["GBP", "USD", "USD", "USD", "CNY"], ["JPY", "JPY", "GBP", "CAD", "EUR"], [155.0, 112.0, 0.9, 1.3, 0.141]], ["USD", "JPY"], ["JPY", "GBP"], ["XYZ", "GBP"], ["CNY", "CAD"] ] `

Output

text [null, 139.5, 0.00803, -1.0, -1.0]

---

Explanation

• getBestRate("USD", "JPY") The optimal path is USD → GBP → JPY

  (1 / 0.9) × 155 = 139.5

  This is better than the direct rate USD → JPY = 112.

• getBestRate("JPY", "GBP") Best path is JPY → USD → GBP, resulting in 0.00803.

• getBestRate("XYZ", "GBP") Returns -1 because currency XYZ does not exist.

• getBestRate("CNY", "CAD") Returns -1 because no conversion path connects the two currencies.

Proposed Solution

` from typing import List, Optional

class Pair: def init(self, to: str, rate: float): self.to = to self.rate = rate

class CurrencyConverter: def init(self, fromArr: List[str], toArr: List[str], rateArr: List[float]): self.map = {} for i in range(len(fromArr)): fromCurrency = fromArr[i] toCurrency = toArr[i] rate = rateArr[i]

        if fromCurrency not in self.map:
            self.map[fromCurrency] = []
        if toCurrency not in self.map:
            self.map[toCurrency] = []

        self.map[fromCurrency].append(Pair(toCurrency, rate))
        self.map[toCurrency].append(Pair(fromCurrency, 1 / rate))

def getBestRate(self, from_: str, to: str) -> float:
    if from_ not in self.map or to not in self.map:
        return -1  # If either currency is not present

    visited = set()
    return self.dfs(from_, to, 1, visited)

def dfs(self, current: str, target: str, rate: float, visited: set) -> float:
    if current == target:
        return rate

    visited.add(current)
    maxRate = -1

    if current in self.map:
        for pair in self.map[current]:
            if pair.to in visited:
                continue

            result = self.dfs(pair.to, target, rate * pair.rate, visited)
            maxRate = max(maxRate, result)

    visited.remove(current)
    return maxRate

`