Amazon Interview Question for SDE1s


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

- Chris June 29, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Joanna April 05, 2020 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Joanna April 05, 2020 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

what if new routes are not allowed?

- Joanna April 07, 2020 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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]))

- Abhinav Raj January 06, 2021 | Flag
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)
	            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

- NinjaCoder July 10, 2017 | Flag Reply
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];
            result.add(new int[] {sum[begin][0], sum[end][0], val});
            sum[begin][1] += val;
            sum[end][1] -= val;
        }
    }

    return result;
}

- funk July 21, 2017 | Flag Reply
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();
		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;
	}
}

- noob September 30, 2017 | Flag Reply
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);
}

- Vinay Kumar Dubey June 29, 2017 | Flag Reply


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