Question

Coinbase| Interview experiences | SDE | Set-1

Answer 1

1. Currency Exchange: a list of currency relationships with exchange values. (BTC - USD) find the best exchange rate from currency1 to currency2. (https://leetcode.com/discuss/interview-question/1335225/Find-best-exchange-rate-from-currency1-to-currency2)

 

There is no possiblility of arbitrage.

 

It's a really hard problem in my opinion for a 45-min interview! First you need to create a graph with the exchange rate as the edge weight. Whatever path that gives you the higher value when multiplying the edges is your solution. First you need to convert the problem to a shortest path problem. To do so:

 

• Instead of finding the value of E1 x E2 x E3 ... and find the path with max value, find the max value for
  log(E1 x E2 x E3 ...) = log(E1) + log(E2) + log(E3) + ...
• We are looking for the minimum value so we multiply each edge by -1. Now we are looking for a min value for
  -log(E1 x E2 x E3 ...) = -log(E1) - log(E2) - log(E3) - ....
• After making edges negative and take a logarithm we have a shortest path problem with negative edges. Dijkstra doesn't work so we need to apply Bellman-Ford algorithm.

1. Connect 4 game. Follow up: Optimize it so that we find the best colum to drop the coin.

 

System Design: Design a trading system

 

IC5 US