Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
Good point. Updated.
public enum Roman {
M(1000), CM(900), D(500), CD(400), C(100), XC(90), L(50), XL(40), X(10), IX(9), V(5), IV(4), I(1);
int value;
public int getValue() {
return value;
}
private Roman(int value) {
this.value = value;
}
public static String toRoman(int n) {
int m;
String ret = "";
for (Roman r : Roman.values()) {
if (r.getValue() <= n) {
m = n / r.getValue();
for (int i = 0; i < m; i++) {
ret += r.toString();
}
n -= m * r.getValue();
}
}
return ret;
}
public static void main(String[] a) {
System.out.println(Roman.toRoman(1999));
}
}
#include<stdio.h>
#include<stdlib.h>
#include<string>
char RCODE[13][3] = {"M", "CM", "D", "CD", "C", "XC", "L","XL", "X", "IX", "V", "IV", "I"};
int BVAL[] = {1000, 900, 500, 400, 100, 90, 50,40, 10, 9, 5, 4, 1};
int main()
{
int n;
int i;
scanf("%d",&n);
while(n>0)
{
for(i=0;i<13;i++)
{
while(BVAL[i]<=n)
{
n=n-BVAL[i];
printf("%s" ,RCODE[i]);
}
}
printf("\n");
scanf("%d",&n);
}
getchar();
return 0;
}
enum Roman {
M(1000), D(500), C(100), L(50), X(10), V(5), I(1);
int value;
public int getValue() { return value; }
public int value(int value) { this.value = value; }
public static String toRoman(int n) {
int m;
String ret;
for (Roman r : Roman.getValues()) {
if (r.getValue() > n) {
m = n / r.getValue();
while (m-- > 0) {
ret += r.toString();
}
n -= m * r.getValue();
}
}
}
}
Interesting ruleset :)
From algorithmic point of view, 98 really should be VCIII but it's not... :)
Your best choice here is to hard-wire the rules like Larry did. Unfortunately this one itself disqualifies the question as there were no extra information provided how to calculate these numbers.
C version of solution provided by larry
#include <stdio.h>
int main()
{
typedef struct
{
char *ch;
int num;
}database;
database a[] = { {"M", 1000}, {"CM", 900}, {"D", 500}, {"CD", 400}, {"C", 100}, {"XC",90},
{"L", 50}, {"XL", 40}, {"X",10}, {"IX", 9}, {"V", 5}, {"IV", 4}, {"I", 1} };
int value = 2012;
int numElements = sizeof(a) / ( sizeof(database) );
printf("value=%d in roman numbers is ", value);
while ( value > 0)
{
for(int i=0; i<numElements; i++)
{
int m=0;
if(a[i].num <= value)
{
m = value / a[i].num;
for(int j=0;j<m;j++)
{
printf("%s",a[i].ch);
}
value = value % a[i].num;
}
}
}
getchar();
return 0;
}
#include<stdio.h>
int bin_srch(int *range,int n,int l,int r,int *i)
{
int m;
if(l<r)
{
if(l==r-1)
*i=l;
else
{
m=(l+r)/2;
if(n<range[m])
bin_srch(range,n,l,m,i);
else
bin_srch(range,n,m,r,i);
}
}
return -1;
}
void decimal_to_roman(int n)
{
if(n>0)
{
int i,range[13]={1,4,5,9,10,40,50,90,100,400,500,900,1000};
char roman[13]={'I',' ','V',' ','X',' ','L',' ','C',' ','D',' ','M'};
if(n>=1000)
{
printf("%c",roman[12]);
decimal_to_roman(n-range[12]);
}
else
{
bin_srch(range,n,0,12,&i);
if(i%2==0)
{
printf("%c",roman[i]);
decimal_to_roman(n-range[i]);
}
else
{
decimal_to_roman(range[i+1]-n);
printf("%c",roman[i+1]);
}
}
}
}
int main()
{
int n;
printf("Enter the number\n");
scanf("%d",&n);
decimal_to_roman(n);
printf("\n");
getch();
}
static string DigitToRoman(int n, int d)
{
string[,] map = new string[3, 3] { { "I", "V", "X" }, { "X", "L", "C" }, { "C", "D", "M" } };
string result="";
if (d <= 2)
{
switch (n)
{
case 0:
result = "";
break;
case 1:
result = map[d, 0];
break;
case 2:
result = map[d, 0] + map[d, 0];
break;
case 3:
result = map[d, 0] + map[d, 0] + map[d, 0];
break;
case 4:
result = map[d, 0] + map[d, 1];
break;
case 5:
result = map[d, 1];
break;
case 6:
result = map[d, 1] + map[d, 0];
break;
case 7:
result = map[d, 1] + map[d, 0] + map[d, 0];
break;
case 8:
result = map[d, 1] + map[d, 0] + map[d, 0] + map[d, 0];
break;
case 9:
result = map[d, 0] + map[d, 2];
break;
}
}
else if (d == 3 && n < 5)
{
while (--n >= 0)
{
result += "M";
}
}
else
{
return "Error! Can't convert numbers larger than 4999.";
}
return result;
}
static string ConvertToRoman(int num)
{
int d = 0;
string result = "";
while (num > 0)
{
int n = num % 10;
result = DigitToRoman(n, d) + result;
d++;
num = num / 10;
}
return result;
}
- Larry March 05, 2012