Goldman Sachs Interview Question for Software Engineer / Developers


Country: Singapore
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
1
of 1 vote

My idea is -
1. 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

- mailchiranjib June 06, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can think of weighted graph and finding shortest distance between 2 nodes.
Eg:
EUR---(1.2)---> USD ---(0.75)--->GBP---(1.7)--->AUD
| |(90)
|___(150)--->JPY-----(0.60)------>INR

- Nitin December 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It should be unicost graph, in my opinion, since the task is to minimize the number of intermediate conversions.

- itsfight May 20, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Just use dijsktra.

- Anonymous July 18, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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));
	}
}

- Nikhil Attri September 19, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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();
}
}

}

- mkag September 30, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

<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>

- mkag September 30, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();
}
}

}

- mkag September 30, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();
		}
    }
 
}

- mkag September 30, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();
		}
    }
 
}

- mkag September 30, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();
		}
    }

}

- mkag mkag September 30, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

"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();
		}
    }
 
}"

- mkag mkag September 30, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- DB February 16, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Lovely just a simple BFS !!!

- yozaam September 10, 2020 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;

}

- DB February 16, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- humbleGeek June 14, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- humbleGeek June 14, 2020 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More