CareerCup

Pseudo code:
// Form DAG of Char, smaller char have bigger chars as its children.
// Something like
// a->b
//  | |->|
//  |->->c (a points to b, c; b points to c, etc)
formDAG(Array<String> dict, Graph<Char> graph) {
	sort(dict); // Sort the dictionary
	Array<Char> chars = new Array<Char>();
	Array<String> recurseDict = new Array<String>();
	char firstChar = dict[0][0]; // First char of first string
	// Remove 1st char from string and add remaining string to recurseDict.
	recurseDict.add(dict[0][1 : dict[0].length]);
	for (int i = 1; i < dict.length; ++i) {
		if (dict[i][0] == firstChar) {
			recurseDict.append(dict[i][1 : dict[i].length]);
		} else {
			// Append firstChar to last of chars list.
			chars.append(firstChar);
			// Recurse on sub-dictionary with removed 1st char.
			formDAG(recurseDict, graph);
			recurseDict.clear();
			// Update firstChar and continue loop.
			firstChar = dict[i][0];
			recurseDict.add(dict[i][1 : dict[i].length]);
		}
	}
	// Form edges from the chars list.
	for (int i = 0; i < chars.length; ++i) {
		if (!graph.nodeExists(chars[j]) {
			graph.createIsolatedNode(chars[i]);
		}
		for (int j = i + 1; j < chars.length; ++i) {
			if (!graph.nodeExists(chars[j]) {
				graph.createIsolatedNode(chars[j]);
			}
			graph.getNode(char[i]).addIfNotAlreadyAChild(
				graph.getNode(char[j]));
		}
	}
}

Finally do a topological sort uding DFS on this graph and return the list.

This wont work always. Suppose I give 2 words: AB and GE (in that order). The only conclusion you can draw is A comes before G. Thats it!! Nothing can be told about B or E. Your solution will print A > G > B > E

The graph formed would be node A points to node G. B, E are independent nodes.

May be the confusion was with topological sort. Well, the language may or may not have precedence order amongst all of the literals, but you can achieve partial precedence ordering using topo sort.

If you go with Cormen topo sort algo, he returns a single list and would get what you mentioned A > G > B > E.
I didn't mean that.
I somehow couldn't express the second part more clearly.
So you have a DAG and the interviewer needs ordering, see what you can do...

Use Trie, the neglected data structure. It will take care of lexicography.