Here is a question that was asked in a contest hosted by indeed in www.hackerearth.com
I need to know how to do such kind of problems
Indeed wants to add a new feature on their website to help the searching process. They want to add a new keyboard to type strings in minimum time. They hired you as developer and explained the problem to you.
You are given a string to type and you need to design a keyboard such that the total time taken to type the string is minimised.
The keyboard consists of 3 rows and 21 columns i.e 63 keys.These 63 keys include all the 26 lowercase alphabets, 26 uppercase alphabets, 10 numeric keys and 1 key for space.
If you are at the key (x,y) and you want to press the key at position (z,w) then the time taken will be abs(x−z)+abs(w−y).
NOTE: Initially your finger is at (1,1).
There is only one line of input that corresponds to the sentence X that is to be typed.
X may contain spaces in between
In the output you need to provide a matrix of size
3×21 that corresponds to the size of the keyboard that is to be formed. There should not be any key repeated and all the 63 symbols should be there. For space you need to output .(dot).
Length of string
X = 1e5 for all the test cases.
Suppose that the time taken to type the sentence is
T then your score will be
T and your aim should be to minimise this score
aA0bB1cC2dD3eE4fF5gG6 hH7iI8jJ9kKlLmMnNoOpP qQrRsStTuUvVwWxXyYzZ.
The keyboard that has been generated in the output may not be the best arrangement that leads to minimized time, but it is a valid answer.