## 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.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
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")
BufferedReader br = new BufferedReader(new FileReader(sFile));
String line = br.readLine();
int i = 0;
while (line != null && i < sInput.length) {
String[] temp = line.split(" ");
sInput[i] = temp;
sInput[i] = temp;
sInput[i] = temp;
i++;
line = br.readLine();
}
} 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);
sTransaction.put(sInput[i], 0);
}
}

private static void getManipulatedTransactionData() {
for (int i = 0; i < sInput.length; i++) {
int val = Integer.parseInt(sInput[i]);
sTransaction.put(sInput[i], sTransaction.get(sInput[i]) - val);
sTransaction.put(sInput[i], sTransaction.get(sInput[i]) + 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) {
sOutPlayer.add(i, entry.getKey());
sOutPlayerData.add(i, entry.getValue());
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;
boolean flag = false;
if (Math.abs(sOutPlayerData.get(i)) == Math.abs(sOutPlayerData.get(j))) {
if (Math.abs(sOutPlayerData.get(i)) != 0) {
temp = sOutPlayer.get(i);
temp = sOutPlayer.get(j);
temp = 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 = sOutPlayer.get(i);
temp = sOutPlayer.get(j);
temp = 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 = sOutPlayer.get(i);
temp = sOutPlayer.get(j);
temp = Math.abs(sOutPlayerData.get(i)) + "";
flag = true;
}
sOutPlayerData.set(i, 0);
sOutPlayerData.set(j, val);
i++;
}
if (flag) {
sResult.add(temp);
}
}
return sResult;
}

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

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

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)!=null){
players.put(transaction, players.get(transaction) - Integer.parseInt(transaction) );
}else{
players.put(transaction, Integer.parseInt(transaction)*-1);
}

if(players.get(transaction)!=null){
players.put(transaction, Integer.parseInt(transaction) + players.get(transaction));
}else{
players.put(transaction, Integer.parseInt(transaction));
}

}
// 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)!=null){
players.put(transaction, players.get(transaction) - Integer.parseInt(transaction) );
}else{
players.put(transaction, Integer.parseInt(transaction)*-1);
}

if(players.get(transaction)!=null){
players.put(transaction, Integer.parseInt(transaction) + players.get(transaction));
}else{
players.put(transaction, Integer.parseInt(transaction));
}

}
// 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)!=null){
players.put(transaction, players.get(transaction) - Integer.parseInt(transaction) );
}else{
players.put(transaction, Integer.parseInt(transaction)*-1);
}

if(players.get(transaction)!=null){
players.put(transaction, Integer.parseInt(transaction) + players.get(transaction));
}else{
players.put(transaction, Integer.parseInt(transaction));
}

}
// 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)!=null){
players.put(transaction, players.get(transaction) - Integer.parseInt(transaction) );
}else{
players.put(transaction, Integer.parseInt(transaction)*-1);
}

if(players.get(transaction)!=null){
players.put(transaction, Integer.parseInt(transaction) + players.get(transaction));
}else{
players.put(transaction, Integer.parseInt(transaction));
}

}
// 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)!=null){
players.put(transaction, players.get(transaction) - Integer.parseInt(transaction) );
}else{
players.put(transaction, Integer.parseInt(transaction)*-1);
}

if(players.get(transaction)!=null){
players.put(transaction, Integer.parseInt(transaction) + players.get(transaction));
}else{
players.put(transaction, Integer.parseInt(transaction));
}

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

}``````

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