Recently the company I work for started another round of recruitment for a mid-level software engineer. One of the things that surprised me from the last round of recruitment (my first) is how many professional software engineers out there simply can’t code. By this I don’t mean that they have good experience with another language but not so much with our weapon of choice (C#); I mean that they just can’t write a simple algorithm.
This time around we have decided to set a simple coding task for the candidate to complete before we offer them an interview. We decided to use an online service to facilitate this - one that offers a simple web-based IDE with syntax highlighting, but no intellisense. Because of this we, naturally, make allowances for typos and simple compiler errors.
When reviewing the submissions they tend to fall into the following categories:
- Did not complete assignment (technically not a submission, of course). This accounts for maybe 10% of applications. I assume this is due to one of the following reasons;
- The applicant can’t actually code,
- The applicant didn’t think the job was worth it, or
- The applicant was offended at the very idea of a coding screen
- Copied and pasted the code directly from Stack Overflow. This actually accounts for almost half of the applications. I don’t object to heavy use of search, Stack Overflow and docs during work, but the point of this submission is to see if you can code, not if you can copy and paste. Additionally, developers who copy and paste from online sources without actually understanding what the code is doing is not someone I want to hire. Interestingly, while the Stack Overflow examples are good algorithms, they don’t actually handle the edge cases too well.
- Original work, but with serious flaws. This accounts for another ~25% of all applications. As mentioned above, I will make generous allowances for typos etc. (I will clean it up enough to compile so I can run our tests against it), but if the algorithm has serious flaws, then it’s pointless proceeding further - at this stage.
- Original work to an acceptable standard. This accounts for a depressingly small number of submissions, but at least the process saves us time interviewing obviously poor candidates.
When we set the test I created my own implementation; partly for fun and partly to have something to test against. I don’t think my own submission is perfect, and it could almost certainly be quicker (I make heavy use of dictionary lookups and linq rather than loops and branches) but the important thing is; it works! It took me about 15 minutes to write (this isn’t a brag - I didn’t have to read and understand the task first, as I was already familiar with it) and a further 30 minutes to cobble together a test harness so I can throw submissions into a new class and run the tests with the minimal of fuss. It allows me to compare it against my own submission and to generate a leaderboard of all previous submissions.
So, here is the task we set, followed by my own attempt (Note: I wouldn’t normally comment my code as heavily as this - or at all).
Roman numerals
Traditional Roman numerals are made up of the following denominations:
I = 1
V = 5
X = 10
L = 50
C = 100
D = 500
M = 1000In order for a number written in Roman numerals to be considered valid there are three basic rules which must be followed.
- Numerals must be arranged in descending order of size, except when being used as part of a subtractive combination (e.g. IV instead of IIII). In these cases: a. Only one I, X and C can be used as the leading numeral in part of a subtractive pair. b. I can only be placed before V and X. c. X can only be placed before L and C. d. C can only be placed before D and M.
- M, C, and X cannot be equalled or exceeded by smaller denominations.
- D, L, and V can each only appear once.
Write a function that parses string representations of Roman numerals and returns the integer value of the numeral. If the numeral is invalid then the function should return -1.
The signature of the function should be:int RomanToDecimal(string roman)
private const int Invalid = -1;
private static readonly IDictionary<char, int> CharacterMap = new Dictionary<char, int>
{
{ 'I', 1 },
{ 'V', 5 },
{ 'X', 10 },
{ 'L', 50 },
{ 'C', 100 },
{ 'D', 500 },
{ 'M', 1000 }
};
private static readonly IDictionary<char, char[]> SubtractivePairs = new Dictionary<char, char[]>
{
{ 'I', new[] { 'V', 'X' } },
{ 'X', new[] { 'L', 'C' } },
{ 'C', new[] { 'D', 'M' } }
};
private static readonly char[] UniqueValues = { 'D', 'L', 'V' };
public int RomanToDecimal(string roman)
{
// null value is considered invalid.
if (roman == null) return Invalid;
// empty or whitespace string considered equal to 0.
if (roman.Trim().Length == 0) return 0;
roman = roman.ToUpper();
// Check there are no invalid characters
if (!roman.All(CharacterMap.Keys.Contains)) return Invalid;
// Check D, L and V appear no more than once
if (UniqueValues.Any(u => roman.Count(c => c == u) > 1)) return Invalid;
var values = new Stack<int>();
int previousValue = Int32.MaxValue;
char previousCharacter = '\0';
int countOfPreviousValue = 0;
for (int i = 0; i < roman.Length; i++)
{
var currentCharacter = roman[i];
var currentValue = CharacterMap[currentCharacter];
// Check count of previous value - important when acertaining if a subtractive pair is valid.
if (previousValue == currentValue) countOfPreviousValue++;
// Check they are ordered descending, if not check if it is a valid subtractive pair.
if (currentValue > previousValue)
{
// Example: XIV is valid, but XIIV is not.
if (countOfPreviousValue > 1) return Invalid;
// If the character value is greater than the previous character value,
// check if the previous character and this character are valid subtractive pairs.
if (!SubtractivePairs.TryGetValue(previousCharacter, out var pair)) return Invalid;
if (!pair.Contains(currentCharacter)) return Invalid;
// If we have a valid subtractive pair, remove the previous value from the stack
// and subtract it from the current value.
values.Pop();
currentValue -= previousValue;
}
values.Push(currentValue);
if (previousValue != currentValue) countOfPreviousValue = 1;
previousValue = currentValue;
previousCharacter = currentCharacter;
}
// Check that lower value denominations to not add to higher than M, C or X (if present)
if (values.Any(v => v == 1000) && values.Where(v => v < 1000).Sum() > 1000) return Invalid;
if (values.Any(v => v == 100) && values.Where(v => v < 100).Sum() > 100) return Invalid;
if (values.Any(v => v == 10) && values.Where(v => v < 10).Sum() > 10) return Invalid;
return values.Sum();
}