Microsoft Interview Question Software Engineer / Developers
//Problem:
//================
//Convert a Roman Numeral string to Decimal.
//Example:
//================
//input:XI.I
//output:11.1
//Roman numbers
//I
//V
//X
//Process
//===============
//1. Declare Assumptions
//2. Explain algo
//3. take an Example
//4. give testcases
//5. 1st write the solution
//6. then add exception handels and try/catch/finally blocks
//7. Order
//ALGO:
//================
//find length of the string & input string into a char array
//run loop to find the decimal at which char array
//find units/decimal values based on location of decimal
//left of decimal[star from Left to decimal to 0] * 1/X
//right of decimal[start from right of decimal to N] *X
//check each array value and if found then update an integer and add on the previous one
//till all the values are not met
//TEST CASES:
//================
//Functional
//1. large units/decimal values
//2. no decimal value
//3. only decimal value
//4. null input
//5. any other non roman input
//6. limit testing[BVA]
//Non functional:
//Performance:
//1. test with same string multiple times , test for time efficiency
//stress
//2. test with executing multiple instance of same method
//load
//4. test with large string
//memory
//5. test with same string multiple time and check memory leakage
//localization\globalization
//6. test with ascii char & special char
//7. test with unicode char
//8. test with kanji characters[japanese]
//9. test with mix of unicode and kanji char
//security
//10. test with escape char \n \a \t
//11. test with non null terminating string and null terminating string
//codecoverage
//exception handeling block
//TEST HARNESS:
//================
using System;
namespace problem
{
public class answer
{
static void Main()
{
String S="test";
Console.WriteLine(convertroman2decimal(S));
Console.ReadLine();
}
//CODE:
//================
public static float convertroman2decimal(string S)
{
try
{
bool dec = new bool();
dec=false;
int decimalindex=0;
int strlen= S.Length;
int unitcount=0;
int decimalcount=0;
char[] strarray=S.ToCharArray();
float result = 0;
for(int d=0; d< strlen-1;d++)
{
if(strarray[d]=='.')
{
decimalcount = strlen-1 - d;
unitcount =strlen-(decimalcount+1);
dec=true;
decimalindex=d;
}
}
if(dec==false)
{unitcount=strlen;
}
for(int i=decimalindex-1; (i>-1) &&( strarray[i]!='.') &&( unitcount>0);i--)
{
int posval=1;
if(strarray[i]=='X' )
{
result += 10*posval;
unitcount--;
posval *=10;
}
else if(strarray[i]=='I' )
{
result += 1*posval;
unitcount--;
posval *=10;
}
else if(strarray[i]=='V' )
{
result += 5*posval;
unitcount--;
posval *= 10;
}
else
{
Console.Write(strarray[i]); //handelled invalid string
}
}
for(int i=decimalindex+1 ;( i< strlen ) && (dec=true) && (decimalcount>0) ;i++)
{
int posval=10;
if(strarray[i]=='X')
{
result += 10*(1/posval);
decimalcount--;
posval *=10;
}
else if(strarray[i]=='I')
{
result += 1*(1/posval);
decimalcount--;
posval *=10;
}
else if(strarray[i]=='V')
{
result += 5*(1/posval); //Not Working Why?
decimalcount--;
posval *=10;
}
else
{
Console.Write(strarray[i]); //handelled invalid string
}
}
return result;
}
catch (Exception ex)
{
Console.WriteLine(ex);
return 0;
}
}
}
}
//ORDER:
//================
//O(N)
Roman to decimal is simple addition of decimal equivalent of roman digit. Only in case of number like IV, it is 5-1 = 4 OR for XC, 100-10 = 90.
#include<iostream>
using namespace std;
int map(char inp)
{
switch (inp)
{
case 'i':
case 'I':
return 1;
case 'v':
case 'V':
return 5;
case 'x':
case 'X':
return 10;
case 'l':
case 'L':
return 50;
case 'c':
case 'C':
return 100;
case 'd':
case 'D':
return 500;
default:
return 0;
}
}
int main()
{
char str[16];
int res = 0,prev = 501,curr = 0;
cout <<"Enter the input ROMAN string = ";
cin >> str;
int len = strlen(str);
for(int i=0;i<len;i++)
{
curr = map(str[i]);
if(curr<=prev)
res += curr;
else
{
res += curr;
res -= 2*prev;
}
prev = curr; //Re-initialize the previous
}
cout <<"The decimal equivalent of input Roman "<<str<<" = "<<res;
return 0;
}
<pre lang="" line="1" title="CodeMonkey84816" class="run-this">public boolean isValid(String romanNumeral) {
if (romanNumeral == null) {
return false;
}
if (romanNumeral.length() == 0) {
return true;
}
String regEx4RomanNumbers = "M{0,3}(CM|C{2,3}|CD?+|DC{0,3})?+(XC|X{2,3}|XL?+|LX{0,3})?+(IX|I{2,3}|IV?+|VI{0,3})?+";
return romanNumeral.toUpperCase().matches(regEx4RomanNumbers);
}
public int romanToDecimal(String romanNumeral) {
if (!isValid(romanNumeral)) {
return -1;
}
char[] r = { 'M', 'D', 'C', 'L', 'X', 'V', 'I' };
int[] d = { 1000, 500, 100, 50, 10, 5, 1 };
int result = 0;
int prev = Integer.MAX_VALUE;
for (char c : romanNumeral.toUpperCase().toCharArray()) {
for (int j = 0; j < r.length; ++j) {
if (c == r[j]) {
result += d[j];
if (d[j] > prev) {
result -= prev << 1;
}
prev = d[j];
}
}
}
return result;
}
</pre><pre title="CodeMonkey84816" input="yes">
</pre>
<pre lang="" line="1" title="CodeMonkey25874" class="run-this">public boolean isValidRomanNumeral(String romanNumeral) {
if (romanNumeral == null) {
return false;
}
if (romanNumeral.length() == 0) {
return true;
}
String regEx4RomanNumbers = "M{0,3}(CM|C{2,3}|CD?+|DC{0,3})?+(XC|X{2,3}|XL?+|LX{0,3})?+(IX|I{2,3}|IV?+|VI{0,3})?+";
return romanNumeral.toUpperCase().matches(regEx4RomanNumbers);
}
public int romanToDecimal2(String romanNumeral) {
if (!isValidRomanNumeral(romanNumeral)) {
return -1;
}
char[] r = { 'M', 'D', 'C', 'L', 'X', 'V', 'I' };
int[] d = { 1000, 500, 100, 50, 10, 5, 1 };
int result = 0;
int prev = Integer.MAX_VALUE;
for (char c : romanNumeral.toUpperCase().toCharArray()) {
for (int j = 0; j < r.length; ++j) {
if (c == r[j]) {
result += d[j];
if (d[j] > prev) {
result -= prev << 1;
}
prev = d[j];
}
}
}
return result;
}
</pre><pre title="CodeMonkey25874" input="yes">
</pre>
This code in JavaScript is what I came up with.
The additional thing about this code is it does throrough validity check of a Roman Numeral following all the rules of Roman Numerals:
1. Highest to lowest left to right. (meaning XII is valid, IIX is not)
2. A 10's place character (M, C, X, I) can be repeated max 3 times. (meaning CCC == 300 is valid, CCCC == 400 is not)
3. A 5's place character can't be repeated and can't be used to subtracted by keeping it on the left (V = 5 is valid, VV == 10, also XLV == 45 is valid, VL == 45 is not)
3. Only one character (a 10's place one obviously) can be used for subtraction. Also this character has to be at least 1/10th of the value of the character it is subtracting from.(VIII ==8 is valid, IIX == 8 is not valid; also XCIX == 99 is valid, IC == 99 is not)
All these validation checks are performed using a Regex and if found valid, conversion to decimal is proceeded with.
function Roman(value) {
this.value = value.split(' ').join('').toUpperCase();
}
Roman.prototype.isValid = function() {
var validity = /^(M{0,4})(CM|CD|D?C{0,3})(XC|XL|L?X{0,3})(IX|IV|V?I{0,3})$/i;
if (validity.test(this.value)) {
return true;
}
return false;
};
Roman.prototype.toDecimal = function () {
if (!this.isValid()) {
return "Invalid!";
}
function getDigit(ch) {
var rom = ['I', 'V', 'X', 'L', 'C', 'D', 'M'];
var dec = [1, 5, 10, 50, 100, 500, 1000];
for(var i = 0; i < rom.length; i++) {
if (ch == rom[i]) {
return dec[i];
}
}
return 0;
}
function isFifthPlace(ch) {
if (ch == 'V' || ch == 'L' || ch == 'D') {
return true;
}
return false;
}
function isPrevTens(big, small) {
if (big / small <= 10) {
return true;
}
return false;
};
var sum = 0;
var l = this.value.length;
for (var i = 0; i < l; i++) {
// get this digit
var currRom = this.value.charAt(i);
var currDec = getDigit(currRom);
var subFlag = false;
// if not the last digit
if (i < l - 1) {
// get next digit
var nextRom = this.value.charAt(i + 1);
var nextDec = getDigit(nextRom);
// if this digit is subtraction of last digit
if (currDec < nextDec && !isFifthPlace(currRom) && isPrevTens(nextDec, currDec)) {
subFlag = true;
} else {
subFlag = false;
}
}
// if subtraction flag is set
if (subFlag) {
sum -= currDec;
} else {
sum += currDec;
}
}
return sum;
};
(function driver() {
var i;
var r = ["XLV", "VL", "LV", "XM", "CCXM", "CMXC", "MMMCMXCIX"];
for(var i = 0; i < r.length; i++) {
var rom = new Roman(r[i]);
console.log(rom.value, rom.toDecimal());
}
}());
dfd
/*
- ankushbindlish March 14, 2010I = 1 (one)
V = 5 (five)
X = 10 (ten)
L = 50 (fifty)
C = 100 (one hundred)
D = 500 (five hundred)
*/
char lastCharacter = 0;
int lastCharacterCount =0;
int Convert(char *inputParam, int i, int j, int &sumSoFar){
// If a length is one return the result from the map table
int size = j-i+1;
if( size <1) return 0;
// Validate for contiguous rule
lastCharacterCount = (inputParam[j] != lastCharacter) ? 0 : lastCharacterCount++;
lastCharacter = inputParam[j];
if(lastCharacterCount == 4){
throw new ArgumentException("Rule 1 : Do not repeat any letter more than three times in a row. ");
}
if(size ==1) return Map(*inputParam);
if(!ValidateRepetitionRule(inputParam[j],inputParam[j-1]))
throw new ArgumentEcxeption("Rule 5 : Only powers of ten (I, X, C, M) can be repeated");
int impactDirection = (inputParam[j] <= inputParam[j-1]) ? 1 :-1;
int mappedValue = Map(inputParam[j]);
// Validate the algnment of symbols
if((impactDirection == 1) && (SumSoFar > mappedValue))
throw new ArgumentEcxeption("Rule 2 : The letters should be arranged from the one with the largest value to the one with the smallest");
if((impactDirection == -1) && inputParam[j-1] == 'V') // Assuming all are in lowercase.
throw new ArgumentEcxeption("Rule 3 : Only powers of ten (I, X, C, M) can be subtracted. ");
}
sumSoFar = mappedValue + impactDirection * Convert(inputParam, i, j-1);
return sumSoFar;
}
int Map(char inputChar){
switch(inputChar){
case 'v' : return 5;
case 'i' : return 1;
case 'x' : return 10;
case 'l' : return 50;
case 'c' : return 100;
case 'd' : return 500;
default : throw new ArgumentException("Rule 4 : Invalid symbol used");
}
}
bool ValidateRepetitionRule(char first, char second){
return (first == second) &&
( (first == 'i') ||
(first == 'm') ||
(first == 'c') ||
(first == 'm'));
}