07.11.2024 07:31
devleader-pro 31 3100 Источник

Привет, Хабр! Меня зовут Василий Беляев. Я руководитель группы разработки фронтенда в «Криптоните». В этой статье мы разберём три задачи из тех, которые можем задать на собеседованиях. Заодно обсудим, зачем вообще решать типовые задания при трудоустройстве, когда есть 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(), как очевидно из названия, переворачивает полученный массив для поворота по часовой стрелке.

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

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

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

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

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

Комментарии (31)


  1. Farongy
    07.11.2024 07:37
    #27524092

    Именно это в итоге показывает реальный уровень кандидата и его соответствие специфике проектов, которыми он займётся.

    За последний год сколько раз у ваших разработчиков появлялась задача поиска палиндрома?


    1. 0Bannon
      07.11.2024 07:37
      #27524634

      У наших разработчиков нефтяных месторождений ни разу.


    1. devleader-pro Автор
      07.11.2024 07:37
      #27525058

      Как минимум 1 раз – на собеседованиях – с помощью этой задачи можно посмотреть и оценить то, насколько кандидат умеет рассуждать и знает методы JS


      1. Farongy
        07.11.2024 07:37
        #27526576

        Интересное у вас место где специфика проектов это прохождение собеседований...


  1. stan_volodarsky
    07.11.2024 07:37
    #27524258

    (str.length/2).toFixed() - это действительно страшно.

    В выражении Math.floor(str.length / 2) вызов Math.floor не нужен. Этот конкретный for и без него отлично будет работать.

    Вычислять верхнюю границу в for плохо и очень плохо. Она вычисляется на каждой итерации.

    Ваши примера кода служат антирекламой компании. Не позорьтесь, уберите подальше.


    1. devleader-pro Автор
      07.11.2024 07:37
      #27525090

      (str.length/2).toFixed() – допустимо, особенно для кандидата на позицию младшего разработчика

      Math.floor(str.length / 2) – в данной ситуации это дополнительная опция – она убирает лишнюю итерацию в конце цикла при нечетном количестве символов

      Главное, это рассуждения кандидата во время собеседования. Если он может объяснить, что к чему, то это огромный плюс кандидату


      1. stan_volodarsky
        07.11.2024 07:37
        #27525178

        `.toFixed()` абсолютно недопустимо. Каждую итерацию вы переводите число в строку и обратно. Ужасная производительность при том что есть метод проще, быстрее и понятнее.


        1. devleader-pro Автор
          07.11.2024 07:37
          #27525236

          Как выше писал - допустимо для кандидата на позицию младшего разработчика


  1. Keeper11
    07.11.2024 07:37
    #27524268

    О(3n)

    Безграмотно. Запись O(n) уже предполагает линейную зависимость от n с каким-то коэффициентом.


    1. devleader-pro Автор
      07.11.2024 07:37
      #27525014

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


    1. stan_volodarsky
      07.11.2024 07:37
      #27525220

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


  1. Lewigh
    07.11.2024 07:37
    #27524314

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

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

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

    Что же объединяет этих двух разработчиков и зачем я про них написал?
    Они оба были победителями олимпиад по программированию и отлично решали алгоритмы.
    И наверняка бы прошли бы любые алгоритмически интервью на 5 с плюсом.

    Понять как мыслит человек можно только поработав с этим человеком и посмотрев как он решает разноплановые задачи а все эти попытки через найти "серебряную пулю" через алгоритмические или system design интервью - просто самообман.
    Не залезете вы в голову человеку даже за 2 часа интервью. Максимум что можно сделать это построить его таким образом чтобы разноплановыми вопросами, размышлениями и небольшими задачами, пошатать собеседуемого и посмотреть что он действительно понимает а что заученно или подсмотрено, построить вопросы так чтобы сложно было дать шаблонный ответ. И прикинуть насколько все это подходит под ваш проект. А дальше только на испытательном смотреть.


    1. Foppa
      07.11.2024 07:37
      #27525118

      А как вам кажется, если смотреть собеседуемого не голыми алгоритмами, а задачами более практическими (как те, что на hackerrank), это дало бы больше информации о собеседуемом?


    1. devleader-pro Автор
      07.11.2024 07:37
      #27525136

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

      У меня есть хороший пример на эту тему. Как то работал на двух разных проектах с двумя разрабами. Уровень говнокода написанного первым стал легендой. Человек просто не мог писать нормально, понятно, расширяемо и оптимально.

      У меня есть похожий пример среди знакомых, но получилось переучить )


  1. IisNuINu
    07.11.2024 07:37
    #27524938

    можно повернуть и против часовой стрелки. почему нет?

    (define-m (rotate-matrix-counter-clockwise source)
    (do ((cur source (map cdr cur))
         (rez '()    (cons (map car cur) rez)))
            ((cdr (find null? cur)) rez)))

(rotate-matrix-counter-clockwise
 '((1 2 3)
   (4 5 6)
   (7 8 9)))
((3 6 9)
 (2 5 8)
 (1 4 7))


  1. Foppa
    07.11.2024 07:37
    #27525132

    В статье я так и не нашел развернутого ответа на вопрос "зачем?"


    1. devleader-pro Автор
      07.11.2024 07:37
      #27525204

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


      1. lightmaann
        07.11.2024 07:37
        #27526978

        И красить кнопки, перегоняя json'ы туда-сюда, за 180к в мес в молодом и амбициозном коллективе)


      1. anaxita
        07.11.2024 07:37
        #27527986

        А серьезная - это какая?


      1. Keeper11
        07.11.2024 07:37
        #27528746

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


        1. stan_volodarsky
          07.11.2024 07:37
          #27529086

          Задачи нужны чтобы:
          побеждать на олимпиадах (сам не пробовал).
          И отвечать на олимпиадные вопросы на ruSO (делаю).
          И чтобы продавать автобусные билеты (с рассадкой по местам) группам людей (задача на графах, делал этим летом).
          И чтобы быстро рассчитывать возможную прибыль от продажи газа при изменениях тарифов (сдаю проект с этом алгоритмом).
          И даже чтобы работать с временными поясами (сдаю проект с этом алгоритмом).


      1. sergey-gornostaev
        07.11.2024 07:37
        #27529120

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


    1. AI-SHA
      07.11.2024 07:37
      #27525438

      Попробуйте прочесть ещё раз.


  1. Question_man
    07.11.2024 07:37
    #27526678

    Сложность алгоритма получается О(3n)

    Не получается, т.к. константы в большом О сгорают.


    1. devleader-pro Автор
      07.11.2024 07:37
      #27526846

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


      1. Question_man
        07.11.2024 07:37
        #27532026

        Не является она корректной, т.к. константы не вносят значительного вклада в рост функции на бесконечности. Данная нотация не имеет никакого отношения ни к банковской сфере, ни к какой либо другой, за исключением мат. анализа, откуда, собственно, она (нотация) была взята. Асcимптотическому анализу все равно, сколько раз мы прошлись по циклу, важна связь между объемом данных и количеством операций. К слову, ваша "оптимизация" на ассимптотику не повлияла никак, т.к. и там, и там линейная сложность.


        1. stan_volodarsky
          07.11.2024 07:37
          #27532048

          Запись O(3n) является корректной. Но класс функций O(3n) совпадает с классом функций O(n). Это класс функций, который растут не быстрее линейной функции. Так как O(n) = O(3n), то коэффициент внутри О обычно не пишут. (Вы можете сказать "масло маслянное", на вас косо посмотрят, но язык так говорить не запрещает, то же самое и для O(3n)).

          Но если пишут, то это восприниматся как дополнительный комментарий: O(3n) растёт так же быстро как O(1n), но мы дополнительно указываем что ожидаемая константа первого алгоритма в три раза хуже ожидамой константы второго.


          1. tkutru
            07.11.2024 07:37
            #27533468

            ожидаемая константа первого алгоритма в три раза хуже

            И? Что это меняет?


  1. dmitry_rozhkov
    07.11.2024 07:37
    #27528752

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

    Чем же, интересно, он подходит больше? Я не специалист по js, но вычислительный процесс и там, и там выглядит как итеративный, а не рекурсивный.


  1. MartianEngineer
    07.11.2024 07:37
    #27528964

    Зря на палиндромы накинулись. Это вполне актуальная практическая задача. Поиск палиндромных последовательностей широко используется в генетике и вычислительной биологии.


    1. valeravv
      07.11.2024 07:37
      #27531264

      Поиск не проверка. Если собеседуемый в заведомо подчиненном положении от собеседующего и воспримет функцию проверки на палиндром как контракт (одновременно с контрактом на работу), а уже при поиске будет вызывать эту функцию каждый раз и не нарушать принятый "ход мыслей", то актуальная практическая задача будет решена неоптимально.