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