Given a string of L, M, R, where L means turn to left, R means turn to right and M means take 1 step forward where you are directed, starting from the origin, and assuming one letter in the string is wrong, what is the maximum distance that can be reached if you follow the path as instructed in the string?

Question

Accepted Answer

The maximum distance that can be reached if one instruction in a string of L, M, R is wrong.

The maximum distance can be reached by following the correct instructions and then taking the opposite direction of the wrong instruction.
For example, if the string is 'LMRM', the correct path would be 'LMR' and then taking a step in the opposite direction of 'M'.
Calculate the distance by summing up the steps taken in the correct path and subtracting the step taken in the wrong direction.

Accepted Answer

This is an interesting problem that can be solved by using dynamic programming. Here's a step-by-step approach:

1. Define the state:

We can define the state as dp[i][j], where i represents the current position along the x-axis and j represents the current position along the y-axis. The value stored in dp[i][j] will be the maximum distance that can be reached from the origin (0, 0) to the point (i, j) assuming that there is at most one wrong instruction in the string.

2. Initialize the base case:

dp[0][0] = 0, as we start from the origin.

3. Recurrence relation:

We can calculate the value of dp[i][j] based on the values of dp[i-1][j], dp[i][j-1], dp[i+1][j], and dp[i][j+1]. If the current instruction is correct, we simply take the maximum of these four values and add 1. If the current instruction is wrong, we take the maximum of these four values and add 1, but we also need to consider the possibility that the wrong instruction might have occurred earlier in the string. To do this, we can subtract 2 from the maximum value, as we would have taken an extra step in the wrong direction.

4. Iterate through the string:

We can iterate through the string, updating the dp table based on the current instruction.

Google Software Engineer interview questions & answers

Popular interview questions of Software Engineer

Top HR questions asked in Google Software Engineer