Amazon Interview Question Software Engineer / Developers
Here is the code to solve this.. This will generate values till 3999. I have not taken care of values bigger than that..
#include<stdio.h>
#define ONE 'I'
#define FIVE 'V'
#define TEN 'X'
#define FIFTY 'L'
#define HUNDRED 'C'
#define FIVE_HUNDRED 'D'
#define THOUSAND 'M'
#define MAX_COUNT 3
#define SUPER_MAX_COUNT 5
void convert(int num, char* str)
{
int j=0, i;
//int count = 0;
int temp;
//char str_temp[4];
int flag_set = 0;
int x = num;
// this will take care of values greater than 1000
temp = x/1000;
if(temp != 0)
{
for(i=0; i<temp; i++)
{
str[j++] = THOUSAND;
}
}
// this will take care of values in 100-1000
x=x%1000;
temp = x/100;
if(temp != 0)
{
if(temp >= SUPER_MAX_COUNT)
{
temp=temp-SUPER_MAX_COUNT;
str[j++] = FIVE_HUNDRED;
flag_set = 1;
}
if(temp >MAX_COUNT)
{
if(flag_set)j--;
str[j++] = HUNDRED;
if(flag_set) str[j++] = THOUSAND;
else str[j++] = FIVE_HUNDRED;
flag_set = 0;
}
else
{
for(i=0; i<temp; i++)
{
str[j++] = HUNDRED;
}
flag_set = 0;
}
}
// this will take care of values in 10-100
x=x%100;
temp = x/10;
if(temp != 0)
{
if(temp >= SUPER_MAX_COUNT)
{
temp=temp-SUPER_MAX_COUNT;
str[j++] = FIFTY;
flag_set = 1;
}
if(temp >MAX_COUNT)
{
if(flag_set)j--;
str[j++] = TEN;
if(flag_set) str[j++] = HUNDRED;
else str[j++] = FIFTY;
flag_set = 0;
}
else
{
for(i=0; i<temp; i++)
{
str[j++] = TEN;
}
flag_set = 0;
}
}
// this will take care of values in 1-10
x=x%10;
temp = x/1;
if(temp != 0)
{
if(temp >= SUPER_MAX_COUNT)
{
temp=temp-SUPER_MAX_COUNT;
str[j++] = FIVE;
flag_set = 1;
}
if(temp >MAX_COUNT)
{
if(flag_set) j--;
str[j++] = ONE;
if(flag_set) str[j++] = TEN;
else str[j++] = FIVE;
flag_set = 0;
}
else
{
for(i=0; i<temp; i++)
{
str[j++] = ONE;
}
flag_set = 0;
}
}
str[j] = '\0';
return;
}
The above solution is terrible. There's a number of nested loops and if statements, it uses modulo which is not needed. You'd never code this up in an interview and get it right the first time.
Pearls suggests loop unraveling, and in this case that's exactly what I'd do.
Hints:
Think through how you'd build up a number, say 3. Easy, keep adding Is to the string and subtracting 1 from n
How about 4? its a special case, print I then add 1 to n
Think through some other special cases (9, 40s, 90s, ...)
Although the above would produce very verbose code, it is easy to write, easy to understand, easy to add to, and can be written bug free on the first pass.
The above solution is terrible. There's a number of nested loops and if statements, it uses modulo which is not needed. You'd never code this up in an interview and get it right the first time.
Pearls suggests loop unraveling, and in this case that's exactly what I'd do.
Hints:
Think through how you'd build up a number, say 3. Easy, keep adding Is to the string and subtracting 1 from n
How about 4? its a special case, print I then add 1 to n
Think through some other special cases (9, 40s, 90s, ...)
Although the above would produce very verbose code, it is easy to write, easy to understand, easy to add to, and can be written bug free on the first pass.
Yes, if you want to max out at 3999, why not just hardcode?
In any case, apparently the "standard" roman numerals max out at 4999. So just hardocde and be done with. To generate the list, you can use any ugly code/resource you want.
Lookup table would be a bit silly. How about for something simpler (only including code to handle numbers up to 38:
String toRomanNumeral(int n) {
StringBuilder b = new StringBuilder();
while (n > 0) {
if (n > 8) {
if (n > 9) {
b.append(TEN);
n -= 10;
} else {
b.append(ONE);
n += 1;
}
} else if (n > 3) {
if (n > 4) {
b.append(FIVE);
n -= 5;
} else {
b.append(ONE);
n += 1;
}
} else {
b.append(ONE);
n -= 1;
}
}
return b.toString();
}
Why would a lookup table be silly?
In fact, trying to write dynamic generation code for this is silly:
1) We only need to work for numbers till 3999.
2) If we write complex code, there is potential for bugs, incurring extra test cost and maintenance costs.
3) Any code which generates the number will be inefficient compared to a lookup table. Lookup tables are real fast.
Just because it is an interview question does not mean you have to write idiotic code.
#include <string>
#include <iostream>
using namespace std;
int lookup(char base) {
switch(base) {
case 'M':
return 1000;
case 'D':
return 500;
case 'C':
return 100;
case 'L':
return 50;
case 'X':
return 10;
case 'V':
return 5;
case 'I':
return 1;
}
return -1;
}
void append(string& s, int& n, char base) {
int b = lookup(base);
if (b > n)
return;
int cur = n - b;
while (cur >= 0) {
n = cur;
cur = n - b;
s += base;
}
}
string decimalToRoman(int n) {
string roman;
append(s, n, 'M');
append(s, n, 'D');
append(s, n, 'C');
append(s, n, 'L');
append(s, n, 'X');
append(s, n, 'V');
append(s, n, 'I');
return roman;
}
#include <string>
#include <iostream>
using namespace std;
int lookup(char base) {
switch(base) {
case 'M':
return 1000;
case 'D':
return 500;
case 'C':
return 100;
case 'L':
return 50;
case 'X':
return 10;
case 'V':
return 5;
case 'I':
return 1;
}
return -1;
}
void append(string& s, int& n, char base) {
int b = lookup(base);
if (b > n)
return;
int cur = n - b;
while (cur >= 0) {
n = cur;
cur = n - b;
s += base;
}
}
string decimalToRoman(int n) {
string roman;
append(s, n, 'M');
append(s, n, 'D');
append(s, n, 'C');
append(s, n, 'L');
append(s, n, 'X');
append(s, n, 'V');
append(s, n, 'I');
return roman;
}
Here's working C# code
char[] RomanChars = new char[] { 'I', 'V', 'X', 'L', 'C', 'D', 'M' };
public string toRoman(int N)
{
if (N > 3999)
return "ERROR too big number";
StringBuilder result = new StringBuilder();
char _one = RomanChars[0];
char _five = RomanChars[1];
char _ten = RomanChars[2];
int current_index = 2;
while (N != 0 )
{
int digit = N%10;
if( digit < 4)
{
for(int i = 0; i< digit; i++)
result.Insert(0, _one);
}
if(digit == 4)
{
result.Insert(0, _five);
result.Insert(0, _one);
}
if(digit > 4 && digit < 9)
{
for(int i = 5; i< digit; i++)
result.Insert(0, _one);
result.Insert(0, _five);
}
if(digit == 9)
{
result.Insert(0, _ten);
result.Insert(0, _one);
}
N = N/10;
_one = RomanChars[Math.Min(current_index, RomanChars.Length-1)];
_five = RomanChars[Math.Min(current_index+1, RomanChars.Length-1)];
_ten = RomanChars[Math.Min(current_index + 2, RomanChars.Length - 1)];
current_index += 2;
}
return result.ToString();
}
The lookup codes shown above is not correct.
Here is a working Java version. I took the idea from here.
http://leepoint.net/notes-java/examples/components/romanNumerals/romanNumeral.html
public static String[] rom=new String[]{"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
public static int[] val=new int[]{1000,900,500,400,100,90,50,40,10,9,5,4,1};
public static int num_marks=13;
public static String decimal2Roman(int num){
StringBuffer result = new StringBuffer();
for(int i=0;i<num_marks;i++){
while (num >= val[i]) {
num -= val[i];
result.append(rom[i]);
}
}
return result.toString();
}
The lookup codes shown above is not correct.
Here is a working Java version. I took the idea from here.
http://leepoint.net/notes-java/examples/components/romanNumerals/romanNumeral.html
public static String[] rom=new String[]{"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
public static int[] val=new int[]{1000,900,500,400,100,90,50,40,10,9,5,4,1};
public static int num_marks=13;
public static String decimal2Roman(int num){
StringBuffer result = new StringBuffer();
for(int i=0;i<num_marks;i++){
while (num >= val[i]) {
num -= val[i];
result.append(rom[i]);
}
}
return result.toString();
}
The lookup codes shown above is not correct.
Here is a working Java version. I took the idea from here.
http://leepoint.net/notes-java/examples/components/romanNumerals/romanNumeral.html
public static String[] rom=new String[]{"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
public static int[] val=new int[]{1000,900,500,400,100,90,50,40,10,9,5,4,1};
public static int num_marks=13;
public static String decimal2Roman(int num){
StringBuffer result = new StringBuffer();
for(int i=0;i<num_marks;i++){
while (num >= val[i]) {
num -= val[i];
result.append(rom[i]);
}
}
return result.toString();
}
The lookup codes shown above is not correct.
Here is a working Java version. I took the idea from here.
http://leepoint.net/notes-java/examples/components/romanNumerals/romanNumeral.html
public static String[] rom=new String[]{"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
public static int[] val=new int[]{1000,900,500,400,100,90,50,40,10,9,5,4,1};
public static int num_marks=13;
public static String decimal2Roman(int num){
StringBuffer result = new StringBuffer();
for(int i=0;i<num_marks;i++){
while (num >= val[i]) {
num -= val[i];
result.append(rom[i]);
}
}
return result.toString();
}
I am actually not too familiar with the exact rules on converting int to roman numeral string. Maybe something like this will work?
public static String convert(int num) {
String answer = "";
for(int i=0; i<num; i++) {
answer = answer + "I";
answer = answer.replace("IIII", "IV");
answer = answer.replace("IVI", "V");
answer = answer.replace("VIV", "IX");
answer = answer.replace("IXI", "X");
answer = answer.replace("XXXX", "XL");
answer = answer.replace("XLX", "L");
answer = answer.replace("LXL", "LC");
answer = answer.replace("LCX", "C");
answer = answer.replace("CCCC", "CD");
answer = answer.replace("CDC", "D");
answer = answer.replace("DCD", "CM");
answer = answer.replace("CMC", "M");
}
return answer;
}
i think Anonymous' solution is going to work and the complexity is O(n). smart answer, btw...
Here is my code with explanation
public static String toRoman(int num)
{
String result="";
String symbols[]={"M","D","C","L","X","V","I"};
int values[]={1000,500,100,50,10,5,1};
while(num > 0)
{
for (int i=0;i<values.length;i++)
{
if(values[i] <=num)
{
//Next gets the next symbol candidate, which can precede the current symbol
//to skip symbols like L and V I am incrementing it by i%2
int next=i+ i%2;
//if values[i] < current number, we see if it can be represented
//in the form where a smaller symbol precedes it
//for that, if we are at i, we subtract the value of next symbol candidate a[next]
//from a[i-1]
//if its less than equal to the number than we use the combination of
//a[next] and a[i-1] to represent the roman no otherwise not
//example:num=40 i=2, a[i-1]=50, a[next]=10 so a[i-1]-a[next]=40, we can use the
//above convention here
//but for number 30, a[i-1]-a[next] gives 40 (same as above) which is greater than 30
//hence we follow the normal convetion here (the else block in the below code)
if ( (i>0) && (next<values.length) &&
(values[i-1]-values[next] <=num))
{
result=result+ symbols[next]+symbols[i-1];
num = num + values[next] - values[i-1] ;
i=-1; //setting the i to -1 helps in further checking of the if conditions
}
else
{
result+=symbols[i];
num-=values[i];
i=-1;
}
}
}
}
return result;
}
public class Roman {
public static void main(String[] args) {
int n = 51;
if (n >= 100) {
while (n >= 100) {
n = n - 100;
System.out.print("C");
}
}
if (n >= 50) {
while (n >= 50) {
n = n - 50;
System.out.print("L");
}
}
if (n >= 10) {
while (n >= 10) {
n = n - 10;
System.out.print("X");
}
}
if (n >= 5) {
while (n >= 5) {
n = n - 5;
System.out.print("V");
}
}
if (n > 0) {
while (n > 0) {
n = n - 1;
System.out.print("I");
}
}
}
}
public class Roman {
public static void main(String[] args) {
int n = 51;
if (n >= 100) {
while (n >= 100) {
n = n - 100;
System.out.print("C");
}
}
if (n >= 50) {
while (n >= 50) {
n = n - 50;
System.out.print("L");
}
}
if (n >= 10) {
while (n >= 10) {
n = n - 10;
System.out.print("X");
}
}
if (n >= 5) {
while (n >= 5) {
n = n - 5;
System.out.print("V");
}
}
if (n > 0) {
while (n > 0) {
n = n - 1;
System.out.print("I");
}
}
}
}
referring to the roman numeral table : hxxp://en.wikipedia.org/wiki/Roman_numerals
convert the decimal number to an array with individual digits.
for e.g. 449
array a= { 9,4,4}
hashmap[i][j] -> results in ith decimal position ( tens, hundredths, thousands etc), jth position in the given range ( i.e. for tens it will be : X,XX,XXX,XL,L,LX,LXX,LXXX,XC)
counter=a.length-1;
while(counter>=0)
{
print( hashmap[ counter+1 ] [ a[counter] ] );
counter--;
}
referring to the roman numeral table : hxxp://en.wikipedia.org/wiki/Roman_numerals
convert the decimal number to an array with individual digits.
for e.g. 449
array a= { 9,4,4}
hashmap[i][j] -> results in ith decimal position ( tens, hundredths, thousands etc), jth position in the given range ( i.e. for tens it will be : X,XX,XXX,XL,L,LX,LXX,LXXX,XC)
counter=a.length-1;
while(counter>=0)
{
print( hashmap[ counter+1 ] [ a[counter] ] );
counter--;
}
referring to the roman numeral table : ptth://en.wikipedia.org/wiki/Roman_numerals
convert the decimal number to an array with individual digits.
for e.g. 449
array a= { 9,4,4}
hashmap[i][j] -> results in ith decimal position ( tens, hundredths, thousands etc), jth position in the given range ( i.e. for tens it will be : X,XX,XXX,XL,L,LX,LXX,LXXX,XC)
counter=a.length-1;
while(counter>=0)
{
print( hashmap[ counter+1 ] [ a[counter] ] );
counter--;
}
Here is the code to solve this.. This will generate values till 3999. I have not taken care of values bigger than that..
- Swaroop March 22, 2009#include<stdio.h> #define ONE 'I' #define FIVE 'V' #define TEN 'X' #define FIFTY 'L' #define HUNDRED 'C' #define FIVE_HUNDRED 'D' #define THOUSAND 'M' #define MAX_COUNT 3 #define SUPER_MAX_COUNT 5 void convert(int num, char* str) { int j=0, i; //int count = 0; int temp; //char str_temp[4]; int flag_set = 0; int x = num; // this will take care of values greater than 1000 temp = x/1000; if(temp != 0) { for(i=0; i<temp; i++) { str[j++] = THOUSAND; } } // this will take care of values in 100-1000 x=x%1000; temp = x/100; if(temp != 0) { if(temp >= SUPER_MAX_COUNT) { temp=temp-SUPER_MAX_COUNT; str[j++] = FIVE_HUNDRED; flag_set = 1; } if(temp >MAX_COUNT) { if(flag_set)j--; str[j++] = HUNDRED; if(flag_set) str[j++] = THOUSAND; else str[j++] = FIVE_HUNDRED; flag_set = 0; } else { for(i=0; i<temp; i++) { str[j++] = HUNDRED; } flag_set = 0; } } // this will take care of values in 10-100 x=x%100; temp = x/10; if(temp != 0) { if(temp >= SUPER_MAX_COUNT) { temp=temp-SUPER_MAX_COUNT; str[j++] = FIFTY; flag_set = 1; } if(temp >MAX_COUNT) { if(flag_set)j--; str[j++] = TEN; if(flag_set) str[j++] = HUNDRED; else str[j++] = FIFTY; flag_set = 0; } else { for(i=0; i<temp; i++) { str[j++] = TEN; } flag_set = 0; } } // this will take care of values in 1-10 x=x%10; temp = x/1; if(temp != 0) { if(temp >= SUPER_MAX_COUNT) { temp=temp-SUPER_MAX_COUNT; str[j++] = FIVE; flag_set = 1; } if(temp >MAX_COUNT) { if(flag_set) j--; str[j++] = ONE; if(flag_set) str[j++] = TEN; else str[j++] = FIVE; flag_set = 0; } else { for(i=0; i<temp; i++) { str[j++] = ONE; } flag_set = 0; } } str[j] = '\0'; return; }