Stripe 电面题目总结 | 汇率计算算法设计 面试辅导 编程面试

问题描述

给定一个包含货币汇率信息的字符串，你需要创建一个方法来获取两种货币之间的汇率。外汇可以双向兑换。

---

基本要求

实现一个 fx 函数，输入两种货币的代码（例如 "USD", "CAD"），返回它们之间的直接汇率。

---

扩展要求 1

fx 函数需要支持最多一次中间货币兑换。例如：

• fx("USD", "JPY") 可以通过 fx("USD", "CAD") * fx("CAD", "JPY") 计算得到。

---

扩展要求 2

fx 函数需要找到最佳汇率（即最大值），允许最多一次中间货币兑换。例如：

• fx("USD", "JPY") 需要比较 fx("USD", "CAD") * fx("CAD", "JPY") 和 fx("USD", "GBP") * fx("GBP", "JPY")，返回较大的那个。

---

核心考点

• 数据结构： 如何表示和存储汇率信息（例如，图）。
• 算法： 如何高效地查找直接汇率和通过中间货币的汇率（例如，图的遍历）。
• 优化： 如何找到最佳汇率（例如，遍历所有可能的中间货币）。

---

解题思路

1. 解析输入字符串： 将汇率信息解析成合适的数据结构，例如使用图来表示货币之间的关系和汇率。
2. 实现 fx 函数：
   • 基本要求： 直接在图中查找两种货币之间的边，返回汇率。
   • 扩展要求 1 & 2： 遍历所有可能的中间货币，计算通过中间货币的汇率，并记录最佳汇率。

---

Java 代码示例

import java.util.*;

class CurrencyExchange {
    private Map<String, Map<String, Double>> graph;

    public CurrencyExchange(String exchangeString) {
        this.graph = buildGraph(exchangeString);
    }

    private Map<String, Map<String, Double>> buildGraph(String exchangeString) {
        Map<String, Map<String, Double>> graph = new HashMap<>();
        // 假设 exchangeString 格式为: "USD CAD 1.40; CAD JPY 100; ..."
        String[] pairs = exchangeString.split(";");
        for (String pair : pairs) {
            String[] parts = pair.trim().split(" ");
            String from = parts[0];
            String to = parts[1];
            double rate = Double.parseDouble(parts[2]);

            graph.putIfAbsent(from, new HashMap<>());
            graph.putIfAbsent(to, new HashMap<>());
            graph.get(from).put(to, rate);
            graph.get(to).put(from, 1.0 / rate); // 添加反向汇率
        }
        return graph;
    }

    public Double fx(String fromCurrency, String toCurrency) {
        // 直接汇率
        if (graph.get(fromCurrency).containsKey(toCurrency)) {
            return graph.get(fromCurrency).get(toCurrency);
        }

        // 间接汇率
        double bestRate = -1;
        for (String intermediate : graph.get(fromCurrency).keySet()) {
            if (graph.get(intermediate).containsKey(toCurrency)) {
                double rate = graph.get(fromCurrency).get(intermediate) * graph.get(intermediate).get(toCurrency);
                bestRate = Math.max(bestRate, rate);
            }
        }
        return bestRate > 0 ? bestRate : null;
    }
}