Google Interview Question for Software Developers


Country: United States




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

@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):
BoA, 485, Well Fargo
BoA, 204, Chase

- Alex September 02, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Alex September 02, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@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.

- Chris September 02, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 September 04, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@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.

- lee.painton September 06, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@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 September 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@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

- Chris September 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- PenChief September 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Any solution in java ?

- Anonymous August 07, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

/*
                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 September 02, 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