Roman to Integer
Asked at Google, Microsoft, Oracle, Uber
Problem
Convert a Roman numeral string to an integer. Roman numerals use letters to represent values, with subtractive notation (e.g., IV = 4, IX = 9). This problem tests your ability to handle special cases and scan strings in reverse.
Asked At
| Company | Difficulty | |
|---|---|---|
| Easy | View all Google questions → | |
| Microsoft | Easy | View all Microsoft questions → |
| Oracle | Easy | View all Oracle questions → |
| Uber | Easy | View all Uber questions → |
How to Think About It
Key insight: Roman numerals are additive from left to right, EXCEPT when a smaller value appears before a larger value (subtractive). For example, IV = 5 - 1 = 4, but VI = 5 + 1 = 6. Scan from right to left: if the current value is less than the previous value, subtract it; otherwise, add it.
The hash map approach: map each Roman character to its value. I=1, V=5, X=10, L=50, C=100, D=500, M=1000. Scan from right to left. Keep track of the "previous" value. If current < previous, subtract current. Otherwise, add current.
Why scan right to left: when you see a smaller value before a larger one (e.g., IV), you know at the larger value that the previous one should be subtracted. By scanning right to left, you naturally handle this: I is added, then V is encountered and I is subtracted, giving 5 - 1 = 4.
Visual walkthrough for "MCMXCIV" (1994):
Right to left: V=5 (add), C=100>5 (add), X=10<100 (add), C=100 (add), M=1000>100 (add), C=100<1000 (subtract), M=1000 (add)
Detailed: V(5) -> C(100) -> X(10<100, add 10) -> C(100) -> M(1000>100, add 1000) -> C(100<1000, subtract 100) -> M(1000)
= 5 + 100 + 10 + 100 + 1000 - 100 + 1000 = 1994
Edge cases: single character (e.g., "V" = 5). All additive (e.g., "LVIII" = 58). All subtractive pairs (e.g., "IV" = 4, "XC" = 90, "CD" = 400, "CM" = 900). Maximum value "MMMCMXCIX" = 3999.
Optimal Approach
Step 1: Create a hash map for Roman character values.
Step 2: Initialize result = 0, prev_value = 0.
Step 3: Scan the string from right to left:
- Get the value of the current character
- If current value < prev_value, subtract it from result
- Otherwise, add it to result
- Set prev_value = current value
Step 4: Return result.
Walkthrough for "MCMXCIV" (1994):
- V(5): add -> result=5
- I(1): 1<5, subtract -> result=4
- C(100): 100>1, add -> result=104
- X(10): 10<100, subtract -> result=94
- M(1000): 1000>10, add -> result=1094
- C(100): 100<1000, subtract -> result=994
- M(1000): 1000>100, add -> result=1994.
Time: O(n) -- single pass through the string. Space: O(1) -- only a few variables.
What Trips People Up in Real Interviews
Scanning left to right and trying to detect subtractive notation. This requires looking ahead at the next character, which adds complexity. Right-to-left scanning handles subtractive notation naturally without lookahead.
Forgetting that only I, X, C, and M can be subtracted. You can subtract I from V or X, X from L or C, C from D or M. You cannot subtract V from anything. The six subtractive patterns are: IV, IX, XL, XC, CD, CM.
Hardcoding all possible values instead of using a hash map. While a hash map is cleaner, some candidates list 15 if/else branches (I, II, III, IV, V, ...). This is error-prone and hard to maintain.
Not handling the edge case of a single character input. The right-to-left scan works fine with one character, but some implementations assume at least two characters and crash.
Confusing the direction of scanning. Left-to-right requires special handling for subtractive pairs (look ahead). Right-to-left naturally handles subtractive notation because you encounter the smaller value first.
Solution Code
def romanToInt(s):
roman = {'I':1, 'V':5, 'X':10, 'L':50, 'C':100, 'D':500, 'M':1000}
result = 0
prev = 0
for ch in reversed(s):
val = roman[ch]
if val < prev:
result -= val
else:
result += val
prev = val
return resultFrequently Asked Questions
What is the Roman to Integer problem?
Convert a Roman numeral string to an integer. Roman numerals use letters to represent values, with subtractive notation (e.g., IV = 4, IX = 9). This problem tests your ability to handle special cases and scan strings in reverse.
How do you solve Roman to Integer?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Roman to Integer?
Roman to Integer is asked at Google, Microsoft, Oracle, Uber. It is a easy difficulty problem.
What are common mistakes on Roman to Integer?
- Scanning left to right and trying to detect subtractive notation. This requires looking ahead at the next character, which adds complexity. Right-to-left scanning handles subtractive notation naturally without lookahead.
- Forgetting that only I, X, C, and M can be subtracted. You can subtract I from V or X, X from L or C, C from D or M. You cannot subtract V from anything. The six subtractive patterns are: IV, IX, XL, XC, CD, CM.
- Hardcoding all possible values instead of using a `hash map`. While a `hash map` is cleaner, some candidates list 15 if/else branches (I, II, III, IV, V, ...). This is error-prone and hard to maintain.
- Not handling the edge case of a single character input. The right-to-left scan works fine with one character, but some implementations assume at least two characters and crash.
- Confusing the direction of scanning. Left-to-right requires special handling for subtractive pairs (look ahead). Right-to-left naturally handles subtractive notation because you encounter the smaller value first.