## Amazon Interview Question

SDE-2s**Country:**United States

**Interview Type:**In-Person

I get the keys are randomized. Just wanted couple clarifications.

Is the question that given the output of a word that was typed from that key board, figure out the actual word ?

Also, when you say

"a restriction was set you need to type the whole word every time, not go character by character "

Do you mean we are allowed to type words to decipher the mapping just not characters like 'a', 'b', 'c' etc in that order ?

Is there any more information about question? Can we choose which word we type each time?

Just to be clear, the optimal strategy to find what gives us "A" is to type "A", and continuously type whatever we receive until "A" is received. The has expected time of n/H_n, where n is the alphabet size and H_n is the nth Harmonic number (so for n = 26, we have 6.74550306...).

This is because the keys are in a permutation, following the pointers will take us in a cycle back to "A", and the average cycle length in a permutation of length n is n/H_n.

If we type a word ("ABC"), we can use the same strategy but the expected time to finish is reduced because either some letters are in the same cycle (so we are doing it from two places and get the whole cycle faster), or they are not which means it is more likely there are more (i.e. shorter) cycles.

But this doesn't feel like an algorithmic question, so perhaps I've misunderstood?

Hey, I don't know much info about the question. But yes you can choose whatever word you type each time. Your optimal strategy sounds good,

In the second example using the word "ABC", sounds very much like the interviewer explained... that you could find "AB" in the same cycle and "C" in another shorter cycle.

But the main question is how to model this problem in code and get the running complexity. As I said the the interviewer used Graphs to model the cycles. Any idea is appreciated

Well, it does not seem it is very well explained and because of this lack of specs it can be an arbitrary complex problem, let me explain it

The goal is you are able to write the desired word with that keyboard which essentially applies a button to char mapping which is not as expected.

I like the intuition of the Simple Substitution Cipher but actually it is not clear from the problems specs, in fact this is just a special case where the transfer function is deterministic (there is no random component) and stateless

Furthermore, as a function, we might have issues in terms of incomplete domain and co-domain:

- pressing a button we do not see any char is → incomplete domain

- after having pressed all the button we see some chars are not represented (there is no input that produces the desired output char) → incomplete co-domain

A simple experiment to check these assumptions hold could be to print at least 2 times the same word and verify the result is the same

Actually this method does not provide any strong guarantee as if the latent transfer function could be arbitrary complex then this complexity will reflect in the modeling process we are working on, but let’s make things not too complicated and accept the above mentioned assumptions about the transfer function which we consider deterministic and stateless

This is a typical type of questions Amz is asking now a days.. It is straight a question to see how you come up with possible solutions

1> You gotto ask a lotta questions for this. You cannot assume anything

2> Clearly there is a ton of ambiguity here. Are you provided with a mapping? if not how are you able to certainly determine atleast a one key of an alphabhet

3> If you were able to make one work mapping, is it certain that the rest of the letter are just one n one mapping? or it is just a random mapping and you are to find the whole mapping first even before trying to find a word.

Unless you know these questions, there is no way you can progress to determine the rest of the process.

no sure, but what if you traverse a graph (bfs or dfs) which has time complexity O(V+E) where V - vertices, E - edges. During traversal populate your own mapping hash table where key - input from keyboard, value - what's going to be displayed on screen and just map letter to letter (hash map key retrieval O(1)).

Clearly, this is a Simple Substitution Cipher. I'm not a specialist, but take a look on the web (unfortunately, I'm not allowed to put links here) and search cryptoanalysis for simple substitution cipher...

- Anonymous January 14, 2019