Mastering Graph Traversal: My Challenging Uber Software Engineer Interview

Software Engineering
, ,
1

uber | Software Engineer | Interview Experience

Interview Date: Not specified
Result: Not specified
Difficulty: Not specified

Interview Process

The interview began with a discussion about my resume. The interviewer then asked high-frequency technical questions related to currency exchange. The main question involved implementing a CurrencyConverter class that calculates the best exchange rate between currencies based on given relationships and rates.

Technical Questions

  • Currency Exchange Problem:
    Given a list of currency relationships with exchange values (e.g., GBP → USD: 109.0), find the best exchange rate from one currency to another. The rates are bi-directional, meaning if the rate from A to B is r, the rate from B to A can be calculated as 1/r. The goal is to find the maximum achievable exchange rate along a valid exchange path. If conversion is not possible, return -1.
    • Implementation Details:
      • CurrencyConverter(String[] fromArr, String[] toArr, double[] rateArr) - Initializes the class with currency pairs and exchange rates.
      • getBestRate(String from, String to) - Returns the best exchange rate from one currency to another.
    • Constraints:
      • 1 ≤ fromArr.length, toArr.length, rateArr.length ≤ 1000
      • 0 < rateArr ≤ 103
      • All currency names consist of English letters and have a length between 1 and 10
    • Approach: Build a graph and use Depth-First Search (DFS) to find the maximum exchange rate along a valid path.

Tips & Insights

Discuss the optimal exchange rate calculation approach with the interviewer during the interview.