Implement Translate Roman Numerals in JavaScript

Interview Questions
September 26, 2016

This is the third article in a series about programming interview questions and how to think through and solve them! This article will cover the roman numeral translation programming interview question in JavaScript.

Given a roman numeral as input, write a function that converts the roman numeral to a number and outputs it. When a smaller numeral appears before a larger one, it becomes a subtractive operation. You can assume only one smaller numeral may appear in front of larger one. For example: if given the input VI, the output should be 6 (5 + 1 = 6) or if given the input IV, the output should be 4 (5–1 = 4).

Analysis

One of our biggest challenges here is knowing if we should be adding the current letter within the roman numeral or subtract it. I decided that, while iterating through, I could peak to the right of the current letter and decide whether to add or subtract. This route would give me a linear time complexity at worst case. Let’s take a look at the pseudocode.

Pseudocode

function translateRomanNumerals(romanNumeral) { Create result variable Split input at each character Iterate through split input Save current letter and next letter into variables If current letter is undefined Return 'null' else if current letter is less than next letter Add current letter minus next letter to result var Double increment count to skip next letter else Add current letter to result Return result }

Time Complexity

The time complexity of the above algorithm should be the same as the number of items produced. This is because as the list grows larger, we have to continue to check each letter to add the value. Therefore, with an input size of n the time complexity is linear — O(n).

Code


function translateRomanNumeral (romanNumeral) { var DIGIT_VALUES = { I: 1, V: 5, X: 10, L: 50, C: 100, D: 500, M: 1000 }; var result = 0; var input = romanNumeral.split(''); for (var i = 0; i < input.length; i++) { var currentLetter = DIGIT_VALUES[input[i]]; var nextLetter = DIGIT_VALUES[input[i + 1]]; if (currentLetter === undefined) { return 'null'; } else { if (currentLetter < nextLetter) { result += nextLetter - currentLetter; i++; } else { result += currentLetter; } } }; return result; }

Nice job making it through this one! As you work through more of the advanced challenges, you’ll need to start utilizing data structures. Interested in learning some now? I wrote a series on data structures in JavaScript here.

Having worked across sites raking in over 50 billion website visits annually, Michael Mitrakos can help your business to crush the web game with an award winning website.

I also created Wanderlust Extension to discover the most beautiful places across the world with highly curated content. Check it out!

More Blog Posts