Google Amazon Interview Question for Software Engineer / Developers


Country: India
Interview Type: Phone Interview




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

I presume the question gives you sorted strings.

Just form a graph(DAG) and do a topological sort.

- LOLer August 15, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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)

- victoriousvishal August 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

but how do u find out m has other incoming edge or not?

- amnesiac April 12, 2013 | Flag
Comment hidden because of low score. Click to expand.
5
of 5 vote

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)

- victoriousvishal August 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
4
of 4 vote

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.

- ChrisRussell41 July 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Very Good Explanation Chris. How do we handle this in Interview. I dont think that we can write the code and explain this entire thing in 1 Hr unless someone has already done this question.

- Andy2000 September 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

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.

- @LOLer August 15, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

- LOLer August 15, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

great approach!!!
Thanks a ton buddy :)

can you please elaborate more on the construction of the DAG in this case.

- addy August 18, 2009 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- oOZz June 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

"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 August 15, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- mpmaster August 15, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Addy August 17, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

sorry the previous comment was by me!

- mpmaster August 15, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

i agree with LOLer's solution of using a DAG and topological sorting...that solves the problem...btw, nice question!

- googler August 18, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- knap August 20, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Isn't it the Topological sorting of graphs ???

- ana October 01, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous December 15, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

the topological sort goes with the assumption that there is atleast one character that occurs nowhere but as the first character of the list of words.

otherwise topological sort would fail as there arent any nodes with 0 in-degree.

- fragzilla March 08, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- ankushbindlish May 05, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- EM June 04, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

this question has been asked before. topological sort

- Anonymous April 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you link me to that thread/question ?

- Anton April 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

question?id=175872

- Anonymous April 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

-- > Construct a Graph . Check for cycles . In case of cycles , no solution exists .
---> Topological Sort of the DAG is the answer .

- Anonymous April 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you explain how to construct the graph ?
Thanks

- Anton April 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Kind of the whole point of this problem...

- Anonymous April 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Anonymous April 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//====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;
}

- Daisy G May 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// The idea is to build the precedence between alphabets to create a
// directed graph. If there is cycle, then training set is not correct - error out;
// otherwise do topological sort for constructed DAG to return alphabet in partial order.

- jzhu May 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This comment has been deleted.

- topcoder June 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- ChrisRussell41 July 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- victoriousvishal August 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- Guest September 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Well all I can say is when you don't know the size before hand then use dynamic allocation. Like vector in C/C++ and ArrayList in java.

- victoriousvishal September 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

why dont we use Tries here

- lucifer August 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I am not comfortable in using tries. But would definitely like to know how we can use it. @lucifer please can you give me the solution using tries?
Thanks!

- victoriousvishal August 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- chetan.j9 April 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}
}

- Arian Hosseinzadeh June 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- ule June 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@ule Yes, the given example is incorrect. Therefore, you cannot determine the alphabet from these given words.

the order should have been {faa, fac, aac}

- oOZz June 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;});

- Anonymous June 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

- mpmaster August 15, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Addy August 17, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- ChrisRussell41 July 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The answer is "!&$*#@"... DAG and topological sort will get you the answer

- cobra July 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The 1st word: $*
The 2nd word: !&

$ must proceed ! in the alphabet right?

- Anonymous July 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

This comment has been deleted.

- Administrator April 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you please elaborate?

- Anonymous April 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why administrator deleted this comment ?

- siva.sai.2020 April 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- viks April 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The question would of course be how to construct this graph.

- Anonymous April 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

We can traverse the Sorted Dictionary just concerning ourselves with the first letter. This we we can build a LinkedHashMap.Traversing which will give us the Precedence Order.

- Free Bird April 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

- Mugatu April 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

No, it's not BFS that you need here. It's a topolgical sort, which is a little different.

- eugene.yarovoi April 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- krishna April 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

How does Topological Sort works?

- Andy2000 September 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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)

- victoriousvishal September 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- Andy2000 September 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- victoriousvishal September 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

As far as I can tell, traversing a DAG in the *proper* order for this problem is almost the same as doing a topological sort anyway.

- eugene.yarovoi September 09, 2012 | 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