Goldman Sachs Interview Question
Software Engineer / DevelopersCountry: Singapore
Interview Type: In-Person
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Scanner;
public class CurrencyConvert {
public static int getMinimum(ArrayList<Integer> unVisited,float []weight){
float minimum = Float.MAX_VALUE;
int position =-1;
for(int i:unVisited){
if(weight[i]<minimum){
minimum=weight[i];
position =i;
}
}
return position;
}
public static float myFunction(HashMap<String,Integer> myHashMap,float[][] adMatrix,String source,String destination,int amount){
ArrayList<Integer> unVisted = new ArrayList<Integer>();
for(int i=0;i<myHashMap.size();i++){
unVisted.add(i);
}
ArrayList<Integer> visited = new ArrayList<Integer>();
float weight[] = new float[myHashMap.size()];
int sourceIndex= myHashMap.get(source);
for(int i=0;i<weight.length;i++){
weight[i]=Integer.MAX_VALUE;
}
weight[sourceIndex]=1;
while(!unVisted.isEmpty()){
int minimumIndex = getMinimum(unVisted,weight);
for(int i=0;i<adMatrix.length;i++){
if(adMatrix[minimumIndex][i]!=0 && weight[minimumIndex]*adMatrix[minimumIndex][i]<weight[i] && unVisted.contains(i)){
weight[i]= weight[minimumIndex]*adMatrix[minimumIndex][i];
}
}
int index = unVisted.indexOf(minimumIndex);
unVisted.remove(index);
}
for(int i=0;i<weight.length;i++){
System.out.println(weight[i]);
}
return weight[myHashMap.get(destination)]*amount;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String nodes ="EUR,USD,GBP,AUD,JPY,INR";
String [] newlength = nodes.split(",");
float [][] adMatrix = new float[newlength.length][newlength.length];
HashMap<String,Integer> myHashMap= new HashMap<>();
for(int i=0;i<newlength.length;i++){
myHashMap.put(newlength[i],i);
}
List<String> graph = new ArrayList<>();
String a = "EUR/USD=1.2";
String b = "USD/GBP=0.75";
String c = "GBP/AUD=1.7";
String d = "AUD/JPY=90";
String e = "GBP/JPY=150";
String f = "JPY/INR=0.6";
graph.add(a);
graph.add(b);
graph.add(c);
graph.add(d);
graph.add(e);
graph.add(f);
for(int i=0;i<graph.size();i++){
String line = graph.get(i);
String[] equaldivide = line.split("=");
String[] curr = equaldivide[0].split("/");
adMatrix[myHashMap.get(curr[0])][myHashMap.get(curr[1])] = Float.parseFloat(equaldivide[1]);
adMatrix[myHashMap.get(curr[1])][myHashMap.get(curr[0])] = 1/Float.parseFloat(equaldivide[1]);
}
String source ="EUR";
String destination ="INR";
System.out.println(myFunction(myHashMap,adMatrix,source,destination,100));
}
}
package test;
import java.util.*;
public class CurrencyConvertor
{
private Map<String, Map<String, Double>> mapping = new HashMap<String, Map<String, Double>>();
private boolean bInit = false;
private boolean bFound = false;
double convert(String src, double amount, String dst) throws Exception {
if (src.equals(dst)) return amount;
if (!bInit) {
init();
bInit = true;
}
bFound = false;
if (mapping.get(src) == null) {
throw new Exception("Invalid conversion");
}
List<String> visited = new ArrayList<String>();
visited.add(src);
double d1 = getRate(visited, src, dst, 1);
if (bFound)
return d1 * amount;
throw new Exception("No mapping invalid conversion");
}
private double getRate(List<String> visited, String src, String dst, double rate) throws Exception {
if (bFound == true) {
return rate;
}
if (mapping.get(src).get(dst) != null) {
bFound = true;
return rate*mapping.get(src).get(dst);
}
double origRate = rate;
for (String sInt : mapping.get(src).keySet()) {
if (visited.contains(sInt)) {
continue;
}
visited.add(sInt);
rate = getRate(visited, sInt, dst, rate*mapping.get(src).get(sInt));
if (bFound == true) {
return rate;
}
visited.remove(sInt);
rate = origRate;
}
return origRate;
}
private void init() {
// Invalid case data, EUR to INR
insert("EUR", "USD", 1.2);
insert("USD", "EUR", 0.75);
insert("YEN", "INR", 1.2);
insert("INR", "YEN", 0.75);
// Valid case data, EUR to INR
// insert("EUR", "USD", 1.2);
// insert("USD", "GBP", 0.75);
// insert("GBP", "AUD", 1.7);
// insert("AUD", "JPY", 90);
// insert("GBP", "JPY", 150);
// insert("JPY", "INR", 0.6);
//
// insert("USD", "EUR", 1.0/1.2);
// insert("GBP", "USD", 1.0/0.75);
// insert("AUD", "GBP", 1.0/1.7);
// insert("JPY", "AUD", 1.0/90);
// insert("JPY", "GBP", 1.0/150);
// insert("INR", "JPY", 1.0/0.6);
}
private void insert(String src, String dst, double rate) {
if (mapping.get(src) == null) {
Map<String, Double> map = new HashMap<String, Double>();
map.put(dst, rate);
mapping.put(src, map);
}
else if (mapping.get(src).get(dst) == null) {
mapping.get(src).put(dst, rate);
}
}
public static void main(String args[])
{
try {
double d = new CurrencyConvertor().convert("EUR", 100, "INR");
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
<p><code><pre class="language-java">
package test;
import java.util.*;
public class CurrencyConvertor
{
private Map<String, Map<String, Double>> mapping = new HashMap<String, Map<String, Double>>();
private boolean bInit = false;
private boolean bFound = false;
double convert(String src, double amount, String dst) throws Exception {
if (src.equals(dst)) return amount;
if (!bInit) {
init();
bInit = true;
}
bFound = false;
if (mapping.get(src) == null) {
throw new Exception("Invalid conversion");
}
List<String> visited = new ArrayList<String>();
visited.add(src);
double d1 = getRate(visited, src, dst, 1);
if (bFound)
return d1 * amount;
throw new Exception("No mapping invalid conversion");
}
private double getRate(List<String> visited, String src, String dst, double rate) throws Exception {
if (bFound == true) {
return rate;
}
if (mapping.get(src).get(dst) != null) {
bFound = true;
return rate*mapping.get(src).get(dst);
}
double origRate = rate;
for (String sInt : mapping.get(src).keySet()) {
if (visited.contains(sInt)) {
continue;
}
visited.add(sInt);
rate = getRate(visited, sInt, dst, rate*mapping.get(src).get(sInt));
if (bFound == true) {
return rate;
}
visited.remove(sInt);
rate = origRate;
}
return origRate;
}
private void init() {
// Invalid case data, EUR to INR
insert("EUR", "USD", 1.2);
insert("USD", "EUR", 0.75);
insert("YEN", "INR", 1.2);
insert("INR", "YEN", 0.75);
// Valid case data, EUR to INR
// insert("EUR", "USD", 1.2);
// insert("USD", "GBP", 0.75);
// insert("GBP", "AUD", 1.7);
// insert("AUD", "JPY", 90);
// insert("GBP", "JPY", 150);
// insert("JPY", "INR", 0.6);
//
// insert("USD", "EUR", 1.0/1.2);
// insert("GBP", "USD", 1.0/0.75);
// insert("AUD", "GBP", 1.0/1.7);
// insert("JPY", "AUD", 1.0/90);
// insert("JPY", "GBP", 1.0/150);
// insert("INR", "JPY", 1.0/0.6);
}
private void insert(String src, String dst, double rate) {
if (mapping.get(src) == null) {
Map<String, Double> map = new HashMap<String, Double>();
map.put(dst, rate);
mapping.put(src, map);
}
else if (mapping.get(src).get(dst) == null) {
mapping.get(src).put(dst, rate);
}
}
public static void main(String args[])
{
try {
double d = new CurrencyConvertor().convert("EUR", 100, "INR");
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
</pre></code></p>
package test;
import java.util.*;
public class CurrencyConvertor
{
private Map<String, Map<String, Double>> mapping = new HashMap<String, Map<String, Double>>();
private boolean bInit = false;
private boolean bFound = false;
double convert(String src, double amount, String dst) throws Exception {
if (src.equals(dst)) return amount;
if (!bInit) {
init();
bInit = true;
}
bFound = false;
if (mapping.get(src) == null) {
throw new Exception("Invalid conversion");
}
List<String> visited = new ArrayList<String>();
visited.add(src);
double d1 = getRate(visited, src, dst, 1);
if (bFound)
return d1 * amount;
throw new Exception("No mapping invalid conversion");
}
private double getRate(List<String> visited, String src, String dst, double rate) throws Exception {
if (bFound == true) {
return rate;
}
if (mapping.get(src).get(dst) != null) {
bFound = true;
return rate*mapping.get(src).get(dst);
}
double origRate = rate;
for (String sInt : mapping.get(src).keySet()) {
if (visited.contains(sInt)) {
continue;
}
visited.add(sInt);
rate = getRate(visited, sInt, dst, rate*mapping.get(src).get(sInt));
if (bFound == true) {
return rate;
}
visited.remove(sInt);
rate = origRate;
}
return origRate;
}
private void init() {
// Invalid case data, EUR to INR
insert("EUR", "USD", 1.2);
insert("USD", "EUR", 0.75);
insert("YEN", "INR", 1.2);
insert("INR", "YEN", 0.75);
// Valid case data, EUR to INR
// insert("EUR", "USD", 1.2);
// insert("USD", "GBP", 0.75);
// insert("GBP", "AUD", 1.7);
// insert("AUD", "JPY", 90);
// insert("GBP", "JPY", 150);
// insert("JPY", "INR", 0.6);
//
// insert("USD", "EUR", 1.0/1.2);
// insert("GBP", "USD", 1.0/0.75);
// insert("AUD", "GBP", 1.0/1.7);
// insert("JPY", "AUD", 1.0/90);
// insert("JPY", "GBP", 1.0/150);
// insert("INR", "JPY", 1.0/0.6);
}
private void insert(String src, String dst, double rate) {
if (mapping.get(src) == null) {
Map<String, Double> map = new HashMap<String, Double>();
map.put(dst, rate);
mapping.put(src, map);
}
else if (mapping.get(src).get(dst) == null) {
mapping.get(src).put(dst, rate);
}
}
public static void main(String args[])
{
try {
double d = new CurrencyConvertor().convert("EUR", 100, "INR");
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
Other simple approach with custom DFS in map of map
package test;
import java.util.*;
public class CurrencyConvertor
{
private Map<String, Map<String, Double>> mapping = new HashMap<String, Map<String, Double>>();
private boolean bInit = false;
private boolean bFound = false;
double convert(String src, double amount, String dst) throws Exception {
if (src.equals(dst)) return amount;
if (!bInit) {
init();
bInit = true;
}
bFound = false;
if (mapping.get(src) == null) {
throw new Exception("Invalid conversion");
}
List<String> visited = new ArrayList<String>();
visited.add(src);
double d1 = getRate(visited, src, dst, 1);
if (bFound)
return d1 * amount;
throw new Exception("No mapping invalid conversion");
}
private double getRate(List<String> visited, String src, String dst, double rate) throws Exception {
if (bFound == true) {
return rate;
}
if (mapping.get(src).get(dst) != null) {
bFound = true;
return rate*mapping.get(src).get(dst);
}
double origRate = rate;
for (String sInt : mapping.get(src).keySet()) {
if (visited.contains(sInt)) {
continue;
}
visited.add(sInt);
rate = getRate(visited, sInt, dst, rate*mapping.get(src).get(sInt));
if (bFound == true) {
return rate;
}
visited.remove(sInt);
rate = origRate;
}
return origRate;
}
private void init() {
// Invalid case data, EUR to INR
insert("EUR", "USD", 1.2);
insert("USD", "EUR", 0.75);
insert("YEN", "INR", 1.2);
insert("INR", "YEN", 0.75);
// Valid case data, EUR to INR
// insert("EUR", "USD", 1.2);
// insert("USD", "GBP", 0.75);
// insert("GBP", "AUD", 1.7);
// insert("AUD", "JPY", 90);
// insert("GBP", "JPY", 150);
// insert("JPY", "INR", 0.6);
//
// insert("USD", "EUR", 1.0/1.2);
// insert("GBP", "USD", 1.0/0.75);
// insert("AUD", "GBP", 1.0/1.7);
// insert("JPY", "AUD", 1.0/90);
// insert("JPY", "GBP", 1.0/150);
// insert("INR", "JPY", 1.0/0.6);
}
private void insert(String src, String dst, double rate) {
if (mapping.get(src) == null) {
Map<String, Double> map = new HashMap<String, Double>();
map.put(dst, rate);
mapping.put(src, map);
}
else if (mapping.get(src).get(dst) == null) {
mapping.get(src).put(dst, rate);
}
}
public static void main(String args[])
{
try {
double d = new CurrencyConvertor().convert("EUR", 100, "INR");
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
package test;
import java.util.*;
public class CurrencyConvertor
{
private Map<String, Map<String, Double>> mapping = new HashMap<String, Map<String, Double>>();
private boolean bInit = false;
private boolean bFound = false;
double convert(String src, double amount, String dst) throws Exception {
if (src.equals(dst)) return amount;
if (!bInit) {
init();
bInit = true;
}
bFound = false;
if (mapping.get(src) == null) {
throw new Exception("Invalid conversion");
}
List<String> visited = new ArrayList<String>();
visited.add(src);
double d1 = getRate(visited, src, dst, 1);
if (bFound)
return d1 * amount;
throw new Exception("No mapping invalid conversion");
}
private double getRate(List<String> visited, String src, String dst, double rate) throws Exception {
if (bFound == true) {
return rate;
}
if (mapping.get(src).get(dst) != null) {
bFound = true;
return rate*mapping.get(src).get(dst);
}
double origRate = rate;
for (String sInt : mapping.get(src).keySet()) {
if (visited.contains(sInt)) {
continue;
}
visited.add(sInt);
rate = getRate(visited, sInt, dst, rate*mapping.get(src).get(sInt));
if (bFound == true) {
return rate;
}
visited.remove(sInt);
rate = origRate;
}
return origRate;
}
private void init() {
// Invalid case data, EUR to INR
insert("EUR", "USD", 1.2);
insert("USD", "EUR", 0.75);
insert("YEN", "INR", 1.2);
insert("INR", "YEN", 0.75);
// Valid case data, EUR to INR
// insert("EUR", "USD", 1.2);
// insert("USD", "GBP", 0.75);
// insert("GBP", "AUD", 1.7);
// insert("AUD", "JPY", 90);
// insert("GBP", "JPY", 150);
// insert("JPY", "INR", 0.6);
//
// insert("USD", "EUR", 1.0/1.2);
// insert("GBP", "USD", 1.0/0.75);
// insert("AUD", "GBP", 1.0/1.7);
// insert("JPY", "AUD", 1.0/90);
// insert("JPY", "GBP", 1.0/150);
// insert("INR", "JPY", 1.0/0.6);
}
private void insert(String src, String dst, double rate) {
if (mapping.get(src) == null) {
Map<String, Double> map = new HashMap<String, Double>();
map.put(dst, rate);
mapping.put(src, map);
}
else if (mapping.get(src).get(dst) == null) {
mapping.get(src).put(dst, rate);
}
}
public static void main(String args[])
{
try {
double d = new CurrencyConvertor().convert("EUR", 100, "INR");
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
package test;
import java.util.*;
public class CurrencyConvertor
{
private Map<String, Map<String, Double>> mapping = new HashMap<String, Map<String, Double>>();
private boolean bInit = false;
private boolean bFound = false;
double convert(String src, double amount, String dst) throws Exception {
if (src.equals(dst)) return amount;
if (!bInit) {
init();
bInit = true;
}
bFound = false;
if (mapping.get(src) == null) {
throw new Exception("Invalid conversion");
}
List<String> visited = new ArrayList<String>();
visited.add(src);
double d1 = getRate(visited, src, dst, 1);
if (bFound)
return d1 * amount;
throw new Exception("No mapping invalid conversion");
}
private double getRate(List<String> visited, String src, String dst, double rate) throws Exception {
if (bFound == true) {
return rate;
}
if (mapping.get(src).get(dst) != null) {
bFound = true;
return rate*mapping.get(src).get(dst);
}
double origRate = rate;
for (String sInt : mapping.get(src).keySet()) {
if (visited.contains(sInt)) {
continue;
}
visited.add(sInt);
rate = getRate(visited, sInt, dst, rate*mapping.get(src).get(sInt));
if (bFound == true) {
return rate;
}
visited.remove(sInt);
rate = origRate;
}
return origRate;
}
private void init() {
// Invalid case data, EUR to INR
insert("EUR", "USD", 1.2);
insert("USD", "EUR", 0.75);
insert("YEN", "INR", 1.2);
insert("INR", "YEN", 0.75);
// Valid case data, EUR to INR
// insert("EUR", "USD", 1.2);
// insert("USD", "GBP", 0.75);
// insert("GBP", "AUD", 1.7);
// insert("AUD", "JPY", 90);
// insert("GBP", "JPY", 150);
// insert("JPY", "INR", 0.6);
//
// insert("USD", "EUR", 1.0/1.2);
// insert("GBP", "USD", 1.0/0.75);
// insert("AUD", "GBP", 1.0/1.7);
// insert("JPY", "AUD", 1.0/90);
// insert("JPY", "GBP", 1.0/150);
// insert("INR", "JPY", 1.0/0.6);
}
private void insert(String src, String dst, double rate) {
if (mapping.get(src) == null) {
Map<String, Double> map = new HashMap<String, Double>();
map.put(dst, rate);
mapping.put(src, map);
}
else if (mapping.get(src).get(dst) == null) {
mapping.get(src).put(dst, rate);
}
}
public static void main(String args[])
{
try {
double d = new CurrencyConvertor().convert("EUR", 100, "INR");
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
"package test;
import java.util.*;
public class CurrencyConvertor
{
private Map<String, Map<String, Double>> mapping = new HashMap<String, Map<String, Double>>();
private boolean bInit = false;
private boolean bFound = false;
double convert(String src, double amount, String dst) throws Exception {
if (src.equals(dst)) return amount;
if (!bInit) {
init();
bInit = true;
}
bFound = false;
if (mapping.get(src) == null) {
throw new Exception("Invalid conversion");
}
List<String> visited = new ArrayList<String>();
visited.add(src);
double d1 = getRate(visited, src, dst, 1);
if (bFound)
return d1 * amount;
throw new Exception("No mapping invalid conversion");
}
private double getRate(List<String> visited, String src, String dst, double rate) throws Exception {
if (bFound == true) {
return rate;
}
if (mapping.get(src).get(dst) != null) {
bFound = true;
return rate*mapping.get(src).get(dst);
}
double origRate = rate;
for (String sInt : mapping.get(src).keySet()) {
if (visited.contains(sInt)) {
continue;
}
visited.add(sInt);
rate = getRate(visited, sInt, dst, rate*mapping.get(src).get(sInt));
if (bFound == true) {
return rate;
}
visited.remove(sInt);
rate = origRate;
}
return origRate;
}
private void init() {
// Invalid case data, EUR to INR
insert("EUR", "USD", 1.2);
insert("USD", "EUR", 0.75);
insert("YEN", "INR", 1.2);
insert("INR", "YEN", 0.75);
// Valid case data, EUR to INR
// insert("EUR", "USD", 1.2);
// insert("USD", "GBP", 0.75);
// insert("GBP", "AUD", 1.7);
// insert("AUD", "JPY", 90);
// insert("GBP", "JPY", 150);
// insert("JPY", "INR", 0.6);
//
// insert("USD", "EUR", 1.0/1.2);
// insert("GBP", "USD", 1.0/0.75);
// insert("AUD", "GBP", 1.0/1.7);
// insert("JPY", "AUD", 1.0/90);
// insert("JPY", "GBP", 1.0/150);
// insert("INR", "JPY", 1.0/0.6);
}
private void insert(String src, String dst, double rate) {
if (mapping.get(src) == null) {
Map<String, Double> map = new HashMap<String, Double>();
map.put(dst, rate);
mapping.put(src, map);
}
else if (mapping.get(src).get(dst) == null) {
mapping.get(src).put(dst, rate);
}
}
public static void main(String args[])
{
try {
double d = new CurrencyConvertor().convert("EUR", 100, "INR");
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}"
A simple C++ solution (Can be further improved with edge cases). The java solutions above don't actually give the conversion with a MINIMUM number of steps. They just give the max value of the converstion irrespective of the number of conversions.
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <map>
using namespace std;
struct CurrencyNode {
string source;
double value;
// no need to use steps here but added anyways
int steps;
CurrencyNode(string src, double val, int s):source(src), value(val), steps(s){};
};
double convert (map<string, map<string, double> > mp, string src, double amount, string dest) {
if (mp[src].empty()) {
cout << "Invalid Conversion" << endl;
return -1;
}
queue<CurrencyNode> q;
q.push(CurrencyNode(src, amount, 0));
while (!q.empty()) {
CurrencyNode node = q.front();
q.pop();
// if the required currency is found then return the rate
if (mp[node.source].find(dest) != mp[node.source].end()) {
return node.value * mp[node.source][dest];
}
// else
for (auto it : mp[node.source]) {
q.push(CurrencyNode(it.first, it.second * node.value, node.steps + 1));
}
}
cout << "Conversion could not be done" << endl;
return -1;
}
void insertIntoMap (map<string, map<string, double> > &mp, string src, string dest, double value) {
mp[src][dest] = value;
}
int main () {
map<string, map<string, double> > mp;
insertIntoMap(mp, "EUR", "USD", 1.2);
insertIntoMap(mp, "USD", "GBP", 0.75);
insertIntoMap(mp, "GBP", "AUD", 1.7);
insertIntoMap(mp, "AUD", "YEN", 90);
insertIntoMap(mp, "GBP", "YEN", 150);
insertIntoMap(mp, "YEN", "PKR", 0.6);
cout << convert(mp, "EUR", 100, "PKR") << endl;
return 0;
}
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <map>
using namespace std;
struct CurrencyNode {
string source;
double value;
// no need to use steps here but added anyways
int steps;
CurrencyNode(string src, double val, int s):source(src), value(val), steps(s){};
};
double convert (map<string, map<string, double> > mp, string src, double amount, string dest) {
if (mp[src].empty()) {
cout << "Invalid Conversion" << endl;
return -1;
}
queue<CurrencyNode> q;
q.push(CurrencyNode(src, amount, 0));
while (!q.empty()) {
CurrencyNode node = q.front();
q.pop();
// if the required currency is found then return the rate
if (mp[node.source].find(dest) != mp[node.source].end()) {
return node.value * mp[node.source][dest];
}
// else
for (auto it : mp[node.source]) {
q.push(CurrencyNode(it.first, it.second * node.value, node.steps + 1));
}
}
cout << "Conversion could not be done" << endl;
return -1;
}
void insertIntoMap (map<string, map<string, double> > &mp, string src, string dest, double value) {
mp[src][dest] = value;
}
int main () {
map<string, map<string, double> > mp;
insertIntoMap(mp, "EUR", "USD", 1.2);
insertIntoMap(mp, "USD", "GBP", 0.75);
insertIntoMap(mp, "GBP", "AUD", 1.7);
insertIntoMap(mp, "AUD", "YEN", 90);
insertIntoMap(mp, "GBP", "YEN", 150);
insertIntoMap(mp, "YEN", "PKR", 0.6);
cout << convert(mp, "EUR", 100, "PKR") << endl;
return 0;
}
There is a problem with inconsistency conversion in the problem statement defined by the original post:
Given a list of currency exchange rates like this:
EUR/USD => 1.2
USD/GBP => 0.75
GBP/AUD => 1.7
AUD/JPY => 90
GBP/JPY => 150
JPY/INR => 0.6
The problem is between
this
GBP/AUD => 1.7
AUD/JPY => 90
and
this
GBP/JPY => 150
So when you test this particular test case, the last pair would overwrite the path created by the first two pairs. And the test case would not pass in most platforms.
There is a problem with inconsistency conversion in the problem statement defined by the original post:
Given a list of currency exchange rates like this:
EUR/USD => 1.2
USD/GBP => 0.75
GBP/AUD => 1.7
AUD/JPY => 90
GBP/JPY => 150
JPY/INR => 0.6
The problem is between
this
GBP/AUD => 1.7
AUD/JPY => 90
and
this
GBP/JPY => 150
So when you test this particular test case, the last pair would overwrite the path created by the first two pairs. And the test case would not pass in most platforms.
My idea is -
- mailchiranjib June 06, 20181. Convert the input to uni-cost graph
2. Find shortest path between two input odes and keep track of the conversation rate of the edges that are part of the shortest path.
3. Multiply the the rates with given amount