## Amazon Interview Question for SDE1s

• 0

Country: India

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

The problem is somewhat ambigous. What's a redundant cash flow path?
I assume we just want to minimize the number of transactions.

After all transactions have been completed, every friend has a delta
neto cash flow. Thas is either positive, 0 or negative.

I put them into a dictionary, where the balance is key and the person
is the value.

Then I need to match positives to negatives untill all summs to 0. This
seems not trivial tough.

let's say positives are: 1, 9, 13
and negatives are: -14, -2, -7
one way is (arrow indicates cash flow, value in parentesis is new
value after transaction):

``````1 (0) -->  -7 (-6)
9 (3) -->  -6 (0)
3 (1) -->  -2 (0)
1 (0) --> -14 (-13)
13 (0) --> -13 (0)``````

but more efficient is:

``````13 (0) --> -14 (-1)
9 (2) -->  -7 (0)
2 (0) -->  -2 (0)
1 (0) -->  -1 (0)``````

the problem here is to find the best solution which seems not trivial.
I've implemented one that uses a greedy strategy which obviously won't
find the best solution all the time.

Appriciate a comment for the best solution, seems like an NP problem.

But it certainly removes "redundant transactions" whatever that might
be exactly.

``````import heapq
from collections import defaultdict
def minimize_transaction(transactions):
# transactions are tubbles with (from, to, amount)
# do all transaction which gives the neto_flow to and from each friends
neto_flow = defaultdict(int)
for transaction in transactions:
neto_flow[transaction[0]] -= transaction[2]
neto_flow[transaction[1]] += transaction[2]

# negatives and positives are min-heaps to be populated
negatives = []
positives = []
for person, amount in neto_flow.items():
if amount < 0:
heapq.heappush(negatives, (amount, person))
elif amount > 0:
heapq.heappush(positives, (-amount, person)) # python has a min heap per default...

# optimize the flow using the two heaps
while positives and negatives:
pos = heapq.heappop(positives)
neg = heapq.heappop(negatives)
amount = max(pos[0], neg[0]) # are both negative values
print("{0} sends \${1} to {2}".format(neg[1], -amount, pos[1]))
if pos[0] - amount < 0:
heapq.heappush(positives, (pos[0] + amount, pos[1]))
elif neg[0] - amount < 0:
heapq.heappush(negatives, (neg[0] + amount, neg[1]))

minimize_transaction([('jane', 'pete', 100),
('pete', 'tiffany', 80),
('tiffany', 'chris', 60),
('tiffany', 'jane', 10),
('chris', 'jane', 10),
('chris', 'pete', 10)])

#output
#jane sends \$40 to chris
#jane sends \$30 to pete
#jane sends \$10 to tiffany``````

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

Hey what if new transactions are not allowed to made, like Tiffany can only pay to Chris or Jane?

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

Hey what if new transactions cannot be created? like if Tiffany can only pay to Chris or Jane?

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

what if new routes are not allowed?

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

This is wrong, in the while loop in the if else conditions, it should be subtraction rather than adding it i.e.

``heapq.heappush(positives, (pos[0] - amount, pos[1]))``

``heapq.heappush(negatives, (neg[0] - amount, neg[1]))``

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

This is similar to the shuffle debts feature in Splitwise.com
Here is a Java solution :

``````import java.io.*;
import java.util.*;

public class SplitWise {
public static void main (String[] args) {
int input[] = {1,9,13,-14,-2,-7};
shuffleDebts(input);
}

static void shuffleDebts(int debts[]) {

Comparator<friendDebtPair> compMax = new maxComparator();
Queue<friendDebtPair> maxHeap = new PriorityQueue<friendDebtPair>(1,compMax);

Comparator<friendDebtPair> compMin = new minComparator();
Queue<friendDebtPair> minHeap = new PriorityQueue<friendDebtPair>(1,compMin);

for(int i=0; i<debts.length; i++)
{
if(debts[i] >= 0)
else
}

while(maxHeap.size() > 0 && minHeap.size() > 0) {
friendDebtPair giver = maxHeap.peek();
int balance = giver.debt + receiver.debt;

if(balance > 0) {
maxHeap.poll();
giver.debt = balance;
minHeap.poll();
}
else if(balance < 0) {
System.out.println(giver.friend + "->" + receiver.friend + ":" + Math.abs(giver.debt));
maxHeap.poll();
minHeap.poll();
}
else {
maxHeap.poll();
minHeap.poll();
}
}

}
}

class friendDebtPair {
int friend;
int debt;
friendDebtPair(int f, int d) {
friend = f;
debt = d;
}
}

class maxComparator implements Comparator<friendDebtPair> {
public int compare(friendDebtPair f1, friendDebtPair f2) {
return(f2.debt - f1.debt);
}
}

class minComparator implements Comparator<friendDebtPair> {
public int compare(friendDebtPair f1, friendDebtPair f2) {
return(f1.debt - f2.debt);
}
}``````

Output:

2->3:13
1->5:7
1->4:2
0->3:1

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

@ChrisK I think the only thing missing from your algorithm to be optimal would be to identify when two friends have equal positive and negative net cash flow in which case you would have them transact with each other and prevent them from going into the heaps in order to ensure that their debt would settle in a single transaction. I believe it's NP as well.

Here's my solution that does the same idea but without heaps. It appears to also not be optimal.

``````/**
* @param n total number of friends
* @param transactions array of 3-tuples {from, to, value}
*/
public static List<int[]> shuffleDebt(int n, int[][] transactions) {
int[][] sum = new int[n][2];

for ( int i = 0; i < n; ++i ) { sum[i][0] = i; } // identify the friends for later use

for (int[] transaction : transactions) {
int from = transaction[0];
int to = transaction[1];
int val = transaction[2];
sum[from][1] -= val;
sum[to][1] += val;
}

Arrays.sort(sum, (sum1, sum2) -> Integer.compare(sum1[1],sum2[1]));

ArrayList<int[]> result = new ArrayList<>();
int begin = 0, end = n-1;

while ( begin < end ) {
if ( sum[begin][1] == 0 ) { begin++; }
else if ( sum[end][1] == 0 ) { end--; }
else {
int val = sum[end][1] >= -sum[begin][1] ? -sum[begin][1] : sum[end][1];
sum[begin][1] += val;
sum[end][1] -= val;
}
}

return result;
}``````

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

``````import java.util.*;
public class SimplifyDebt
{
public static void main(String[] args)
{
Graph g = new Graph();
System.out.println(g);
SimplifyDebt s= new SimplifyDebt();
Graph newG = s.simplify(g);
System.out.println(newG);
}

public Graph simplify(Graph g)
{
Map<Integer, Integer> map = solve(g);
PriorityQueue<Node> inq = new PriorityQueue<>(10,new Comparator<Node>(){
public int compare(Node a, Node b)
{
return Integer.compare(b.owe, a.owe);
}
});

PriorityQueue<Node> outq = new PriorityQueue<>(10, new Comparator<Node>(){
public int compare(Node a, Node b)
{
return Integer.compare(a.owe, b.owe);
}
});
System.out.println(map);
for(Map.Entry<Integer, Integer> entry: map.entrySet())
{
if(entry.getValue()<0)
outq.offer(new Node(entry.getKey(), entry.getValue()));
else
inq.offer(new Node(entry.getKey(), entry.getValue()));
}
System.out.println(inq);
System.out.println(outq);
return evaluate(inq,outq);
}

private Graph evaluate(PriorityQueue<Node> inq, PriorityQueue<Node> outq)
{
Graph g = new Graph();
while(!inq.isEmpty() && !outq.isEmpty())
{
Node in = inq.poll();
Node out = outq.poll();
int owe = (out.owe * -1)>in.owe?in.owe:(out.owe*-1);
int sum = in.owe+out.owe;
if(sum < 0)
{
}
else if(sum >0)
{
}
}
return g;
}

private Map<Integer, Integer> solve(Graph g)
{
Map<Integer, Integer> tempMap = new HashMap<>();
for(Integer from: g.map.keySet())
{
for(Node node : g.map.get(from))
{
tempMap.put(from, tempMap.getOrDefault(from, 0)-node.owe);
tempMap.put(node.to, tempMap.getOrDefault(node.to, 0)+node.owe);
}

}
return tempMap;
}

}

class Graph
{
Map<Integer, List<Node>> map;

public Graph()
{
this.map = new HashMap<>();
}

public void addTransaction(int from, int to, int owe)
{
List<Node> list = map.getOrDefault(from, new ArrayList<Node>());
map.put(from, list);
}

public String toString()
{
return this.map.toString();
}
}

class Node
{
int to;
int owe;

Node(int to, int owe)
{
this.to = to;
this.owe = owe;
}

public String toString()
{
return this.to+":"+owe;
}
}``````

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

void minCashFlowRec(int amount[])
{
]
int mxCredit = getMax(amount), mxDebit = getMin(amount);
if (amount[mxCredit] == 0 && amount[mxDebit] == 0)
return;
int min = minOf2(-amount[mxDebit], amount[mxCredit]);
amount[mxCredit] -= min;
amount[mxDebit] += min;

cout << "Person " << mxDebit << " pays " << min
<< " to " << "Person " << mxCredit << endl;

minCashFlowRec(amount);
}

void minCashFlow(int graph[][N])
{
int amount[N] = {0};

for (int p=0; p<N; p++)
for (int i=0; i<N; i++)
amount[p] += (graph[i][p] - graph[p][i]);

minCashFlowRec(amount);
}

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.