Привет, Хабр! Меня зовут Василий Беляев. Я руководитель группы разработки фронтенда в «Криптоните». В этой статье мы разберём три задачи из тех, которые можем задать на собеседованиях. Заодно обсудим, зачем вообще решать типовые задания при трудоустройстве, когда есть 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, представляющий собой матрицу размером 3x3 и повернём её так, чтобы верхняя строка стала правым столбцом.
Способ 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()
, как очевидно из названия, переворачивает полученный массив для поворота по часовой стрелке.
Код выглядит короче, но выполняется вдвое дольше из-за необходимости дважды обращаться к каждому элементу матрицы. Как видим, не все функциональные приёмы одинаково полезны.
А как можно повернуть массив против часовой стрелки? Ждём твой ответ в комментариях!
Решение задач из этой статьи можно посмотреть на этой видеозаписи.
Вместо заключения
Есть много критериев подходящего кандидата, но не все они равноценные. Дипломы и сертификаты можно купить, домашние проекты — «позаимствовать» на гитхабе, а вот решение задач (особенно в реальном времени) сразу показывает, как человек мыслит и к каким алгоритмическим конструкциям он привык. В большинстве случаев даже для очень простой задачи существует несколько вариантов решения. На собеседовании важно не просто решить её, но и выбрать оптимальный способ, а также не забывать рассуждать на тему решения вслух. Именно это в итоге показывает реальный уровень кандидата и его соответствие специфике проектов, которыми он займётся.
Комментарии (5)
stan_volodarsky
07.11.2024 07:37(str.length/2).toFixed()
- это действительно страшно.
В выраженииMath.floor(str.length / 2)
вызовMath.floor
не нужен. Этот конкретныйfor
и без него отлично будет работать.
Вычислять верхнюю границу вfor
плохо и очень плохо. Она вычисляется на каждой итерации.
Ваши примера кода служат антирекламой компании. Не позорьтесь, уберите подальше.
Keeper11
07.11.2024 07:37О(3n)
Безграмотно. Запись O(n) уже предполагает линейную зависимость от n с каким-то коэффициентом.
Lewigh
07.11.2024 07:37Есть много критериев подходящего кандидата, но не все они равноценные. Дипломы и сертификаты можно купить, домашние проекты — «позаимствовать» на гитхабе, а вот решение задач (особенно в реальном времени) сразу показывает, как человек мыслит и к каким алгоритмическим конструкциям он привык.
Можно сколько угодно себя убеждать что "волшебные" алгоритмические задачи решать все ваши проблемы с подбором и как будто бы показывают как человек мыслит, но реальность такова что такие задачи показывают только как человек решает... такие задачи, причем именно за ограниченное время.
У меня есть хороший пример на эту тему. Как то работал на двух разных проектах с двумя разрабами. Уровень говнокода написанного первым стал легендой. Человек просто не мог писать нормально, понятно, расширяемо и оптимально. Его код проще было полностью заново переписать чем пытаться модифицировать. Другой разраб, будучи мидлом, как то раз решил простейшую задачу по блокировке доступа к ресурсу, таким образом что про это хоть отдельную статью писать. Вместо добавления обычного флага и поля с датой, история вылилась в многопоточное решение с отдельным экзекутором и хитрыми механизмами разблокировок в стиле "машинного обучения". При этом все это работало плохо и в случае повторного доступа к странице - блокировало пользователя без возможности как то блокировку снять до таймаута. Решение было просто легендарное.
Что же объединяет этих двух разработчиков и зачем я про них написал?
Они оба были победителями олимпиад по программированию и отлично решали алгоритмы.
И наверняка бы прошли бы любые алгоритмически интервью на 5 с плюсом.
Понять как мыслит человек можно только поработав с этим человеком и посмотрев как он решает разноплановые задачи а все эти попытки через найти "серебряную пулю" через алгоритмические или system design интервью - просто самообман.
Не залезете вы в голову человеку даже за 2 часа интервью. Максимум что можно сделать это построить его таким образом чтобы разноплановыми вопросами, размышлениями и небольшими задачами, пошатать собеседуемого и посмотреть что он действительно понимает а что заученно или подсмотрено, построить вопросы так чтобы сложно было дать шаблонный ответ. И прикинуть насколько все это подходит под ваш проект. А дальше только на испытательном смотреть.
Farongy
За последний год сколько раз у ваших разработчиков появлялась задача поиска палиндрома?
0Bannon
У наших разработчиков нефтяных месторождений ни разу.