CareerCup

The solution I have in mind has two parts:

A) from the words, figure out which letter precedes which. This gives you a DAC where there is an edge from char 'a' to char 'b' only if 'a' supersedes 'b' in the order.

B) Run DFS to get (a) topological order. The topological order is the reverse order of the items you mark as visited.

1. Start with an all zeros 26 by 26 matrix.
2. Go through the list of words from top to bottom. As you go from one word to the next you will determine the relative order of two letters. Enter 1 in the corresponding cell in the 26 by 26 matrix for the pair whose order you just determined. For example if the first word is "dhk" and the next word is "dhf", it is determined that "k" < "f". So you would enter 1 in the cell corresponding to k-f. Something like this:

a b c d e f g h i j k l m n o p q r s t u v w x y z
a
b
c
d
e
f
g
h
i
j
k            1           
l
m
n
o
p
q
r
s
t
u
v
w
x
y
z

3. After you are done going through the words, the row that doesn't have a 1 in any of the cells is the last letter of the new alphabet
4. Remove the row and column corresponding to the last letter
5. A new will become empty when the column and the row corresponding to the last letter are removed from the matrix. The new row is the second last letter.
6. Repeat steps 4 and 5 until the order of letters is determined.

A c++ implementation of the algorithm described above:

#include <iostream>
#include <vector>
#include <string>

using namespace std;
void updateMatrix(vector<vector<char>>& matrix, string word1, string word2) {
	auto it1 = word1.begin();
	auto it2 = word2.begin();
	
	while(it1 != word1.end() && it2 != word2.end()) {
		if(*it1 != *it2) break;
        it1++;it2++;
	}
	if(it1 != word1.end() && it2 != word2.end()) {
		if(matrix[*it1 - 'a'][*it2 - 'a' + 1] != 1) {
			matrix[*it1 - 'a'][*it2 - 'a' + 1] = 1;
			matrix[*it1 - 'a'][0]++;
		}
	}
}

vector<char> determineAlphabet(vector<string> dict) {
	vector<vector<char>> matrix = vector<vector<char>>(26,vector<char>(28,0)); //firist column is count of 1s, last column is the letter itself
	for(int i = 0; i < 26; i++) matrix[i][27] = 'a' + i;
	for(int i = 1; i < dict.size(); i++) {
		updateMatrix(matrix, dict[i-1], dict[i]);
	}
	int remainingLetters = 26;
	while(remainingLetters > 1) {
		for(int i = 0; i < remainingLetters; i++) {
			if(matrix[i][0] == 0) {
				for(int j = 0; j < remainingLetters; j++) {
					if(matrix[j][i + 1] == 1) {
						matrix[j][0]--;
					}
				}
				swap(matrix[i], matrix[remainingLetters - 1]);
                break;
			}
		}
		remainingLetters--;
	}
	vector<char> ret;
	for(int i = 0; i < 26; i++) ret.push_back(matrix[i][27]);
	return ret;
}

int main() {
	vector<string> dict = {"ze", "yf", "xd", "wd", "vd", "ua", "tt", "sz", "rd", "qd", "pz", "op", "nw", "mt", "ln", "ko", "jm", "il", "ho", "gk", "fa", "ed", "dg", "ct", "bb", "ba"};
	auto A = determineAlphabet(dict);
	for(auto ch: A) cout << ch << ", ";
	return 0;
}
Output:
z, y, x, w, v, u, t, s, r, q, p, o, n, m, l, k, j, i, h, g, f, e, d, c, b, a,

Create 2 hashtables that store the children/parents relationships among the letters. Then run topological sort. Code seems kinda long though.

import java.util.*;

class NewOrder {

	static String findOrdering(String[] words) {
		HashMap<Character, HashSet<Character>> children = new HashMap<Character, HashSet<Character>>();
		HashMap<Character, HashSet<Character>> parents = new HashMap<Character, HashSet<Character>>();
		for(String word : words) {
			for(Character ch : word.toCharArray()) {
				if(children.containsKey(ch))
					continue;
				children.put(ch, new HashSet<Character>());
				parents.put(ch, new HashSet<Character>());
			}
		}

		for(int i=1; i<words.length; i++) {
			String prev = words[i-1];
			String curr = words[i];
			int len = prev.length();
			for(int j=0; j<len; j++) {
				char ch = prev.charAt(j);
				char ch2 = curr.charAt(j);
				if(ch != ch2) {
					children.get(ch).add(ch2);
					parents.get(ch2).add(ch);
					break;
				}
			}
		}

		StringBuilder sb = new StringBuilder();
		LinkedList<Character> noParents = new LinkedList<Character>();
		for(Character ch : parents.keySet()) {
			if(parents.get(ch).isEmpty())
				noParents.add(ch);
		}
		while(!noParents.isEmpty()) {
			char ch = noParents.removeFirst();
			sb.append(ch);
			for(Character ch2 : children.get(ch)) {
				parents.get(ch2).remove(ch);
				if(parents.get(ch2).isEmpty())
					noParents.add(ch2);
			}
		}
		return sb.toString();
	}

	public static void main(String[] args) {
		System.out.println(findOrdering(args));
	}
}

Create a DAC relating the letters to each other and create topological sorted value from the DAC to get a suitable ordering. This will be unfortunately O(n*m + p*p) where n is the number of words, m is the number of characters in each word, and p is the number of characters in the alphabet. It will also take O(p*p) memory:

public static Character[] getCharOrder(String[] sortedWords){
	if(sortedWords == null){
		throw new NullPointerException();
	}
	Graph<Character> g = generateGraph(sortedWords);
	ArrayList<Character> ordering = g.getTopologicalSort();
	return ordering.toArray();
}

//Operates only linearly to generate connections ( O(n) time ). 
//Could be changed to build connections between every word but that would be
//much slower (O(n^2) time).
private Graph<Character> generateGraph(String[] arr){
	Graph<Character> g = new Graph<Character>();
	for(int i = 1; i < arr.length; i++){
		char[] word1 = arr[i-1].getChars();
		char[] word2 = arr[i].getChars();
		char[] difference = getFirstDifference(word1, word2);
		if(difference != null){
			g.addNode(difference[o]);
			g.addNode(difference[1]);
			g.addConnection(difference[1], difference[0]);
		}
	}
}

private char[] getFirstDifference(char[] arr1, char[] arr2){
	for(int i = 0; i < arr1.length && i < arr2.length; i++){
		if(arr1[i] != arr2[i]){
			return new char[]{arr1[i], arr2[i]};
		}
	}
	return null;
}

static class Graph<T>{
	HashMap<T, Integer> indexMap = new HashMap<T, Integer>();
	ArrayList<T> nodeValue = new ArrayList<T>();
	ArrayList<HashSet<Integer>> connections = new ArrayList<HashSet<Integer>>();

	void addNode(T val){
		Integer index = this.indexMap.get(val);
		if(index == null){
			this.indexMap.put(val, this.nodeValue.size());
			this.nodeValue.add(val);
			this.nodeValue.add(new HashSet<Integer>());
		}
	}

	void addConnection(T val1, T val2){
		Integer i1 = this.indexMap.get(val1);
		Integer i2 = this.indexMap.get(val2);
		this.connections.get(i1).add(i2);
	}

	ArrayList<T> getTopologicalSort(){
		TopoWorker<T> worker = new TopoWorker<T>(this);
		worker.execute();
		return worker.result;
	}

	static class TopoWorker{
		final int CHECKING = 1;
		final int COMPLETED = 2;
		int[] nodeStatus;
		Graph g;
		ArrayList<T> result;
		
		TopoWorker(Graph g){
			this.g = g;
			this.nodeStatus = new int[g.nodeValue.size()];
			this.result = new ArrayList<T>(g.nodeValue.size());
		}

		void execute(){
			if(this.nodeStatus.length == 0){
				return;
			}
			for(int i = 0; i < this.nodeStatus.length; i++){
				executeRecur(i);
			}
		}

		void executeRecur(int i){
			if(this.nodeStatus[i] == CHECKING){
				throw new IllegalArgumentException("There is no valid ordering"+
						"because cycles exist");
			}
			if(this.nodeStatus[i] == COMPLETED){
				return;
			}
			this.nodeStatus[i] = CHECKING;
			for(Integer connTo : g.connections.get(i)){
				executeRecur(connTo);
			}
			this.nodeStatus[i] = COMPLETED;
			this.result.add(g.nodeValue.get(i));
		}
	}
}

Hi, I have written a recursive solution. Build relationshipMap -> Flatten the map -> return the longest entry. I guess the time complexity would be O(n*m), where n= # of words and m = maxLen(words).

import java.util.HashMap;
import java.util.Map;

/**
 * Created by Akshat on 8/11/2014.
 */

public class AlienLanguage{

    public String evaluate(String[] words){

        Map<Character, String> relationshipMap = genRelationship(words, new HashMap<>());
        Map<Character, String> flattenRelationshipMap = flattenRelationships(relationshipMap);
        /*
         find and return entry in flattenRelationshipMap that satisfies value.size == sizeOf(relationshipMap)
         rationale -: 
         relationshipMap =>
            a -> c, d -> a, b -> d
            size = 3
         flattenRelationshipMap
            a -> c, d -> ac, b -> dac
            size(dac) = 3
         return "b"+"dac"
        */
        for(Map.Entry<Character, String> entry : flattenRelationshipMap.entrySet())
        {
            if(entry.getValue().length() == flattenRelationshipMap.size())
                return entry.getKey()+entry.getValue();
        }

        return null;
    }

    /**
     *  Recursive code that keeps on flattening the map until progress is being made
     */
    private Map<Character, String> flattenRelationships(Map<Character, String> map)
    {
        boolean isProgressMade = false;

        for(Map.Entry<Character, String> entry: map.entrySet())
        {
            String val = map.get(entry.getValue().charAt(entry.getValue().length()-1));
            if(val !=null)
            {
                entry.setValue(entry.getValue()+val);
                isProgressMade = true;
            }
        }

        if(isProgressMade)
            flattenRelationships(map);

        return map;
    }

    /**
     * Recursive code, that checks the 0th index of previous and current word
     * if(prev!=next) -> record the relation prev -> next
     * else recurse for next char of previous and current word
     *
     */
    private Map<Character, String> genRelationship(String[] words, Map<Character, String> map)
    {
        if(words.length == 0)
            return map;

        for(int i=1; i<words.length;i++)
        {
            char prev = words[i-1].charAt(0);
            char curr = words[i].charAt(0);
            if(prev!=curr)
            {
                map.put(prev, curr+"");
            }else{
                map = genRelationship(new String[]{words[i - 1].substring(1), words[i].substring(1)}, map);
            }

        }
        return map;
    }

}

Test Case -:

public class AlienLanguageTest {

    @Test
    public void evaluate()
    {
        String words[] = {"baa", "abcd", "abca", "cab", "cad"};
        AlienLanguage alienLanguage = new AlienLanguage();
        Assert.assertEquals("wrong order", "bdac", alienLanguage.evaluate(words));
    }

    @Test
    public void evaluate1()
    {
        String words[] = {"caa", "aaa", "aab"};
        AlienLanguage alienLanguage = new AlienLanguage();
        Assert.assertEquals("wrong order", "cab", alienLanguage.evaluate(words));
    }

    @Test
    public void evaluate2()
    {
        String words[] = {"ze", "yf", "xd", "wd", "vd", "ua", "tt", "sz", "rd", "qd", "pz", "op", "nw", "mt", "ln", "ko", "jm", "il", "ho", "gk", "fa", "ed", "dg", "ct", "bb", "ba"};
        AlienLanguage alienLanguage = new AlienLanguage();
        Assert.assertEquals("wrong order", "zyxwvutsrqponmlkjihgfedcba", alienLanguage.evaluate(words));
    }

}

This one simply compares two consecutive words and looks for the first letters of them, if they are different, changes the order of the alphabet according to them. If they are the same, looks for the next two letters in the same two words... Continues like this

#include <string>
#include <iostream>
using namespace std;
int indexOf(string main, char letter){
	for (int a = 0; a < main.length();a++){
		if (main[a]==letter)
			return a;
	}
	return -1;
}
string alphabet(string * arr, int size){
	string alph = "abcdefghijklmnopqrstuvwxyz";
	for (int a = 0; a < size-1;a++){
		int ind = 0;
		while(ind < arr[a].length() && ind < arr[a+1].length() && arr[a][ind] == arr[a+1][ind])		ind++;
		if (ind < arr[a].length() && ind < arr[a+1].length()){
			int first = indexOf(alph, arr[a][ind]);
			int last = indexOf(alph, arr[a+1][ind]);
			if (first > last){
				string temp = alph;
				alph = temp.substr(0, last);
				alph += temp.substr(last + 1, first - last);
				alph += temp[last];
				alph += temp.substr(first+1, temp.length());
			}
		}
	}
	return alph;
}

Here is C++ version of solution.

This algorithm performs the following two steps.
Given the list of M words, whose longest one is N.
1) constructed directed graph of letters based on words O(MN)
2) performs BFS to find the topological ordering. Running time O(N), Space O(N)

#include <set>
#include <string>
#include <vector>
#include <map>
#include <iostream>
using namespace std;

struct vertex {
	char v;
	bool visited;
	set<vertex *> dst;
	vertex(char c): v(c), visited(false){}
};

void dfs (vertex * s, string& buffer)
{
	if (s->dst.size() == 0)
	{
		return;
	}
	set<vertex *>::iterator iter;
	for (iter = s->dst.begin(); iter != s->dst.end(); iter++)
	{
		if (!(*iter)->visited)
		{			
			(*iter)->visited = true;
			dfs((*iter), buffer);
		}
	}
	buffer.insert(0, 1, s->v);
}

void extract_orders(vector<string> input)
{
	map<char, vertex *> hashtable;
	map<char, vertex *>::iterator iter;
	string buffer;
	for (int i = 0; i < input.size(); i++)
	{
		char src = input[i][0];
		for (int j = 1; j <input[i].length(); j++)
		{
			vertex * v = 0;
			vertex * w = 0;
			char dst = input[i][j];
			map<char, vertex *>::iterator vfound;
			map<char, vertex *>::iterator wfound;

			if ((wfound = hashtable.find(dst)) == hashtable.end())
			{
				w = new vertex(dst);
				hashtable[w->v] = w;
			} else
			{
				w = wfound->second;
			}

			if ((vfound =hashtable.find(src))== hashtable.end())
			{
				v = new vertex(src);
				hashtable[v->v] = v;
			} else {
				v = vfound->second;
			}

			if (v->dst.find(w) == v->dst.end())
				v->dst.insert(w);			
			src = dst;
		}
	}
	
	dfs(hashtable[input[0][0]], buffer);
	cout<<"sequence = "<<buffer<<endl;
}

int main()
{
	vector<string>input;
	input.push_back("abcdefo");
	input.push_back("begz");
	input.push_back("hijk");
	input.push_back("abcedefgh");
	input.push_back("ikjom");

	extract_orders(input);
	return 1;
}