How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Stripe.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Stripe during technical interviews.

Compute currency conversions with graph algorithms

Quick Overview

Stripe software-engineer onsite coding question: design data structures and algorithms to compute currency conversions from pairwise exchange rates. It tests modeling currencies as a weighted directed graph, chaining rates with BFS/DFS to answer queries (or -1 when unknown), supporting online updates and many queries efficiently, detecting contradictions and arbitrage in cycles, and computing all rates against a base via topological sort on a DAG, with time and space complexity analysis.

Compute currency conversions with graph algorithms

Company: Stripe

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

##### Question You are given a set of pairwise currency exchange relations such as `A:B = 1:1.5` and `B:C = 1:1.5`, meaning `1 A = 1.5 B` and `1 B = 1.5 C`. Design the data structures and algorithms to support the following: 1. **Store direct conversions.** Ingest the given pairwise rates into a structure you can query and update. 2. **Answer conversion queries.** Given a query like `A:C`, return the implied conversion rate by chaining the known rates, or `-1` (unknown) if no path connects the two currencies. 3. **Support many queries efficiently.** Explain how to serve a large number of queries without re-deriving every chain from scratch each time. 4. **Support online updates.** Allow inserting a new rate or updating an existing one, interleaved with queries, and keep query answers consistent. 5. **Detect and report contradictions.** When a newly inserted rate conflicts with the rate implied by existing relations (within a tolerance), detect and report the contradiction instead of silently corrupting the data. 6. **Topological computation for a DAG.** When the relation graph is a DAG with a chosen base currency, compute the relative rate of every currency against the base using a topological ordering. 7. **Cycles and arbitrage.** Explain how to handle cycles: a consistent cycle should multiply back to 1, while an inconsistent cycle (product != 1) signals a contradiction or an arbitrage opportunity. 8. **Map vs. graph reasoning.** Explain when a simple direct-lookup map suffices versus when a graph traversal or topological sort is actually required. 9. **Complexity and edge cases.** State the time and space complexity of each operation, and describe how you handle missing paths and contradictory inputs.

Quick Answer: Stripe software-engineer onsite coding question: design data structures and algorithms to compute currency conversions from pairwise exchange rates. It tests modeling currencies as a weighted directed graph, chaining rates with BFS/DFS to answer queries (or -1 when unknown), supporting online updates and many queries efficiently, detecting contradictions and arbitrage in cycles, and computing all rates against a base via topological sort on a DAG, with time and space complexity analysis.

You are given a set of pairwise currency exchange relations. Each relation `[A, B, r]` means `1 A = r B` (i.e. `A:B = 1:r`). The implied rate along a chain of relations is the product of the per-hop rates; the reciprocal edge `B -> A` carries weight `1/r`. Given the list of known rates and a list of queries, return the implied conversion rate for each query. For a query `[src, dst]`: - Return `1.0` if `src == dst` and `src` is a known currency. - Return the product of rates along any path from `src` to `dst` if one exists. - Return `-1.0` if either currency is unknown, or no path connects them. Model the currencies as a weighted directed graph (each currency a node; relation `A:B=1:r` an edge `A -> B` with weight `r` and reciprocal `B -> A` with weight `1/r`), then answer each query with a BFS/DFS that accumulates the product of edge weights. Example: rates `[['A','B',1.5], ['B','C',1.5]]`, query `['A','C']` returns `2.25` (1.5 * 1.5); `['C','A']` returns `0.4444...` (1/2.25); `['A','X']` returns `-1.0` (X unknown).

Constraints

Each rate is given as [src, dst, r] with r > 0, meaning 1 src = r dst.
1 <= number of currencies (V) <= 10^3.
Currency symbols are non-empty strings.
A query for an unknown currency, or between two currencies with no connecting path, returns -1.0.
A query [X, X] for a known currency X returns 1.0; for an unknown X it returns -1.0.
Inputs are assumed consistent (no contradictory cycles); any path between two currencies yields the same rate.

Examples

Input: ([['A', 'B', 1.5], ['B', 'C', 1.5]], [['A', 'C'], ['A', 'B'], ['C', 'A'], ['A', 'X']])

Expected Output: [2.25, 1.5, 0.4444444444444444, -1.0]

Explanation: A:C chains 1.5 * 1.5 = 2.25; A:B is the direct rate 1.5; C:A is the reciprocal 1/2.25 = 0.4444...; X is an unknown currency so A:X returns -1.0.

Input: ([['USD', 'EUR', 0.9], ['EUR', 'GBP', 0.85]], [['USD', 'GBP'], ['GBP', 'USD'], ['USD', 'USD']])

Expected Output: [0.765, 1.307189542483661, 1.0]

Explanation: USD:GBP = 0.9 * 0.85 = 0.765; GBP:USD is the reciprocal 1/0.765 = 1.30718...; USD:USD is the identity 1.0.

Input: ([], [['A', 'B']])

Expected Output: [-1.0]

Explanation: No rates were ingested, so neither A nor B exists in the graph and the query returns -1.0.

Input: ([['A', 'B', 2.0]], [['A', 'C'], ['C', 'A'], ['A', 'A']])

Expected Output: [-1.0, -1.0, 1.0]

Explanation: C is an unknown currency, so both A:C and C:A return -1.0. A:A is the identity 1.0 because A is a known currency.

Input: ([['X', 'Y', 4.0], ['Y', 'Z', 0.25]], [['X', 'Z'], ['Z', 'X']])

Expected Output: [1.0, 1.0]

Explanation: X:Z = 4.0 * 0.25 = 1.0, a consistent chain; Z:X is the reciprocal 1/1.0 = 1.0, confirming the cycle multiplies back to 1.

Hints

Model currencies as nodes and each rate A:B=1:r as a directed edge A->B with weight r. Always add the reciprocal edge B->A with weight 1/r so conversions work both directions.
The implied rate of a path is the PRODUCT of its edge weights, not the sum. Carry an accumulated product as you traverse.
Run a BFS or DFS from the query's source, accumulating the product; return the accumulator the moment you reach the destination.
Handle the edge cases first: if either currency was never seen, return -1.0; if source equals destination (and is known), return 1.0; if the search exhausts with no path, return -1.0.

Last updated: Jun 26, 2026

Loading coding console...

Quick Overview

Compute currency conversions with graph algorithms

Company: Stripe

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

Constraints

Each rate is given as [src, dst, r] with r > 0, meaning 1 src = r dst.
1 <= number of currencies (V) <= 10^3.
Currency symbols are non-empty strings.
A query for an unknown currency, or between two currencies with no connecting path, returns -1.0.
A query [X, X] for a known currency X returns 1.0; for an unknown X it returns -1.0.
Inputs are assumed consistent (no contradictory cycles); any path between two currencies yields the same rate.

Examples

Input: ([['A', 'B', 1.5], ['B', 'C', 1.5]], [['A', 'C'], ['A', 'B'], ['C', 'A'], ['A', 'X']])

Expected Output: [2.25, 1.5, 0.4444444444444444, -1.0]

Explanation: A:C chains 1.5 * 1.5 = 2.25; A:B is the direct rate 1.5; C:A is the reciprocal 1/2.25 = 0.4444...; X is an unknown currency so A:X returns -1.0.

Input: ([['USD', 'EUR', 0.9], ['EUR', 'GBP', 0.85]], [['USD', 'GBP'], ['GBP', 'USD'], ['USD', 'USD']])

Expected Output: [0.765, 1.307189542483661, 1.0]

Explanation: USD:GBP = 0.9 * 0.85 = 0.765; GBP:USD is the reciprocal 1/0.765 = 1.30718...; USD:USD is the identity 1.0.

Input: ([], [['A', 'B']])

Expected Output: [-1.0]

Explanation: No rates were ingested, so neither A nor B exists in the graph and the query returns -1.0.

Input: ([['A', 'B', 2.0]], [['A', 'C'], ['C', 'A'], ['A', 'A']])

Expected Output: [-1.0, -1.0, 1.0]

Explanation: C is an unknown currency, so both A:C and C:A return -1.0. A:A is the identity 1.0 because A is a known currency.

Input: ([['X', 'Y', 4.0], ['Y', 'Z', 0.25]], [['X', 'Z'], ['Z', 'X']])

Expected Output: [1.0, 1.0]

Explanation: X:Z = 4.0 * 0.25 = 1.0, a consistent chain; Z:X is the reciprocal 1/1.0 = 1.0, confirming the cycle multiplies back to 1.

Hints

Model currencies as nodes and each rate A:B=1:r as a directed edge A->B with weight r. Always add the reciprocal edge B->A with weight 1/r so conversions work both directions.
The implied rate of a path is the PRODUCT of its edge weights, not the sum. Carry an accumulated product as you traverse.
Run a BFS or DFS from the query's source, accumulating the product; return the accumulator the moment you reach the destination.
Handle the edge cases first: if either currency was never seen, return -1.0; if source equals destination (and is known), return 1.0; if the search exhausts with no path, return -1.0.

Last updated: Jun 26, 2026

Loading coding console...