Geek Answers Handbook

Submit a word with alphabet

This is an interview question:

Imagine an alphabet of words. Example: a ==> 1 b ==> 2 c ==> 3 . z ==> 26 ab ==> 27 ac ==> 28 . az ==> 51 bc ==> 52 and so on.

Thus, the sequence of characters should only be in ascending order (ab is valid, but ba is not). If any word prints its index, if it is valid and 0 if not.

 Input Output ab 27 ba 0 aez 441

Note. Brute force is not allowed. Here is the link to the question: http://www.careercup.com/question?id=21117662

I can understand this solution as:

  • Total words 2 ^ 26 -1.
  • For a given word, first words with a small size.
  • Let n be the word length,
    • The total number of words with a size less than n is C (26, 1) + C (26, 2) + ... + C (26, n -1)
  • Then calculate how many words with the same size up to a given word
  • The sum of two numbers, plus one, is the result

Link: sites.google.com/site/spaceofjameschen/annnocements/printtheindexofawordwithlettersinascendingorder--microsoft

In the sample solution, I realized how the author calculated the number of words with a size smaller than the word .size (). But in the code, I'm not too sure how to find the number of words of the same size as word.size () that appear before the word.

This bit is:

 char desirableStart; i = 0; while( i < str.size()){ desirableStart = (i == 0) ? 'a' : str[i - 1] + 1; for(int j = desirableStart; j < str[i]; ++j){ index += NChooseK('z' - j, str.size() - i - 1); // Choose str.size() - i - 1 in the available charset } i ++; }

Can someone help me understand this bit? Thanks.

+2
algorithm data-structures count
source share
2 answers

First of all (you probably got this part, but for the sake of completeness), the NChooseK function calculates a binomial coefficient, i.e. the number of ways to select k elements from a set of n elements. This function is called C(n, k) in your comments, so I will use the same notation.

Since the letters are sorted and not repeated, this is just the number of ways to create n-letter words described in the task, which is why this is why the first part of the function gives you the correct position:

 int index = 0; int i = 1; while(i < str.size()) { // choose *i* letters out of 26 index += NChooseK(26, i); i++; }

For example, if your entry was aez , this would get the index of the word yz , which is the last possible two-letter combination: C(26, 1) + C(26, 2) = 351 .

At this point, you have the starting index of your n-letter word, and you need to see how many combinations of n-letter words you need to skip to get to the end of the word. To do this, you need to check each individual letter and count all possible combinations of letters, starting with one letter after the previous one (the desirableStart variable in your code) and ending with checking the letter.

For example, for aez you will act as follows:

  • Get the last 2-letter word index ( yz ).
  • Increase the index by one (this is really done at the end of your code, but it makes sense to do it here in order to maintain the correct position): now we are in the abc index.
  • First letter a , no need to increase. You are still on abc .
  • Second letter e , counting combination for the 2nd letter from b to e . This will lead you to aef (note that f is the first valid third character in this example, and desirableStart will take care of that).
  • Third letter z , combinations of combinations for the third letter, from f to z . This will lead you to aez .

What the last part of your code does:

 // get to str.size() initial index (moved this line up) index ++; i = 0; while( i < str.size()) { // if previous letter was `e`, we need to start with `f` desirableStart = (i == 0) ? 'a' : str[i - 1] + 1; // add all combinations until you get to the current letter for (int j = desirableStart; j < str[i]; ++j) { char validLettersRemaining = 'z' - j; int numberOfLettersToChoose = str.size() - i - 1; index += NChooseK(validLettersRemaining, numberOfLettersToChoose); } i++; } return index;
+2
source share

there is no difference between calculating the number of words of the same size and the counterparty for shorter words.

you can be led astray by indexing arrays in c starting at 0. Thus, although i < str.size() might suggest otherwise, the last iteration of this loop actually counts words of the same size as the words whose index is equal to computed .

0
source share

More articles:


All Articles