Amazon Coding Interview Question - Integer to Roman (LeetCode)

Показать описание

Check out my interview prep platform for learning the patterns!

Integer to Roman is a popular LeetCode coding question asked at many tech companies including Amazon, Google, Apple, Bloomberg, and Adobe. This algorithm question is a math based question involving the use of the division and modulus operators.

To solve this problem, we first must define all roman numerals that we could potentially have in our result. Roman numerals do have some odd edge cases where occasionally we must perform subtraction from the roman numeral on the right to the roman numeral on the left. Once we have all of our conversions ranging from 1000 to 1, we then can convert any integer to a roman numeral.

We loop over all of our numerals and divide the number from our input number. The result from division is the number of symbols we must add to our result for that specific conversion. Once we append the roman numeral(s) to our result, we then utilize the modulus operator to chop off the most significant digit from our input number. We do this for each conversion until our input number becomes zero.

The time complexity of our solution is going to be big oh of N where N is the number of roman numeral characters we have in our result. We use the repeat function in Java to generate all of the characters. Our space complexity is constant since we do not initialize any extra memory in the algorithm.

Рекомендации по теме

Комментарии

The time complexity is technically O(1) since the number of Roman numeral symbols and the max value (3999) are both fixed. So, the number of iterations and the result length are always bounded by constants.

asifjamil_

Upload more videos man. You explain the concepts so smoothly and simply

vaibhavjoshi

your videos keep getting better ! thanks a lot!

SarveshKumar-nhpd

u could use a Map instead of Numeral class I tried and it works

developlogic

Superb Explanation... Loved it - after you explained how to solve it, I myself tried to code and solved the problem too... Thankyou

coderart__

I understand having map entries for all the roman numerals in the problem statement - I, V, X, L, etc

What was the thought process/reasoning you had for also having map entries for the additional ones - CM, CD, XC, etc?

lasredchris