Home » Interview coding problems/challenges

Special Keyboard

Special Keyboard: In this article we are going to see an interview problem that is special keyboard problem and its solution – which has been featured in Amazon interview rounds.
Submitted by Radib Kar, on June 09, 2020

Problem statement:

Imagine you have a special keyboard with four types of keys:

Key 1: Prints 'I' on screen

Key 2: Select whatever printed in screen

Key 3: Copy selection to buffer

Key 4: Append buffer on-screen after what has already been printed. If you can only press the keyboard for N times (with the above four keys), write a program to produce maximum numbers of I's possible to be printed on the screen.

Input:

Input is N, number of times keys can be pressed in total.

Output:

Print maximum number of I's possible to print

Constraints:

1 ≤ N ≤ 75

Example:

Input:
2

Output:
2

Explanation:
We can at most get 2 I's on screen by pressing 
following key sequence Key1, key1.
Pressing other keys have no effect. 
Like key 1, key2 will produce only one I on screen. 

Input:
7

Output:
9

Explanation:
We can at most get 9 I's on screen by pressing 
following key sequence.
Key1, Key1, Key1, Key2, Key3, key4, Key4

I //after pressing key1
I I  //again pressing key 1
I I I //again pressing key1
 
I I I //pressing key2 selects three I's
I I I // pressing key3 copies these three I's to buffer
I I I I I I // pressing key4 appends these three I's 
I I I I I I I I I // pressing key4 again appends these three I's 

Solution Approach:

Basically,

Two things need to be understood to solve this problem

Key4 appends whatever is printed already on screen before 3 key pressing

That means at moment 4,

You can append whatever was printed while moment 1 as to print in moment 4, you need to press key2 at moment 2 and key3 at moment 3.

So, the recursive function can be written as

Let,

F(n) = max number of I’s printed on screen

So, for n>3

F(n) = max(f(j)*(n-j-1)) for 1<=j<=n-3

Where, 
F(j) = already printed characters up to moment j 
and (n-j-1) is number of appending possible   

So, now we need to convert the recursion into DP.

1)  Initialize dp[n+1] like following base value;
2)  for i=0 to n
        dp[i]=i;
3)  Fill the DP table
        for i=4 to n
            for j=i-3 to 1,j--
                dp[i]=max(dp[i],dp[j]*(i-j-1));
            end for
        End for
4)  Return dp[n]

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

int specialKeyboard(int n)
{

    int dp[n + 1];
    for (int i = 0; i <= n; i++)
        dp[i] = i;

    for (int i = 6; i <= n; i++) {
        for (int j = i - 3; j >= 1; j--) {
            dp[i] = std::max(dp[i], dp[j] * (i - j - 1));
        }
    }

    return dp[n];
}

int main()
{
    int t, n, item;

    cout << "Input n, number of times keys to be pressed: ";
    scanf("%d", &n);
    
    cout << "max no of i's got printed: " << specialKeyboard(n) << endl;

    return 0;
}

Output:

Input n, number of times keys to be pressed: 7
max no of i's got printed: 9