Roman to Integer Palantir Python Interview Question

Given a valid Roman numeral, convert it to an integer.

in case you don't think about the Roman empire that often, and need a crash-course on how to go from Superbowl "XLIV" to an actual number, here's the table mapping the numerals to their values:

The numerals are generally written from largest to smallest from left to right. For example, the number 11 is written as XI, where X represents 10 and I represents 1, so the total is 11.

Similarly, XXX would be 30 (unless we're talking about your browser's search history).

Example 1:

Input: s = "XI"

Output: 11

Explanation: X = 10, I = 1, XI = 11

In certain cases, a smaller numeral comes before a larger one to indicate subtraction. For example, 4 is written as IV, where I comes before V, meaning 1 is subtracted from 5, resulting in 4. Similarly, 90 is written as XC, where X comes before C, meaning 10 is subtracted from 100, giving 90.

This subtraction rule applies in the following cases:

• I comes before V (5) or X (10) to make 4 and 9.
• X comes before L (50) or C (100) to make 40 and 90.
• C comes before D (500) or M (1000) to make 400 and 900.

Example 2:

Input: s = "LXIX"

Output: 69

Explanation: L = 50, X = 10, IX = 9, LXIX = 69. Nice.

Approach 1

Intuition

Roman numerals are typically written in two ways:

1. From largest to smallest values.
2. From smallest to largest values (in cases where subtraction is used).

In coding interviews, it’s really easy to get overwhelmed, so let’s not worry about the tricky cases where we have to subtract one numeral from another. Instead, let's focus on the simpler cases where Roman numerals appear in decreasing order.

For example:

• XV is 15. Here, X (10) comes before V (5), so we just add them together.
• DCLV is 655. D = 500, C = 100, L = 50, and V = 5. Again, we sum these values.

If the input was in this format, we would solve it like this:

This code works perfectly for cases where numerals are in descending order (largest to smallest). We just iterate through the string and add up the values.

Now, let’s address the second case. When a smaller numeral precedes a larger numeral, we need to subtract the smaller from the larger. The rule is simple: If the current numeral is smaller than the next one, treat them as a pair and subtract the smaller from the larger.

Here’s how we implement this:

• If the current character (numeral) is smaller than the next one, we subtract it and move forward by two positions.
• If it’s not smaller, we just add the current character’s value to the result and move to the next one.

Here’s the code for this case:

Approach 2

This approach works similarly to the first one but makes handling numeral pairs more straightforward. Instead of comparing consecutive numerals manually, we predefine all numeral combinations where subtraction is needed (like IV, IX, etc.) and store them in a dictionary for quick $O(1)$ access.

By doing this, we can check if two consecutive characters form a valid Roman numeral pair, and if so, we add their corresponding value from the dictionary. If not, we treat each character individually.

Here is the code: