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

*at moment 3.*

**key3**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

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.