Google Interview Question
Software DevelopersCountry: United States
My idea is to calc balances the companies have after running all of the transactions. Then, using max and min heaps, generate consolidated transactions.
Not sure if it's not possible to make amount of consolidated transactions less. Maybe DP should be used.
#include <unordered_map>
#include <vector>
#include <string>
#include <iostream>
#include <queue>
using namespace std;
class Transaction {
public:
Transaction(string const &payee, int amount, string const &payer)
{
payee_ = payee;
amount_ = amount;
payer_ = payer;
}
string payee_, payer_;
int amount_;
};
class Company {
public:
Company(string name, int balance)
{
name_ = name;
balance_ = balance;
}
string name_;
int balance_;
bool operator<(Company const &other) const
{
return balance_ < other.balance_;
}
};
vector<Transaction> Consolidate(vector<Transaction> const &transactions)
{
unordered_map<string, int> balance;
for (auto t : transactions) {
balance[t.payer_] -= t.amount_;
balance[t.payee_] += t.amount_;
}
priority_queue<Company> pq1, pq2;
for (auto el : balance) {
if (el.second > 0) {
pq1.push(Company(el.first, el.second));
} else if (el.second < 0) {
pq2.push(Company(el.first, el.second * -1));
}
}
vector<Transaction> out;
while (!pq1.empty()) {
Company pos_balance_company = pq1.top();
pq1.pop();
Company neg_balance_company = pq2.top();
pq2.pop();
int amount = min(pos_balance_company.balance_, neg_balance_company.balance_);
pos_balance_company.balance_ -= amount;
neg_balance_company.balance_ -= amount;
if (pos_balance_company.balance_ != 0) {
pq1.push(pos_balance_company);
} else {
pq2.push(neg_balance_company);
}
out.push_back(Transaction(pos_balance_company.name_, amount, neg_balance_company.name_));
}
return out;
}
int main(int argvc, char const **argv)
{
vector<Transaction> trans;
trans.push_back(Transaction("BoA", 132, "Chase"));
trans.push_back(Transaction("BoA", 827, "Chase"));
trans.push_back(Transaction("Well Fargo", 751, "BoA"));
trans.push_back(Transaction("BoA", 585, "Chase"));
trans.push_back(Transaction("Chase", 877, "Well Fargo"));
trans.push_back(Transaction("Well Fargo", 157, "Chase"));
trans.push_back(Transaction("Well Fargo", 904, "Chase"));
trans.push_back(Transaction("Chase", 976, "BoA"));
trans.push_back(Transaction("Chase", 548, "Well Fargo"));
trans.push_back(Transaction("BoA", 872, "Well Fargo"));
vector<Transaction> out = Consolidate(trans);
for (auto t : out) {
cout << t.payee_ << ", " << t.amount_ << ", " << t.payer_ << "\n";
}
return 0;
}
@Makarand: I had the same results except your last step. I think the last step is incorrect because at your second step b receives 689, and spends nothing, at the last step she receives only 204.
but neither can I conclude, how the get to the 482 flow from b to w as the question suggest as result. Especially not because b clearly receives money on all edges. I think there is an error with the question.
Further, if the graph is more complex, there will always be several options where you can re-route the cash flow, some will in the near future pay out to be better because it allows further reduction whereas the other path wouldn't allow this. Thus it seems there is no greedy approach to the problem.
Neither is clear if we can introduce new flows among nodes or if we can only work on existing edges. Then if an edge has only a positive flow, can we reverse it or would that be a new edge?
I would solve it calculating net-flow in each node (sum of incomming - sum of outgoing). Then I would try to connect negative flow to positive flow such that the number of connections is minimal. I think that's a bipartite matching (graph) problem, I'm not fit enough with all the flow network algorithms to get a clear statement how to solve it optimally. Maybe someone could help here.
Dumb question - why isn't it sufficient to simply calculate the net flow for each party, remove those with net zero, and sort by net flow?
Then each party pays the next the entire amount of their net. After removing the net zeros, this will result in n -1 edges. Can someone come up with a counterexample?
@SR
Your method will fail to capture solutions involving disjoint graphs.
For example:
A -1
B -2
C 3
D -4
E -5
F 9
The optimal solution is n-2 edges
B 2 A
A 3 C
E 5 D
D 9 F
Your method works as long as there are no disjoint graphs. It's possible you could account for those and separate the sorted nodes into separate graphs before solving.
@ChrisK. If we do the transactions keeping track of the companies' balance, after all of the transactions the balances are the following:
Well Fargo: -485
BoA: 689
Chase: -204
Which, by hand can be written in two transactions:
Well Fargo pays 485 BoA
Chase pays 204 BoA
Your code produces 3 transactions:
from 2 to 1 $ 189
from 0 to 2 $ 674
from 0 to 1 $ 15
Probably a bug somewhere.
@Alex, thanks, you're right the whole graph strategy code is pretty much crap ;-( I wanted to do everythin in once, but that outcome is wrong. My first idea, that works, is to remove all cycles first. Then add flow from forward and cross edges to existing (shortest) path. I should stick with it. I still don't think that's the most efficient way to solve it in the graph, but the impl above was just wrong. need to remove it
The idea here:
* Each transaction is identified by a string "Payer->Payee"
* Before we insert the this transaction to our ledger ("G" in the code) with the given amount, we check if we have a reversed transaction "Payee->Payer"
** If we do have such a transaction, we subtract the amount.
*** If the updated amount is negative, we remove the reversed transaction ("Payee->Payer") and insert "Payer->Payee" with the diff amount.
*** If the updated amount is zero - remove the reversed transaction and move on to the next transaction
*** Else (the reversed transaction is bigger than the current transaction) so just update the reverse transaction amount and continue
This is done in roughly o(n)
#include "CommonHeader.h"
static std::unordered_map<std::string, int> G;
static std::string make_key(const std::string& payer, const std::string& payee) { return payer + "->" + payee; }
static int& GetPayment(const std::string& key)
{
if(G.count(key) == 0) {
G[key] = 0;
}
return G[key];
}
static bool HasPayment(const std::string& key)
{
if(G.count(key) == 0) return false;
return true;
}
void ProcessPayments(const std::vector<std::tuple<std::string, std::string, int> >& transcations)
{
// Build the payment matrix
for(size_t i = 0; i < transcations.size(); ++i) {
const std::tuple<std::string, std::string, int>& paymentInfo = transcations[i];
const std::string& payee = std::get<0>(paymentInfo);
const std::string& payer = std::get<1>(paymentInfo);
int amount = std::get<2>(paymentInfo);
std::string key = make_key(payer, payee);
std::string reverse_key = make_key(payee, payer);
// Check to see if we have a reversed payment
if(HasPayment(reverse_key)) {
int& reversedAmount = GetPayment(reverse_key);
reversedAmount -= amount;
if(reversedAmount < 0) {
// Remove the reversed payment and add the current payment
int& tmpAmount = GetPayment(key);
tmpAmount += abs(reversedAmount);
// The erase must come *after* we update the new value of else we might get an invalid pointer
G.erase(reverse_key);
} else if(reversedAmount == 0) {
G.erase(reverse_key);
} else {
// nothing to be done here
}
} else {
int& tmpAmount = GetPayment(key);
tmpAmount += amount;
}
}
// Print the transcations
std::for_each(G.begin(), G.end(), [&](const std::unordered_map<std::string, int>::value_type& vt) {
std::cout << vt.first << ":" << vt.second << std::endl;
});
}
/*
I was tempted to try paper and pencil calculations on these records
I got a slightly different answer than what is suggested here.
*/
// c->b : 132, 827, 585 (1544)
// b->w : 751
// w->c : 877, 548 (1425)
// c->w : 157, 904 (1061)
// b->c : 976
// w->b : 872
// becomes
// c->b : 568
// w->b : 121
// w->c : 364
// reduced to
// w->c : 485
// c->b : 689
// reduced to
// c ->b: 204
// so chase pays bofa 204 ?? is this correct ?
@Makarand, @ChrisK. Yes, it looks like the answer is not right in the example. My code boils it down to these two transactions (payee, amount, payer):
- Alex September 02, 2017BoA, 485, Well Fargo
BoA, 204, Chase