The Race Car problem places a car at position 0 with speed 1. It has two instructions: A (accelerate: move by speed, then double speed) and R (reverse: keep position, set speed to 1 in opposite direction). Find the minimum number of instructions to reach a target position. This hard coding problem uses BFS or DP to find the shortest sequence. The dynamic programming interview pattern is the core.
Meta, Amazon, and Google ask this hard problem because it requires careful state-space reasoning — the state is (position, speed) and you want minimum steps to reach (target, any speed). Both BFS (on state space) and DP on position are valid approaches.
DP on position. dp[t] = minimum instructions to reach position t. For each t: either overshoot and reverse back, or undershoot, reverse, and approach from below. Key recurrences: for each number of accelerations n toward target, combine with reversal scenarios. dp[t] = n + 1 + dp[t - (2^n - 1)] (overshoot n steps then come back) or dp[t] = n + 2 + m + dp[2^m - 1 - (t - (2^n - 1))] (undershoot, reverse twice, approach remainder).
target=3. dp[3] via: n=2 (position=3 exactly) → 2 A's. dp[3] = 2.
target=6: need 5 instructions: A,A,A,R,A,R,A... dp[6] = 5.
Race Car is a challenging DP problem with a non-obvious state space. The key insight: to reach any target, you either overshoot with n accelerations then reverse and backtrack, or undershoot, reverse, go back m steps, reverse again, then continue. Enumerate these two cases for each target. Practice BFS on (position, speed) state space as the alternative approach — both deepen understanding of optimal control problems.
