Зачем искать палиндромы и вращать матрицы в поисках лучшей работы

Привет, Хабр! Меня зовут Василий Беляев. Я руководитель группы разработки фронтенда в «Криптоните». В этой статье мы разберём три задачи из тех, которые можем задать на собеседованиях. Заодно обсудим, зачем вообще решать типовые задания при трудоустройстве, когда есть Google и ChatGPT

Собеседование как свидание: каждый пытается произвести хорошее впечатление, но порой сбивается из-за волнения. Некоторым физически трудно рассказывать о себе, а другие — наоборот слишком красноречиво вещают о своих достижениях. Поэтому один из важных моментов общения с соискателем — проверка его знаний с помощью небольших алгоритмических задач.

Палиндром

Если какой-то набор символов одинаково читается в обе стороны, его называют палиндромом. Например, фраза «уверен и не реву», слово «radar» и число «404» — всё это палиндромы.

Первый способ проверки того, является ли строка палиндромом, кажется самоочевидным. Мы просто разбиваем строку на массив символов методом split(''), перечисляем символы в обратном порядке с помощью функции reverse() и объединяем в новую строку методом join('') для сравнения получившейся строки с исходной через оператор строгого равенства '===':

function checkPalindrome(str) {     return str === str.split('').reverse().join(''); }

Такой код быстро пишется и легко читается, но долго исполняется. Сложность алгоритма получается О(3n). Попробуем ускорить?

Второй способ апеллирует к математической логике. Он показывает, что для проверки на наличие палиндрома нет нужды проходить массив по три раза. Достаточно пройти его наполовину, — ведь само определение палиндрома говорит о том, что он делится пополам!

const originalWord = "шалаш"  function checkPalindrome(str){     for (let i = 0; i < (str.length/2).toFixed(); i++) {         if(str[i] !== str[str.length - i - 1]){             return false         }     }     return true }  checkPalindrome(originalWord)

Тонкий момент здесь связан с тем, что в JS нет строгой типизации, но length — всегда число, а метод .toFixed() возвращает строку. Во избежание возможных ошибок лучше заменить .toFixed() математическим методом  Math.floor, чтобы сразу получить целое число:

for (let i = 0; i < Math.floor(str.length / 2); i++) {

Остальной код останется без изменений. Мы просто помещаем в константу originalWord проверяемую строку, а затем передаём её функции checkPalindrome для анализа. В ней строка str принимается в качестве аргумента и цикл for проходит её от 0 до половины (str.length / 2). Внутри цикла проверяется, равен ли каждый следующий символ с индексом i зеркальному для него символу с индексом str.length - i - 1. Если они не равны, то функция возвращает false. То есть, строка не является палиндромом.

Примечание: во всех случаях надо не забыть очистить строку от лишних символов: убрать пробелы, знаки препинания и т.д. Иначе код будет работать корректно только в простых случаях.

Во втором способе код сложнее для восприятия, но выполняется минимум в шесть раз быстрее, поскольку максимальная сложность алгоритма получается O(n/2). Если первая и последняя буква не будут равны, цикл прервется раньше. Как думаете: какой вариант выберет джун, а какой — миддл?

Задача подсчёта элементов в списке

Это одна из самых часто встречающихся задач, с которой начинается обработка входных данных. Рассмотрим пару вариантов её решения.

Вариант 1

Допустим, у нас есть такой несортированный список элементов: ‘Чай’, ‘Кофе’, ‘Картошка’, ‘Кофе’, ‘Десерт’, ‘Стейк’, ‘Кофе’. Одни элементы встречаются лишь раз, а другие повторяются. Давайте узнаем, сколько у нас каких элементов:

const listOfItems = ['Чай', 'Кофе', 'Картошка', 'Кофе', 'Десерт', 'Стейк', 'Кофе']  function countlist(listarray){     const result = {}     listarray.forEach(element => {         if(result[element]){             result[element] +=1         } else {             result[element] = 1         }     });     return result }  countlist(listOfItems) 

Решение здесь довольно прямолинейное. Сначала мы создаём массив listOfItems в который помещаем все элементы списка. Затем используем функцию countlist, которая создаёт изначально пустой объект result. Чтобы наполнить result, метод forEach перебирает каждый элемент массива. Если элемента ещё нет в result, он добавляется в него с начальным значением 1. Если же элемент уже хранится в result, то его значение просто увеличивается на единицу. В итоге в result накапливаются записи, указывающие частоту встречаемости каждого элемента.

Такой код может быть использован для подсчёта элементов любого типа, а не только строковых.

Вариант 2 предлагает использовать встроенные методы массивов, что сократит количество кода, и в некоторых ситуациях может быть оптимальнее. В нём мы используем метод reduce(), благодаря чему накапливаем указание частоты встречаемости каждого элемента списка в одном проходе:

const listOfItems = ['Чай', 'Кофе', 'Картошка', 'Кофе', 'Десерт', 'Стейк', 'Кофе'];  function countList(listArray) {      return listArray.reduce((acc, item) => {          acc[item] = (acc[item] || 0) + 1;          return acc;      }, {});  }  countList(listOfItems)

Повторюсь: оба способа верны. Просто первый легче для восприятия, а второй больше подходит для больших-преогромных данных.

Сбой Поворот матрицы

Задачи с матрицами чуть сложнее и тоже часто встречаются на собеседованиях. Что поделать, матрицы повсюду: от картинок до шифрования. Рассмотрим пару способов повернуть матрицу на 90° по часовой стрелке. Для примера создадим двумерный массив originalMatrix, представляющий собой матрицу размером 3×3 и повернём её так, чтобы верхняя строка стала правым столбцом.

Способ 1.

Как и в предыдущей задаче, мы начинаем с того, что создаём пустой массив result. Только теперь он применяется для хранения элементов новой матрицы.

const originalMatrix = [     [1, 2, 3],     [4, 5, 6],     [7, 8, 9], ]  function rotateRight(matrix){     const result = []     for (let i = matrix.length-1; i >= 0; i--) {         for (let j = 0; j < matrix[i].length; j++) {             if(result[j]){                 result[j].push(matrix[i][j])             } else {                 result[j] = [matrix[i][j]]             }         }     }     return result }  rotateRight(originalMatrix)

Здесь мы используем функцию rotateRight, которая принимает исходную матрицу как аргумент. Формирование новой матрицы выполняется с помощью двух циклов: внешнего и внутреннего.

Внешний цикл проходит по всем строкам исходной матрицы в обратном порядке, считывая её снизу вверх. Вложенный цикл проходит по элементам каждой строки.

Если в result уже существует массив для текущего столбца (result[j]), то текущий элемент добавляется в этот массив. В противном случае создаётся новый массив с текущим элементом.

Код универсален в том плане, что поворачивает не только квадратные, но и прямоугольные матрицы любого размера. Алгоритм выполняется за время n, где n — размерность матрицы, поскольку каждый элемент обрабатывается однократно. Попробуем переписать его в функциональном стиле?

Способ 2.

Для функционального варианта обратимся к методам map и reverse.

const originalMatrix = [     [1, 2, 3],     [4, 5, 6],     [7, 8, 9], ];  function rotateRight(matrix) {     return matrix[0].map((_, index) =>          matrix.map(row => row[index]).reverse()     ); }  console.log(rotateRight(originalMatrix));

В этом варианте мы используем метод map для создания новой матрицы. Чтобы узнать число столбцов будущей матрицы, мы получаем длину первой строки через matrix[0]. Затем создаём столбцы из элементов исходной матрицы. Для этого внутри первого map вызывается второй и генерируется новый массив. Он будет содержать элементы из каждой строки матрицы с текущим индексом. Метод reverse(), как очевидно из названия, переворачивает полученный массив для поворота по часовой стрелке.

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

А как можно повернуть массив против часовой стрелки? Ждём твой ответ в комментариях!

Решение задач из этой статьи можно посмотреть на этой видеозаписи.

Вместо заключения

Есть много критериев подходящего кандидата, но не все они равноценные. Дипломы и сертификаты можно купить, домашние проекты — «позаимствовать» на гитхабе,  а вот решение задач (особенно в реальном времени) сразу показывает, как человек мыслит и к каким алгоритмическим конструкциям он привык. В большинстве случаев даже для очень простой задачи существует несколько вариантов решения. На собеседовании важно не просто решить её, но и выбрать оптимальный способ, а также не забывать рассуждать на тему решения вслух. Именно это в итоге показывает реальный уровень кандидата и его соответствие специфике проектов, которыми он займётся.