## Goldman Sachs Interview Question for Associates

• 1
of 1 vote

Country: India
Interview Type: Phone Interview

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

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

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

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.

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

We combine (A->B=5 and B ->C=8 to C->A=3 ) and (A->D =10 and D->B = 11 to B ->A=1)
So we have
C->A=3
B->A=1
C->D=9
C->A=12

Combining futher, Minimum 3 transactions:
B->A=1
C->A=15
C->D=9

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

Solved this and seems to be working:

``````import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

/** Algorithm to minimize number of trassaction.
* Eg:
* A->B = Rs. 5
* B->C = Rs. 8
* C->D = Rs. 9
* A->D = Rs. 10
* D->B = Rs. 11
* C->A = Rs. 12
* =================
* A->B = 5 */

class Transaction {

private static File sFile;
private static String[][] sInput;
private static HashMap<String, Integer> sTransaction;
private static ArrayList<String> sOutPlayer;
private static ArrayList<Integer> sOutPlayerData;
private static ArrayList<String[]> sResult;

private static void parseTransaction() {
sTransaction = new HashMap<String, Integer>();
try {
@SuppressWarnings("resource")
int i = 0;
while (line != null && i < sInput.length) {
String[] temp = line.split(" ");
sInput[i][0] = temp[0];
sInput[i][1] = temp[1];
sInput[i][2] = temp[2];
i++;
}
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}

private static void getAllPlayer() {
for (int i = 0; i < sInput.length; i++) {
sTransaction.put(sInput[i][0], 0);
sTransaction.put(sInput[i][1], 0);
}
}

private static void getManipulatedTransactionData() {
for (int i = 0; i < sInput.length; i++) {
int val = Integer.parseInt(sInput[i][2]);
sTransaction.put(sInput[i][0], sTransaction.get(sInput[i][0]) - val);
sTransaction.put(sInput[i][1], sTransaction.get(sInput[i][1]) + val);
}
}

private static void sortByValue() {
List<Map.Entry<String, Integer>> entries = new LinkedList<Map.Entry<String, Integer>>(
sTransaction.entrySet());

Collections.sort(entries, new Comparator<Map.Entry<String, Integer>>() {

@Override
public int compare(Entry<String, Integer> o1,
Entry<String, Integer> o2) {
return o1.getValue().compareTo(o2.getValue());
}
});
sOutPlayer = new ArrayList<String>();
sOutPlayerData = new ArrayList<Integer>();
int i = 0;
for (Map.Entry<String, Integer> entry : entries) {
i++;
}
}

private static ArrayList<String[]> minimizeTransaction() {
if (sOutPlayerData.get(0) >= 0) {
return null;
}
sResult = new ArrayList<String[]>();
int i = 0;
int j = sOutPlayer.size() - 1;
while (i <= j) {
String[] temp = new String[3];
boolean flag = false;
if (Math.abs(sOutPlayerData.get(i)) == Math.abs(sOutPlayerData.get(j))) {
if (Math.abs(sOutPlayerData.get(i)) != 0) {
temp[0] = sOutPlayer.get(i);
temp[1] = sOutPlayer.get(j);
temp[2] = Math.abs(sOutPlayerData.get(i)) + "";
flag = true;
}
sOutPlayerData.set(i, 0);
sOutPlayerData.set(j, 0);
i++;
j--;
} else if (Math.abs(sOutPlayerData.get(i)) > Math.abs(sOutPlayerData.get(j))) {
int val = Math.abs(sOutPlayerData.get(i)) - Math.abs(sOutPlayerData.get(j));
if (Math.abs(sOutPlayerData.get(j)) != 0) {
temp[0] = sOutPlayer.get(i);
temp[1] = sOutPlayer.get(j);
temp[2] = Math.abs(sOutPlayerData.get(j)) + "";
flag = true;
}
sOutPlayerData.set(i, val * -1);
sOutPlayerData.set(j, 0);
j--;
} else {
int val = Math.abs(sOutPlayerData.get(j)) - Math.abs(sOutPlayerData.get(i));
if (Math.abs(sOutPlayerData.get(i)) != 0) {
temp[0] = sOutPlayer.get(i);
temp[1] = sOutPlayer.get(j);
temp[2] = Math.abs(sOutPlayerData.get(i)) + "";
flag = true;
}
sOutPlayerData.set(i, 0);
sOutPlayerData.set(j, val);
i++;
}
if (flag) {
}
}
return sResult;
}

private static void display() {
for (int i = 0; i < sResult.size(); i++) {
System.out.println(sResult.get(i)[0] + " -> " + sResult.get(i)[1] + " = "
+ sResult.get(i)[2]);
}
}

public static void getMinimizedTransaction(String iFile, int numberOfTransaction) {
sFile = new File(iFile);
sInput = new String[numberOfTransaction][3];

parseTransaction();
getAllPlayer();
getManipulatedTransactionData();
sortByValue();
minimizeTransaction();
display();
}
}``````

Checked with the above input:
output 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

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

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

}``````

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

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

}

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

``````/**
*
*/
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;
}

}``````

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

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

}

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

``````/**
*
*/
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;
}

}``````

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.

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