Bag of Tokens Interview Question for Google

You are given an initial power of power, an initial score of 0, and a bag of tokens given as an integer array tokens, where each tokens[i] denotes the value of token*_i*.

Your goal is to maximize the total score by strategically playing these tokens. In one move, you can play an unplayed token in one of the two ways (but not both for the same token):

Face-up: If your current power is at least tokens[i], you may play token*_i*, losing tokens[i] power and gaining 1 score.
Face-down: If your current score is at least 1, you may play token*_i*, gaining tokens[i] power and losing 1 score.

Return the maximum possible score you can achieve after playing any number of tokens.

Example 1:

tokens = [100], power = 50

Output: 0

Explanation: Since your score is 0 initially, you cannot play the token face-down. You also cannot play it face-up since your power (50) is less than tokens[0] (100).

Example 2:

tokens = [200,100], power = 150

Output: 1

Explanation: Play token*₁* (100) face-up, reducing your power to 50 and increasing your score to 1.

There is no need to play token*₀*, since you cannot play it face-up to add to your score. The maximum score achievable is 1.

Example 3:

tokens = [100,200,300,400], power = 200

Output: 2

Explanation: Play the tokens in this order to get a score of 2:

Play token*₀* (100) face-up, reducing power to 100 and increasing score to 1.
Play token*₃* (400) face-down, increasing power to 500 and reducing score to 0.
Play token*₁* (200) face-up, reducing power to 300 and increasing score to 1.
Play token*₂* (300) face-up, reducing power to 0 and increasing score to 2.

Constraints:

0 <= tokens.length <= 1000
0 <= tokens[i], power < 10^4

Naive Solution

A brute-force approach would involve exploring all possible combinations of playing tokens face-up or face-down and keeping track of the maximum score achieved. This can be done using recursion. However, this approach is not efficient.

Complexity Analysis

Time Complexity: O(2^n), where n is the number of tokens. This is because each token can be played in two ways (face-up or face-down).

Space Complexity: O(n) due to the recursion depth.

Optimal Solution: Greedy Approach

To maximize the score, we should use a greedy approach. Sort the tokens in ascending order. Then, try to play the smallest tokens face-up to gain score. If the power is not enough to play the smallest token face-up, and if we have a score greater than 0, then play the largest token face-down to gain power. This way, we can maximize our score.

Algorithm

Sort the tokens in ascending order.

Initialize power, score, left (0), and right (tokens.length - 1).

While left <= right:

If power >= tokens[left], play the token face-up:
- power -= tokens[left]
- score += 1
- left += 1
- Update maxScore = max(maxScore, score)
Else, if score > 0:
- Play the token face-down:
  - power += tokens[right]
  - score -= 1
  - right -= 1
Else:
- Break (cannot play any more tokens).

Return maxScore

Code

import java.util.Arrays; class Solution { public int bagOfTokensScore(int[] tokens, int power) { Arrays.sort(tokens); int score = 0; int maxScore = 0; int left = 0; int right = tokens.length - 1; while (left <= right) { if (power >= tokens[left]) { power -= tokens[left]; score++; left++; maxScore = Math.max(maxScore, score); } else if (score > 0) { power += tokens[right]; score--; right--; } else { break; } } return maxScore; } }

Complexity Analysis

Time Complexity: O(n log n), where n is the number of tokens. This is due to the sorting step.

Space Complexity: O(1). We are using constant extra space.

Edge Cases

Empty tokens array: return 0.

Initial power is less than the smallest token and initial score is 0: return 0.

All tokens can be played face-up: return tokens.length.