Implement a Coin-Constrained Jump Strategy
Company: Coinbase
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Take-home Project
You are implementing an autopilot strategy for a simple side-scrolling jump game.
A character moves forward automatically. On each game tick, your strategy must decide whether the character should jump.
Game rules:
- If the character touches the ground, it loses.
- If the character goes above the top boundary, it loses.
- The map contains coins. When the character collides with a coin, the coin is collected and the score increases.
- Every jump costs one coin.
- If the strategy attempts to jump when the character has no coins left, the jump cannot happen; the character will continue falling and may lose.
There are therefore three main failure modes:
1. Hitting the top boundary.
2. Hitting the ground.
3. Running out of coins when a jump is needed.
Implement a strategy function that, given the current game state, returns whether the character should jump on this tick. The strategy should keep the character alive as long as possible while collecting coins and avoiding unnecessary jumps.
Your implementation should reason about the current vertical position, vertical velocity, remaining coins, nearby collectible coins, and the risk of hitting the top or bottom boundary.
Quick Answer: This question evaluates a candidate's ability to design a stateful decision-making strategy combining physics-based motion reasoning, resource-constrained planning, and collision/constraint handling.
You are given the current state of a side-scrolling jump game and a lookahead window for the next few ticks. Your task is to decide whether the strategy should request a jump on the current tick.
The character moves one column forward every tick. Vertical motion is governed by the following rules:
1. If the strategy requests a jump and the character has at least 1 coin, it spends 1 coin and its vertical velocity increases by jump_power.
2. The character then moves vertically: position += velocity.
3. If the new position is less than or equal to 0, the character hits the ground and loses.
4. If the new position is greater than or equal to height, the character hits the top boundary and loses.
5. If still alive, the character may collect the coin in the current upcoming column. future_coins[i] gives the coin height for tick i + 1, or -1 if there is no coin in that column. A coin is collected only if the character's position exactly matches that height.
6. Gravity is then applied: velocity -= 1.
Safe vertical positions are therefore 1 through height - 1.
You must return whether jumping now is better than not jumping now, assuming that after this tick the strategy will act optimally for the rest of the lookahead window.
Compare outcomes in this order:
1. Survive more ticks within the lookahead window.
2. If tied, end with more coins.
3. If still tied, use fewer successful jumps.
4. If still tied, return False to avoid an unnecessary jump.
A jump request when coins = 0 has no effect.