Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
this will work :
have a list of words in a file handy, this will help :
save it in a file with name "SortAlphabets.in" ( or change the code, whatever suits your fancy, but see that it has enough words ) and put it in the same directory
here's the java code :
import java.util.*;
import java.io.*;
class SortAlphabets{
static ArrayList<String> list = new ArrayList<String>();
static HashSet<Character> charSet = new HashSet<Character>();
static ArrayList<Character> charList;
static int a[][];
static int charSetSize;
public static void process ( String str1 , String str2 ){
// find the first character of disagreement
int count = 0;
while ( count < str1.length() && count < str2.length() && str1.charAt(count) == str2.charAt(count) )
count++;
if ( count == str1.length() || count == str2.length() ) // when one is substring of another
return;
a[charList.indexOf(str1.charAt(count))][charList.indexOf(str2.charAt(count))]=-1;
a[charList.indexOf(str2.charAt(count))][charList.indexOf(str1.charAt(count))]=1;
}
public static void printMatrix(){
int i,j;
for ( i=0 ; i<charSetSize ; i++ ){
for ( j=0 ; j<charSetSize ; j++ )
System.out.format("%3d ",a[i][j]);
System.out.print("\n");
}
}
public static void main(String[] args){
int i,j,k;
// read a file and store things into arrays
try {
File ip = new File("SortAlphabets.in");
FileReader reader = new FileReader(ip);
BufferedReader bf = new BufferedReader(reader);
String line;
while ( (line = bf.readLine() ) != null ){
for ( i=0 ; i<((String)line).length() ; i++ )
charSet.add(line.charAt(i));
list.add(line);
}
} catch (Exception e){
System.out.println("some error"+e.getMessage());
}
charList = new ArrayList<Character>(charSet);
// "list" contains all the words
// "charSet" , "charList" contains the exhaustive set of characters.
charSetSize=charSet.size();
a = new int[charSetSize][charSetSize]; // the matrix contains relation of each character with all others
/* convention of the 2d matrix :
0 - equal
1 - a[i][j] = 1 , then charSet[i] > charSet[j]
-1 - a[i][j] = -1 , then charSet[i] < charSet[j]
2 - still unknown
*/
// initialize
for ( i=0 ; i<charSetSize ; i++ )
for ( j=0 ; j<charSetSize ; j++ ){
if ( i==j )
a[i][j]=0;
else
a[i][j]=2;
}
//System.out.println(charSet);
// for each word in the list , process.
String first,second;
Iterator itr = list.iterator();
first = (String)itr.next();
while ( itr.hasNext() ){
second=(String)itr.next();
process(first,second);
first=second;
}
//***************************************
// use dynamic programming to establish relation between all.
for ( i=0 ; i<charSetSize ; i++ )
for ( j=0 ; j<charSetSize ; j++ )
for ( k=0 ; k<charSetSize ; k++ ){
if ( k==i || j==i )
continue;
if ( a[i][j] == 1 && a[k][i] == 1 )
a[k][j]=1;
else if ( a[i][j] == -1 && a[k][i] == -1 )
a[k][j]=-1;
}
//printMatrix();
// check if order has been established between all
boolean flag=false;
for ( i=0 ; i<charSetSize ; i++ )
for ( j=i ; j<charSetSize ; j++ )
if ( a[i][j] == 2 ){
flag=true;
System.out.println("order could not be established between : "+charList.get(i)+" and "+charList.get(j));
}
if ( flag )
return;
// create the HashMap , key = sum of each row of a , value = character
HashMap<Integer,Character> hm = new HashMap<Integer,Character>();
for ( i=0 ; i<charSetSize ; i++ ){
k=0;
for ( j=0 ; j<charSetSize ; j++ )
k+=a[i][j];
hm.put(k,charList.get(i));
}
// get a list of keys , sort and print
ArrayList<Integer> mapKeys = new ArrayList<Integer>(hm.keySet());
Collections.sort(mapKeys);
itr = mapKeys.iterator();
while ( itr.hasNext()){
System.out.println(hm.get(itr.next()));
}
}
}
sure,
first let us understand the problem clearly.
you are given a set of words, in lexical order ( i.e. the order in which they will appear in a dictionary )
find the order of the alphabets.
( we're in a time when ascii was not invented yet )
some facts :
given two words in a dictionary, there's only one position common to both words that decides the precedence.
that actually is based on the precedence of the character at that position.
for eg take the words :
something, funny.
the position is 0 ,
and funny < something because f < s
another ,
something, silly
position = 1;
and silly < something because i < o
The first thing we want to do is find all the unique characters from the list. Then find their order.
we are up to taking two words a time and finding those characters that decide the precedence , and then recording the fact
into a table.
say we found 4 unique characters in a certain language, ch1 , ch2 , ch3 and ch4
then we processed some words of the language given in order and got the following table :
ch1 ch2 ch3 ch4
ch1 0 -1 -1 1
ch2 1 0 2 2
ch3 1 2 0 2
ch4 -1 2 2 0
here array[ch1][ch2] = -1 means ch1 < ch2
array[ch3][ch1] = 1 means ch3 > ch1
array[ch2][ch3] = 2 means order is still unknown
array[ch1][ch1] = 0 ; ch1 = ch1
therefore
ch1 < ch2
ch1 < ch3
ch4 < ch1
now a catch :
ch1 < ch2 , ch4 < ch1 implies :
ch4 < ch1 < ch2 implies ch4 < ch2
But what logic do we use to update the in the table ?
Sure Brute force would do, but there's a better way.
These kinds of problems can be solved using dynamic programming.
Remember our college ada book ?
You'd want to read Dynamic programming section and the Warshall's and Floyd's algorithm.
in short,
if a < b , then a < ( everything > b )
and if a > b then a > ( everyting < b )
so the table now becomes :
ch1 ch2 ch3 ch4
ch1 0 -1 -1 1
ch2 1 0 2 1
ch3 1 2 0 1
ch4 -1 -1 -1 0
order still could not be established between ch3 and ch2,
we need to process some more words
say we did and the table now is :
ch1 ch2 ch3 ch4
ch1 0 -1 -1 1
ch2 1 0 1 1
ch3 1 -1 0 1
ch4 -1 -1 -1 0
find the sum of each row.
ch1 -1
ch2 3
ch3 1
ch4 -3
order them :
ch4 < ch1 < ch3 < ch2 is your answer.
and don't worry, you wont get conflicts with the sum :P
P.S.
An idea, like a ghost ... must be spoken to a little before it will explain itself.
-Charles Dickens
Since words are in order take the first letter of each word store them
do this for all letter
finally merge them remove the duplicate... it will be more clear if u can give some eg
Example:
suppose words are: 1. $ @ !
2. @ ^ (
3. ! ^ (
then order will be: $ @ ! ^ (
check your soln for : 1. $ @ !
2. @ ^ (
3. ! ) *
4. ) * ^
It might be the case where number of words given in the input are not enough to give a clear sign of precedence.
e.g w1="! @ $", w2="! @ % " , w3="! ^ & ".
Its clear that ! < @ < $, and @ < %. But we can't yet compare $ and %.
Simlarly, we ^ & @ $ % all these 5 characters are incomparable.
This gives an intuition of a precedence graph like structure for problem solving, where are directed edge from A->B means that A precedes B. Unrelated nodes don't have a precedence relationship directly or transitively.
import java.util.*;
public class Lex1{
static HashMap<Character,HashSet<Character>> charhashSet = new HashMap<Character,HashSet<Character>>();
static Set<Character> notroot = new HashSet<Character>();
public static void process(String first,String second){
int i=0;
while(i<first.length() && i<second.length() && first.charAt(i) ==second.charAt(i)){
//if(first.charAt(i) == second.charAt(i))
i++;
//else break;
}
System.out.println(first + " "+ second+ " "+" diff at " +i);
if(charhashSet.containsKey(first.charAt(i)))
charhashSet.get(first.charAt(i)).add(second.charAt(i));
else{
HashSet<Character> list = new HashSet<Character>();
list.add(second.charAt(i));
charhashSet.put(first.charAt(i),list);
}
notroot.add(second.charAt(i));
}
public static Character getUnvisited(Character current){
HashSet<Character> list = charhashSet.get(current);
if(list == null || list.isEmpty())
return null;
else{
Iterator it = list.iterator();
Character c = (Character)it.next();
list.remove(c);
return c;
}
}
public static ArrayList<Character> topologySort(){
//Set<Character> root = charHashSet.getKey()
Character root = null;
for(Character c:charhashSet.keySet()){
if(!notroot.contains(c)){
root = c;
//root.add(c);
break;
}
}
if(root==null)
return null;
Stack<Character> stack = new Stack<Character>();
//stack.push(root);
Character current = root;
ArrayList<Character> result = new ArrayList<Character>();
while(true){
Character c = getUnvisited(current);
if(c!=null){
stack.push(current);
current = c;
}else{
//System.out.print(current + " ");
result.add(current);
if(!stack.empty())
current = stack.pop();
else
break;
}
}
return result;
}
public static void lex(ArrayList<String> words){
Iterator it = words.iterator();
String first = (String)it.next();
String second;
while(it.hasNext()){
second = (String)it.next();
process(first,second);
first = second;
}
System.out.println(charhashSet);
ArrayList<Character> result = topologySort();
int i=result.size()-1;
System.out.print(result.get(i--));
while(i>=0){
System.out.print(" -> " +result.get(i));
i--;
}
System.out.println("");
}
public static void main(String[] args){
ArrayList<String> words = new ArrayList<String>();
for(String word:args)
words.add(word);
lex(words);
}
}
Using DAG, topology sort
store the alphabet in a linked list (easy insertion )
start by storing the first letters of each word in order - for example - apple bad dog store - a,b,d in the linked list
maintain a pointer to the previous word as you go to the next one - if it starts with the same letter as the previous one then storet he 2nd letters of each in order in the linked list(thiese may unconnected list fragments) from- act, apple, bad, dog - we get the fragments - A,B, D and C,P
we may need to use a hash table to store indexes to the linked list nodes
Form a directed graph with edges (u,v) where 'u' belongs to Word1 and 'v' belongs to Word2 such that word1 and word2's first different character is u and v respectively and word1 < word2 in lexical ordering. Now perform topological sort and the result is the lexical ordered alphabets. Note if enough words are not given, we cannot establish lexical ordering for all alphabets.
- Anonymous March 25, 2012