Interview Question

Senior Software Engineer Interview Seattle, WA

Given a series of words written using a scrambled alphabet

  , figure out what order the letters of the alphabet are in.
technical, algorithm

Interview Answer

6 Answers


Use a graph!

Interview Candidate on Apr 27, 2013

More than three words would be helpful. Do what with a graph? How would you build it? How would you search it?

Another Candidate on May 1, 2013

Given a ciphertext C, and plaintext P, the problem is to find a key K that converts the ciphertext to plaintext. Without considering the asymptotic complexity, it should be straighforward to generate the key combinations using a backtracking search algorithm.

Sea on May 3, 2013

More specifically, you would be given a list of words in the ciphertext which are in alphabetical order. Your job is to determine the alphabetic order of the ciphertext letters. In a graph, each node would represent a letter, the directed edge would indicate ordering of the two letters it connects. Once the graph is built you can do a simple traversal of the graph to generate your alphabetical ordering. Hope that helps!

Anonymous on May 3, 2013

I think I didn't get the question. Could someone elaborate on it a bit please?

Alexander Korobeynikov on May 3, 2013


An example of what I believe the question is presenting to the applicant is as follows.

Say I knew one of the words was 'CAT'. Now, if I look at the scrambled 3 letter word, and it was ZBS, then I know that C = Z, A = B, and T = S. Essentially, potentially every letter in the alphabet (up to 26 letters in total) are not of the same value.

So, if I had another example word, say 'TACS', and the given scrambled word is 'SBCY', then I now know that S = Y as well.

This is not an explanation of how to approach the problem, as we're not given any sample words; This is simply my interpretation of how the question is supposed to be interpreted as @Alexander is probably not the only person who does not understand the question.

Of course, I could have it wrong too, so who knows.

Anonymous on May 31, 2013

Add Answers or Comments

To comment on this question, Sign In with Facebook or Sign Up