How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Coinbase.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Coinbase during technical interviews.

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.

Constraints

2 <= height <= 50
1 <= jump_power <= 10
1 <= position < height
-height <= velocity <= height
0 <= coins <= 20
0 <= len(future_coins) <= 40
Each value in future_coins is either -1 or an integer in the range [1, height - 1]

Examples

Input: (10, 3, 1, -1, 1, [-1])

Expected Output: True

Explanation: Without jumping, the character moves to position 0 and loses immediately. With a jump, it spends 1 coin, moves safely upward, and survives the only tick.

Input: (8, 4, 5, 0, 2, [-1, -1])

Expected Output: False

Explanation: Jumping now makes the character move to position 9, which is above the top boundary height = 8. Not jumping survives both ticks.

Input: (10, 3, 2, 0, 1, [5, -1, -1, -1])

Expected Output: True

Explanation: Jumping now reaches height 5 on the first tick, collects the coin, and still survives all 4 ticks. Not jumping can also survive all 4 ticks, but ends with fewer coins, so jumping is optimal.

Input: (10, 3, 5, 0, 2, [])

Expected Output: False

Explanation: There are no future ticks to optimize. Both actions are equivalent, so the strategy should avoid an unnecessary jump.

Input: (7, 3, 1, -1, 0, [3])

Expected Output: False

Explanation: The character has no coins, so a jump request has no effect. Both jump and no-jump lead to immediate loss, so return False on the tie.

Input: (9, 2, 3, 1, 1, [4, 4, -1])

Expected Output: False

Explanation: Not jumping collects the coin at height 4 on the first two ticks and survives all 3 ticks. Jumping now rises too high and cannot survive as long.

Hints

A state is fully determined by the current tick index, position, velocity, and remaining coins. That suggests memoization or dynamic programming.
Instead of storing just whether a state is winning, compare states with a tuple such as (survived_ticks, ending_coins, -successful_jumps_used).

Quick Overview

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.