Палиндром

Я здесь, чтобы предложить вам самые популярные вопросы для подготовки к собеседованию. Сегодня я рад представить вам: палиндромы.

Палиндром – это слово, которое пишется одинаково в прямом и обратном порядке. Знаковые примеры включают «гоночный автомобиль», «11:11» и «какашки».

В контексте вопроса на собеседовании по кодированию это «слово» обычно представляется в виде строки, иногда длинной строки, которая не является настоящим словом.

Пример:

"aaaaaaabbbbbeeeeetttteeeebbbbbaaaaaaa"

Вопрос об интервью с палиндромом является популярным, потому что он может включать в себя манипуляции со строками, в частности перестановку строк, и предлагает несколько дополнительных вопросов по оптимизации.

Легкий способ (возможно, слишком простой)

function palindrome(str) {
   const reversed = str.split('').reverse().join('')
   return str === reversed
}

Этот первый пример очень прост и может считаться «обманом», потому что он настолько прямолинеен, что вы можете писать на Ruby.

Вы берете строку, разбиваете ее на массив и вызываете встроенный метод reverse() для массива (это та часть, которая упрощает работу). Это переворачивает все буквы, а затем вы снова соединяете их вместе в виде строки. Затем вы возвращаете логическое значение исходной строки === перевернутой строки. Если они === это палиндром, если нет… вы знаете, в чем дело.

Обратный звонок

function palindrome(str) {
  return str.split('').every((char, i) => {
    return char === str[str.length - i - 1]
  })
}

В этом подходе используется метод JavaScript .every(), который проверяет, все ли элементы в массиве проходят проверку. В данном случае мы проверяем равенство между персонажем и его палиндромным аналогом (сейчас это актуально). Сначала нам нужно превратить строку в массив путем разбиения, а затем мы проверяем каждый символ, сравнивая его с последним символом, предпоследним символом и так далее. Мне очень нравится такой подход.

Простой цикл

function palindrome(str) {
  for(let i=0; i<str.length; i++)
    if (str[i] !== str[str.length-1-i]) {
      return false
    }
  return true
}

Я люблю этот метод за его простоту. Он похож на предыдущий подход, но использует простой цикл. О чем вы еще хотите попросить? Ну, интервьюер может попросить больше оптимизации. Они могут сказать: «А что, если вы имеете дело с очень длинной строкой? Повторение этого может потребовать много итераций». На что вы скажете: «Я так и думал, что ты это скажешь! Следуйте за мной к следующему примеру!»

Оптимизированный цикл

function palindrome(str) {
  
  for(let i=0; i<str.length/2; i++)
    if (str[i] !== str[str.length-1-i]) {
      return false
    }
  return true
}

С помощью простой корректировки мы можем сделать наш простой цикл в два раза эффективнее. Давайте подумаем о проблеме…

Палиндром — это слово, которое пишется одинаково как в прямом, так и в обратном порядке, поэтому вторая половина — это просто первая половина в перевернутом виде. Итак, в таком случае, почему мы зацикливаемся на всем этом? Давайте просто пройдемся по первой половине, и мы сможем сравнить таким же образом, ссылаясь на символы во второй половине, как мы это делали раньше!

Теперь интервьюер спросит: «Когда вы можете начать?».

Рекурсивный

function palindrome(string) {
   let x = string.length
   
   if (x < 2) {
      return true
   } else if (string[x-1] === string[0]) {
      return palindrome(string.substring((x-1), 1))
   } else {
      return false
   }
}

Вероятно, было бы неплохо иметь возможность рекурсивно писать некоторые из ваших алгоритмов интервью. Насколько я слышал, интервьюерам это нравится, хотя рекурсивные функции не так уж эффективны.

В этом примере мы сначала указываем базовый случай, что строка состоит из одного символа. Если длина меньше двух, это палиндром (технически). Мы, оператор else if, просматриваем символы на противоположных сторонах, пока не дойдем до самой середины (базовый случай).

Черт, у нас все хорошо!