## Facebook Interview Question for Software Engineer / Developers

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
4
of 4 vote

``````#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;
}``````

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

k is constant.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

Kamy, arrays can access any index in O(1); thus, this algorithm works in O(n).

Comment hidden because of low score. Click to expand.
3
of 5 vote

``````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;
}``````

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

above solution won't work. it returns 10 for "IIX"

Comment hidden because of low score. Click to expand.
1
of 1 vote

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;
}

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

Your code doesn't work for some cases. eg, III =3; but your code will produce 1 as the answer. Like @showell30 said, you have to process the string right to left.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````static int Convert(string s) {
Dictionary<char, int> map = new Dictionary<char, int>();

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]];
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````static int Convert(string s) {
Dictionary<char, int> map = new Dictionary<char, int>();

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]];
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````static int Convert(string s) {
Dictionary<char, int> map = new Dictionary<char, int>();

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]];
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.IOException;

public class RomanStringToIntegerConversion {
public static void main(String[] args) throws IOException{

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]))
}
}

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);
}
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.