# Return a rank for string of letters based on alphabetical permutations

So, first off, a little bit of unrelated information: I am preparing for a technical interview. I was reading this article, How to Prepare for (and Ace) the Technical Interview, by Rich Hein and I decided to try to tackle the problem he uses as an example.

From the article:

We are looking for a solution that is compact and runs quickly. What quickly means to us depends on the language you use, but it should take no longer than 500 milliseconds to run. Please use what language you are most comfortable with. However, please know that we do not have Visual Studio so C++ solutions should have the ability to compile with the standard G++.

Problem: Consider a word as any sequence of capital letters A-Z, not limited to just dictionary words. For any word with at least two different letters there are other words composed of the same letters but in a different order. For instance, stationarily and antiroyalist, which happen to both be dictionary words. For our purpose alianrostily is also a word composed of the same letters as these two. We can then assign a number to every word based on where it falls within an alphabetically sorted list of all words made up of the same set of letters.

One way to do this would be to generate the entire list of words and then find the desired ones, but this would be slow if the word is long. Write a program that takes a word as a command line argument and prints to standard output its number. Do not use the method above of generating the entire list. Your program should be able to accept any word 25 letters or less in length possibly with some letters repeated. It should use no more than 1 gig of memory and take no more than 500 milliseconds to run.

emphasis mine

So, this is my summarized understanding of the problem:

Create a function that accepts a capitalized string of letters. You are tasked with finding its alphabetical ranking among the possible permutations for that given input. Your method should return the integer ranking. Do not store a list of the permutations.

What I first did was open up Excel and using the following example dacb come up with an equation of how to do this:

Then, I wrote the program as a C# Console Application:

using System;
using System.Collections.Generic;

namespace WordAlphabeticalRank
{
class Program
{
static void Main(string[] args)
{
var testArray = new []{ "DACB", "CA", "FLCR", "RTZX" };

foreach (var test in testArray)
{
Console.WriteLine("Alphabetical rank of \"{0}\": {1}", test, AlphabeticalRank(test));
}

}

public static int AlphabeticalRank(string s)
{
var rankingArray = new List<char>(s.ToCharArray());
rankingArray.Sort();
var score = 1; //this is the lowest possible rank

for(int i = 0; i < s.Length -1; i++){

var rank = rankingArray.IndexOf(s[i]);
score += Factorial(rank) * rank;

rankingArray.RemoveAt(rank);
}

return score;
}

public static int Factorial(int n)
{
var product = 1;
for (int i = n; i > 0; i--)
{
product *= i;
}

return product;
}
}
}


The above program, when run outputs:

Alphabetical rank of "DACB": 20
Alphabetical rank of "CA": 2
Alphabetical rank of "FLCR": 3
Alphabetical rank of "RTZX": 2

So, what points can I improve on? Did I understand the problem correctly? (I wasn't able to ask questions, but I definitely would have because I have some questions about the wording and examples). Was Excel a good idea? Is my solution easy to understand? And, last but not least, does it meet the requirements?

• From the question: "However, please know that we do not have Visual Studio" It is unlikely that a C# solution would be acceptable in this situation. You must adhere to all conditions set in the interview/question. At the very least ask and check your understanding. – rossum Jun 9 '15 at 21:33
• That's fair. I didn't adhere to that specific requirement because I know I will be able to choose my language (and the place I am interviewing is based on the Microsoft stack using C#). Astute observation though, thanks for pointing it out :) – Carrie Kendall Jun 9 '15 at 21:35

Your program should be able to accept any word 25 letters or less in length

The largest possible answer then is $25! = 15511210043330985984000000$. This value won't fit in an int, a long, or even a ulong. I would recommend using a BigInteger.

• Good point. I've not much ventured into the world of insanely large numbers and overlooked the storage capacity of my measly ole Int32 . I will look into that type. – Carrie Kendall Jun 10 '15 at 1:40

Your program should be able to accept any word 25 letters or less in length possibly with some letters repeated

There seems to be a bug in the program. Take the string AAB -- there are only three distinct permutations of the letters, so we should get the following results:

AlphabeticalRank("AAB") => 1
AlphabeticalRank("ABA") => 2
AlphabeticalRank("BAA") => 3


But we actually get

AlphabeticalRank("AAB") => 1
AlphabeticalRank("ABA") => 2
AlphabeticalRank("BAA") => 5

• Oh, yeah. The ranking system doesn't really take into consideration duplicate characters. I need to put some thought into that.. – Carrie Kendall Jun 10 '15 at 2:01