Compute currency conversions with graph algorithms

Q: Compute currency conversions with graph algorithms

This question evaluates skills in graph modeling, algorithm design, data structure selection, dynamic updates, and consistency checking for weighted relations, focusing on computing implied conversion rates, detecting contradictory inputs, and reasoning about cycles and arbitrage.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Given a set of 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 algorithms and data structures to: (

answer queries like 'A:C' by returning the implied conversion rate, or -1 if unknown; (
support online updates by inserting or updating a rate and handling multiple queries efficiently; (
detect and report contradictions when a new rate conflicts with implied rates; and (
when the relation graph is a DAG, compute consistent relative rates for all nodes using a topological ordering and explain how to handle cycles and potential arbitrage. Analyze time and space complexity.

Compute currency conversions with graph algorithms

Overview

Comments (0)