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)).
This formulation is not clear at all. The statement can mean many things.
If it is a substitution cipher to unravel, one can scan a document typed with this keyboard for character frequencies (well-known tables for each human language are available).
More naively, I would type one letter at a time to know the substitution, then operate on words. I do not think that is the real challenge, but as the statement is formulated, I do not see anything forbidding me from doing so.
The keyboard operates a substitution on the letters, and permutations can be decomposed into cycles. Are these cycles the same as the "cycles" mentionned in the statement?
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