Bag of Tokens

Bag of Tokens

What is this problem about?

The Bag of Tokens interview question is a strategic resource management game. You start with an initial amount of power and zero score. You are given an array of tokens, each with a specific value. You can play a token in two ways:

1. Face-up: If your power is >= token value, lose power and gain 1 score.
2. Face-down: If your score is > 0, lose 1 score and gain power equal to the token's value. The goal is to find the maximum score you can achieve. This Bag of Tokens coding problem is about trading power for score and vice versa.

Why is this asked in interviews?

Companies like Apple and Adobe use this to test a candidate's greedy optimization logic. It requires you to realize that to maximize score, you should buy score with the least power (smallest tokens) and buy power with the least score (largest tokens).

Algorithmic pattern used

This follows the Array, Sorting, Two Pointers, Greedy interview pattern. You sort the tokens and use two pointers. The left pointer represents the smallest tokens (best for gaining score) and the right pointer represents the largest tokens (best for gaining power).

Example explanation

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

1. Sort tokens: [100, 200, 300, 400].
2. Left=0, Right=3: Power (200) >= 100. Play face-up. Score=1, Power=100.
3. Left=1, Right=3: Power (100) < 200. Can't play face-up.
4. Trade score: Use 1 score to play 400 face-down. Score=0, Power=500.
5. Left=1, Right=2: Power (500) >= 200. Play face-up. Score=1, Power=300.
6. Left=2, Right=2: Power (300) >= 300. Play face-up. Score=2, Power=0. Max Score: 2.

Common mistakes candidates make

• Not Sorting: Trying to play tokens in the given order, which is rarely optimal.
• Incomplete Trades: Trading score for power even when there are no tokens left to "buy" with that new power.
• Max Score tracking: Forgetting to keep track of the highest score reached, as the score might decrease in the final steps to gain power that can't be used.

Interview preparation tip

Whenever you have two ways to "spend" and "earn" two different resources, consider sorting the options and using a two-pointer greedy approach to optimize the exchanges.