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.