Facebook Interview Question Software Engineer / Developers
Country: United States
Interview Type: In-Person
isn't switch as running through an array of constant dimension K , looking for the correct match? If so the complexity of what you wrote in O(n * k) where n is the size of the string.
Nice, straightforward solution with clean code. An alternative solution is to process the string in reverse order, which makes the CM scenario become a sign flip on C instead of a double subtraction.
int Roman2Int(string s)
{
if(s.length()==0)return 0;
unordered_map<char,int> table;
table['I'] = 1;
table['V'] = 5;
table['X'] = 10;
table['L'] = 50;
table['C'] = 100;
table['D'] = 500;
table['M'] = 1000;
int ans = table[s[s.length()-1]];
for(int i=s.length()-2;i>=0;i--)
{
if(table[s[i]] < table[s[i+1]])
ans -= table[s[i]];
else
ans += table[s[i]];
}
return ans;
}
You could avoiding using hashmap by creating a separate function and using case statements in it. But I like your solution, it's compact yet so readable.
O(k) space
O(n) time
public int getValue(String romNum){
Map <Character, Integer> romanNumeralToInteger = new LinkedHashMap <Character, Integer>(){
{
put('I', 1);
put('V', 5);
put('X', 10);
put('L', 50);
put('C', 100);
put('D', 500);
put('M', 1000);
}
};
int total = 0;
int prev = 0;
for (int i = 0; i < romNum.length(); i++){
char cur = romNum.charAt(i);
int curVal = romanNumeralToInteger.get(cur);
if (prev < curVal){
total -= prev*2;
}
total+=curVal;
prev = curVal;
}
return total;
Javascript solution inspired by @showell30 comment:
var r2n = {
I: 1,
V: 5,
X: 10,
L: 50,
C: 100,
D: 500,
M: 1000,
};
function roman2num(roman) {
var sum = 0,
curr = 0,
prev = 0;
for (var i=roman.length-1; i>=0; i--) {
curr = r2n[roman[i]];
sum += curr >= prev ? curr : -curr;
prev = curr;
}
return sum;
}
console.log(roman2num(['C','M','I','V']));
Output should be: 904
static int Convert(string s) {
Dictionary<char, int> map = new Dictionary<char, int>();
map.Add('I', 1);
map.Add('V', 5);
map.Add('X', 10);
map.Add('L', 50);
map.Add('C', 100);
map.Add('D', 500);
map.Add('M', 1000);
int total = 0;
int previous = map[s[0]];
for (int i = 0; i < s.Length; i++) {
if (previous >= map[s[i]])
{
total = total + map[s[i]];
}
else {
total = total + map[s[i]] - 2 * previous;
}
previous = map[s[i]];
}
return total;
}
static int Convert(string s) {
Dictionary<char, int> map = new Dictionary<char, int>();
map.Add('I', 1);
map.Add('V', 5);
map.Add('X', 10);
map.Add('L', 50);
map.Add('C', 100);
map.Add('D', 500);
map.Add('M', 1000);
int total = 0;
int previous = map[s[0]];
for (int i = 0; i < s.Length; i++) {
if (previous >= map[s[i]])
{
total = total + map[s[i]];
}
else {
total = total + map[s[i]] - 2 * previous;
}
previous = map[s[i]];
}
return total;
}
static int Convert(string s) {
Dictionary<char, int> map = new Dictionary<char, int>();
map.Add('I', 1);
map.Add('V', 5);
map.Add('X', 10);
map.Add('L', 50);
map.Add('C', 100);
map.Add('D', 500);
map.Add('M', 1000);
int total = 0;
int previous = map[s[0]];
for (int i = 0; i < s.Length; i++) {
if (previous >= map[s[i]])
{
total = total + map[s[i]];
}
else {
total = total + map[s[i]] - 2 * previous;
}
previous = map[s[i]];
}
return total;
}
My attempt at it. Salient features of my solution:
1. I am using no auxiliary memory.
2. Code is more readable as I am only flipping signs for 2 cases.
3. I am scanning the string from left to right.
Following is a C++ solution.
int AssociatedValue(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;
}
int Roman2Int(string s)
{
int i;
if(s.length()==0)return 0;
int result = 0;
for(i=0;i<s.length()-1;i++)
{
if(AssociatedValue(s[i]) < AssociatedValue(s[i+1]))
result -= AssociatedValue(s[i]);
else
result += AssociatedValue(s[i]);
}
result += AssociatedValue(s[i]);
return result;
}
Time complexity = O(n) where n is the length of input string.
Space complexity = O(1)
My solution to this problem uses an auxiliary hashmap and solves the problem in O(n) time
import java.util.Set;
import java.io.File;
import java.util.HashMap;
import java.util.HashSet;
import java.io.FileReader;
import java.io.IOException;
import java.io.BufferedReader;
public class RomanStringToIntegerConversion {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in)));
String[] romanString = br.readLine().split("");
HashMap<String, Integer> romanToIntegerMap = new HashMap<String, Integer>();
romanToIntegerMap.put("I", 1);
romanToIntegerMap.put("V", 5);
romanToIntegerMap.put("X", 10);
romanToIntegerMap.put("L", 50);
romanToIntegerMap.put("C", 100);
romanToIntegerMap.put("D", 500);
romanToIntegerMap.put("M", 1000);
int numLength = romanString.length;
Set<Integer> lessIndices = new HashSet<Integer>();
for(int i = 0; i < numLength; ++i){
if(i+1 < numLength){
if(romanToIntegerMap.get(romanString[i]) < romanToIntegerMap.get(romanString[i+1]))
lessIndices.add(i);
}
}
int num = 0;
for(int i = 0; i < numLength;){
if(!lessIndices.contains(i)){
num = num + romanToIntegerMap.get(romanString[i]);
++i;
}
else{
num = num + romanToIntegerMap.get(romanString[i+1]) - romanToIntegerMap.get(romanString[i]);
i+=2;
}
}
System.out.println("The integer representation of the roman numeral is : " + num);
}
}
- Anonymous February 27, 2013#include <iostream> #include <string> using namespace std; int Roman2Num(string &a){ int sum = 0; int cur = 1001; int pre = 0; for (int i = 0; i<a.length(); i++){ switch (a[i]){ case 'I': cur = 1; break; case 'V': cur = 5; break; case 'X': cur = 10; break; case 'L': cur = 50; break; case 'C': cur = 100; break; case 'D': cur = 500; break; case 'M': cur = 1000; break; } if (cur <= pre) sum += cur; else sum = sum - pre - pre + cur; pre = cur; } return sum; } int main(){ string a; cin >> a; cout << Roman2Num(a) << endl; return 0; }