“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.

Intuition

Some quick thoughts:

1. This feels like a graph problem — we have states and transitions. A state obviously needs to hold the current position, but it should also hold the *speed* that we have currently. Transitions operate on the current position and the current speed. We’ll use a breadth-first search, since we want to get to the target position with the minimum number of moves.
2. We don’t want to get stuck in cycles. For example, I could give an infinite amount of the instruction “R”, which just reverses my direction but doesn’t move me closer to my target goal, so I need to avoid visiting the same position with the same speed twice.
3. We have some positions which we’ll never use. For an extreme example, say our goal position is 5 — we’d never want to go to, say, a position of 1,000,000, because that’s way over our goal; we’d want to reverse and head back to our target position.

Code

Let’s go over the data structures we’ll need:

• A deque for our breadth-first search ( collections.deque )
• A visited set to store the past states we’ve already seen

We start our queue with the initial position, speed, and a number of steps initialized to 0.

We then execute the BFS, see the code below:

Importantly, we have a pruning condition for the “reverse” condition. If on the next step with our current speed we would be ahead of the target and our speed is still positive, or we’d be behind the target and our speed is negative, then we’d want to reverse. This shrinks the search space and eliminates the unnecessary possibilities described in step 3 above.

Another way to intuit this is use an example; say that pos=target-1(we’re just one away from hitting target), and speed is some really large number. The best move here is to reverse, then reverse again, then accelerate, since the two reverses effectively resets our speed to 1 and keeps our direction the same.

Hope this was helpful and good luck!

For more articles like this, follow me on Medium. Not a member yet? Join the community. Want more software engineering interview guides and coding question tips? Check out all of my writing organized by topic in this article.

If you have any requests for what I should write, please let me know!