Amazon Interview Question Applications Developers
Country: United States
Interview Type: In-Person
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.
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.
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?
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!!!!
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.
- Anonymous August 30, 2012Then do a topological search in the graph.