## Amazon Interview Question for Applications Developers

Country: United States
Interview Type: In-Person

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

Walk through each word, and insert into trie like directed graph. For each node you keep track of it 'largest' subchild. When you insert a new child for that node, also add an edge between the largest subchild and the new node, and make the new node the largest.

Then do a topological search in the graph.

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

Can you please explain the second step with a small example, ie, what to do after building the directed graph?

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

stackoverflow.com/questions/3123554/question-from-interview-retrieve-alphabetic-order-from-dictionary

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

First create DAG then use topological sort ......

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

Could you explain your question a little bit?

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

Suppose you are given all the dictionary words in the same order like a, ant, ball, cat, do, dog, fog, frock etc.
From these words you know that there are alphabets a, n, t, b, l, c, d, o, g, f, r, k.
You don't know the order of these alphabets before hand.
You will have to find the order of these alphabets based on the order of the given words.
From a and ant you cannot make out anything.
From ant and ball you can make out that a comes before b in the order.
From ball and cat you can make out that b comes before c in the order.
From cat and do you can make out that c comes before d in the order.
From do and dog you cannot make out anything.
From dog and fog you can make out that d comes before f in the order.
From fog and frock you can make out that o comes before r in the order.
From these clues you should make out the order of the alphabets.

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

I have missed out something.
Not necessarily you will be given all the dictionary words, but the words which are sufficient enough to make out the order of the alphabets.
You can always say you cannot make out the order if the words given are not sufficient.

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

From what I understand of the question, a doubly linked list or self balancing BST should work. (My vote would be with doubly linked list though)..
However, from the example you have given, we can interpret order for a,b,c,d,f; but not certain for o,g,r,k. For e.g., we know that r comes after o, but we don't know what comes before o. We need more words for that. Similarly, no info is given about k.
Am I getting the question right?

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

You can always say you cannot make out the order if the words given are not sufficient.

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

From the way OP described it, it really just sounds like a LinkedHashMap...

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

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

1) Create a int array of size 26 and intialize all the elements by 0. Also intialize a counter by 0.
2) Then start reading each word's alphabet and subtract ascii code of 'a'. Eg let the first work be "ball". Then read 'b'- 'a' (which =1). Let this value be x
3) now go to a[x] and check the value there. If the value==0. then a[x]= counter and counter++.
else do not do anything.
4) After reading all the words once we will have the order in which the alphabets appear in those words.

Now create one new character array (say , char solution[])for 26 chars. Which will be the answer.
Read array a[] created above (which has the order of the alphabets) in the following sense:
if a[0]=7, this means alphabet a comes 7th. Therefore go to solution[7] store 'a' and so on.

Thats it!!!!

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.