Facebook Interview Question Interns
Country: United States
Interview Type: Phone Interview
Now that I've seen someone else's solution, I wish I had iterated over the string from right-to-left.
long parse_roman(string const &roman) {
static map<char, long> values = {
{'I', 1 },
{'V', 5 },
{'X', 10 },
{'L', 50 },
{'C', 100 },
{'D', 500 },
{'M', 1000 },
};
long total = 0;
long lastdigit = 0;
long lastrun = 0;
for (auto i = roman.begin(); i != roman.end(); ++i) {
auto value = values.find(*i);
if (value == values.end()) {
ostringstream message;
message << "Illegal digit: " << *i;
throw runtime_error(message.str());
}
long digit = value->second;
if (digit == lastdigit) {
lastrun += digit;
} else {
if (digit < lastdigit) {
total += lastrun;
} else {
total -= lastrun;
}
lastdigit = lastrun = digit;
}
}
total += lastrun;
return total;
}
Borth the above solutions are wrong, because they don't handle the case XLIV.
Proper solution starts from end of string and proceeds towards first char. add if the prev elem is greater than cur. subtract if prev is less than cur.
prevValue = 0;
curSum = 0;
for ( i= str.lenght(0-1; i >=0; i--) {
curElem = str.at(i);
curValue = valueMap.find(curElem)->second;
if ( prevValue > 0 && prevValue < curValue) {
curSum = curSum - curValue;
else {
curSum +=curValue;
}
prevValue = curValue;
}
return curSum;
String str = "MCMXLVII";
HashMap<Character, Integer> roman = new HashMap<Character, Integer>();
roman.put('M', 1000);
roman.put('C', 100);
roman.put('L', 50);
roman.put('X', 10);
roman.put('V', 5);
roman.put('I', 1);
char[] chars = str.toCharArray();
int lastValue = Integer.MAX_VALUE;
int total = 0;
for(int i = 0; i < chars.length; i++)
{
char c = chars[i];
int value = roman.get(c);
if(value > lastValue)
total += (value-lastValue*2);
else
total += value;
lastValue = value;
}
System.out.println(total);
What are the rules to convert?
This is a bad interview question. Some people might not even know roman numerals, and those more familiar have a distinct advantage. Hard to judge anything by this question.
public static int RomanToInteger(string s)
{
int result = 0;
int d = 1;
int prev = -1;
for(int i = s.Length - 1; i >= 0; i--)
{
int curr = 0;
switch(s[i])
{
case 'I':
curr = 1;
break;
case 'V':
curr = 5;
break;
case 'X':
curr = 10;
break;
case 'L':
curr = 50;
break;
case 'C':
curr = 100;
break;
case 'D':
curr = 500;
break;
case 'M':
curr = 1000;
break;
default:
throw new Exception("Invalid roman numeral");
}
if (prev == -1 || curr > prev) d = 1;
else if (curr < prev) d= -1;
result += d * curr;
prev = curr;
}
return result;
}
Actually this would Work:
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package romantodecimal;
/**
*
* @author ASUS
*/
import java.util.Scanner;
public class RomanToDecimal {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
RomanToDecimal obj=new RomanToDecimal();
Scanner sc=new Scanner(System.in);
System.out.println("Enter Roman:");
System.out.println(obj.convert(sc.nextLine()));
}
public int convert(String s){
String []r={"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
int []v={1000,900,500,400,100,90,50,40,10,9,5,4,1};
int index=0;
int result=0;
while(!s.equals("")&&index<13){
while(s.startsWith(r[index])){
result+=v[index];
s=s.substring(r[index].length());
}
index++;
}
return result;
}
}
This code will be ok.
int Roman2Int(std::string & str) {
int rs = 0;
int pre = 1001;
int cur = 0;
for (int i = 0; i < str.size(); i++) {
if (str[i] == 'I') cur = 1;
else if (str[i] == 'V') cur = 5;
else if (str[i] == 'X') cur = 10;
else if (str[i] == 'L') cur = 50;
else if (str[i] == 'C') cur = 100;
else if (str[i] == 'D') cur = 500;
else cur = 1000;
if (cur <= pre) rs += cur;
else rs = rs - pre + (cur - pre);
pre = cur;
}
return rs;
}
My solution
package Other;
import java.util.HashMap;
public class Roman {
public static int roman2Decimal(String roman) {
HashMap<Character, Integer> values = new HashMap<Character, Integer>();
values.put('M', 1000);
values.put('C', 100);
values.put('L', 50);
values.put('X', 10);
values.put('V', 5);
values.put('I', 1);
int value = 0;
for (int index = 0; index < roman.length();) {
int tmp = 0;
char current = roman.charAt(index);
do {
tmp += values.get(current);
index++;
} while( index + 1 < roman.length() && roman.charAt(index) == current);
if (index < roman.length()
&& values.get(current) < values.get(roman.charAt(index))) {
tmp *= -1;
}
value += tmp;
}
return value;
}
public static void main(String args[]) {
System.out.println(roman2Decimal("IV"));
}
}
package Other;
import java.util.HashMap;
public class Roman {
public static int roman2Decimal(String roman) {
HashMap<Character, Integer> values = new HashMap<Character, Integer>();
values.put('M', 1000);
values.put('C', 100);
values.put('L', 50);
values.put('X', 10);
values.put('V', 5);
values.put('I', 1);
int value = 0;
for (int index = 0; index < roman.length();) {
int tmp = 0;
char current = roman.charAt(index);
do {
tmp += values.get(current);
index++;
} while( index + 1 < roman.length() && roman.charAt(index) == current);
if (index < roman.length()
&& values.get(current) < values.get(roman.charAt(index))) {
tmp *= -1;
}
value += tmp;
}
return value;
}
public static void main(String args[]) {
System.out.println(roman2Decimal("IV"));
}
}
class RomanNumeral {
public static int getNumberr (char c) {
switch(c) {
case 'I':
return 1;
case 'V':
return 5;
case 'X':
return 10;
case 'L':
return 50;
case 'C':
return 100;
case 'D':
return 500;
case 'M':
return 1000;
}
return 0;
}
public static int getNumber(String roman) {
int x = 0;
for (int i = 0; i < roman.length(); i++) {
int a = getNumberr(roman.charAt(i));
int b = (i+1) < roman.length() ? getNumberr(roman.charAt(i+1)) : 0;
if (a < b) {
x = x+ (b - a);
i++;
}
else {
x = x+ a;
}
}
return x;
}
public static void main(String args[]) {
String str = "MMMMCMXCIX";
System.out.println(" value is "+getNumber(str));
}
}
Roman numerals: see the wikipedia
const static string romanStr = "IVXLCDM"; const static int romanVal = {1, 5, 10, 50, 100, 500, 1000}; int GetRomanValue(string input) { int total = 0, temp = 0; for (string::iterator it = input.rbegin(); it != input.rend(); ++ it){ size t = romanString.find(*it); total += romanVal[t] > temp? romanVal[t] : -romanVal[t]; temp = romanVal[t]; } return total; }Suppose that "input" is a valid string of Roman characters.
- peter tang November 01, 2012