Google Interview Question for Software Engineers


Country: United States
Interview Type: In-Person




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

EDITED 22.11.'16
I went through everything again, it took much more than 45 minutes.
/*
Assumption and sumary:
- the enemeis have to be fought in order (1st, 2nd, ...) order isn't 
  free to choose
- assume to maximize on money after fighting all enemies

Approach:
- dp(i, s, m) = max money at i, after proceeding through i-th enemy 
- s = remaining strength at i, s0 is given
- m = remaining money at i, m0 is given 
- s[i] = strength used to fight enemy i (0 <= s[i])
- m[i] = money used to bribe enemy i (0 <= m[i])
- game starts with dp(0, s0, m0)

Recursion:                                         
                   / dp(i+1, s-s[i], m)        , if s >= s[i]
dp(i, s, m) = max /  dp(i+1, s+s[i], m - m[i]) , if m >= m[i]
                  \  = -1, if m < m[i] and s < s[i]
				   \ = m0, if i == n-1

Prove of NP-completness: let's try to deduce knap-sack to 
this problem:
	The knapsack recursion:    
	dp(i, space) = 	
	  max / dp(i+1, space-size[i])+value[i], if size[i]<=space 
	      \ dp(i+1, space) 
    
    The problem (1) is a knap-sack problem (2):
	- 1: if we fight an enemy we use strength
	  2: if an item is included, it uses space
	- 1: if we can't fight an enemy due to lack of strength, 
	     we have to us money
	  2: if the item doesn't fit into the bag, we "loose"
	     the value of the item
	- 1: if we bribe an enemy, we gain strength
	  2: if we leave an item behind, we do not use space
	     actually we have to modify this to, if an item is 
		 left behind, it will make additional space in the
		 knap-sack (which is totally not real-world)	     
	  2: Additions needed on knapsack:
		 - an item can only be excluded if the total
		   value of excluded items is not higher than
		   a given arbitrary value
		 - pack the items in order and an item that 
		   is not packed increases the space of the 
		   knap-sack

	or the other way around, if we wouldn't add the strength
	of a bribed enemy, order wouldn't matter and we had a pure 
	knap-sack problem. 

	Concluding, this problem is at least as hard as knap-sack 
	and thus it is NP-complete.

A pseude polynomial algorith for knap-sack exists. 
That is exponential in the number of bits used to represent 
the space of the knap-sack - thus polynomial to the actual 
space. 

our initial recursion was:
                   / dp(i+1, s-s[i], m)        , if s >= s[i]
dp(i, s, m) = max /  dp(i+1, s+s[i], m - m[i]) , if m >= m[i]
                  \  = -1, if m < m[i] and s < s[i]
				   \ = m0, if i == n-1

while writing this with memoization is okay, there is a problem with
it:
  a subproblem is only reused if it has the exact same strength and 
  money at a certain position. It would be better, 
  if we do not consider solutions that lead to less
  money at the same strength level at a certain index i.

An iterative approach can solve it:
  create an array dp of size n + 1 (n=amount of enemeies)
  every entry has an array reaching from 0..MAX-STRENGTH
  that entry carries the max-money for that strength

  then initialize that first array with the start condition that is:
  dp[0][0..s0] = m0;
  dp[0][s0+1..MAX_STRENGTH+1] = -1;

  int maxmoney = -1;
  for(i = 0; i < n; i++)
  {
	  int s = s[i]; // strength of the enemy
	  int m = m[i]; // cost to bribe it
	  
	  maxmoney = -1;
	  for(int j = MAX_STRENGTH; j >= 0; j++)
	  {
	      if(j >= s) maxm = max(maxm,  dp[i][j - s] - m); // bribe				
		  if(j <= MAX_STRENGTH - s) maxm = max(maxm, dp[i][j + s]); // fight
		  dp[i + 1][j] = maxm; // note, the money will be reused as "higher bar" 
		                       // for less strength case 
	  }	  
  }

  maxmoney contains the result

  this code can further be optimized:
  1) there is no need for MAX_STRENGTH as we can dynamically calculate it at every step and only use
     as much
  2) we do not need a matrix on space, but only the last result and the current result, so 
     two alternating buffers are okay, see implementation below  

  runtime: O(n*MAX_STRENGTH)
  space (optimized): O(MAX_STRENGTH)
*/

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
#include <utility>
#include <cassert>

using namespace std;

// iterative version, turns out to be very similar to knap-sack
// iterative approach
class MaximizeMoney_Iterative
{
private:	
	vector<int> strength_;
	vector<int> money_;
	int steps_; // calculation step counter
	int maxMoney_;

public:
	int getSteps() const { return steps_; }
	int getMaxMoney() const { return maxMoney_; }  

	void solve(const vector<int>& money, const vector<int> strength, int m0, int s0)
	{
		steps_ = 0;
		strength_ = strength;
		money_ = money;
		
		vector<vector<int>> dp(2, vector<int>());
		for(int j = 0; j <= s0; j++) dp[0].push_back(m0);

		int maxm = -1; // max money at step i		
		for(int i = 0; i < strength_.size(); i++)
		{
			int s = strength_[i]; // strength of the enemy
			int m = money_[i]; // cost to bribe it
			int maxs = dp[i & 1].size() + s  - 1;
			maxm = -1;
			dp[(i + 1) & 1].clear(); 
			for(int j = maxs; j >= 0; j--)
			{
				if(j >= s) maxm = max(maxm,  dp[i & 1][j - s] - m);				
				if(j < dp[i & 1].size() - s) maxm = max(maxm, dp[i & 1][j + s]);
				if(maxm >= 0)
				{
					if(dp[(i + 1) & 1].size() == 0)
					{ 
						dp[(i + 1) & 1] = vector<int>(j + 1, 0);
					}
					dp[(i + 1) & 1][j] = maxm;
				}
				steps_ ++;
			}
		}

		maxMoney_ = maxm;
	}	
};

// the recursive version with memoization, much harder to analyze
// and understand
class MaximizeMoney_RecursiveMemo
{
private:	
	vector<int> strength_;
	vector<int> money_;
	unordered_map<int, int> memo_;
	int steps_; // calculation step counter
	int maxMoney_;

public:
	int getSteps() const { return steps_; }
	int getMaxMoney() const { return maxMoney_; }  

	void solve(const vector<int>& money, const vector<int> strength, int m0, int s0)
	{
		steps_ = 0;
		memo_.clear();
		strength_ = strength;
		money_ = money;
		maxMoney_ = maxMoney(0, m0, s0);
	}

private:
	int maxMoney(int i, int m, int s)
	{
		if(m < 0 || s < 0) return -1;
		if(i == strength_.size()) return m; // through..

		int key = createKey(m, s, i);
		auto mi = memo_.find(key);
		if(mi != memo_.end()) return mi->second;
			
		steps_++; // count calculation steps 
		int res = max(maxMoney(i + 1, m - money_[i], s + strength_[i]), 
					maxMoney(i + 1, m, s - strength_[i]));

		memo_[key] = res;
		return res; 
	}

	static int createKey(int m, int s, int i)
	{
		assert((s < 1024) && (m < 1024) && (i < 1024));
		return (s << 20) | (m << 10) | i;
	}
};


void runCase(const string& tcase, const vector<int>& s, const vector<int>& m, int m0, int s0)
{
	MaximizeMoney_RecursiveMemo mmr;	

	cout << "\n" << tcase << endl;
	cout << "  problem has at most " << (1ULL << s.size()) << " combinations " << endl; 
	mmr.solve(m, s, m0, s0);
	cout << "  recursive algo with memoization solved in #steps:" << mmr.getSteps() << " money@end:" << mmr.getMaxMoney() << endl;

	MaximizeMoney_Iterative mmi;
	mmi.solve(m, s, m0, s0);
	cout << "  iterative algo solved in #steps:" << mmi.getSteps() << " money@end:" << mmi.getMaxMoney() << endl;	
}


int main()
{
	runCase("simple case 1",
		{1, 2, 1, 4, 2, 3, 1, 5, 6, 7, 8, 1, 2, 3, 5, 3, 5, 3, 2, 1},
		{5, 4, 1, 2, 3, 7, 8, 1, 2, 3, 4, 2, 6, 1, 3, 1, 6, 5, 3, 2},
		16, 6);

	runCase("simple case 2",
		{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20},
		{20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1},
		100, 100);  

	runCase("simple case 3",
		{20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20},
		{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20},
		50, 50);  

/* output:
simple case 1
  problem has at most 1048576 combinations 
  recursive algo with memoization solved in #steps:834 money@end:4
  iterative algo solved in #steps:486 money@end:4

simple case 2
  problem has at most 1048576 combinations 
  recursive algo with memoization solved in #steps:2838 money@end:84
  iterative algo solved in #steps:3188 money@end:84

simple case 3
  problem has at most 1048576 combinations 
  recursive algo with memoization solved in #steps:2647 money@end:14
  iterative algo solved in #steps:2859 money@end:14
*/
}

- Chris November 22, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

ChrisZ, I cannot leave comment on your post. But I see some problem on your solution
It doesn't say that the player keep the enemy's money when fight. It just says "keep Your money" which doesn't mean player keep the enemy's money but it means the player's money doesn't reduced when fight.
And your algorithm doesn't consider of the facing order(which enemy the player meet first.) The right solution is finding enemies to bride to get enough power to beat the strongest enemy then fight rest of all. It doesn't need DP. Just sort enemies by strength order then check combination which makes the sum of power is greater than (the strongest enemy's power - player's initial power)

- pppz November 19, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

ChrisZ, I cannot leave comment on your post. But I see some problem on your solution
It doesn't say that the player keep the enemy's money when fight. It just says "keep Your money" which doesn't mean player keep the enemy's money but it means the player's money doesn't reduced when fight.
And your algorithm doesn't consider of the facing order(which enemy the player meet first.) The right solution is finding enemies to bride to get enough power to beat the strongest enemy then fight rest of all. It doesn't need DP. Just sort enemies by strength order then check combination which makes the sum of power is greater than (the strongest enemy's power - player's initial power)

- pppz November 19, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@ppz, you are totally right with the money, I oversaw that.
But it doesn't change so much, in my opinion (while it is still a mistake), remove the +m[i] / money[i] from the recursion and the rest stays the same but has now optimization potential. We can still deduce it from knap-sack, it's even easier that way.

I think I consider the order (i in the recursive method) mean, it sais you have to fight them in order, that's what the algo does. So the re-use (memoization) is a certain amount of money and strength at a certain position. If money only decreases or stais the same over time, I think I can get rid of a paramter in the memoization.

could you maybe code your greedy based algo, I can't see how you can do this without trying all options and re-using options you explored.

The problem is, that sometimes one needs to make a local bad decision which still leads to the overal best result and this is difficult with greedy technique.

- Chris November 19, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

Oh, it doesn't mention if the player has to meet the enemies in the given order or the player can decide the order of the enemies which makes the problem totally different. I assumed the player can decide the order. If the player can decide the order, then just bride enemies until the player's strength reaches to the strongest enemy's strength then fight rest of them.
If the player cannot decide the order, then DP will reduce the complexity.
Additionally, it doesn't need to reduce player's strength when it fights.

- pppz November 20, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The enemies must be fought in the order they are given, you cannot choose it.

- camiloni42 November 20, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

camiloni42 what are we expected to optimize for in the solution. Are we trying to find the solution that leaves the character with the maximum money or maximum strength? Please clarify

- divm01986 November 20, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@ divm01986 We need to optimized for maximum money (i.e. spend as little as possible).

- camiloni42 November 21, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The enemies don't have money, they've price. You can either fight with them at cost of your strength or buy their strength. For recursion suggested by chrisM,

/ dp(i+1, s-s[i], m) , if s >= s[i]
dp(i, s, m) = max /  dp(i+1, s+s[i], m-m[i]) , if m >= m[i]
                  \  = -1, if m < m[i] and s < s[i]
				   \ = m, if i == n-1

But I am not clear how comparison happens for max. There are 2 quantities: power and money and how to decide what is optimal: ending war with more power or money?

- vishalsahunitt November 22, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@pppz: But your proposal doesn't consider ordering as well right? What if the strongest opponent is the first one? What if the strongest is the cheapest one? I seriously doubt that there is a better solution than the polynomial one, its like a 0/1 knapsack problem with additional constraints on the order you place elements in your knapsack. Could you maybe explain your strategie in more detail?

- Bernhard November 22, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def buy_cheap_str(str_needed, opponents, cache):
    if str_needed <= 0:
        return 0
        
    key = str(str_needed) + ":" + str(len(opponents))
    if key not in cache:
        opp_1 = opponents[0]
        if len(opponents) == 1:
            if opp_1[0] < str_needed:
                cache[key] = 99999999999
            else:
                cache[key] = opp_1[1]
        else:
            with_opp_1 = buy_cheap_str(str_needed - opp_1[0], opponents[1:], cache) + opp_1[1]
            without_opp_1 = buy_cheap_str(str_needed, opponents[1:], cache)
            cache[key] = min(with_opp_1, without_opp_1)
    
    return cache[key]

def fight(person, opponents):
    sum_str = sum([s for s, p in opponents ])
    
    cur_str = person[0]
    cur_money = person[1]
    
    str_diff = sum_str - cur_str
    str_needed = (str_diff + str_diff%2)/2
    money_spent = buy_cheap_str(str_needed, opponents, dict())
    
    return cur_money - money_spent
    
print fight((100,100), [(107,10),(107,15),(260,40),(52,20)])

- Nitish Garg December 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def fight_planner(monsters, init_strength, init_money):
    options = [(init_strength, init_money,"")]
    for (monster_strength, monster_price) in monsters:
        options_bribe = [(s+monster_strength, m-monster_price, h+", bribe") for (s,m,h) in options if m-monster_price >= 0]
        options_beat = [(s,m,h+", beat") for (s,m,h) in options if s >= monster_strength]
        options = join_options(options_bribe, options_beat)
        if len(options) == 0:
            raise Exception('mission impossible')
    return options[-1]


def join_options(opt1, opt2):
    out = []
    max_money = -1
    while len(opt1) > 0 or len(opt2) > 0:
        if len(opt1) > 0 and len(opt2) > 0:
            if opt1[0][:1] > opt2[0][:1]:
                nxt = opt1.pop(0)
            else:
                nxt = opt2.pop(0)
        elif len(opt1) > 0: nxt = opt1.pop(0)
        else: nxt = opt2.pop(0)
        if nxt[1] > max_money:
            out.append(nxt)
            max_money = nxt[1]
    return out


print fight_planner([(3,12),(3,1),(5,8),(7,12)],4,2)

- Yair January 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def fight_planner(monsters, init_strength, init_money):
    options = [(init_strength, init_money,"")]
    for (monster_strength, monster_price) in monsters:
        options_bribe = [(s+monster_strength, m-monster_price, h+", bribe") for (s,m,h) in options if m-monster_price >= 0]
        options_beat = [(s,m,h+", beat") for (s,m,h) in options if s >= monster_strength]
        options = join_options(options_bribe, options_beat)
        if len(options) == 0:
            raise Exception('mission impossible')
    return options[-1]


def join_options(opt1, opt2):
    out = []
    max_money = -1
    while len(opt1) > 0 or len(opt2) > 0:
        if len(opt1) > 0 and len(opt2) > 0:
            if opt1[0][:1] > opt2[0][:1]:
                nxt = opt1.pop(0)
            else:
                nxt = opt2.pop(0)
        elif len(opt1) > 0: nxt = opt1.pop(0)
        else: nxt = opt2.pop(0)
        if nxt[1] > max_money:
            out.append(nxt)
            max_money = nxt[1]
    return out


print fight_planner([(3,12),(3,1),(5,8),(7,12)],4,2)

- Yair January 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I am confused that what do you mean optimal solution of this problem? Do you mean that we need to make sure the solution ends with largest amount of money(or largest strength)?

- tiandiao123 October 04, 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