Comments 34
Именно это в итоге показывает реальный уровень кандидата и его соответствие специфике проектов, которыми он займётся.
За последний год сколько раз у ваших разработчиков появлялась задача поиска палиндрома?
(str.length/2).toFixed() - это действительно страшно.
В выражении Math.floor(str.length / 2) вызов Math.floor не нужен. Этот конкретный for и без него отлично будет работать.
Вычислять верхнюю границу в for плохо и очень плохо. Она вычисляется на каждой итерации.
Ваши примера кода служат антирекламой компании. Не позорьтесь, уберите подальше.
(str.length/2).toFixed() – допустимо, особенно для кандидата на позицию младшего разработчика
Math.floor(str.length / 2) – в данной ситуации это дополнительная опция – она убирает лишнюю итерацию в конце цикла при нечетном количестве символов
Главное, это рассуждения кандидата во время собеседования. Если он может объяснить, что к чему, то это огромный плюс кандидату
О(3n)
Безграмотно. Запись O(n) уже предполагает линейную зависимость от n с каким-то коэффициентом.
Запись является корректной и регулярно используется в узких кейсах, например — в банковской сфере. В данной ситуации мы показали такой записью, что по строке будет три прохода
Я сам на лекциях иногда оставляю константы внутри О-большого. Формально это не ошибка, а лишь излишество. Которое может дать представление о константе алгоритма. Что удобно если мы сравниваем алгоритмы с одной асимптотикой.
Есть много критериев подходящего кандидата, но не все они равноценные. Дипломы и сертификаты можно купить, домашние проекты — «позаимствовать» на гитхабе, а вот решение задач (особенно в реальном времени) сразу показывает, как человек мыслит и к каким алгоритмическим конструкциям он привык.
Можно сколько угодно себя убеждать что "волшебные" алгоритмические задачи решать все ваши проблемы с подбором и как будто бы показывают как человек мыслит, но реальность такова что такие задачи показывают только как человек решает... такие задачи, причем именно за ограниченное время.
У меня есть хороший пример на эту тему. Как то работал на двух разных проектах с двумя разрабами. Уровень говнокода написанного первым стал легендой. Человек просто не мог писать нормально, понятно, расширяемо и оптимально. Его код проще было полностью заново переписать чем пытаться модифицировать. Другой разраб, будучи мидлом, как то раз решил простейшую задачу по блокировке доступа к ресурсу, таким образом что про это хоть отдельную статью писать. Вместо добавления обычного флага и поля с датой, история вылилась в многопоточное решение с отдельным экзекутором и хитрыми механизмами разблокировок в стиле "машинного обучения". При этом все это работало плохо и в случае повторного доступа к странице - блокировало пользователя без возможности как то блокировку снять до таймаута. Решение было просто легендарное.
Что же объединяет этих двух разработчиков и зачем я про них написал?
Они оба были победителями олимпиад по программированию и отлично решали алгоритмы.
И наверняка бы прошли бы любые алгоритмически интервью на 5 с плюсом.
Понять как мыслит человек можно только поработав с этим человеком и посмотрев как он решает разноплановые задачи а все эти попытки через найти "серебряную пулю" через алгоритмические или system design интервью - просто самообман.
Не залезете вы в голову человеку даже за 2 часа интервью. Максимум что можно сделать это построить его таким образом чтобы разноплановыми вопросами, размышлениями и небольшими задачами, пошатать собеседуемого и посмотреть что он действительно понимает а что заученно или подсмотрено, построить вопросы так чтобы сложно было дать шаблонный ответ. И прикинуть насколько все это подходит под ваш проект. А дальше только на испытательном смотреть.
А как вам кажется, если смотреть собеседуемого не голыми алгоритмами, а задачами более практическими (как те, что на hackerrank), это дало бы больше информации о собеседуемом?
Решение алгоритмов можно заучить, а изучить и понимать. При решении задач на алгоритмы мы просим рассуждать для оценки понимания того, что человек не зазубрил решение
У меня есть хороший пример на эту тему. Как то работал на двух разных проектах с двумя разрабами. Уровень говнокода написанного первым стал легендой. Человек просто не мог писать нормально, понятно, расширяемо и оптимально.
У меня есть похожий пример среди знакомых, но получилось переучить )
можно повернуть и против часовой стрелки. почему нет?
(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))В статье я так и не нашел развернутого ответа на вопрос "зачем?"
Чтобы устроиться на вакансию разработчика в серьёзную компанию, нужно продемонстрировать своё алгоритмическое мышление и умение работать над задачами разного типа.
И красить кнопки, перегоняя json'ы туда-сюда, за 180к в мес в молодом и амбициозном коллективе)
А серьезная - это какая?
То есть вы подтверждаете, что алгоритмические задачи нужно исключительно для собеседований?
Задачи нужны чтобы:
побеждать на олимпиадах (сам не пробовал).
И отвечать на олимпиадные вопросы на ruSO (делаю).
И чтобы продавать автобусные билеты (с рассадкой по местам) группам людей (задача на графах, делал этим летом).
И чтобы быстро рассчитывать возможную прибыль от продажи газа при изменениях тарифов (сдаю проект с этом алгоритмом).
И даже чтобы работать с временными поясами (сдаю проект с этом алгоритмом).
Чтобы продать билеты, нужна база данных с логической моделью, нужен фронтенд и бэкенд, желательно с резервированием сетевой части и бэкапами\репликами данных, нужна инфраструктура и заказчик, который всё это оплатит.
Быстрый расчет возможной прибыли от продажи газа при измерениях тарифов возможен грамотным экономистом, если у него есть доступ к данным по продажам, подсчитает хоть на Эксельке или запросом в песочнице, если данных слишком много, и это решение устойчиво при смене алгоритма.
Временные пояса - это скорее область прикладной библиотеки по работе с датой и временем с указанием часового пояса. Олимпиадное тут только если придумывает какую-то хитрую аппроксимацию того, что уже есть в стандартной библиотеке. Или может раскроете, что там необычного кроется во временных поясах?
Или можно пойти просто в Сбер, например. В нём целая куча проектов не заставляет кандидатов прыгать через горящие кольца на собеседованиях, при этом уж посерьёзнее Криптонита.
Попробуйте прочесть ещё раз.
Сложность алгоритма получается О(3n)
Не получается, т.к. константы в большом О сгорают.
Ранее уже отвечал: Запись является корректной и регулярно используется в узких кейсах, например — в банковской сфере. В данной ситуации мы показали такой записью, что по строке будет три прохода
Не является она корректной, т.к. константы не вносят значительного вклада в рост функции на бесконечности. Данная нотация не имеет никакого отношения ни к банковской сфере, ни к какой либо другой, за исключением мат. анализа, откуда, собственно, она (нотация) была взята. Асcимптотическому анализу все равно, сколько раз мы прошлись по циклу, важна связь между объемом данных и количеством операций. К слову, ваша "оптимизация" на ассимптотику не повлияла никак, т.к. и там, и там линейная сложность.
Запись O(3n) является корректной. Но класс функций O(3n) совпадает с классом функций O(n). Это класс функций, который растут не быстрее линейной функции. Так как O(n) = O(3n), то коэффициент внутри О обычно не пишут. (Вы можете сказать "масло маслянное", на вас косо посмотрят, но язык так говорить не запрещает, то же самое и для O(3n)).
Но если пишут, то это восприниматся как дополнительный комментарий: O(3n) растёт так же быстро как O(1n), но мы дополнительно указываем что ожидаемая константа первого алгоритма в три раза хуже ожидамой константы второго.
Повторюсь: оба способа верны. Просто первый легче для восприятия, а второй больше подходит для больших-преогромных данных.
Чем же, интересно, он подходит больше? Я не специалист по js, но вычислительный процесс и там, и там выглядит как итеративный, а не рекурсивный.
Зря на палиндромы накинулись. Это вполне актуальная практическая задача. Поиск палиндромных последовательностей широко используется в генетике и вычислительной биологии.
Поиск не проверка. Если собеседуемый в заведомо подчиненном положении от собеседующего и воспримет функцию проверки на палиндром как контракт (одновременно с контрактом на работу), а уже при поиске будет вызывать эту функцию каждый раз и не нарушать принятый "ход мыслей", то актуальная практическая задача будет решена неоптимально.
Если делаешь веб-интерфейс к научным трудам по генетике и расчётам вычислительной биологии?
Не думал, что решения алгоритмических задач на JS станут интересным для меня жанром чтения (не разрабатываю на JS).
Зачем искать палиндромы и вращать матрицы в поисках лучшей работы