“Hard” Google Coding Interview Question: Racecars!

Here’s the problem:

Your car starts at position 0 and speed +1 on an infinite number line. Your car can go into negative positions. Your car drives automatically according to a sequence of instructions 'A' (accelerate) and 'R' (reverse):

When you get an instruction 'A', your car does the following:

position += speed

speed *= 2

When you get an instruction 'R', your car does the following:

If your speed is positive then speed = -1

otherwise speed = 1

Your position stays the same.

For example, after commands "AAR", your car goes to positions 0 --> 1 --> 3 --> 3, and your speed goes to 1 --> 2 --> 4 --> -1.

Given a target position target, return the length of the shortest sequence of instructions to get there.

As an example, say we have a target of 3. Since we always start from position 0, the shortest sequence of instructions is “AA”, our answer is 2. We go from positions 0 -> 1 -> 3.

If we had a target of 6, the answer is 5 (“AAARA”). We go from 0 -> 1 -> 3 -> 7 -> 7 (reversed directions, same position) -> 6.

https://unsplash.com/photos/S9sJUJQAwb8