## Amazon Interview Question for SDE-2s

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
1
of 1 vote

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...

Comment hidden because of low score. Click to expand.
0
of 0 vote

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 ?

Comment hidden because of low score. Click to expand.
0

the question if given output of a word that was typed from that key board, figure out how many tries you need to do get the word you were trying to type.

Yes you cannot decipher the mapping character by character...

Comment hidden because of low score. Click to expand.
0
of 0 vote

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?

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

If the letters mapped:
a - > b
b - > c
c - > b

Then the algorithm would never make it back to a, it would continuously loop between b and c.

To clarify the question further:
* Can the letters map to themselves? (i.e. a - > a)
* Can the mappings have cycles? (a -> b -> a or a -> b -> c -> b)

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)).

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.