Ebay Interview Question Software Engineer / Developers
Country: United States
Not going to type it out, but in general (1) express all roman numerals in terms of each other - i.e. "V" = "IIIII", (2) parse given roman numerals character by character, reducing each character down to it's most basic form (in terms of I's), (3) concatenate the 2 strings of I's, (4) and simply count the length of the resulting string.
The one guy who just converts roman numerals to integars - that isn't allowed in the question.
The algorithm has just five steps:
Substitute for any subtractives in both values; that is; "uncompact" the Roman values.
Put the two values together—catenate them.
Sort the symbols in order from left-to-right with the "largest" symbols on the left.
Starting with the right end, combine groups of the same symbols that can make a "larger" one and substitute the single larger one.
Compact the result by substituting subtractives where possible.
As an example, perform CCCLXIX + DCCCXLV.
1. Substitute for any subtractives to obtain: CCCLXVIIII + DCCCXXXXV
2. Catenate to obtain: CCCLXVIIIIDCCCXXXXV
3. Sort to obtain: DCCCCCCLXXXXXVVIIII
4. Combine groups to obtain: DCCCCCCLXXXXXXIIII
DCCCCCCLLXIIII
DCCCCCCCXIIII
DDCCXIIII
MCCXIIII
5. Substitute any subtractives to obtain: MCCXIV
You can verify that this is indeed the correct by converting the values to regular notation: 369 + 845 = 1214.
Resubmission - sorry, I did not surround with
.
#include <string>
#include <cstdio>
#include <cmath>
#include <cassert>
using namespace std;
// finite number of characters; just a reminder to myself
static const char numerals[] = {'I', 'V', 'X', 'L', 'C', 'D', 'M'}; // 1, 5, 10, 50, 100, 500, 1000
// Model for a roman numeral
struct RomanNumeral{
int nM; // number of Ms
int nD; // number of Ds
int nC; // number of Cs
int nL; // number of Ls
int nX; // number of Xs
int nV; // number of Vs
int nI; // number of Is
RomanNumeral ()
: nM(0),nD(0),nC(0),nL(0),nX(0),nV(0),nI(0)
{
}
};
// Optimize the roman numeral, inline. e.g. VIIIII -> VV -> X
static void optimizeRoman(RomanNumeral & r){
int n5I = (int)floor(r.nI/5.); r.nI %= 5; r.nV += n5I; // 1
int n2V = (int)floor(r.nV/2.); r.nV %= 2; r.nX += n2V; // 5
int n5X = (int)floor(r.nX/5.); r.nX %= 5; r.nL += n5I; // 10
int n2L = (int)floor(r.nL/2.); r.nL %= 2; r.nC += n2V; // 50
int n5C = (int)floor(r.nC/5.); r.nC %= 5; r.nD += n5I; // 100
int n2D = (int)floor(r.nD/2.); r.nD %= 2; r.nM += n2V; // 500
}
// Convert a string rep of roman numeral to RomanNumeral rep.
static const RomanNumeral str2roman(const string& str) throw (string){
RomanNumeral R;
for(int i=0; i<str.size(); i++){
char c = str[i];
if( c == 'M' || c == 'm' ) R.nM++;
else if( c == 'D' || c == 'd' ) R.nD++;
else if( c == 'C' || c == 'c' ) R.nC++;
else if( c == 'L' || c == 'l' ) R.nL++;
else if( c == 'X' || c == 'x' ) R.nX++;
else if( c == 'V' || c == 'v' ) R.nV++;
else if( c == 'I' || c == 'i' ) R.nI++;
else{
throw "Illegal!";
}
}
// make sure it's optimized
optimizeRoman(R);
return R;
}
// convert a RomanNumeral rep to a string
static const string roman2str(const RomanNumeral& r){
// assume RomanNumeral is optimized
string str = "";
for(int i=0; i<r.nM; i++){
str += 'M';
}
for(int i=0; i<r.nD; i++){
str += 'D';
}
for(int i=0; i<r.nC; i++){
str += 'C';
}
for(int i=0; i<r.nL; i++){
str += 'L';
}
for(int i=0; i<r.nX; i++){
str += 'X';
}
for(int i=0; i<r.nV; i++){
str += 'V';
}
for(int i=0; i<r.nI; i++){
str += 'I';
}
return str;
}
// Add two RomanNumeral rep of roman numerals
static const RomanNumeral add(const RomanNumeral& left, const RomanNumeral& right)
{
RomanNumeral R;
R.nM = left.nM + right.nM;
R.nD = left.nD + right.nD;
R.nC = left.nC + right.nC;
R.nL = left.nL + right.nL;
R.nX = left.nX + right.nX;
R.nV = left.nV + right.nV;
R.nI = left.nI + right.nI;
optimizeRoman(R);
return R;
}
// Add two string reps of roman numerals
static const string add(const string& left, const string& right)
{
RomanNumeral sum = add( str2roman(left), str2roman(right) );
return roman2str(sum);
}
static void printRoman( const RomanNumeral& r ){
printf("M=%d,D=%d,C=%d,L=%d,X=%d,V=%d,I=%d\n",
r.nM, r.nD, r.nC, r.nL, r.nX, r.nV, r.nI);
}
//===================================================================
// MAIN MAIN MAIN!!!
//===================================================================
int main(int argc, const char** argv){
assert(argc >= 3);
string str1 = argv[1];
string str2 = argv[2];
string str3 = add(str1, str2);
printf("%s + %s = %s\n", str1.c_str(), str2.c_str(), str3.c_str());
}
Instead of writing this 1000 lines of code, it would be better if you can explain the logic.
- Anonymous January 08, 2012