Goldman Sachs Interview Question
AssociatesCountry: India
Interview Type: Phone Interview
If we have the sample data as given above -
Find the unique variables in the data and we can make a table like this below
A B C D
-5 5 0 0
0 -8 8 0
0 0 -9 9
-10 0 0 10
0 11 0 -11
12 0 -12 0
Sum-3 8 -13 8
So finally we can take out the -3 and -13 Rs from A and C and add 8 and 8 into A and D
So, the total number of transactions = 4.
Also, we can verify the calculation by checking the Total of all the sum which should be zero.
Sum of A+B+C+D=0
-3+8-13+8=0
Define number of total parties participating in transaction as variables.In this case 4(A,B,C,D).
for every input example C->A = 3 transaction increment increment first variable and decrement second variable by R.H.S qty i.e 3 in this case. So we have C=3 and A =-3 .
perform same for all the transaction.
finally we have something as
A= -3
B=8
C=-13
D=8
Start transaction with most nagitive to most positive
C->D = 8 ; after this (A =-3;B=8;C=-5;D=8) take most negative and most positive among these i.e C,B
C->B =5 ; after this (A=-3; B=3)
A->B = 3
completed in 3 transactions.
I have used the Java and Maps to solve this problem. Hope this helps
/**
*
*/
package practice;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
/**
*
* This class is to minimise the transaction between the all the players
* e.g.
A->B = Rs. 5
B->C = Rs. 8
C->D = Rs. 9
A->D = Rs. 10
D->B = Rs. 11
C->A = Rs. 12
We need to minimise the transaction in the above
*
*/
public class MinimiseTransaction {
/**
* @param args
*/
private static String transactions[][] = {
{"A","B","5"},
{"B","C","8"},
{"C","D","9"},
{"A","D","10"},
{"D","B","11"},
{"C","A","12"},
//{"D","A","3"}
};
static Map<String, Integer> minimalTransactionMap = new HashMap<String, Integer>();
public static void main(String[] args) {
// TODO Auto-generated method stub
Map<String, Integer> players = new HashMap<String, Integer>();
// From the above transaction first find the list of players and also find whether they are going to gain or loose
for(String[] transaction : transactions){
// The 0th element of the array will be a gainer
if(players.get(transaction[0])!=null){
players.put(transaction[0], players.get(transaction[0]) - Integer.parseInt(transaction[2]) );
}else{
players.put(transaction[0], Integer.parseInt(transaction[2])*-1);
}
if(players.get(transaction[1])!=null){
players.put(transaction[1], Integer.parseInt(transaction[2]) + players.get(transaction[1]));
}else{
players.put(transaction[1], Integer.parseInt(transaction[2]));
}
}
// Print the gainers and loosers
///System.out.println(players);
// This method should be invoked till all the values are 0
while(!ifTransactionDone(players))
findMaxGainerAndLooser(players);// Now find the maximum gainer and maximum looser
System.out.println(minimalTransactionMap);
}
private static void findMaxGainerAndLooser(Map<String, Integer> players) {
// TODO Auto-generated method stub
int max = 0; String maxKey="";
int min = 0; String minKey="";
boolean first = true;
for(Entry<String, Integer> playerGainLoss : players.entrySet()){
if(first){
max = playerGainLoss.getValue();
min = playerGainLoss.getValue();
maxKey = playerGainLoss.getKey();
minKey = playerGainLoss.getKey();
first = false;
}
if(playerGainLoss.getValue() > max){
max = playerGainLoss.getValue();
maxKey = playerGainLoss.getKey();
}
if(playerGainLoss.getValue() < min){
min = playerGainLoss.getValue();
minKey = playerGainLoss.getKey();
}
}
if(max == 0 && min==0)
return;
// Find absolute of which one is greater
if(max > (min*-1)){
players.put(minKey, 0);
players.put(maxKey, max + min);
minimalTransactionMap.put(minKey+"->"+maxKey, min*-1);
}else if(max < (min*-1)){
players.put(maxKey, 0);
players.put(minKey, max+min);
minimalTransactionMap.put(minKey+"->"+maxKey, max);
}else{
players.put(maxKey, 0);
players.put(minKey, 0);
minimalTransactionMap.put(minKey+"->"+maxKey, max);
}
}
public static boolean ifTransactionDone(Map<String, Integer> players){
boolean transactionEnd = true;
for(Entry<String, Integer> playerTrans : players.entrySet()){
if(playerTrans.getValue()!=0){
transactionEnd = false;
break;
}
}
return transactionEnd;
}
}
/**
*
*/
package practice;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
/**
*
* This class is to minimise the transaction between the all the players
* e.g.
A->B = Rs. 5
B->C = Rs. 8
C->D = Rs. 9
A->D = Rs. 10
D->B = Rs. 11
C->A = Rs. 12
We need to minimise the transaction in the above
*
*/
public class MinimiseTransaction {
/**
* @param args
*/
private static String transactions[][] = {
{"A","B","5"},
{"B","C","8"},
{"C","D","9"},
{"A","D","10"},
{"D","B","11"},
{"C","A","12"},
//{"D","A","3"}
};
static Map<String, Integer> minimalTransactionMap = new HashMap<String, Integer>();
public static void main(String[] args) {
// TODO Auto-generated method stub
Map<String, Integer> players = new HashMap<String, Integer>();
// From the above transaction first find the list of players and also find whether they are going to gain or loose
for(String[] transaction : transactions){
// The 0th element of the array will be a gainer
if(players.get(transaction[0])!=null){
players.put(transaction[0], players.get(transaction[0]) - Integer.parseInt(transaction[2]) );
}else{
players.put(transaction[0], Integer.parseInt(transaction[2])*-1);
}
if(players.get(transaction[1])!=null){
players.put(transaction[1], Integer.parseInt(transaction[2]) + players.get(transaction[1]));
}else{
players.put(transaction[1], Integer.parseInt(transaction[2]));
}
}
// Print the gainers and loosers
///System.out.println(players);
// This method should be invoked till all the values are 0
while(!ifTransactionDone(players))
findMaxGainerAndLooser(players);// Now find the maximum gainer and maximum looser
System.out.println(minimalTransactionMap);
}
private static void findMaxGainerAndLooser(Map<String, Integer> players) {
// TODO Auto-generated method stub
int max = 0; String maxKey="";
int min = 0; String minKey="";
boolean first = true;
for(Entry<String, Integer> playerGainLoss : players.entrySet()){
if(first){
max = playerGainLoss.getValue();
min = playerGainLoss.getValue();
maxKey = playerGainLoss.getKey();
minKey = playerGainLoss.getKey();
first = false;
}
if(playerGainLoss.getValue() > max){
max = playerGainLoss.getValue();
maxKey = playerGainLoss.getKey();
}
if(playerGainLoss.getValue() < min){
min = playerGainLoss.getValue();
minKey = playerGainLoss.getKey();
}
}
if(max == 0 && min==0)
return;
// Find absolute of which one is greater
if(max > (min*-1)){
players.put(minKey, 0);
players.put(maxKey, max + min);
minimalTransactionMap.put(minKey+"->"+maxKey, min*-1);
}else if(max < (min*-1)){
players.put(maxKey, 0);
players.put(minKey, max+min);
minimalTransactionMap.put(minKey+"->"+maxKey, max);
}else{
players.put(maxKey, 0);
players.put(minKey, 0);
minimalTransactionMap.put(minKey+"->"+maxKey, max);
}
}
public static boolean ifTransactionDone(Map<String, Integer> players){
boolean transactionEnd = true;
for(Entry<String, Integer> playerTrans : players.entrySet()){
if(playerTrans.getValue()!=0){
transactionEnd = false;
break;
}
}
return transactionEnd;
}
}
/**
*
*/
package practice;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
/**
*
* This class is to minimise the transaction between the all the players
* e.g.
A->B = Rs. 5
B->C = Rs. 8
C->D = Rs. 9
A->D = Rs. 10
D->B = Rs. 11
C->A = Rs. 12
We need to minimise the transaction in the above
*
*/
public class MinimiseTransaction {
/**
* @param args
*/
private static String transactions[][] = {
{"A","B","5"},
{"B","C","8"},
{"C","D","9"},
{"A","D","10"},
{"D","B","11"},
{"C","A","12"},
//{"D","A","3"}
};
static Map<String, Integer> minimalTransactionMap = new HashMap<String, Integer>();
public static void main(String[] args) {
// TODO Auto-generated method stub
Map<String, Integer> players = new HashMap<String, Integer>();
// From the above transaction first find the list of players and also find whether they are going to gain or loose
for(String[] transaction : transactions){
// The 0th element of the array will be a gainer
if(players.get(transaction[0])!=null){
players.put(transaction[0], players.get(transaction[0]) - Integer.parseInt(transaction[2]) );
}else{
players.put(transaction[0], Integer.parseInt(transaction[2])*-1);
}
if(players.get(transaction[1])!=null){
players.put(transaction[1], Integer.parseInt(transaction[2]) + players.get(transaction[1]));
}else{
players.put(transaction[1], Integer.parseInt(transaction[2]));
}
}
// Print the gainers and loosers
///System.out.println(players);
// This method should be invoked till all the values are 0
while(!ifTransactionDone(players))
findMaxGainerAndLooser(players);// Now find the maximum gainer and maximum looser
System.out.println(minimalTransactionMap);
}
private static void findMaxGainerAndLooser(Map<String, Integer> players) {
// TODO Auto-generated method stub
int max = 0; String maxKey="";
int min = 0; String minKey="";
boolean first = true;
for(Entry<String, Integer> playerGainLoss : players.entrySet()){
if(first){
max = playerGainLoss.getValue();
min = playerGainLoss.getValue();
maxKey = playerGainLoss.getKey();
minKey = playerGainLoss.getKey();
first = false;
}
if(playerGainLoss.getValue() > max){
max = playerGainLoss.getValue();
maxKey = playerGainLoss.getKey();
}
if(playerGainLoss.getValue() < min){
min = playerGainLoss.getValue();
minKey = playerGainLoss.getKey();
}
}
if(max == 0 && min==0)
return;
// Find absolute of which one is greater
if(max > (min*-1)){
players.put(minKey, 0);
players.put(maxKey, max + min);
minimalTransactionMap.put(minKey+"->"+maxKey, min*-1);
}else if(max < (min*-1)){
players.put(maxKey, 0);
players.put(minKey, max+min);
minimalTransactionMap.put(minKey+"->"+maxKey, max);
}else{
players.put(maxKey, 0);
players.put(minKey, 0);
minimalTransactionMap.put(minKey+"->"+maxKey, max);
}
}
public static boolean ifTransactionDone(Map<String, Integer> players){
boolean transactionEnd = true;
for(Entry<String, Integer> playerTrans : players.entrySet()){
if(playerTrans.getValue()!=0){
transactionEnd = false;
break;
}
}
return transactionEnd;
}
}
/**
*
*/
package practice;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
/**
*
* This class is to minimise the transaction between the all the players
* e.g.
A->B = Rs. 5
B->C = Rs. 8
C->D = Rs. 9
A->D = Rs. 10
D->B = Rs. 11
C->A = Rs. 12
We need to minimise the transaction in the above
*
*/
public class MinimiseTransaction {
/**
* @param args
*/
private static String transactions[][] = {
{"A","B","5"},
{"B","C","8"},
{"C","D","9"},
{"A","D","10"},
{"D","B","11"},
{"C","A","12"},
//{"D","A","3"}
};
static Map<String, Integer> minimalTransactionMap = new HashMap<String, Integer>();
public static void main(String[] args) {
// TODO Auto-generated method stub
Map<String, Integer> players = new HashMap<String, Integer>();
// From the above transaction first find the list of players and also find whether they are going to gain or loose
for(String[] transaction : transactions){
// The 0th element of the array will be a gainer
if(players.get(transaction[0])!=null){
players.put(transaction[0], players.get(transaction[0]) - Integer.parseInt(transaction[2]) );
}else{
players.put(transaction[0], Integer.parseInt(transaction[2])*-1);
}
if(players.get(transaction[1])!=null){
players.put(transaction[1], Integer.parseInt(transaction[2]) + players.get(transaction[1]));
}else{
players.put(transaction[1], Integer.parseInt(transaction[2]));
}
}
// Print the gainers and loosers
///System.out.println(players);
// This method should be invoked till all the values are 0
while(!ifTransactionDone(players))
findMaxGainerAndLooser(players);// Now find the maximum gainer and maximum looser
System.out.println(minimalTransactionMap);
}
private static void findMaxGainerAndLooser(Map<String, Integer> players) {
// TODO Auto-generated method stub
int max = 0; String maxKey="";
int min = 0; String minKey="";
boolean first = true;
for(Entry<String, Integer> playerGainLoss : players.entrySet()){
if(first){
max = playerGainLoss.getValue();
min = playerGainLoss.getValue();
maxKey = playerGainLoss.getKey();
minKey = playerGainLoss.getKey();
first = false;
}
if(playerGainLoss.getValue() > max){
max = playerGainLoss.getValue();
maxKey = playerGainLoss.getKey();
}
if(playerGainLoss.getValue() < min){
min = playerGainLoss.getValue();
minKey = playerGainLoss.getKey();
}
}
if(max == 0 && min==0)
return;
// Find absolute of which one is greater
if(max > (min*-1)){
players.put(minKey, 0);
players.put(maxKey, max + min);
minimalTransactionMap.put(minKey+"->"+maxKey, min*-1);
}else if(max < (min*-1)){
players.put(maxKey, 0);
players.put(minKey, max+min);
minimalTransactionMap.put(minKey+"->"+maxKey, max);
}else{
players.put(maxKey, 0);
players.put(minKey, 0);
minimalTransactionMap.put(minKey+"->"+maxKey, max);
}
}
public static boolean ifTransactionDone(Map<String, Integer> players){
boolean transactionEnd = true;
for(Entry<String, Integer> playerTrans : players.entrySet()){
if(playerTrans.getValue()!=0){
transactionEnd = false;
break;
}
}
return transactionEnd;
}
}
/**
*
*/
package practice;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
/**
*
* This class is to minimise the transaction between the all the players
* e.g.
A->B = Rs. 5
B->C = Rs. 8
C->D = Rs. 9
A->D = Rs. 10
D->B = Rs. 11
C->A = Rs. 12
We need to minimise the transaction in the above
*
*/
public class MinimiseTransaction {
/**
* @param args
*/
private static String transactions[][] = {
{"A","B","5"},
{"B","C","8"},
{"C","D","9"},
{"A","D","10"},
{"D","B","11"},
{"C","A","12"},
//{"D","A","3"}
};
static Map<String, Integer> minimalTransactionMap = new HashMap<String, Integer>();
public static void main(String[] args) {
// TODO Auto-generated method stub
Map<String, Integer> players = new HashMap<String, Integer>();
// From the above transaction first find the list of players and also find whether they are going to gain or loose
for(String[] transaction : transactions){
// The 0th element of the array will be a gainer
if(players.get(transaction[0])!=null){
players.put(transaction[0], players.get(transaction[0]) - Integer.parseInt(transaction[2]) );
}else{
players.put(transaction[0], Integer.parseInt(transaction[2])*-1);
}
if(players.get(transaction[1])!=null){
players.put(transaction[1], Integer.parseInt(transaction[2]) + players.get(transaction[1]));
}else{
players.put(transaction[1], Integer.parseInt(transaction[2]));
}
}
// Print the gainers and loosers
///System.out.println(players);
// This method should be invoked till all the values are 0
while(!ifTransactionDone(players))
findMaxGainerAndLooser(players);// Now find the maximum gainer and maximum looser
System.out.println(minimalTransactionMap);
}
private static void findMaxGainerAndLooser(Map<String, Integer> players) {
// TODO Auto-generated method stub
int max = 0; String maxKey="";
int min = 0; String minKey="";
boolean first = true;
for(Entry<String, Integer> playerGainLoss : players.entrySet()){
if(first){
max = playerGainLoss.getValue();
min = playerGainLoss.getValue();
maxKey = playerGainLoss.getKey();
minKey = playerGainLoss.getKey();
first = false;
}
if(playerGainLoss.getValue() > max){
max = playerGainLoss.getValue();
maxKey = playerGainLoss.getKey();
}
if(playerGainLoss.getValue() < min){
min = playerGainLoss.getValue();
minKey = playerGainLoss.getKey();
}
}
if(max == 0 && min==0)
return;
// Find absolute of which one is greater
if(max > (min*-1)){
players.put(minKey, 0);
players.put(maxKey, max + min);
minimalTransactionMap.put(minKey+"->"+maxKey, min*-1);
}else if(max < (min*-1)){
players.put(maxKey, 0);
players.put(minKey, max+min);
minimalTransactionMap.put(minKey+"->"+maxKey, max);
}else{
players.put(maxKey, 0);
players.put(minKey, 0);
minimalTransactionMap.put(minKey+"->"+maxKey, max);
}
}
public static boolean ifTransactionDone(Map<String, Integer> players){
boolean transactionEnd = true;
for(Entry<String, Integer> playerTrans : players.entrySet()){
if(playerTrans.getValue()!=0){
transactionEnd = false;
break;
}
}
return transactionEnd;
}
}
Solved this and seems to be working:
Checked with the above input:
- Scorpion King April 19, 2016output is :
C -> D = 8
C -> B = 5
A -> B = 3
Checked with this input:
A B 8
B C 4
C A 4
Output:
A -> B = 4