返回题库

外汇货币转换器

Fx Currency Converter

专题
General / 综合
难度
L2
来源
MyntBit

题目详情

在外汇市场中，货币以对的形式交易，缺失的直接汇率通常通过美元等中间货币进行三角套算。构建健壮的实时定价系统需要高效处理这些隐含汇率计算。

任务：实现一个外汇转换器，支持通过任意中间货币的三角套算。

英文原题

In foreign exchange (FX) markets, currencies are traded in pairs, and missing direct exchange rates are often triangulated through intermediate currencies like the US Dollar (USD). Building robust pricing graphs to compute these cross rates is essential for accurate cross-currency pricing and identifying arbitrage opportunities.
Task
Implement an FXConverter class that calculates currency conversions given a set of spot exchange rates.
The constructor receives historical rates as three arrays:

解析

问题分析

外汇市场中的货币对交易需要处理缺失的直接汇率。当 USD/EUR 和 USD/JPY 都有报价但 EUR/JPY 没有直接报价时，需要通过美元三角套算得出隐含汇率。核心是图论中的最短路径问题——以货币为节点、汇率为边权构建有向图。

解决方案

class FXConverter {
    std::unordered_map<std::string, 
        std::unordered_map<std::string, double>> rates_;
public:
    void addRate(const std::string& base, const std::string& quote, double rate) {
        rates_[base][quote] = rate;
        rates_[quote][base] = 1.0 / rate;  // 添加反向边
    }
    
    double convert(const std::string& from, const std::string& to, double amount) {
        if (from == to) return amount;
        // BFS/DFS 寻找套算路径，或 Floyd-Warshall 预处理所有货币对
        auto it = rates_[from].find(to);
        if (it != rates_[from].end()) return amount * it->second;
        
        // 三角套算：尝试通过中间货币
        for (auto& [intermediate, rate1] : rates_[from]) {
            auto it2 = rates_[intermediate].find(to);
            if (it2 != rates_[intermediate].end()) {
                return amount * rate1 * it2->second;
            }
        }
        throw std::runtime_error("No conversion path found");
    }
};

关键考虑

  1. 套算路径长度：实际系统中最多支持 3-4 步套算。路径越长，累积误差越大。
  2. 买卖价差：买入价和卖出价不同，转换方向影响结果。应使用对客户不利的方向。
  3. 更新频率：汇率每秒变化多次，需支持实时更新和缓存失效。
  4. 时间复杂度：预处理 Floyd-Warshall O(V³)；单次转换 O(1)；三角套算 O(V)。

英文解析

Analysis

FX market currency pair trading must handle missing direct rates. When USD/EUR and USD/JPY are both quoted but EUR/JPY lacks a direct quote, the implied rate must be derived through USD triangular arbitrage. The core is a shortest-path graph problem — constructing a directed graph with currencies as nodes and exchange rates as edge weights.

Solution

class FXConverter {
    std::unordered_map<std::string, 
        std::unordered_map<std::string, double>> rates_;
public:
    void addRate(const std::string& base, const std::string& quote, double rate) {
        rates_[base][quote] = rate;
        rates_[quote][base] = 1.0 / rate;  // add reverse edge
    }
    
    double convert(const std::string& from, const std::string& to, double amount) {
        if (from == to) return amount;
        auto it = rates_[from].find(to);
        if (it != rates_[from].end()) return amount * it->second;
        
        // Triangular arbitrage: try via intermediate currency
        for (auto& [intermediate, rate1] : rates_[from]) {
            auto it2 = rates_[intermediate].find(to);
            if (it2 != rates_[intermediate].end()) {
                return amount * rate1 * it2->second;
            }
        }
        throw std::runtime_error("No conversion path found");
    }
};

Complexity & Edge Cases

  • Time complexity: O(1) for direct rate lookup; O(N) for cross-rate through N intermediaries
  • Space complexity: O(C^2) for C currencies in full rate matrix
  • Edge cases: (1) Triangular arbitrage: rate inconsistencies across currency pairs. (2) Missing rate for exotic currency pairs requires path computation. (3) Rate staleness: cached rates older than threshold produce incorrect conversions.

Key Considerations

  1. Cross-rate path length: Production systems support at most 3-4 step cross-rates. Longer paths accumulate greater error.
  2. Bid-ask spread: Buy and sell rates differ; conversion direction affects the result. Use the unfavorable direction for the client.
  3. Update frequency: Rates change multiple times per second; real-time updates and cache invalidation are required.
  4. Time complexity: Floyd-Warshall preprocessing O(V\u00b3); single conversion O(1); triangular lookup O(V).