Bag of Tokens

MediumGreedytwo pointers

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You start with power and a score of 0, plus a bag of tokens with values tokens[i]. Each token may be played **at most once**, in any order, in one of two ways: - **Face up:** if your current power is at least tokens[i], lose tokens[i] power and gain 1 score. - **Face down:** if your current score is at least 1, gain tokens[i] power and lose 1 score. You may stop at any time and do not need to play every token. Return the **largest score** you can hold at any moment.

Examples

Input: tokens = [50], power = 20
Output: 0
You cannot afford the only token face up, and you have no score to play it face down.
Input: tokens = [30,60], power = 40
Output: 1
Play 30 face up (score 1, power 10). Playing 60 face down would drop the score back to 0.
Input: tokens = [10,40,70,100], power = 50
Output: 2
Play 10 and 40 face up (score 2, power 0), 100 face down (score 1, power 100), then 70 face up (score 2).

Constraints

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

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More two pointers problems