Google Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Phone Interview
Graph creation:
struct Node{
char val;
Node*[] list;
};
Start from the first pair in the dictionary. Compare two strings in this pair. When I am comparing two consecutive strings then i should compare till first mismatch.
Eg: aad & aab, in this case create an edge d -> b
then go to that character's node "list" (here node list of char "d") and if the new character (char "b") to be linked is not already present then add it....Do the above steps for all the consecutive pairs in the dictionary.
Finally do topological sort in the following way to return precedence of characters OR error in case the graph has a cycle (cycle in case of wrong input)!
L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
remove a node n from S
insert n into L
for each node m with an edge e from n to m do
remove edge e from the graph
if m has no other incoming edges then
insert m into S
if graph has edges then
return error (graph has at least one cycle)
else
return L (a topologically sorted order)
Graph creation:
struct Node{
char val;
Node*[] list;
};
Start from the first pair in the dictionary. Compare two strings in this pair. When I am comparing two consecutive strings then i should compare till first mismatch.
Eg: aad & aab, in this case create an edge d -> b
then go to that character's node "list" (here node list of char "d") and if the new character (char "b") to be linked is not already present then add it....Do the above steps for all the consecutive pairs in the dictionary.
Finally do topological sort in the following way to return precedence of characters OR error in case the graph has a cycle (cycle in case of wrong input)!
L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
remove a node n from S
insert n into L
for each node m with an edge e from n to m do
remove edge e from the graph
if m has no other incoming edges then
insert m into S
if graph has edges then
return error (graph has at least one cycle)
else
return L (a topologically sorted order)
This is a great problem. I really don't like (or perhaps don't fully comprehend) the answers given on this thread. Let's dig deeper on this one and explore:
Problem restatement:
There exists an alphabet comprising some number of characters.
The order of the alphabet, i.e. the full-ordering, is not known.
You are given a list of "words" comprised of characters from the alphabet.
The list of words is given to be sorted in lexicographical order.
Write a program to deduce the order of the alphabet.
For the sake of example, let's assume that we're using an English alphabet (i.e. we know the full order). Now assume we have a set of words sorted in ascending lexicographical order:
aardvark
ant
bee
cat
cow
dog
horse
llama
sheep
zebra
Given that we know the order of the English alphabet, it's easy to see that the list of animals comprising our input data is correctly sorted.
Now forget that you know anything at all about the English alphabet. Erase from your mind the fact that you know which characters comprise the alphabet (the problem statement doesn't bound the set of characters or make any guarantee that the set of words use all characters in the alphabet). Also, erase from your mind the fact that you know the order of the English alphabet.
Let's take the first word "aardvark". What does this tell us? It tells us that the characters "a", "r", "d", "v", and "k" are present in the alphabet. Does it provide any information that can be used to establish the order of these characters? NO! Remember that it's the order of the words in the list and thus comparisons between adjacent words in the list that provides clues about the order of the alphabet.
Okay, now let's look at the first and second words:
aardvark
ant
What does this tell us? We see two new characters "n" and "t" by inspection of "ant". What's more we notice that the characters in the first column are both "a". So clearly the lexicographical ordering of these two words wasn't decided on the basis of the first column. Looking at the second column we note that the characters are different and correctly conclude that in our alphabet "a" proceeds "n".
How about the third column? Sorry, no more clues here. We know that the order of "aardvark" and "ant" was decided on the basis of the second column character and cannot deduce anything further by comparing the third column.
So on we go through the list of animal words... Below I've reproduced the lexicographically sorted list of words in the left column, and indicate the "clues" in the right column. For simplicity I'm not going to list new characters discovered in the alphabet but rather focus only on clues about the order of the characters in the alphabet.
Note that because you actually do know the order of the English alphabet, you can easily vet this information without doing insane mental gymnastics. Also note that by convention an order clue is indicated by an ordered pair representing an edge in a directed graph. For example (a,b) indicates a directed edge from tail vertex "a" to head vertex "b" indicating that "a" proceeds "b" in the alphabet.
aardvark no order clues
ant (a,n) based on column 2
bee (a,b) based on column 1
cat (b,c) based on column 1
cow (a,o) based on column 2
dog (c,d) based on column 1
horse (d,h) based on column 1
llama (h,l) based on column 1
sheep (l,s) based on column 1
zebra (s,z) based on column 1
n
/
a -> b -> c -> d -> h -> l -> s -> z
\
o
Now remember that you know the order of the English alphabet and vet this graph. Makes sense right? For example we know that "n" comes after "a" as does "b" and "o". And clearly a -> b -> c -> d -> h -> l -> s -> z is correctly ordered.
Note that given our sorted list of animals we do not know the order of "b", "n" and "o". All we know is that they follow "a".
Also note that there are bunch of characters used in our list of animal words for which no clues were found. These are not show in the ASCII graph above. But these are really in the graph too (all with zero in-degree).
I seriously question the utility of doing a topological sort... It would produce a somewhat interesting result BUT is essentially meaningless except in the case that every vertex has out-degree one.
You could imagine a system that attempts to deduce ordering on an alphabet that exposes an interface DoesXProceedY(x, y) which returns YES, NO or KNOWN. Such a system could not (in general) use a topological sort of the graph to deduce the correct answer. Instead, it would need the graph topology.
Hope this helps.
Thanks. I think DAG is the way to go. But as I see from here http://en.wikipedia.org/wiki/Topological_sorting after DAG, I think we can sort by DFS to find the sorted order as the solution by Topological Sort is not necessarily unique as it depends on random node u pick for the sorting. Correct if I am wrong.
If you do not get a unique ordering, then there are multiple possible orderings.
For instance {a,b,c,d}
a > b, b > c.
Any of the following a b c d, d a b c, a d b c is a perfectly valid ordering given the constraints.
This question has been asked many times before. I've already reported as duplicate.
1. Create a DAG from letters by comparing each word with the next. Since the word list is sorted, comparing the letters by location, gives which letter comes before the other.
2. Topological sort of the DAG will give you the order of the letters in the alphabet
"precedence order on the alphabet set " - can somebody please explain this.
and if the words are coming in sorted order what is the criterion for the ordering of the words.
if the ordering of words are Lexicographic order then final output of the algo by mpmaster doesn't look okay.
please correct me if i am wrong.
@Addy
I think by precedence order we are asked to find the final sorted order of the set. For eg, we know A is greater than B, but in the given set we do not know the order. We have to find the order of the set based on a set of sorted words given to us. I am not clearly understanding Lexicographic order part and how this would fail.
It would be great if you can give more insight on this.
what i mean by lexographic order is alphabetic or dictionary order http://en.wikipedia.org/wiki/Lexicographical_order.
and what i mean to say is
say these words are in sorted order
$, *
!, &
*, #
&, $, @
#, @
and you say the final precedence is( !, &, $, *, #), but if this is the precedence then "&, $, @" should be in the 2nd number in the list. because there can't be a word starting with a lower precedence(! or *) before '&' , if the word list is sorted.
Yes, Loler is right. At least thats what I had in mind (when posting the question). To elaborate the sol.
Constructing the dag - {for now lets assume its english lang we are dealing with)
Consider a pair of words in the list with w1 < w2. We can draw a small edge between letters which come after common prefix. For eg. disgruntled < disinterested. Then g-->i.
This will form a dag. Top sort it.
Note that this graph may not be connected. In which case our dataset is insufficient to deduce complete order of the alphabetset from. Though you can have isolated pockets of letters with order defined.
now the question is how to create that graph... here is my approach:
example:
given words:
acd
ab
cbe
de
every position in word gives a list of sort alphabets. so we have k (max number of characters in longest word given as input) so here k=3
while charplace<k
..for all given words word[i]
....go through charater in word at position k and place this in already built graph remembering that it comes after the character in earlier words[0-i][k] at position k
so here is how it works.
after first iteration: (a->c, c->d)=> a->c->d
after 2nd iteration: a->c->d and a->c->b->e (cant wirte like graph here)
after 3rd iteration: a->c->d->e and a->c->b->e
after topological sorting u will get: a c b/d e (2 answers)
if we had one more word like: bd then this wil give only one answer: a c b d e
I am still confused. Can someone help ?
"You are then given a set of words coming from the language in the sorted order"
- List of word sorted ( acb,cba, bca) or word itself is sorted (abc,bc, c) or both (a, ab,bc, abc) ???
Case 1 :
Traversing the array and create an edge between two alphabet with distance 1 or infinite(if unknown)
Traversing the array would give you a acyclic traversal with covering all nodes., other there is no unique solution to the problem.
Case 2 Assuming words are sorted
Then each word is a graph, clubbed together all the word to form a unified graph.
Perform topological sort
Please help me understand the question and its probable solution.
Thanks
Ankush
Hi Ankush
Words come in a sorted order, not the characters inside the words, so I guess you are right in considering the approach one.
In approach 1, for example, there can be words like:
cab
dab
adc
From these three words, we can conclude the following:
c+a+b<d+a+b<a+d+c
which means
c<d,b<c,b<d
i.e b<c<d, but we do not know about a yet.
If another word comes say, bcd
then, by comparing last 2 words, we can get a<b
Therefore: a<b<c<d.
Given any 2 words, compare the characters lexicographically and come up with a solution.
-- > Construct a Graph . Check for cycles . In case of cycles , no solution exists .
---> Topological Sort of the DAG is the answer .
public static String sortBasedOnKey(String sort, String key)
{
String result = "";
int[] count = new int[key.length()];
for (char ch:sort.toCharArray())
{
boolean isKey = false;
for (int i=0;i<key.length();i++)
{
if (key.charAt(i) == ch)
{
count[i]++;
isKey = true;
}
}
if (!isKey)
{
result +=ch;
}
}
for (int i = count.length-1;i>=0;i--)
{
for (int j=0;j<count[i];j++)
{
result = key.charAt(i)+result;
}
}
return result;
}
//====define the graph
public class Node {
public char value;
public List<Node> ajacent;
public String color;
public Node(char value) {
this.value = value;
this.ajacent = new ArrayList<Node>();
this.color = "white";
}
}
public Node buildG(String[] strings) {
Node root = null;
Node current = null;
for(int i=0;i<strings.length;i++) {
char[] charArr = strings.charArray();
if(i == 0) {
root = current;
}
addAjacent(root,charArr,current);
current = new Node(charArr[0]);
}
return root;
}
public void addAjacent(Node root, char[] chars, Node current) {
if(root == null) {
return;
}
ArrayList<Node> nodelist = new ArrayList<Node>();
for(int i=0;i<chars.length - 1;i--) {
Node oldNode = findNOde(chars[i],root);
if(oldNode != null) {
nodelist.add(oldNode);
} else {
Node newNode = new Node(chars[i]);
nodelist.add(newNode);
}
}
for(int i=0;i<nodelist.size();i++){
List<Node> ajacent = new ArrayList<Node>();
for(int j=i+1;j<nodelist.size();j++) {
ajacent.add(nodelist.get(j));
}
nodelist.get(i).ajacent = ajacent;
}
if(current != null) {
current.ajacent.add(nodelist.get(0));
}
nodelist.clear();
}
public Node findNOde(char value,Node root) {
if(root.value == value) {
return root;
} else {
root.color = grey;
}
for(Node node:root.ajacent) {
if(node.color.equals("white") {
return findNode(value,node);
}
}
root.color = "black";
refreshStatus(root);
return null;
}
public void refreshStatus(Node root) {
for(Node node:root.ajacent) {
node.color = "white";
refreshStatus(node);
}
}
//====find the precedence
public List<Character> findPrecedence(char value,Node root) {
List<Character> precedences = new ArrayList<Character>();
root.color = "grey";
for(Node node:root.ajacent) {
if(node.value == value) {
precedences.add(root.value);
} else {
if(node.color.equals("white")){
List<Character> subpres = findPrecedence(value,node);
node.color = "grey";
precedences.copyAll(subpres);
}
}
}
return precedences;
}
Is the following an accurate re-statement of the problem?
There exists an alphabet comprising some number of characters.
The order of the alphabet, i.e. the full-ordering, is not known.
You are given a list of "words" comprised of characters from the alphabet.
The list of words is given to be sorted in lexicographical order.
Write a program to deduce the order of the alphabet.
Bonus:
1. What is the space/time complexity of your algorithm?
2. Given the problem statement, is it possible to deduce the full (complete) order of the alphabet? Explain your answer in detail.
Graph creation:
struct Node{
char val;
Node*[] list;
};
Start from the first pair in the dictionary. Compare two strings in this pair. When I am comparing two consecutive strings then i should compare till first mismatch.
Eg: aad & aab, in this case create an edge d -> b
then go to that character's node "list" (here node list of char "d") and if the new character (char "b") to be linked is not already present then add it....Do the above steps for all the consecutive pairs in the dictionary.
Finally do topological sort in the following way to return precedence of characters OR error in case the graph has a cycle (cycle in case of wrong input)!
L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
remove a node n from S
insert n into L
for each node m with an edge e from n to m do
remove edge e from the graph
if m has no other incoming edges then
insert m into S
if graph has edges then
return error (graph has at least one cycle)
else
return L (a topologically sorted order)
How to we find the initial set S ?, if the alphabet size is know before hand we can use bit vector(in this case english 26 size) to find them, but how about finding the set when we don't know the alphabet size?
c++ code here.. for constructing DAG from pair of consecutive two strings. And topological sort over constructed DAG.
#include <iostream>
#include <list>
#include <vector>
#include <string>
#include <stack>
#include <deque>
#include <set>
using namespace std;
#define NO_OF_ALPHABETS 26
#define NOT_VISITED 0
#define TEMP_VISITED -1
#define VISITED 1
typedef vector < set<int> > graph_t;
// Assume all are ascii characters between 'a' and 'z' only
void AddEdge( graph_t &myGraph, char *s1, char* s2);
void PrintTopologicalOrder( graph_t &myGraph, int startNode );
int GetUnvisitedNode(char * isVisited, int size );
void AddEdge( graph_t &myGraph, char *s1, char* s2)
{
while( (*s1 != 0) && (*s2 != 0) )
{
if( *s1 == *s2 )
{
s1++;
s2++;
continue;
}
else
{
myGraph[*s1-'a'].insert(*s2-'a');
break;
}
}
}
void PrintTopologicalOrder(graph_t &myGraph)
{
char isVisited[NO_OF_ALPHABETS];
memset( isVisited, NOT_VISITED, NO_OF_ALPHABETS);
stack<int> myStack; // for DFS
deque<int> resultOrder;
set<int>::iterator it;
int startNode = GetUnvisitedNode(isVisited, NO_OF_ALPHABETS);
while( startNode!= -1 )
{
myStack.push(startNode);
while( !myStack.empty() )
{
int currNode = myStack.top();
isVisited[currNode] = TEMP_VISITED;
int countFreeNodes = 0;
for(it = myGraph[currNode].begin(); it!= myGraph[currNode].end(); it++ )
{
if(isVisited[*it] == TEMP_VISITED)
{
cout << "Loop present, Path not possible" << endl;
return;
}
else if(isVisited[*it] == NOT_VISITED)
{
isVisited[*it] = TEMP_VISITED;
myStack.push(*it);
countFreeNodes++;
break;
}
}
if(countFreeNodes == 0 )
{
isVisited[currNode] = VISITED;
myStack.pop();
resultOrder.push_front(currNode);
}
}
startNode = GetUnvisitedNode(isVisited, NO_OF_ALPHABETS);
}
cout << "Topological order" << endl;
for( deque<int>::iterator it = resultOrder.begin();it!= resultOrder.end(); it++ )
{
char c = *it+'a';
cout << c << "->";
}
cout << endl;
}
int GetUnvisitedNode(char * isVisited, int size )
{
for(int i=0;i<size;i++)
{
if( isVisited[i] == NOT_VISITED )
return i;
}
return -1;
}
int main()
{
FILE * fp = fopen("words.txt", "r");
graph_t myGraph;
myGraph.resize(NO_OF_ALPHABETS);
char * string1 = new char[1024]; char * string2 = new char[1024];
string1[0] = 0; string2[0] = 0;
while( fscanf(fp, "%s", string2 )!=EOF )
{
AddEdge( myGraph, string1, string2);
strcpy(string1, string2);
}
PrintTopologicalOrder(myGraph);
return 0;
}
Node[] create_graph(String[] list){
HashSet<Node> set = new HashSet<Node>();
for (int i = 0 ; i < list.length ; i++)
for (int j = 0 ; j < list[i].length() ; j++)
if (!set.contains(list[i].charAt(j)))
set.add(list[i].charAt(j)));
int char_size = set.size();
Node[] G = new Node[char_size];
HashMap<Character , Node> map = new HashMap<Character , Node>();
int index = 0;
for (int i = 0 ; i < list.length ; i++)
for (int j = 0 ; j < list[i].length() ; j++){
Node[index] = new Node(list[i].charAt(j));
map.put(list[i].charAt(j) , Node[index]);
}
for (char C : set){
for (int i = 0 ; i < list.length ; i++){
boolean seen = false;
for (int j = 0; j < list[i].length() ; j++){
if (list[i].charAt(j) == C)
seen = true;
else if (seen == true){
map.get(list[i].charAt(j)).following.add(list[i].charAt(j));
}
}
}
}
//Now the graph is ready , we need to to DFS on it , to topoligically sort it
Topological-Sort(G);
//output the list of node's characters
}
char[] Topological-Sort(Node[] G){
int time = 0;
for (int i = 0 ; i < G.length ; i++)
if (!G[i].visited)
DFS-Visit(G[i] , time);
//sort in DECREASING ORDER based on each Node's FINISH_TIME
//we can use counting sort , as there aren't many nodes and the integers (time values) are not very large
int max = Integer.MIN_VALUE;
for (int i = 0 ; i < G.length ; i++)
if (max < G[i].finish_time)
max = G[i].finish_time;
int[] counter = new int[max + 1];
for (int i = 0 ; i < G.length ; i++)
counter[G[i].finish_time]++;
for (int i = 1 ; i < counter.length ; i++)
counter[i] += counter[i-1];
Node[] helper = new Node[G.length];
for (int i = counter.length - 1 ; i>= 0 ; i--){
helper[counter[G[i].finish_time]] = G[i];
counter[G[i].finish_time]--;
}
for (int i = 0 ; i < helper.length ; i++)
Node[i] = helper[i];
int left = 0 ;
int right = Node.length;
while (left < right){
Node temp = Node[left];
Node[left] = Node[right];
Node[right] = temp;
left++;
right--;
}
char[] result = new char[G.length];
for (int i = 0 ; i < G.length ; i++)
result[i] = G[i].c;
return result;
}
void DFS-Visit(Node n , int time ){
n.visited = true;
n.visit_time = time;
time++;
for (int i = 0 ; i < n.following.size() ; i++)
if (!n.following.get(i).visited)
DFS-Visit(n.following.get(i) , time);
time++;
n.finish_time = time;
}
class Node{
int visit_time , finish_time;
boolean visited;
ArrayList<Node> following;
char c;
public Node(char c){
following = new ArrayList<Node>();
visited = false;
this.c = c;
}
}
By the way, given sequence {fac, faa, aac} is not sufficient to determine the complete alphabet ordering. To be specific, the order of "f" and "c" can't be determined.
sites.google.com/site/spaceofjameschen/home/stl/find-dictionary-order----google
hash_map<char, int> s;
set<pair<char, char>> orderPair;
for(int i = 0; i < dict.size(); ++i)
{
for(int j = 0; j < dict[i].size(); ++j){
s.insert(make_pair(dict[i][j], 0));
}
}
for(int i = 0; i < dict.size() - 1; ++i){
string str1 = dict[i];
string str2 = dict[i + 1];
int j = 0;
while(str1[j] == str2[j]){
j ++;
}
orderPair.insert(make_pair(str1[j], str2[j]));
}
bool changed = true;
while(changed)
{
changed = false;
for(auto it = orderPair.begin(); it != orderPair.end(); ++it){
int ord1 = s[it->first];
int ord2 = s[it->second];
if(ord2 != max(ord1 + 1, ord2)){
changed = true;
s[it->second] = max(ord1 + 1, ord2);
}
}
}
cout << "----------------------------" << endl;
for(auto it = s.begin(); it != s.end(); ++ it){
order.push_back(make_pair(it->first, it->second));
}
sort(order.begin(), order.end(),
[=](pair<char, int> i, pair<char, int> j)->bool
{return i.second < j.second;});
Let set be {$, !, &, *, %, #}
set of words
$, *
!, &
*, #
&, $, @
#, @
Final answer is there are n positions that needs to be filled up with n alphabets in ascending order. We can give weights to each alphabets, finally all weights shud be 1 to n.
As you encounter each alphabet, give weights in increasing order. If the alphabet already has a weight in the previous word, then in this word it should start with that word and the remaining alphabets should have weights above this number. Eventually when u finish they ll have corresponding weights.
After first word: $ -1, *-2
2nd word:
!(not present in first word so give 1)-1, &(not present in first word so give 2)-2
After second word :
$-1, *-2
!-1, &-2
3rd word:
*-2, #-3 (*-present in first with 2, pick the maximum value in whichever word it was there)
After third Word:
$ -1, *-2
!-1, &-2
*-2, #-3 (*-present in first with 2, pick the maximum value in whichever word it was there)
4th word:
& - 2 (it was present in 3rd word with this value)
$ -3(But it is already present with value 1. So wherever it was present make it 3, and the others after it in that word should increase by 2(3-1))
After 4th word: (The key is after each instance, each symbol should have the same weight in all the words ie, if $ is 3 in first word, it should be 3 in every word)
$-3, *-4
!-1, &-2
*-4, #-5
&-2, $-3, @-4
5th word
#-5, @-6
After 5th word:
$-3, *-4
!-1, &-2
*-4, #-5
&-2, $-3, @-6
Now each of them have unique positions and the precedence order is !, &, $, *, #, @ with values 1, 2, 3, 4, 5, 6.
This is the algorithm. Haven’t thought about data structures to implement this. But I think it should be fairly simple.
say these words are in sorted order
$, *
!, &
*, #
&, $, @
#, @
and you say the final precedence is( !, &, $, *, #), but if this is the precedence then "&, $, @" should be in the 2nd number in the list. because there can't be a word starting with a lower precedence(! or *) before '&' , if the word list is sorted.
I too am highly suspicious of mpmaster's answer.
If the first "word" is "$*" and the second word is "!&" and they're lexicoographically sorted in ascending order (i.e. "$*" < "!&") then it's simply impossible for "!" to appear before "$" in the alphabet order as asserted.
Given the five input "words" and order specified there's not enough data to establish a full ordering of the alphabet as I understand it.
The input data does allow you to deduce a partial ordering which is "$!*&#". There's not enough information to determine the order of "@" (which is what I think you meant by "%" in the alphabet set specified).
You can build a directed graph and traverse it in order to find the precedence of characters. in this case e--->b .. similarly do for all other words in dictionary ..
1. Extract all relation couples from dictionary. Remove duplicates.
E.g.: dictionary (and, ant, bet) will result in (a,b), (d,t).
2. Build a digraph with letters as nodes and relation couples as directed edges. Label all nodes with 0. This digraph has no cicles.
3. Traverse the graph BFS starting from first node (the first letter of the first dictionary word) and "relax" the nodes as we encounter them. Relaxing here means to replace the node label with the BFS step. In the end each node will be labeled with the longest path length from start node.
4. If two nodes have same label then there is no solution. Otherwise the label order gives the alphabet order.
No, it's not BFS that you need here. It's a topolgical sort, which is a little different.
Form the above two notes:
we can formulate the following algorithm.
(a)Sort the dictionary with respect to first character and assign ranks for each character(which ever comes first will get lowest rank).
for each pair
(b) if Rank[c1] < Rank [c2] place an edge from c2 to c1.
(c) Now we have strings sorted by each character, with in each group of strings, proceed forward character and if str1[i] comes before str2[i] then place a directed edge in the graph from str2[i] - > str1[i].
(d) perform topological sort on the graph.
I know this is a very inefficient algorithm, i would appreciate if some one improves this.
Thanks,
Teja.
@Andy2000 - topological sort works in the following way: the following code returns precedence of characters OR error in case the graph has a cycle (cycle in case of wrong input)!
L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
remove a node n from S
insert n into L
for each node m with an edge e from n to m do
remove edge e from the graph
if m has no other incoming edges then
insert m into S
if graph has edges then
return error (graph has at least one cycle)
else
return L (a topologically sorted order)
Thanks Man!! I think in this question we dont need to do topological sort then. If we can just make a DAG and then retrieve all of the elements of DAG in an order, that will be order of Language. Isn't?
Well you're right only when the input is not wrong! If the input is wrong then the graph which you built will have cycle and in that case you can't just traverse the graph! I hope you get it..
I presume the question gives you sorted strings.
- LOLer August 15, 2009Just form a graph(DAG) and do a topological sort.