CareerCup

This should be approached with a Directed Graph/Precedence graph and then performing a topological sort on the top of it.

I thought this should be something like cryptography algorithm, but you said it could be resolved using graph as data structure? Could you give more details?

Thanks!

Can you please let me know what does "Use the file to reconstruct the new alphabet for as much as possible." means with an example.

That means find out what the new alphabet is.

We know the old alphabet is (a, b, c, ...., z) which is the English alphabet, and the new alphabet is what we want to find out.

You receive inequality relationships as you go through the file, and basically you integrate these scatter inequalities.

Given the new dictionary where its length is represented by n, we can solve this in O(n lg n):

k=0,i=0,j=0;
while(i<n)
{
ch=Dictionary[i][0];
NewAlphabetOrder[j++]=ch;
while(true)
{
c=Dictionary[(1<<k)-1)][0]; //i.e., search at every 2^k steps
if(c==ch)
 k++;
else
  break;
}
begin=1<<(k-1);//i.e., 2^(k-1)
end=(1<<k)-1; i.e., 2^k
//Now binary search to find the first occurrence of c in this range and update value of the counter, i, accordingly
i=Find_First_Occurrence(Dictionary,begin,end,c); // this returns the index of first occurrence of the character, c, in the dictionary 
}