Google Interview Question: Given a series of words writt... | Glassdoor

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

7 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

Anonymous on Nov 4, 2014

Add Answers or Comments

To comment on this, Sign In or Sign Up.