Это третья статья из серии о вопросах на собеседовании по программированию и о том, как их продумать и решить! В этой статье будет рассмотрен вопрос собеседования с программистом по переводу римских цифр в JavaScript.

Учитывая римскую цифру в качестве входных данных, напишите функцию, которая преобразует римскую цифру в число и выводит его. Когда меньшее число появляется перед большим, это становится операцией вычитания. Вы можете предположить, что только одна меньшая цифра может появиться перед большей. Например: если задан входной VI, выход должен быть 6 (5 + 1 = 6), или если задан вход IV, выход должен быть 4 (5–1 = 4).

Анализ

Одна из наших самых больших проблем - знать, следует ли добавлять текущую букву к римской цифре или вычитать ее. Я решил, что во время итерации я смогу подняться вправо от текущей буквы и решить, прибавлять или вычитать. В худшем случае этот маршрут даст мне линейную временную сложность. Давайте посмотрим на псевдокод.

Псевдокод

function translateRomanNumerals(romanNumeral) {
  Create result variable
  Split input at each character
  
  Iterate through split input
    Save current letter and next letter into variables
    If current letter is undefined
      Return 'null'
    else 
      if current letter is less than next letter
        Add current letter minus next letter to result var
        Double increment count to skip next letter
      else
        Add current letter to result
  Return result
}

Сложность времени

Временная сложность описанного выше алгоритма должна быть такой же, как количество произведенных элементов. Это связано с тем, что по мере увеличения списка мы должны продолжать проверять каждую букву, чтобы добавить значение. Следовательно, при размере ввода n временная сложность линейна - O (n).

Код

Хорошая работа, пройти через это! По мере того, как вы будете решать более сложные задачи, вам нужно будет начать использовать структуры данных. Хотите узнать что-нибудь прямо сейчас? Я написал серию статей о структурах данных в JavaScript здесь.

Этот пост написал один из инструкторов Banyan Codecamp, нового учебного курса по программированию, разработанного с единственной целью: превратить начинающих программистов в способных инженеров под руководством старших инженеров. Получи высшее образование, сделай шестизначное число и учись на прекрасном острове Бали. Чтобы узнать больше, посетите www.codeinbali.com.