Google Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
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)
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)
@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.
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.
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?
@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?
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)])
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)
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)
- Chris November 22, 2016