## Amazon Interview Question

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

**Interview Type:**In-Person

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

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

- dd.vijay January 04, 2019Is 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 ?