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));
}
Console.Read();
}
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?
