Amazon Interview Question for SDE-2s


Country: United States
Interview Type: In-Person




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 ?

- dd.vijay January 04, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- klausv January 06, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 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...

- Anonymous January 14, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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?

- Yawn January 16, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- klausv February 06, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- Anonymous February 08, 2019 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More