Race Car

HardDynamic Programming1d dp

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

A car starts at position 0 with speed +1 on an infinite number line (negative positions are allowed). It follows a sequence of two instructions: - A (accelerate): position += speed, then speed *= 2. - R (reverse): if speed is positive it becomes -1, otherwise it becomes +1. Position does not change. Given target, return the length of the shortest instruction sequence that leaves the car exactly at position target. The speed when it arrives does not matter.

Examples

Input: target = 3
Output: 2
"AA" moves the car 0 -> 1 -> 3.
Input: target = 6
Output: 5
"AAARA" goes 0 -> 1 -> 3 -> 7, reverses, then moves back to 6.

Constraints

  • 1 <= target <= 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 1d dp problems