Twitter Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
#include<string>
using namespace std;
int roman_number(string str);
int main() {
char s[80];
int value;
scanf("%s",s);
value = roman_number(s);
printf("The roman value is %d",value);
return 0;
}
int roman_number(string str)
{
bool flagI = false, flagX = false, flagC = false;
int cnt[] = {0,0,0,0,0,0,0};
int i, sum=0, len = str.length();
char ch;
for(i = len-1;i >= 0; i--) {
ch=str.at(i);
switch(ch) {
case 'I':
cnt[0]++;
if ((flagX || flagC) ||
(cnt[0]>3) || (flagI && cnt[0]>1)) {
printf("wrong input \n");
goto err;
}
if (!flagI) {
sum = sum + 1;
} else {
sum = sum - 1;
}
break;
case 'V':
cnt[1]++;
if (cnt[1]>1) {
printf("wrong input \n");
goto err;
}
flagI = true;
sum = sum + 5;
break;
case 'X':
cnt[2]++;
if (flagC || (cnt[2]>3) || (flagX && cnt[2]>1)) {
printf("wrong input \n");
goto err;
}
flagI = true;
if (!flagX) {
sum = sum + 10;
} else {
sum = sum - 10;
}
break;
case 'L':
cnt[3]++;
if (cnt[3]>1) {
printf("wrong input \n");
goto err;
}
flagX = true;
sum = sum + 50;
break;
case 'C':
cnt[4]++;
if (cnt[4]>3 || (flagC && cnt[4]>1)) {
printf("wrong input \n");
goto err;
}
flagX = true;
if (!flagC) {
sum = sum + 100;
} else {
sum = sum - 100;
}
break;
case 'D':
cnt[5]++;
if (cnt[5]>1) {
printf("wrong input \n");
goto err;
}
flagC = true;
sum = sum + 500;
break;
case 'M':
cnt[6]++;
if (cnt[6]>3) {
printf("wrong input \n");
goto err;
}
flagC = true;
sum = sum + 1000;
break;
}
}
return sum;
err:
return -1;
}
private final static TreeMap<Character, Integer> romanMap = new TreeMap<Character, Integer>();
static {
romanMap.put('M', 1000);
romanMap.put('D', 500);
romanMap.put('C', 100);
romanMap.put('L', 50);
romanMap.put('X', 10);
romanMap.put('V', 5);
romanMap.put('I', 1);
}
public int romanToInt(String s) {
int intNum = 0;
int prev = 0;
for (int i = s.length() - 1; i >= 0; i--) {
int temp = romanMap.get(s.charAt(i));
if (temp < prev)
intNum -= temp;
else
intNum += temp;
prev = temp;
}
return intNum;
}
int keyval[] = { 1000, 900, 500, 400, 100,90, 50, 40, 10, 9, 5, 4, 1 };
char keystr[13][] = { "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" };
int i;
char str[] = "XXIV";
char *ptr=str;
int val=0;
for(i=0; i<13 ; i++)
{
l=strlen(keystr[i]);
if(!strncmp(ptr,keystr[i],l))
{
val+=keyval[i];
ptr+=l;
}
}
printf("\n val: %d", val);
Your code is both inefficient and incorrect. For starters try and understand the problem, take a few examples and then write the code. You calculate string length for all possible combinations each time. Whereas this problem can be solved using one pass linear scan.
This is one pass scan Sir!
if the strlen bothers you, replace 'l' with ls[i] with ls defined as follow: int ls[]={ 1, 2, 1, 2, etc...
I replied above for the "inefficient". Let me reply for the "incorrect". I made a small change with "while" instead of "if" and tested it OK.
#include <stdio.h>
int keyval[] = { 1000, 900, 500, 400, 100,90, 50, 40, 10, 9, 5, 4, 1 };
char keystr[13][3] = { "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" };
char str[] = "XXIV";
void decode()
{
char *ptr=str;
int i, l;
int val=0;
for(i=0; i<13 ; i++)
{
l=strlen(keystr[i]);
while(!strncmp(ptr,keystr[i],l))
{
val+=keyval[i];
ptr+=l;
}
}
printf("\n val: %d", val);
}
void main()
{
int i;
decode();
exit(000);
}
Let me give you a hint. You can solve this by scanning each character once and you don't need to keep compound character sets like IV, IX etc. Think about addition and subtraction. You are thinking too complex.
- george.maggessy April 10, 2013