Dynamic Programming - maximum number of A using Ctrl-A, Ctrl-C, Ctrl-V keys (Google interview question)

2 users say they have been asked this quesiton in interview.
Difficulty Level:

Problem Statement

You are given following four keys on a keyboard:
1. print A (print a single character A)
2. Ctrl-A (Select All)
3. Ctrl-C (Copy selected content)
4. Ctrl-V (Append the selected content right next to already printed content)

Pressing any of the above keys is considered a single keystroke. You need to find out the maximum number of A's you can print using N such keystrokes.

Few examples would make things clear:

Input: N = 5, Output = 5.
You can print 'A A A A A' by pressing 'Print A' keystroke 5 times.

Input N = 7, Output = 9.
Using 'Print A' 7 times will only give you - 'A A A A A A A'. But the following combination of keystrokes will give you the maximum number of A's:
 - Use Print A 3 times => 'A A A'
 - Use Ctrl-A, Ctrl-C, Ctrl-V together, it will copy the already printed A's (3 in number) and append 3 more right next to the output making it 6 A's => 'A A A A A A'
 - Use Ctrl-V. This is the tricky - We already have 3 A's copied in the buffer, so to print them out this time you only need to press Ctrl-V once. This will append 3 more A's right next to the above output => 'A A A A A A A A A'
 
Input N = 10, output = 20
The sequence will be - Print A, Print A, Print A, Print A, Print A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V, Ctrl-V


Building the Solution

It is very important to understand the problem statement thoroughly before trying your hands at any kind of solution. Writing out the output sequence for few more cases by hand would really help. The basic idea is that once we have a combination of Ctrl-A, Ctrl-C and Ctrl-V, we can reuse Ctrl-V repeatedly to append the same copied content again and again. Thus with every extra Ctrl-V, we are adding as many A's that are there in the copied buffer with a single keystroke. For example, for N = 7, the first few keystrokes are - Print A, Print A, Print A, Ctrl-A, Ctrl-C, Ctrl-V. After this sequence of 6 keystroke, we have 6 A's in the output with 3 A's still in the copied buffer. Now, with just one more keystroke of Ctrl-V, we can append 3 more characters to the output making it 9 A's.

Now, the next evident question is how many Print A keystrokes are needed before we start the sequence of Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V, Ctrl-V ... Ctrl-V. For that, there is no other option but you need to try all the possibilities. Let us again look at an example to explain it better (N = 10):

  1.  1 Print A, Ctrl-A, Ctrl-C, Ctrl-V, another 6 Ctrl-V => 8 A's
  2.  2 Print A, Ctrl-A, Ctrl-C, Ctrl-V, another 5 Ctrl-V => 14 A's
  3.  3 Print A, Ctrl-A, Ctrl-C, Ctrl-V, another 4 Ctrl-V => 18 A's
  4.  4 Print A, Ctrl-A, Ctrl-C, Ctrl-V, another 3 Ctrl-V => 20 A's
  5.  5 Print A, Ctrl-A, Ctrl-C, Ctrl-V, another 2 Ctrl-V => 20 A's
  6.  6 Print A, Ctrl-A, Ctrl-C, Ctrl-V, another 1 Ctrl-V => 18 A's
  7.  7 Print A, Ctrl-A, Ctrl-C, Ctrl-V  => 14 A's
  8.  8 Print A, after this no other option than to press Print A twice => 10 A's
  9.  9 Print A, after this no other option than to press Print A once more => 10 A's
  10.  10 Print A => 10 A's
  11.  3 Print A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V, Ctrl-A, Ctrl-C, Ctrl-V => 18 A's

... and so on ..

option #1 to option #10 seems the most natural choices, but from where did option #11 came from ?
option #11 stems from the fact that while we were evaluating option #7, we considered that we can get a maximum of only 7 A's for N=7 and then using this value with another combination of (Ctrl-A, Ctrl-C and Ctrl-V) would double that value. But, if you see the examples stated along with the question, the maximum we can get for N=7 is 9 A's and not 7 A's. Hence, this extra case. Similarly we need to evaluate all the other cases.

So, we can see that there is no fixed pattern as such to derive at any conclusion. There is no sure method to tell us whether we have to maximize 'Print A' or 'Ctrl-V', only option as stated above is to try out all the combinations recursively. Things to note:

  •  while we are trying out all the solutions, we need not consider 8, 9, and 10 from the above example, since they all lead us to the same result of printing all A's as we cannot use the full combination of (Ctrl-A, Ctrl-C, Ctrl-V) which requires 3 keystrokes. Using it in partial doesn't help in any way. So, for each N we need to start our search from N-3 down to 1.
  •  For inputs N = 1 to N = 6, the maximum is N itself. We can use this information to put some base case in our solution.

Recursive Solution

combining the above points, we see that we have to break the problem into smaller subproblems and need to solve them individually. The recurrence relation can formally be stated as:

F(N) = MAX(F(j) * (N - j -1)) where N-3 <= j <= 1

Here is the recursive program:

#include <stdio.h>
#include <stdlib.h>

#define N 20

int compute_max(int i);
int main()
{
printf("Maximum A's for %d is %d \n", N, compute_max(N));

return 0;
}

int compute_max(int i)
{
int j;
int max = 0;
int temp;

if (i <= 6)
return i;

for (j = i - 3; j > 0; j--) {
temp = (i - j -1) * compute_max(j);
if (temp > max) {
max = temp;
}
}

return max;
}


Dynamic Programming Solution

A close look at recursive solution shows that we solve same subproblem multiple number of times, leading to an exponential run time.  Check the image below:


Maximum number of A using Ctrl A, Ctrl C and Ctrl V - Dynamic Programming | EduSagar
To get rid of this limitation we seek help from dynamic programming, since this problem exhibits both the properties of dynamic programming - optimal substructure and overlapping subproblem. For this, we will use an extra array which will store the maximum value for a subproblem once it is solved. Later on, whenever we come back to solve the same problem again, we will reuse this value within again trying to evaluate from scratch. This takes up O(n) extra space, but reduces the run time to O(n2). Here is the program:

#include <stdio.h>
#include <stdlib.h>

#define N 20

int compute_max(int i);
int main()
{
int i = 1, j, k, temp;
int arr[N+1];

arr[0] = 0;
for (; i <= 6; i++)
arr[i] = i;

for (; i <= N; i++) {
arr[i] = i;
for (j = i - 3; j > 0; j--) {
temp = (i - j - 1) * arr[j];
if (temp > arr[i])
arr[i] = temp;
}
}

printf("Maximum A's for %d is %d \n", i, arr[N]);

return 0;
}

Dynamic programming solution with O(n) complexity

Let F(x) be the maximum number of A's we can output using x keystrokes. Now consider two possible options available to us once we have F(x):

  • F(x), Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V, Ctrl-V, Ctrl-V, Ctrl-V  => F(x) * 6
  • F(x), Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V  => F(x) * 6


But the later sequence is better, in a sense that the content which is in the copy buffer is 2*F(x) in the second case, while it is F(x) in the first case. So, if we extend this with another keystroke, the later sequence will give F(x) * 8, while the first one will result in F(x) * 7. This gives us an opportunity to optimize the above listed Dynamic Programming solution. Instead of always iterating from N-3 down to 1, we should only consider 4 consecutive Ctrl-V keystrokes to get the maximum number of A's. To achieve the same, replace the inner for loop from previous Dynamic Programming solution to this one:

for (j = i - 3, k = 1; ((k <= 4) && (j > 0)); j--, k++) {
...
}

This reduces the overall complexity from O(n2) to 4*O(n) which is effectively O(n). Do share your thoughts and comments if you feel something amiss.


comments powered by Disqus