How to Answer: Create the card-power game.
Advice and answer examples written specifically for a Java Intermediate Level Greedy job interview.
2. Create the card-power game.
This question shows the developer's ability to work with Java integers and arrays.
You invent a new single-player game- “The card-power gameâ€. In this game, you are given an integer power and an array of cards initially. The value of cards[i] denotes the power required to play the ith card. Your score is 0 initially. You play a series of moves to maximize your score.
In one move, you choose the ith card with power cards[i]. You can play one in two ways:
1. Play card face up:- If your current power is at least cards[i], you play the ith card face up. Your power decreases by cards[i] and you gain 1 score.
2. Play card face down:- If your current score is at least 1, you play the ith card face down. Your power increases by cards[i] and you lose 1 score.
You can play a card at most once in any order. It may be the case that you don’t play some cards. Return your maximized score.
/*Example*/
Given: cards = [100, 200, 300, 400] power = 200
Expected output: 2
Explanation:
1. Play 0th card face up power = 100 score = 1
2. Play 3rd card face down power = 500 score = 0
3. Play 1st card face up power = 300 score = 1
4. Play 2nd card face up power = 0 score = 2
Solution:
We will play cards face up and face down greedily. First of all, we will sort the cards with their power in increasing order. We will play cards face up starting from the lowest power. If we need more power, we will play the card face down with the highest power.
class Solution {
public int maxScore(int[] cards, int power) {
Arrays.sort(cards);
int left = 0;
int right = cards.length - 1;
int score = 0;
int ans = 0;
while(left <= right && (power >= cards[left] || score > 0)) {
// we have enough power to play lower cards face up
// this will reduce power and increase score by 1
while(left <= right && power >= cards[left]) {
power -= cards[left];
left++;
score++;
}
ans = Math.max(ans, score);
// play a higher card face down to increase power
if (left <= right && score > 0) {
power += cards[right];
right--;
score--;
}
}
return ans;
}
}
Time complexity- O(n logn) // to sort the array
Space complexity- O(1)
Written by S. Kumar on June 27th, 2021