Convert a Roman Numeral to an Integer

Question

This question asks the candidate to convert a given Roman numeral string into its corresponding integer value.

Codemia · Accepted Answer

To convert a Roman numeral to an integer, we can iterate through the string from left to right. We will maintain a mapping of Roman numeral characters to their integer values. The key aspect of Roman numerals is that when a smaller numeral appears before a larger numeral, it should be subtracted rather than added.

1. Create a mapping of Roman numerals to integers: {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}.
2. Initialize a variable `total` to 0.
3. Loop through the string, comparing each numeral to the next one:
   - If the current numeral is less than the next, subtract its value from `total`.
   - Otherwise, add its value to `total`.
4. Return the `total` after the loop.

The time complexity of this algorithm is O(n), where n is the length of the Roman numeral string, as we iterate through the string once. The space complexity is O(1) since we are using a fixed-size mapping and a few variables.

```python
def roman_to_int(s: str) -> int:
    roman_map = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
    total = 0
    for i in range(len(s)):
        if i + 1 < len(s) and roman_map[s[i]] < roman_map[s[i + 1]]:
            total -= roman_map[s[i]]
        else:
            total += roman_map[s[i]]
    return total
```
This code accurately converts a Roman numeral to its integer equivalent.

When implementing this solution, consider edge cases such as invalid strings containing characters not in the Roman numeral system. You might want to validate the input before processing it. Additionally, handle cases where the Roman numeral representation is not valid, such as 'IIII' or 'VV'.

Convert a Roman Numeral to an Integer

Apple

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

Apple Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string