Amazon Interview Question
SDE1sCountry: India
Hey what if new transactions are not allowed to made, like Tiffany can only pay to Chris or Jane?
Hey what if new transactions cannot be created? like if Tiffany can only pay to Chris or Jane?
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)
maxHeap.add(new friendDebtPair(i,debts[i]));
else
minHeap.add(new friendDebtPair(i,debts[i]));
}
while(maxHeap.size() > 0 && minHeap.size() > 0) {
friendDebtPair giver = maxHeap.peek();
friendDebtPair receiver = minHeap.peek();
int balance = giver.debt + receiver.debt;
if(balance > 0) {
System.out.println(giver.friend + "->" + receiver.friend + ":" + Math.abs(receiver.debt));
maxHeap.poll();
giver.debt = balance;
maxHeap.add(giver);
minHeap.poll();
}
else if(balance < 0) {
System.out.println(giver.friend + "->" + receiver.friend + ":" + Math.abs(giver.debt));
maxHeap.poll();
minHeap.poll();
receiver.debt = balance;
minHeap.add(receiver);
}
else {
System.out.println(giver.friend + "->" + receiver.friend + ":" + Math.abs(receiver.debt));
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
@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];
result.add(new int[] {sum[begin][0], sum[end][0], val});
sum[begin][1] += val;
sum[end][1] -= val;
}
}
return result;
}
import java.util.*;
public class SimplifyDebt
{
public static void main(String[] args)
{
Graph g = new Graph();
g.addTransaction(1, 2, 400);
g.addTransaction(2, 3, 200);
g.addTransaction(3, 1, 100);
g.addTransaction(3, 4, 200);
g.addTransaction(4, 1, 100);
g.addTransaction(3, 5, 1000);
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);
g.addTransaction(out.to, in.to, owe);
int sum = in.owe+out.owe;
if(sum < 0)
{
outq.add(new Node(out.to, sum));
}
else if(sum >0)
{
inq.add(new Node(in.to, sum));
}
}
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>());
list.add(new Node(to, owe));
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;
}
}
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);
}
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):
but more efficient is:
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.
- Chris June 29, 2017