Это ответ на статью, что алгоритмические собеседования не нужны. Простите за кликбейтный заголовок, но он такой и там.
Я утверждаю, что алгоритмические интервью - лучший вариант для ФААНГА из всех пока придуманных.
Еще раз акцентирую внимание, что моя статья относится лишь к условному ФААНГУ. Многие аргументы из этой статьи теряют значимость в других случаях: если у вас маленькая фирма, мало кандидатов или у вас всего 10 пользователей, то вам может гораздо лучше подойти какая-то альтернатива.
У ФААНГА есть несколько особенностей:
Очень большое количество кандидатов. Вы проводите очень много интервью.
Найм регулярно ведется из других городов а то и стран с релокацией.
Многие кандидаты хотят попасть в компанию даже не надеясь остаться там надолго. Ради строчки в резюме, ради релокации, ради хотя бы нескольких вкусных зарплат.
Своя внутренняя кухня: там часто используются технологии, не использующиеся снаружи. Зачастую, потому что они появились на несколько лет раньше публичных аналогов.
Огромное количество данных с которыми постоянно что-то надо делать. Поэтому большая часть разработчиков там регулярно действительно решает алгоритмические задачки.
Поэтому, собеседование должно удовлетворять следующим критериям (в порядке важности):
-
Высокий процент отсева. У вас итак десятки или сотни кандидатов на место. Отсюда вытекают следующие требования:
Собеседование должно быть сложным.
Нужна широкая градация оценок.
Нужно постоянно генерировать новые вопросы/задания. Иначе всякие конторы будут натаскивать кандидатов отвечать на известное множество вопросов.
-
Низкий false-positive. Тут довольно высока цена ошибки найма. Многие кандидаты релоцируются, зарплаты высокие.
Поэтому еще и важна сложность считерить. Поскольку многие хотят хоть тушкой, хоть чучелом попасть на теплое место, а там как-нибудь просимулировать деятельность какое-то время, если интервью можно обмануть - у вас будет очень много таких умников и false-positive возрастет.
Стандартизируемость и наличие объективных критериев. Когда у вас тысячи интервьюверов по всему миру, вам надо как-то привести все к общему знаменателю. Объективные критерии также необходимы, ибо иначе вас завалят судебными исками. Вроде того, где Гугл обвинили в дискриминации по возрасту за вопрос о количестве бит в байте (мол, во время молодости кандидата и по 40 бит было в байте! Вопрос специально сконструирован для отсечения немолодых кандидатов).
Масштабируемость. У вас тысячи интервьюверов, которые регулярно тратят свое рабочее время на подготовку, проведение и проверку интервью. Поэтому должна быть возможность относительно легко натренировать много собеседующих, а сами собеседования не должны быть очень длинными.
Релевантность. Хочется, чтобы навыки, позволяющие проходить интервью, также позволяли кандидату хорошо работать.
Низкий false-negative. Хорошо бы, чтобы отличные кандидаты не заваливали интервью, потому что, например, оно слишком стрессово, или им не повезло с заданием. Как жестоко это не звучит, но этот критерий - самый последний. С таким количеством кандидатов, можно мириться с тем, что кто-то из них интервью завалит, если метод собеседования удовлетворяет другим критериям лучше.
Алгоритмические интервью, часто прежде всего ругают за релевантность (хотя я с этим не согласен, о чем поговорю ниже), но забывают про все остальные критерии. А они важнее релевантности из-за масштабов ФААНГов.
Вот как на эти критерии ложатся алгоритмические интервью:
Они достаточно сложные. Есть огромная вариация оценок: задачу часто можно решить несколькими способами с разной эффективностью, можно оценить читаемость кода, простоту кода, способность объяснить свое решение, как кандидат свой код проверяет и т.д.
Тут низкий false-positive. Поскольку задачек довольно много, то вряд ли кандидат просто выучил попавшуюся ему задачу. А если кандидат способен, условно говоря, развернуть бинарное дерево, то уж json-ы перекладывать он точно сможет (чем, правда, ему и придется заниматься львиную часть рабочего времени). И код он писать точно может не только случайно меняя исходник, пока оно не заработает.
Так же тут весьма сложно считерить. Видно, если кандидат пытается гуглить или с кем-то консультируется.Тут все стандартизовано и составлены объективные критерии. Кандидат или написал код, или не написал. Видно, работает ли код за O(n log n) или O(2^n). Код может удовлетворять объективным критериям качества: понятные имена, обработка крайних случаев, переусложненность и т.д.
Эти интервью масштабируемы. Проверять их относительно просто. От интервьювера не требуется каких-то очень высоких навыков - много кого можно натренировать их проводить. Они не требуют много времени интервьювера: 45 минут на само интервью и 30 минут написать отчет.
Я утверждаю, что эти собеседования более-менее релевантны.
Начнем с того, что абсолютно все программисты всегда пишут алгоритмы: любой ваш код - это последовательность действий, объясняющая компьютеру, что делать. Даже если вы "джейсоны перекладываете". Иногда это совсем тривиальные алгоритмы, но все же алгоритмы.
Далее, эти интервью в значимой степени проверяют умение мыслить алгоритмически и знание каких-то чуть-чуть нетривиальных структур данных и алгоритмов (стеки, хеш-таблицы, обход графа, бин поиск, динамическое программирование и т.д.). Конечно могут быть индивидуумы, которые довели решение задач до автоматизма не имея этих умений, или им попалась заученная задача, но это очень большая редкость. А эти умения в ФААНГе применяются относительно часто. Я лично коммитил в прод и динамическое программирование, и бинарный поиск по ответу и всякие структуры данных из хитрых стеков или очередей. И на интервью спрашиваю ту задачу, которую лично коммитил. И она на фоне других литкод задач ничем не выделяется.
Часто встречаю мнение, что алгоритмы нужны только разработчикам библиотек и фреймворков, а "инженеры-прикладники" просто используют эти готовые решения. Но в ФААНГах значимая доля разработчиков именно такими библиотеками и занимается! И даже остальные разработчики относительно часто вынуждены писать именно алгоритмы уровня medium литкод задач.
Потом, часто вы можете просто думать, что вам алгоритмы ни разу не понадобились. Если их не знать, то у вас даже не возникнет мысль, что вот тут надо Алгоритм применить. Посмотрите задачки на литкоде: часто они сформулированы в виде "сделаейте вот это и вот это" и можно буквально перевести условие в медленный код. А когда у вас еще и нет сформулированной задачи а лишь баг в треккере, вы сами у себя в голове формулируете "надо сделать вот это и вот это" и делаете это даже не задумываясь, "а может тут хеш-таблицу стоит впендюрить".
Плюс, такие интервью проверяют умение писать код, а это и есть основная работа программиста.
Да, такие интервью не проверяют другие навыки: например, умение проектировать системы, работать в команде или какие-то специфичные знания под проект. Но для этого в ФААНГах проводятся отдельные интервью: system design, behavioral и domain specific knowledge interview.
Еще я встречал аргумент, что такие интервью дают приемущества олимпиадникам. Во-первых, их очень мало, чтобы сильно повлиять на общую популяцию работников в компании. Во-вторых, а чем они хуже? Единственный их минус, с которым я согласен - свежие олимпиадники пишут плохо читаемый олимпиадный код, заточенный под очень быстрое написание. Но в ФААНГах почти везде код-ревью, и этот дефект лечится буквально за 2 недели. Где-то утверждали, что олимпиадники усложняют код на ровном месте, я с этим не согласен. Такое поведение в том числе мешает и олимпиадные задачи писать. Да и код-ревью эту проблему тоже решает.Высокий false-negative - слабое место таких интервью, да. Многие отличные разработчики принципиально отказываются готовиться к таким интервью и заваливают их. Многие слишком стрессуют писать код под присмотром или тупят над задачами.
Это несколько нивелируется правом на ошибку. В гугле, например, аж до 5 алгоритмических секций дается. И если вы одно из них завалите а в другом чуть затупите - это не приговор. В самом интервью прощаются мелкие ошибки вроде опечаток. Никто не требует знания наизусть стандартных функций. Я лично, когда проходил интервью, забыл, что про lower_bound или upper_bound: какой там порядок параметров и что конкретно оно возвращает. Интервьювер разрешил предположить, что мне удобно, и лишь в комментарии написать, что эта функция по моему предположению делает. Интервью я прошел.
Но, как я выше уже говорил, этот критерий - не самый определяющий для ФААНГов. Все еще достаточное количество отличных разработчиков справляются с такими интервью.
А теперь я сравню алгоритмические собеседования с альтернативами, которые люди предлагали в комментариях к разным статьям:
Испытательный срок. На мой взгляд, почти по всем критериям этот метод сильно лучше алгоритмов. Это вообще самый релевантный метод почти без ошибок. Но он физически невозможен в ФААНГах. Критерий масштабируемости тут на нуле.
Тестовое домашнее задание. Это лучше алгоритмических задачек тем, что оно более приближенно к средней работе, которую надо будет выполнять. Но тут хуже масштабируемость: задания сложнее придумывать, дольше и сложнее проверять. На тестовых заданиях легче читерить. Как только условный гугл введет такие задания, вместо "курсов по подготовке к интервью" появятся конторы по выполнению за вас задания и обучению, что и как говорить, как будто это написали вы. Можно давать его под присмотром, но все-равно это будет занимать слишком много времени интервьювера. Если же его сокращать для масштабируемости, то в итоге или придем к слишком простым заданиям, или тем же литкод-задачам.
Дать задачу из багтрекера. Вроде как испытательный срок на минималках. Но тут проблема в том, что большинство задач в баг-трекере объяснять кандидату будешь только 3 часа. Плюс там все жутко секретное. Если же что-то и можно выделить и абстрагировать, то там будет или та же самая литкод задачка уровня easy и реже medium, или будет что-то большое, что нужно пару часов только ковырять. Да и хороших для интервью задач из багтрекера много не наберешь. Тут сильно хуже масштабируемость. И потом, в ФААНГах своя кухня, свои IDE, свои системы, которые кандидату и за пару дней не объяснишь. Так что особо приблизить условия к боевым все-равно не получится.
Дать кусок кода и попросить исправить в нем ошибку. Такие задачи сильно сложнее придумывать. Такие интервью слишком простые и у них недостаточный процент отсева. Если же задания запутывать специально, то там с релевантностью будет не лучше, чем у алгоритмов. Это не проверяет умение писать новый код, так что false-positive тут выше. Тут хуже с градацией оценок.
Посмотреть github кандидата. Во-первых, это вообще неприменимо к джунам. Да и без этого, у матерых программистов может быть и другое хобби, а рабочий код - под NDA. Во-вторых, тут все плохо со стандартизацией и объективными критериями. И с масштабированием тут хуже. Проверять чужие проекты сильно дольше. Оценить решение задачи гораздо проще, чем въезжать в какой-то чужой проект - пул возможных интервьюверов сильно сужается. Тут очень легко читерить. Уже сейчас есть предложения о github-профиле под ключ. Если условный гугл станет их проверять, это станет очень массовым явлением.
Тест на знание технологии/языка программирования. С технологиями сложно - в ФААНГах своя кухня. С языками - придумать много разных вопросов очень тяжело. Ограниченное количество существующих вопросов будут зазубривать (false-positive). Не проверяет умение писать код (false-positive). Это еще более отдалено от обычной работы программиста. Тут все плохо с отсевом и релевантностью.
"Разговор по душам" о какой-то технологии. Не проверяет, что кандидат может писать код (false-positive). Стандартизация и объективные критерии тут хромают. Потом, в ФААНГах своя внутренняя кухня. А собеседующие не работают с фреймворками, которые знает кандидат. О чем им говорить? О каких-то общих подходах? Тут больше хорошо подвешенный язык будет проверяться, а не навыки кандидата (опять false-positive). Плюс, оценить чьи-то словесные аргументы сильно сложнее - такие интервью только матерые сеньеры смогут проводить. Это плохо масштабируемо.
"Разговор по душам" о старых проектах. Вроде: "расскажите о каком-нибудь интересном проекте из практики". Это неприменимо к джунам. И, как и в предыдущем случае, тут хуже false-positive, стандартизируемость и объективность и масштабируемость.
"Разговор по душам" о выданном куске кода. Не проверяет что кандидат может писать код. Как и в предыдущем случае, тут хуже false-positive, стандартизируемость и объективность и масштабируемость.
"Обсудить задачу из практики интервьювера". Обычно что-то интересное будет сильно большое. Если его абстрагировать и упрощать, или выдмывать, то или получится стандартное system design interview, или те же литкод задачки, но без кодинга. Обсуждать что-то сильно сложнее чем оценивать решение алгоритмической задачки, поэтому тут сужается пул интервьюверов. И такие задачи сложнее придумывать. Как и с остальными интервью с "поговорить" в названии тут хуже false-positive, стандартизируемость и объективность и масштабируемость.
Интервью такого же формата, но задачи не настолько алгоритмические. Тут все будет плохо или с отсевом или масштабируемостью. Если из задач выкинуть все алгоритмы, то они будут слишком просты. Один способ их усложнять - это увеличивать объем кода и тогда станет дольше их проверять. Или можно усложнять размер системы, и тогда интервью выродится в system design и увеличиваются требования к интервьюверам, что тоже снижает масштабируемость.
Есть ли какие-то еще альтернативы? Добро пожаловать в комментарии.
Комментарии (133)
panzerfaust
19.11.2023 13:19+25Извините, но статья больше похожа на флекс "а вот у нас в фаанге". В общем-то к фаангу особо ни у кого претензий нет. Когда вас каждый день штурмуют тысячи желающих получать 1кк/сек и пить халявный ред булл из офисного холодильника, то логично ожидать, что у вас выработается иммунная система в виде 9000 стадий интервью.
Претензии обычно к всяким хитровыдуманным конторам, которые сначала дрючат тебя "как в фаанг", но потом не предлагают ни вознаграждение "как в фаанг", ни корп культуру "как в фаанг", ни инженерные вызовы "как в фаанг".
wataru Автор
19.11.2023 13:19+1Обычно ругают эти интервью не делая исключения для фаанга. В тот же Яндекс регулярно летят камни, хотя это вполне как фаанг и по количеству кандидатов и по желаемости строчки в резюме и по решаемым задачам.
Edit: вот даже статья, на которую я ссылаюсь начинается:
Не так давно писал в соцсетях хейт‑пост по поводу «алгоритмических секций» при приёме на работу в Яндекс.
Ravager
19.11.2023 13:19+8Забавно только что раньше все туда хотели попасть а теперь им приходится привлекать внешних хров. И везде пестрит реклама приглашений в Яндекс, или их туры по городам. Кажется очереди за забором уже нет, но привычка осталась.
wataru Автор
19.11.2023 13:19Одно другое не исключает. Вон, у гугла очереди точно есть, а их хедхантеры весьма активны. Мне от них постоянно приглашения сыпались.
Ravager
19.11.2023 13:19+2Да, они и раньше были активными. Но чтобы давать рекламу из каждого утюга и ездить самим по городам - такого не видал.
panzerfaust
19.11.2023 13:19+7В тот же Яндекс регулярно летят камни
В Яндекс летят камни как раз из-за момента с вознаграждением. Я не скажу за всю Одессу, но у джависта в РФ есть куча опций получать такие же или более вкусные плюшки, чем в Яндексе, но с несравнимо меньшим головняком.
wataru Автор
19.11.2023 13:19-1Мне кажется, компенсация в Яндексе не так и плоха, как о ней думают. В россии люди привыкли не считать бонусы, а в Яндексе почти половина зарплаты у некоторых моих знакомых идет акциями. Так что фактически компенсация гораздо выше, чем это выглядит, если смотреть только на вилку зарплаты. В офисе у них я там был (очень давно, правда) - плюшки вполне себе на уровне Гугла были. А с тех пор, вроде как, и новый офис построили.
Потом, даже если там компенсация действительно не самая вкусная, это никак не влияет на указанные мной критерии применимости собеседований. Влияет лишь объем заявок от кандидатов. И он действительно большой. Может, из-за репутации компании. Или из-за аггресивного хед-хантинга.
Hivemaster
19.11.2023 13:19+7Про релевантность не соглашусь. Попадались мне люди, которые заучили наизусть описание основных алгоритмов и их реализации, но без малейшего понимания. Они идеально проходили алгоритмические интервью, а потом были неспособны писать мало-мальски приемлемый код. Каждые полгода-год перепрыгивали к другому работодателю, как только раскрывалась их несостоятельность.
wataru Автор
19.11.2023 13:19+1Мне кажется, это должна быть огромная редкость. Во-первых, хотя бы на интервью этот человек мог писать мало-мальски приемлемый код. Ибо если там вывалить что-то совсем ужасное, то это жирный минус. Во-вторых, умение понимать, когда какой алгоритм надо применять, требует определенных интеллектуальных способностей. Их точно хватило бы чтобы писать мало-мальски приемлемый код.
Скорее, я бы поверил, что таким людям, допустим, что-то не нравится в работе и им лень прикладывать хоть какие-то усилия для написания хорошего кода. К сожалению, это никакое интервью не проверит. А регулярные переходы на новое место часто практикуются для быстрого роста зарплаты.
sergey-gornostaev
19.11.2023 13:19+4Не такая уж и редкость. Ко мне такие тоже приходили. На алгоритмических интервью, очевидно, не приходится писать реальный код и выбирать алгоритм. Кандидату дают задачу написать например обход графа или сбалансировать красно-чёрное дерево и он набирает код, который до этого перепечатывал уже десять тысяч раз, или выполняет повороты по вызубренным правилам. Согласно вашим же пунктам 3 и 4 интервьюер крупной компании в детали не вдаётся - типовое задание выдал, корректный ответ получил, отметку "пройдено" поставил, следующий.
Hivemaster
19.11.2023 13:19Ага, а потом этого крутильщика деревьев нанимают, дают ему таску в джире и через некоторое время он приходит к тимлиду с претензией, что задача недостаточно подробно описана, он не понимает, что делать. Тимлид в шоке, конечно, задача описана достаточно конкретно, но новичок ждёт чуть ли не пошаговой инструкции о том, какой код писать. Задачу для него предельно конкретизируют, долго ждут результата и на выходе получают код не только нестабильный и непроизводительный, но и абсолютно неподдерживаемую лапшу. Первый раз списывают на трудности онбординга, но ситуация повторяется ещё раз и ещё раз. Потом руководство говорит, что увольнять тяжело, может дать человеку ещё шанс. Цикл прокручивается ещё несколько раз. Вся команда уже в ярости, никто не рад разгребать проблемы за мастером прохождения собеседований, никому не нравится возиться в его говнокоде. Наш герой понимает, что на носу аттестация и пишет по собственному желанию, чтобы повторить историю с другим нанимателем, верящим в силу алгоритмических собеседований.
Ravager
19.11.2023 13:19+4Проблема имхо не в алгоритмах, а в том что тебе нужно придумать решение в ограниченное время, когда на тебя смотрят несколько человек.
wataru Автор
19.11.2023 13:19Если бы время было неограниченно, то интервью были бы простыми и не отсекали бы достаточное количество кандидатов. Поэтому будь там какое угодно другое интервью, там все-равно было бы и жесткое ограничение по времени и стрессовая ситуация.
sgjurano
19.11.2023 13:19+2Это вот любопытно на самом деле - а зачем ставить себе цель отсекать кандидатов?
Они могут решать задачи бизнеса? Могут.
Делают это не хуже литкодовцев? Не хуже.
Так зачем тогда мучать и их и интервьюеров?
wataru Автор
19.11.2023 13:19Потому что у вас, условно говоря, каждый месяц приходит 10000 кандидатов и появляется 100 новых позиций. Если интервью простое, то вот получат у вас 9000 максимальный бал. Что с ними делать?
Брать 100 случайных (вспоминается - "нам не нужны неудачники")? Брать 100 первых, а остальные идут лесом? Чем это лучше случайного выбора? Брать всех прошедших в порядке FIFO по мере появления мест (время ожидания приема на работу скоро станет от 5 лет)?
zergon321
19.11.2023 13:19+2Ну так и пускай берут 100 самых первых прошедших интервью для позиции и быстро закрывают её. Или компания не заинтересована в быстром закрытии позиции? А если получается, что работа на деле простая и тех, кто знает, как выполнять её, очень много, пускай снижают за неё вознаграждение. Тогда огромная часть людей уйдёт сама. А не устраивать тест китайской каллиграфии
wataru Автор
19.11.2023 13:19Чем брать 100 первых лучше случайного метода? Только скоростью найма? Поскольку тут оформления, релокации, и в любом случае пара недель бюрократии и еще пара недель только онбординга, то подождать неделю и рассмотреть еще 2000 кандидатов, разницы во времени закрытия позиции особо не оказывает. Вам, как бизнесу, имея такой выбор кандидатов логично хотябы попытаться выбрать лучших.
А если получается, что работа на деле простая и тех, кто знает, как выполнять её, очень много
Много желающих ее выполнять. Со способностью ее выполнять хорошо - вопрос сложнее. Как я в разделе про релевантность писал - в ФААНГах алгоритмы действительно пригождаются. Это не единственный нужный навык, но он со способностью хорошо работать коррелирует. Алгоритмические интервью тут возможно не самые-самые релевантные, да. Но из всех релевантных критериев они удобнее ложатся на другие критерии.
piton_nsk
19.11.2023 13:19Брать 100 случайных (вспоминается - "нам не нужны неудачники")? Брать 100 первых, а остальные идут лесом? Чем это лучше случайного выбора? Брать всех прошедших в порядке FIFO по мере появления мест (время ожидания приема на работу скоро станет от 5 лет)?
Есть специальный алгоритм именно для этого - задача о разборчивой невесте.
wataru Автор
19.11.2023 13:19Тут не такой случай. Невеста должна сразу, посмотрев на жениха сказать да/нет. При найме на работу же можно посмотреть всех и потом выбрать. Получится оптимальнее. А главное, невеста у нас - неразборчивая. Суть в том, что вы не знаете, а какого вообще уровня могут быть женихи. Если вы знаете, что их ценность от 0 до 100, и уже первый имеет оценку 98 - то лучше его сразу взять. Так и при найме - у вас очень большой опыт собеседования очень большого количества кандидатов - вам не надо отбрасывать n/e первых только для того, чтобы понять какого они уровня бывают.
Потом, возвращаясь к началу этой ветки, если интервью не сложное, с высоким уровнем отсева кандидатов, то получите вы почти всегда, что 37-ой чувак, как и 35 из 36 каллибровочных, набрал высший бал. Спрашивается, чем виноваты первые 35, которых по алгоритму невесты надо только посмотреть?
piton_nsk
19.11.2023 13:19При найме на работу же можно посмотреть всех и потом выбрать.
Если у вас постоянный поток в сотни и тысячи кандидатов ("подождать неделю и рассмотреть еще 2000 кандидатов"), как вы собрались смотреть их всех? Всех можно посмотреть если пришло с десяток резюме, а дальше стало пусто. Это только для микроконторы будет работать.
wataru Автор
19.11.2023 13:19как вы собрались смотреть их всех?
В гугле периодически проходят собрания комитета по найму который сравнивает лучших кандидатов с прошлого собрания (не все пришедших, конечно - большую часть рекрутеры по очевидно слабым отчетам с интервью режут) и выбирает до N лучших (при условии, конечно, прохождения нижней планки). Так получается, допустим, "посмотреть всех за месяц" и выбрать лучших.
mvv-rus
19.11.2023 13:19+2А это правильно - стрессоустойчивость тестировать? Что, в реальной работе у вас там стресса много что ли?
wataru Автор
19.11.2023 13:19+1Интервью не имеют своей целью тестировать стрессоустойчивость. Стресс, к сожалению, это неизбежный побочный результат требования к сложности интервью.
longclaps
19.11.2023 13:19+8Я в чем-то согласен савтором. Алгоритмы действительно полезны. Здорово, если соискатель знает все алгоритмы, о чем ни спросишь, и может воспроизвести их не гугля. Хуже, когда соискатель выдаёт оригинальное решение, если оно неоптимально - он умеет думать самостоятельно, но не оптимально. Здесь вам не фолс-позитив!
Одно плохо в алго-собеседованиях: нарвёшься на такого вот козла, а у него в башке пять критериев, на роже спесь, а в душе - злоба. Прямо хоть святых выноси.
К уважаемому @wataru это, разумеется, не относится.
Tempest23
19.11.2023 13:19+6Я утверждаю, что алгоритмические интервью - лучший вариант для ФААНГА из всех пока придуманных.
Я рад за них. Осталось понять, зачем это аудитории хабра. Рискну предположить, что львиная доля людей здесь в указанных компаниях не работает и не собирается. Информация для нас либо иррелевантна, либо этот тезис тут просто лишний, если полезность выходит за рамки очерченного круга.
wataru Автор
19.11.2023 13:19Я думаю, достаточное количество уже работает или собирается в будущем работать в ФААНГе или им подобным (тот же Яндекс).
А главное, тут в комментариях эти интервью часто отвергают в принципе, как явление. И постоянно ругают в том числе и гугл с яндексом. Даже статья, которой я отвечаю начинается:
Не так давно писал в соцсетях хейт‑пост по поводу «алгоритмических секций» при приёме на работу в Яндекс.
SpiderEkb
19.11.2023 13:19Вообще это продолжение разговора о понимании сути алгоритмов и умении их правильно и по месту использовать. А также о том, что не всегда и не везде метрика ТТМ превалирует над всем остальным, в том числе эффективность. кода.
Рискну предположить, что львиная доля людей здесь в указанных компаниях не работает и не собирается
И на чем основано Ваше предположение? На том, что Вы с этим не сталкивались? Ну да, возможно не сталкивались. Но почему думаете что "львиная доля"? Среди ваших знакомых таких нет? Ну и что? А если я скажу, что за 30+ лет разработки у меня никогда ТТМ не был на первом месте, но главным была надежность и эффективность (основанная на понимании и правильном использовании алгоритмов)? И среди моего круга знакомых это так. Могу я на основании этого рассуждать о "львиной доле"?
dom1n1k
19.11.2023 13:19+2Испытательный срок. На мой взгляд, почти по всем критериям этот метод сильно лучше алгоритмов.
На самом деле, это очень проблемный метод. По очень многим причинам — временным, финансовым, организационным, моральным, юридическим...
Algrinn
19.11.2023 13:19+5Ой, да на собеседовании нужно сначала позадавать простых вопросов из резюме кандидата, чтобы он не нервничал, а потом задать 50 сложных вопросов, чтобы сравнить его с десятком других кандидатов. Результаты оформить в виде таблицы и отправить наверх начальству. Можно задать тройку вопросов и на алгоритмы. Всё хорошо, когда в меру. Нужно не забывать, что программист без интернета обладает в несколько раз более слабым анализом, чем с интернетом. В действительно топовые компании целесообразно давать тестовые задания. А вот что действительно не нужно делать, так это сначала целый час выносить человеку мозг, а потом заставлять его в состоянии стресса писать код. После таких собеседований остаются крайне неприятные впечатления о фирме и большой негатив.
1755
19.11.2023 13:19В университете у нас был преподаватель, который на экзамене давал пользоваться открыто всем чем угодно: конспектами, лекциями, книгами и интернетом. Принцип простой: предмет сложный и если человек не готовился к предмету заранее, то на экзамене за пару часов ничего не вымучает.
Мне кажется, этот принцип работает и с интервью на позицию инженера. Да и приближено к работе.
SpiderEkb
19.11.2023 13:19В университете у нас был преподаватель, который на экзамене давал пользоваться открыто всем чем угодно: конспектами, лекциями, книгами и интернетом. Принцип простой: предмет сложный и если человек не готовился к предмету заранее, то на экзамене за пару часов ничего не вымучает.
У нас так было практически по всем "внутрифакультетским" предметам (а это 80% того, что читалось на старших курсах).
Изначально это шло от спецкурсов - чтобы шпоры/флаги не писали (все спецкурсы "закрытые" были, там конспекты выдавали под пропуск на время лекций, а так они в спецгруппе хранились, к экзамену тоже готовились "за загородкой"). Ну а потом и на все остальные предметы распостранилось.
В результате билет - это так, прелюдия. А дальше допвопросы "на понимание темы". Помнится, один из спецкурсов сдавали, я зашел в 9 утра в первой группе, вышел первым(!) в два часа дня. А в целом экзамен часов до восьми вечера длился...
1755
19.11.2023 13:19Да, тоже такая же тема была, что несколько часов уходило на ответ. Но в целом считаю это имеет право на жизнь на собеседованих: если спрашивать задания тестовые на кодинг, особенно алгоритмические, то давать возможность пользоваться интернетом. А потом уже от итогового решения отталкиваться и разговаривать. Если человек без опыта, то просто скопирует и ничего не сможет не пояснить, ни поменять толком, ни прикинуть сложность. Из общения будет многое понятно.
ruomserg
19.11.2023 13:19+10Алгоритмическое интервью - это типичный пример ситуации, когда то что надо проверить - проверить сложно. Поэтому мы проверяем не то, что нужно - а то, что проверить легко. Как говорится: "Любая сложная проблема имеет простое, легко объяснимое, и быстро реализуемое НЕПРАВИЛЬНОЕ решение". (C) Законы Мерфи.
Понятно, что когда вам надо отсеять 99% кандидатов - вы в любом случае закончите разновидностью "китайского экзамена по каллиграфии" (это когда ведущий задает все более редкие и малоизвестные слова и термины, а присутствующие должны за сильно ограниченное время вспомнить и нарисовать соответствующий иероглиф. Исторически применялось для отбора кандидатов на должность чиновников в упомянутой стране). Означает ли это что человек выучивший тысячи редких иероглифов (в нашем случае - алгоритмов) является наилучшим кандидатом ? Вряд ли. Объективно, мы можем утверждать что он имеет определенную мотивацию и хорошую память - не более того. Разумеется, мотивированный кандидат с хорошей памятью лучше немотивированного идиота - но непонятно, почему это считается вершиной способов отбора...
При этом, я замечаю, что программирование - это пожалуй единственная дисциплина, в которой отбор настолько, э-э, самобытен. Если вы придете наниматься играть в оркестр - от вас, разумеется, попросят какое-то докказательство музыкального образования, но в конечном счете, руководитель оркестра попросит вас сыграть. Он не будет проводить тест на знание конструкции музыкальных инструментов, его не интересует ваша способность запомнить годы жизни сотен композиторов (если, конечно вы не нанимаетесь музыковедом). Вы собираетесь играть - ну вот и покажите как вы играете! Если вы придете устраиваться сварщиком - вас спросят, что вы варили, и сюрприз (!) дадут в руки аппарат и попросят что-нибудь сварить. Я смею утверждать, что в большинстве случаев - основным свойсвом программиста, которое мы хотим проверить - является умение ЧИТАТЬ и ПОНИМАТЬ написанный код, а также находить проблемы в уже существующем коде. И вот это надо проверить. Я не вижу проблемы приготовить кусок кода, и предложить его отрецензировать/улучшить/пофиксить. Это намного лучше предскажет то, как разработчик будет вести себя в реальной разработке...
wataru Автор
19.11.2023 13:19-1Вы собираетесь играть - ну вот и покажите как вы играете
Ну вот в ФААНГах просят играть очень редко играемую и очень сложную увертюру. Которая иногда оркестру выпадает, хоть он и гораздо чаще играет более простые вещи.
Я не вижу проблемы приготовить кусок кода, и предложить его отрецензировать/улучшить/пофиксить
Я упомянул эту альтернативу в статье. Такое интервью получается сильно проще. Его будут проходить буквально все кроме совсем проходимцев. Или там придется какие-то совсем хитро спрятанные проблемы вставлять (почти как кирилическая "c" вместо английской "c"). Это даже менее релевантно работе, чем умение писать код.
Потом, писать код сложнее. Поэтому людей, которые могут чужой код прочесть и понять, но не могут свои мысли в виде кода оформить - гораздо больше чем людей способных наоборот лишь писать код, но плохо понимать чужой. Так что у такого интервью будет выше false-positive.
ruomserg
19.11.2023 13:19+9Сложность написания кода повсеместно преувеличена. Программирование - это не сольное выступление, где определяющими являются личные способности конкретного исполнителя. Раньше - оно таким было, сейчас - нет. Сейчас основная способность программиста - это решать задачу не прибегая к черной магии (потому что стоимость поддержки большой системы всегда на порядки больше стоимости ее создания), и иметь страх - то есть чувствовать, как ваши изменения могут негативно сказаться на других частях системы. Для этого нужны, разумеется, знания из области алгоритмов. Потому что человек без опыта не видит и не чувствует когда он переходит от O(n) к O(n^2) и потом к O(x^n). Но пытаться из алгоримического интервью выводить пригодность человека к дальшейшей работе - ну... безумие на самом деле.
Мне это вот еще что напомнило - в достопамятные 90-е годы, банк в соседнем здании брал на работу уборщиц - не иначе как с высшим образованием. Ну потому что уборщица с квалификацией инженера - как минимум дисциплинирована, ответственна, и не будет пить в рабочее время в подсобке. Является ли такой способ найма ценной находкой и масштабируемой практикой, или плодом извращенного состояния рынка труда в то время - решайте сами.
Я, безусловно, проверяю способность людей программировать - но не заставляю их извращаться с заучиванием алгоритмов. Мне достаточно чтобы человек просто при мне попрограммировал. Что угодно - от игры в крестики-нолики до простейшего клиент-серверного приложения. И даже не обязательно до конца...
ruomserg
19.11.2023 13:19+5... и еще - "трудные проблемы" типа "заменить латинскую букву на русскую" - это верх идиотизма и продолжение идей типа "проверим то, что легче проверить" в сторону доведения до абсурда. В чтении кода можно проверить гораздо больше. Один уровень, если человек может увидеть и исправить функциональную ошибку (например, код должен суммировать проценты, но фактически этого не делает). Другой - если человек видит потенциальные необработанные краевые условия и особые случаи. Третий - если видит квадратичную сложность и спрашивает, кто и как часто это будет вызывать. Дальше - если человек имеет понимание о NFA/NFR и может выдать предложения, например по улучшению maintainability и extensibility кода... И все это в ответ на простой вопрос: "посмотрите, все ли в порядке с этим куском кода - и скажите, что бы тут стоило поменять ?".
microuser
19.11.2023 13:19+1А врача наверное попросят кого-нибудь вылечить? На самом деле все не так, в остальных сферах смотрят на образование и опыт из резюме, для остального есть испытательный срок.
dio4
19.11.2023 13:19Я на собесах сам задаю воросы тем, кто меня интервьюирует. Интересно бвло бы посмотреть как вы бы отвечали на них, а потом тут опубликовать.
wataru Автор
19.11.2023 13:19Задавайте. На что смогу - отвечу.
trueMoRoZ
19.11.2023 13:19+4Скажите, у вас в вашей работе часто возникает необходимость написать какой-нибудь нетривиальный алгоритм за 5 минут? При этом на вас оценивающе смотрят два других программиста, и от этого зависит ваше будущее.
SpiderEkb
19.11.2023 13:19Можно отвечу?
Скажите, у вас в вашей работе часто возникает необходимость написать какой-нибудь нетривиальный алгоритм за 5 минут?
Нет. Но вот выбрать из 2-3-х вроде бы похожих алгоритмов тот, что в данном конкретном случае при данных конкретных условиях будет работать на 15-20% быстрее остальных - сплошь и рядом. Неправильный выбор даст плохой результат на нагрузочном тестировании и потребует переписать от 40 и более процентов кода.
А для этого, согласитесь, надо знать особенности этих алгоритмов - чем они отличаются, когда какой лучше и т.п.
Я согласен что писать на собесе сортировку пузырьком - бред. От таких (да и в принципе тестовых) задачек я отказываюсь сразу. Но вот на вопрос "вот такое вот условия задачи, такие вот данные, нужно вот это - какой алгоритм выберете и почему" - буду отвечать потому что это вопрос по делу. На мой взгляд.
wataru Автор
19.11.2023 13:19Нет, за 5 минут не возникает. Да, вы правы, интервью отличается от работы. Но таким будет любое интервью, удовлетворяющее необходимим критериям. Интервью будет обязательно сложное, потому что у вас 100 кандидатов на место. Да, кто-то обязательно не справится с ним только из-за стресса. Это печально, но масштабируемого решения этому нет.
Но, вы немного преувеличиваете. Во-первых, впендюрить std::unordered_map - это не слишком сложно. И у вас 30 минут это написать а не 5 минут. Вполне рабочая производительность написать 15 строк кода за 30 минут.
Интервьювер обычно один. А последние два года, после пандемии - и то он смотрит на вас через камеру в вашем ноутбуке.
SpiderEkb
19.11.2023 13:19Во-первых, впендюрить std::unordered_map - это не слишком сложно
А кто-то контролирует что в данном конкретном случае std::unordered_map будет оптимальным решением? Вот именно он, а не какой-то иной контейнер?
"Как надо в общем случае" - это вопрос базового образования. А вот "как не надо именно здесь" - это уже вопрос уровня и опыта.
Я уже неоднократно упоминал - в личной практике замена одного типа контейнера на другой (с другими алгоритмами) дал на нагрузочном тестировании 20%-й прирост в скорости. Причем, это был модуль с очень высокой плотностью вызовов (сотни миллионов вызовов в сутки) и очень высокой критичностью.
gun_dose
19.11.2023 13:19+2Мне в фаангах работать не приходилось, но имхо для небольших компаний (до сотни работников) спрашивать алгоритмы и паттерны имеет смысл только для уж совсем зелёных джунов, у которых в списке достижений только окончание каких-то курсов и то, что они хорошо кушают. Что касается сеньоров и миддлов, там всегда можно придумать вопрос по предметным технологиям и сразу будет понятен уровень собеседуемого.
Zara6502
19.11.2023 13:19+2При всей определенной зацикленности в РФ на алгоритмах и отсылке на якобы популярность такого подхода на западе, скажу, что да, вероятно в каком-то гугле или амазоне, может быть, про алгоритмы что-то и спрашивают, но и помимо этих компаний полно тех, что имеет мировое имя, но при найме не смотрит ни на образование ни на алгоритмы, так как они, внезапно, не ограничены поиском тех, кто будет в эти алгоритмы. Как я и писал ранее, тест на дальность метания гранаты не говорит о том что вы первоклассный танкист. Я понимаю бла-бла-бла образ мышления, база и т.п., но это именно бла-бла-бла - скажем так, толковых ребят без высшего образования я встречаю чаще чем с высшим, да, есть определенные проблемы с будущем с некоторыми аспектами, но они менее существенны на мой взгляд.
ptr128
19.11.2023 13:19Есть ещё вариант оценки кандидата. По ГПХ за фиксированную оплату предлагается сделать задачу. Если кандидат сделает эту задачу качественно и быстро, то почасовая оплата получается вполне приемлемой. Через месяц на таких задачах вполне можно принимать решение о том, подходит такой кандидат или нет.
wataru Автор
19.11.2023 13:19Это вообще не применимо к ФААНГу. Во-первых, из-за масштаба. Вы бы применили этот метод, если у вас 100 кандидатов на место одно. Во-вторых, попробуйте оформить вот так кандидата из другой страны, например. Если у вас маленькая фирма и мало кандидатов, то это хороший вариант, да.
ptr128
19.11.2023 13:19Это способ не выбора одного кандидата из ста, а выбора одного кандидата их двух-трёх оставшихся после предыдущих отсевов. И как раз крупному бизнесу легче иметь стек таких не срочных задач, чем мелкому. С оформлением вообще не понял. Договор на конкретный объем работ оформить всегда можно. А тут ещё и удалёнка. В чем проблемы?
wataru Автор
19.11.2023 13:19Ну, оформлять из другой страны часто сложнее.
выбора одного кандидата их двух-трёх оставшихся после предыдущих отсевов
Ну хорошо, допустим это у нас такой последний этап. Чем до этого отсеять 97 кандидатов?
И как раз крупному бизнесу легче иметь стек таких не срочных задач, чем мелкому.
Если требуемый поток задач действительно мал, то да.
ptr128
19.11.2023 13:19Ну, оформлять из другой страны часто сложнее.
Как раз по ГПХ оформлять не надо.
Чем до этого отсеять 97 кандидатов?
Кроме обычных HR фильтров, целый ряд способов указан в конце статьи. Я лишь добавил еще один.
Если требуемый поток задач действительно мал, то да.
Не понял Вашу мысль. Как раз наоборот, чем больше поток задач, тем больше среди них таких, по которым сроки не горят или которые все равно в ближайшие недели некому на доску поставить.
wataru Автор
19.11.2023 13:19Как раз по ГПХ оформлять не надо.
Для разных стран все по разному.
Кроме обычных HR фильтров, целый ряд способов указан в конце статьи. Я лишь добавил еще один.
Так проблема остается нерешена. Я всю статью расписывал, почему остальные методы не подходят отсеить 99 из ста кандидатов. Вы предлагаете исползовать их для отсева 97, а потом еще 2 вот этим методом. Вы не сильно поменяли условия.
Как раз наоборот, чем больше поток задач, тем больше среди них таких, по которым сроки не горят
Эти задачи кто-то должен выделить, оформить, потом проверить и интегрировать. Обратите внимание, я писал не про количество потенциальных задач, которые можно выделить, а про количество задач, нужных на выходе (слово "требуемых"). Да, если это последний этап отсева и кандидатов мало, а бизнес большой, то это можно использовать. Но заменить этим способом основные этапы отсева - нельзя. Даже если бизнес большой, он не будет выделять тысячу инженеров только для выделения вот таких вот задач. Он перейдет на более масштабируемый метод, даже если относительная нагрузка не так велика.
ptr128
19.11.2023 13:19+1Проблема в том, что включая в основной обязательный этап отсева экзамены по написанию кода и алгоритмам, отсеиваите не только тех, кто не может с этими заданиями справиться, но и тех, кто и не собирается тратить свое время на этот детский сад.
mvv-rus
19.11.2023 13:19Дык, "неудачники нам не нужны"(с). У гугла отсев чрезмерный и, возможно, очасти иррациональный. Но при его потоке соискателей это не его проблема.
PS А ещё так отсеется некоторое количество шибко умных, не желающих в дисциплину. А без дисциплины в конторах такого размера тяжко, так что больно умные там не нужны.
ptr128
19.11.2023 13:19+1Мне сложно представить соискателя с 10-20-30 годами опыта, претендующего на должность тимлида или архитектора и согласного тратить часы на решение задач для джунов.
wataru Автор
19.11.2023 13:19+1А мне нет. Я таких каждый день на работе кучу вижу.
Потом, если это задачи для джунов - то они для такого опытного разработчика очень просты?
ptr128
19.11.2023 13:19Я таких каждый день на работе кучу вижу.
И где Вы работаете, если не секрет? )))
для такого опытного разработчика очень просты
В том то и дело. Предположим, на некотором экзамене по математике нужно знать только таблицу умножения. Было бы на этом экзамене хоть какое-то преимущество у освоившего математический анализ?
wataru Автор
19.11.2023 13:19И где Вы работаете, если не секрет? )))
Не секрет. В гугле.
Предположим, на некотором экзамене по математике нужно знать только таблицу умножения.
Любая аналогия подобна котенку с дверцей. Я не утверждал, что у опытных разработчиков есть какие-то особые приемущества в алгоритмических интервью. В каких-то местах им легче - они точно смогут написть лаконичный код без ошибок. С другой стороны, свежие студенты могут помнить больше алгоритмов, так что матерым сеньерам придется немного освежить их в памяти и подготовиться к интервью.
Моя реплика про то, что эти интервью просты - это был ответ на ваше "задачи для джунов". Как бы сеньер должен справлятся с задачами для джуна играючи, нет?
ptr128
19.11.2023 13:19+1Не секрет. В гугле.
Вас не выгонят за такой инсайд? Любой инвестор услышав что, тимлиды или архитекторы гугла согласны тратить часы на решение задач для джунов, понесется акции продавать. )))
Я не утверждал, что у опытных разработчиков есть какие-то особые приемущества в алгоритмических интервью.
Естественно. Их нет и быть не может. Поэтому смысла опытному разработчику соревноваться с джунами тут тоже нет. Все его преимущества в опыте и знаниях в таком соревновании не дают ничего.
wataru Автор
19.11.2023 13:19Поэтому смысла опытному разработчику соревноваться с джунами тут тоже нет.
Во-первых, он с ними и не соревнуется. На позицию сенъера джуна итак не возьмут. Так что он соревнуется с другими сеньерами. Во-вторых, смысл есть. Может он тупо хочет работать в условном гугле. Это не такая и невероятная история - сеньерские зарплаты в ФААНГе вообще заманчивые. И задачи там попадаются весьма интересные.
ptr128
19.11.2023 13:19+1он соревнуется с другими сеньерами
На алгоритмах? )))
И почему мы вдруг опустились с тимлида или архитектора до синьора?
И задачи там попадаются весьма интересные
Или не попадаются. Собственно говоря именно поэтому, я для себя даже не рассматривал такой вариант. Я сначала выбираю интересную для меня задачу и только после этого претендую на вакансию.
SpiderEkb
19.11.2023 13:19Опытный разработчик - это не только алгоритмы (уж коль на то пошло), но и способность принести что-то новое в данную область из других, где раньше работали.
Я вот с удивлением обнаружил что ряд вещей, с которыми плотно работал "в прошлой жизни" (промавтоматизация) нашло свои аналоги в банке. Особенно что касается распараллеливания обработки, межпроцессного взаимодействия, организации конвейеров и т.п. Т.е. такие темы, которые "не для джунов".
SpiderEkb
19.11.2023 13:19Дело не в сложности. Дело в том, что я, например, готов обсудить пути решения реальной задачи (в т.ч. алгоритмы которые там будут использоваться с объяснением почему именно этот именно тут). Но не готов тратить время и силы на решение олимпиадных задачек которые и близко отношения к реальной работе не имеют.
Именно поэтому ушел в своей время с собеса в яндексе. Просто прямо им сказал - "этом без меня развлекайтесь". И в тех пор рекрутерам из яндекса сразу отказываю когда приходят.
wataru Автор
19.11.2023 13:19Я про это написал. Согласен, false negative - слабое место алгоритмических интервью. Но оно не 0 и у других методов, а обязательные для специфики ФААНГа условия сделают так, что любое интервью будет сложным и стрессовым. И всегда найдется тот, кто будет выше выбранного метода. Ну и, с такой "очередью за забором" можно смириться с несколькими принципиально не принимающими такие интервью гениями. Достаточное количество не сильно глупее людей согласны и потерпеть ради вкусной зарплаты.
ptr128
19.11.2023 13:19+1смириться с несколькими принципиально не принимающими такие интервью гениями. Достаточное количество не сильно глупее людей согласны и потерпеть ради вкусной зарплаты.
Вот поэтому гений скорее попадет в IBM, чем в Google. И, в результате, ежегодная патентная активность IBM в несколько раз выше, чем Google, несмотря на то, что по рыночной капитализации первая уступает второй на порядок.
Кстати, на IBM мне приходилось пару раз фрилансить. Как-то у них эта система все же работает. Но для приема в штат требовали хотя бы кандидатскую, на что у меня ни сил, ни желания не было.
wataru Автор
19.11.2023 13:19Но для приема в штат требовали хотя бы кандидатскую
Вот и ответ. Тоже вариант для радикального снижения количества заявок. Еще менее релевантно, чем алгоритмические интервью, на мой взгляд. Зато с отсеченем, масштабированием и стандартизацией - тут все отлично. А уж false-negative тут на порядки хуже. В IT сплошь и рядом работают люди без образования, сколько там гением, которым закрыт путь в IBM!
ежегодная патентная активность IBM в несколько раз выше, чем Google,
Патентная активность - не самый хороший критерий, на мой взгляд. У патентных троллей она еще выше, но там не обязательно много гениев.
ptr128
19.11.2023 13:19сколько там гением, которым закрыт путь в IBM
Я думаю, около нуля. Гений легко не только кандидатскую, но и докторскую защитит. Благо IBM не просто требует кандидатскую, а предлагает темы для аспирантуры. Или кого Вы называете гениями?
Патентная активность - не самый хороший критерий, на мой взгляд. У патентных троллей она еще выше
Вы вообще в курсе, кто такие патентные тролли? Откуда у них патентная активность? Они лишь скупают патенты, в совершенно редчайших случаях пытаясь регистрировать новые.
wataru Автор
19.11.2023 13:19Я думаю, около нуля. Гений легко не только кандидатскую, но и докторскую защитит.
И с гораздо меньшими усилиями он прочитает пол книжки, потратит несколько вечеров на прорешивание задачек на литкоде и потом легко пройдет алгоритмическое интервью. Но на этот "детский сад" он тратить время не собирается. А писать статьи, неделями их вылизывать, прыгать через обруч и плясать на одной ноге по прихоти ревьюверов, потом месяцами вылизывать диссертацию и проходить гораздо более стрессовое чем любое интервью событие - защиту - он собирается.
ptr128
19.11.2023 13:19+1прочитает пол книжки, потратит несколько вечеров на прорешивание задачек на литкоде и потом легко пройдет алгоритмическое интервью
Не получив на нем ни йоты преимущества перед студентами, сделавшими тоже самое.
Вот скажите, если взять сто школьников средних классов и заставить Вас соревноваться с ними в таблице умножения, каковы шансы у Вас на победу?
месяцами вылизывать диссертацию и проходить гораздо более стрессовое чем любое интервью событие - защиту - он собирается
Естественно. Менять работу можно десятки раз. А диссертация останется навсегда.
mvv-rus
19.11.2023 13:19А можно я вместо @wataru отвечу, хоть вы меня и не любите (точнее, так даже лучше будет, мне теперь можно ваши действиия смело называть своим именем)
Вот скажите, если взять сто школьников средних классов и заставить Вас соревноваться с ними в таблице умножения, каковы шансы у Вас на победу?
Как минимум - равные: у меня эта таблица прошита в голове ещё в школе. А если нужно будет соревноваться в (полу)устном счете до 1000 - скорее всего, обойду их. Я же в общаге много, годами, в Монополию играл, и там было правило у нас: "ошибки делать не запрещается". То есть если ошибся в свою пользу - тебя поправят обязательно, в пользу других - твое право, ну, может потом, после партии кто-нибудь расскажет, куда пара сотен тысяч делась. Не, конечно, результаты промежуточные на бумаге фиксировались, но вот считать на бумаге, как в школе учили, не получалось: скорость игры не позволяла. И да, колькуляторов не было.
А нынешним школьникам, в эпоху всеобщей доступности калькуляторов, такой опыт взять уже неоткуда. Кстати, ходить в магазин такой опыт тоже позволяет.
Естественно. Менять работу можно десятки раз. А диссертация останется навсегда.
Ну, про диссертацию (советскую/российскую) я тоже знаю много. Нелицеприятного. И главное, что о диссертации надо запомнить: это экзамен на чин. Стереометрию там учить не надо. И вообще, главным органом при написании диссертации является зад, а не голова: потому что усидчивость требуется превыше всего. Ну, и для успеха защиты требуется, чтобы научный руководитель был уважаемым в научных кругах человеком
Но это - про нашу богоспасаемую. А чо там в Америке на PhD делается - это я не знаю.
ptr128
19.11.2023 13:19вы меня и не любите
Я не Вас не люблю, а Вашу страсть к демагогии.
Как минимум - равные
То есть Ваши шансы на победу будут 1%? Вместо 99.9% при соревновании по дифурам в частных производных. ЧТД.
И сразу вопрос, если нужна именно победа то есть смысл участия в первом соревновании? А во втором?
про диссертацию (советскую/российскую) я тоже знаю много
Ссылку на свой диссер дадите? Или опять "знаете", но их желтых СМИ?
mvv-rus
19.11.2023 13:19Я не Вас не люблю, а Вашу страсть к демагогии.
...которой не существует, но которую вы мне приписываете. Вот я и говорю: не любите. Ну, или вы просто в логику не умеете, и она вас раздражает.
То есть Ваши шансы на победу будут 1%? Вместо 99.9% при соревновании по дифурам в частных производных. ЧТД
Ну, если для работы на позиции объективно подходят 100 человек, то 1% - это честный шанс. И да, я понимаю, что вам, привыкшему устраиваться по знакомству, такой шанс не нравится, но есть ведь и другая сторона: люди без знакомств, достойные занять эту позицию. И ч к ним ближе.
Ну, а то, что вы объявили этот критерий заведомо негодным - это просто неверно. Потому что верный критерий априори неизвестен (опять назовете это демагогией, да?). Наниматель отбирает работников как хочет и несет сам все риски: будет плохо отбирать - получит неадекватных работников. Если для нанимателя отбор по зннанию алгоритмов оптимален - имеет право.
Ссылку на свой диссер дадите?
Нет. У меня в интернетах политика - не разглашать никакую персональную информацию, не нужную для обсуждения вопроса. Тем более, что в данном случае ссылка на дисер - это ниачом, а "ачом" - это выписка из трудововой, со стажем работы в учреждениях АН СССР/РФ (которой тем более не будет). Не хотите верить обоснованности моего мнения - да пожалуйста.
SpiderEkb
19.11.2023 13:19Вот поэтому гений скорее попадет в IBM, чем в Google.
Там вообще интересная тема... По словам Френка Солтиса (одного из отцов-основателей AS/400, которая построена на совершенно отличных от остальных ОС принципах)
Менее года назад я был в Буэнос-Айресе на встрече с группой пользователей этой системы. По окончании встречи молодой репортер газеты «La Nacion» спросил меня: «Сформулируйте, пожалуйста, коротко причины того, почему в AS/400 столь много новшеств?». И я ответил: «Потому что никто из ее создателей не заканчивал MIT.» Заинтригованный моим ответом, репортер попросил разъяснений. Я сказал, что не собирался критиковать MIT, а лишь имел в виду то, что разработчики AS/400 имели совершенно иной опыт, нежели выпускники MIT. Так как всегда было трудно заставить кого-либо переехать с восточного побережья в 70-тысячный миннесотский городок, в лаборатории IBM в Рочестере практически не оказалось выпускников университетов, расположенных на востоке США. И создатели AS/400 — представители «школ» Среднего Запада — не были так сильно привязаны к проектным решениям, используемым другими компаниями.
Один из примеров их подходов. Есть у них Standard Time Format - u64 где старшие 52 бита есть количество микросекунд от начала эпохи, младшие 12 - "биты уникальности", гарантирующие что несколько последовательных вызовов в течении одной микросекунды дадут уникальные значения (при это есть возможность вызывать как с установленными битами уникальности, так и без них - заполненными нулями).
Так вот, начало эпохи у них знаете какое?
1928-23-08 12:03:06.314752Кто сможет быстро догадаться почему именно так?
Преобразование к стандартному UNIX time (но с микросекундами)
#include <stdio.h> #include <mih/matmdata.h> #define IBM_EPOCH 0x4A2FEC4C82000000ULL #define MKSECS 1000000ULL int main() { unsigned long long tod; unsigned sec, usec; matmdata(&tod, _MDATA_CLOCK_UTC_NOT_UNIQUE); // приводим к UNIX time tod -= IBM_EPOCH; // убираем биты уникальности tod >>= 12; sec = (unsigned)(tod / MKSECS); usec = (unsigned)(tod % MKSECS); printf("MatMData: %u.%06u\n", sec, usec); return 0; }matmdata - функция-обертка над "машинной инструкций" Materialize Machine Data (MATMDATA)
zergon321
19.11.2023 13:19+3В комментах за меня уже всё сказали. А я добавлю, что люди других специальностей часто удивляются, что разработчику каждый раз при трудоустройстве приходится сдавать квалификационный экзамен, на котором его будут ещё и пытаться завалить, чтобы платить поменьше, при этом отсеивает он даже действительно годных к работе кандидатов
Vladimirsencov
19.11.2023 13:19+1Да можно согласиться. Если человек может решить задачу, то что то он знает и как то пишет код. Не самый лучший подход, но в голову ничего умнее не приходит с лёгким масштабированием и адекватными критериями.
Foror
19.11.2023 13:19>Есть ли какие-то еще альтернативы?
Да. Создать специализированную компанию для проведения интервью. На её базе даже организовать бесплатные (за счёт работадателей конечно и для тех у кого конечно есть опыт в разработке) курсы для тех, кто прям хочет в компанию вашего типа, но теряется в алгоритмах.Или когда нужно закрыть конкретный стек технологий. Такая компания может дать рекомендацию работадателю, что человек в короткие сроки его освоит. Сейчас в этом плане безумие - если ты имеешь опыт разработки 20 лет в определенной области, но ты не подходишь в эту же область, если не проходишь по тегам HR. Тем самым потенциальный сотрудник конечно может потратить больше времени (если у него есть пробелы) или наоборот меньше, но будет более компетентно оценен.
Кто будет вести интервью? Опытные программисты, которые заинтересуются такой работой, естественно высокооплачиваемые. Или высокой оплатой за каждого найденного специалиста. Даже сейчас видел нечто подобное, когда компания платит, за найденного для них программиста.
Думаю такая компания будет выгоднее для работадателей (в плане затрат), чем отвлечение высокооплачиваемых специалистов работадателя от основной работы. Она будет работать чётче, находить людей на порядки быстрее, имея в том числе базу специалистов, вести их карьеру и т.д. Хотя конечно нужно считать сойдётся тут экономика или нет.
В общем, дарю идею для стартапа. Как получите инвестиции, можете отблагодарить в личке )sergey-gornostaev
19.11.2023 13:19Создать специализированную компанию для проведения интервью.
Есть такие, кадровыми агентствами называются. Мало того, что результат далеко не идеален, так ещё и бывают случаи целенаправленного обмана в попытках впарить неликвид.
Или когда нужно закрыть конкретный стек технологий. Такая компания может дать рекомендацию работадателю, что человек в короткие сроки его освоит.
Каким образом это можно гарантировать?
Кто будет вести интервью? Опытные программисты, которые заинтересуются такой работой, естественно высокооплачиваемые.
Во-первых, никто не сможет отсобеседовать кандидата лучше, чем тимлид команды, которому потом с этим кандидатом работать. Во-вторых, никогда не встречал программистов, которым нравилось бы проводить собеседования, вряд ли такие вообще существуют. В-третьих, опытный программист, который ведёт собеседования вместо программирования, быстро становится неопытным.
Foror
19.11.2023 13:19>Есть такие, кадровыми агентствами называются
Там отбирают ещё хуже. По ключевым словам. Это не работает.
>случаи целенаправленного обмана
Впариваешь неликвид у тебя не будет заказов от крупных контор. А потом и от мелких. Закрываешься. Здесь решает репутация.
>Каким образом это можно гарантировать?
Более детально изучаешь кандидата, в отличии от потоковых интервью. Смотришь гитхаб, задаёшь вопросы, даёшь тестовую задачу и т.д. Со временем это будет на уровне интуиции, когда будешь каждый день собеседовать новых людей.
Не говоря уже о возможности собирать базу таких детальных интервью и во второй раз ты автоматически будешь знать данного кандидата и видеть его рост.
>никто не сможет отсобеседовать кандидата лучше, чем тимлид команды
Тимлид команды не умеет собеседовать, иначе бы он работал не тимлидом, а в кадровом агенстве.> никогда не встречал программистов, которым нравилось бы проводить собеседования
Вы прям всех опрашивали? Или это те случаи, когда человека отрывают от работы? Конечно никому не будет нравиться, когда отрывают от работы и просят делать то, на что не подписывался.
>опытный программист, который ведёт собеседования вместо программирования, быстро становится неопытным
Наоборот такой программист только вырастет профессионально. Это золотая жила иметь возможность разговаривать со специалистами, читать их код, задавать им вопросы, узнавать о достоинствах и недостатках тех или иных фреймворков и подходов.
Я не говорю уже о том, что такой человек будет иметь отличную базу по алгоритмам и собеседованиям. С первого взгляда сможет видеть потенциал любого новичка.Foror
19.11.2023 13:19Но такую контору конечно должен открывать человек, знающий что требуется в конкретных конторах. Чтобы подгонять оптимальных кандидатов.
Plesser
Ну собственно говоря Ваша статья как бы не противоречит тем утверждениям что были в статье которой Вы оппонируете. В вашем стеке видимо действительно важны алгоритмы, что бы добиться максимальной производительности/компактности (нужное подчеркнуть). Но при всем моем уважении к Вам и вашей компании, компаний где требуется такой стек как у вас минимум. Большинство компаний надо что бы программист создавал код с использованием готовых библиотек (в том числе ваших) и писал его в классических паттернах что бы его было удобно и быстро поддерживать.
wataru Автор
Алгоитмы, конечно, сильнее важны именно в "нашем стеке". Но большая часть статьи о других критериях, специфичных для масштабов ФААНГа.
Plesser
А какое процентное отношение программистов, которые разрабатывают алгоритмы с "обычными" программистами в компаниях ФААНГа?
wataru Автор
Поправлю вас - тут не разрабатывают алгоритмы, а применяют. Разрабатывают их computer scientist-ы. Но процент тех, кому приходится алгоритмы применять, я вам назвать не могу. По ощущениям, больше половины хоть раз да и применяли. Процентов 10 с алгоритмами работают довольно часто.
Вот разработчиков Хрома того же - куда записывать? Вроде и не библиотека, а код нашпигован всякими алгоритмами и структурами данных.
Формалного разделения никакого на "обычных" программистов и алгоритмистов, конечно же нет.
Plesser
Я вас правильно понимаю, алгоритм есть а реализации его нет? И программисты ФААНГа просто зная о наличии алгоритмы его должны реализовать?
wataru Автор
Ну вот мне понадобилось недавно искать максимум в двигающемся окне (при работе над хромом). Про это, кстати, даже задача на литкоде есть. Даже уровня hard. Желательно побыстрее, ибо поток, в котором это будет происходить итак бутылочное горлышко. Ну не было этой реализации в репозитории гугла. Мне первому это выпало с сотней элементов в окне. Пришлось самому реализовывать.
Plesser
Ну то есть Вы нашли готовый алгоритм и его реализовали? Тогда я не понимаю, в чем тут будет отличие Вас от "обычного" программиста?
Alexandroppolus
"Обычный" программист мог остановиться на решении за O(n*k), где k - размер окна.
Plesser
Обычно у программиста есть требования за какое время его программа должна что то делать полезное.
wataru Автор
Ну вот там требование было "чем быстрее тем лучше". Итак этот поток регулярно подтормаживает и то там то тут фрейм дропается.
Plesser
Тогда достаточно требования сделать быстрее чем существующее решение скажем на 25%
wataru Автор
Нет, это как бы новая фича. Надо добавить код в поток, который и так уже является бутылочным горлышком.
Plesser
Ну так технических требований нет что ли? Просто, сделайте что бы было красиво? Ну тогда у вас беда с архитектором и аналитиками.
wataru Автор
Техническое требование, как часто бывает - исправить баг. У вас там архитекторы с аналитиками вообще все тикеты в багтрекере, что ли, просматривают и составляют технические требования о том, как их фиксить? А программисты только и делают, что кодируют выданное им решение?
Большие проекты так не работают. Уже мидлы-сеньеры должны сами быть немножно аналитиками и не дергать людей по каждому пустяку.
Plesser
Аналитик для начало должен воспроизвести эту самую ошибку, на больших системах это не тривиальная задача. И потом когда он сумеет воспроизвести эту ошибку уже отдать ее разработчику. Мы работаем так.
wataru Автор
Это хром. Баг репорт от разработчика.
Их очень много - аналитиков не напасешься.
Plesser
Вы реально думаете что к примеру в банковской АБС меньше ошибок?
Может все таки тут вопрос в культуре программирования а не скилах в алгоритмах?
wataru Автор
Ошибок может и не меньше, а вот баг репотртов - точно. Одно дело, когда у вас сотни миллионов пользователей и десятки тысяч разработчиков. У банковской АБС, я думаю, числа поменьше.
Plesser
А как вы думаете сколько у нас клиентов? Несколько миллионов, если не десятков. А сколько они транзакций в день совершают пластиковыми карточками и межбанком? Я вот только сегодня совершил уже порядка 5 транзакций. А еще только половина дня.
Резюмирая, давайте не будем мериться у кого толще. Сильное требование по алгоритмическому программированию, как минимум достаточно узкая ниша на рынке труда. Даже нейронные сети сейчас уже не пишут с нуля а используют готовые фреймворки. Если Вас устраивает текущее положение дел в месте где Вы работаете, ок. Но только не надо это текущие положение натягивать на весь рынок IT.
wataru Автор
И часто эти клиенты вообще воспринимают свою карточку как продукт, которому можно отправить баг репорт? Нет, у вас клиенты - это банки. И вся их армия тех-специалистов сильно меньше армии всех веб разработчиков в мире.
Согласен. У нас сильно разные ситуации. Я лишь хотел объяснить почему тут просто физически аналитики не могут составлять тех задания по каждому багу.
И... эти фреймворки пишет Фаанг. Тот же TensorFlow - гугловый.
Опять же, я не натягиваю на весь рынок IT. А лишь на ФААНГ.
Plesser
Да, вопрос сколько людей пишет TensorFlow и сколько людей пользуется им?
Кто Вам это сказал? Наши клиенты это физические и юридические лица. А другие банки это контрагенты, если мы говорим про пластиковые карточки.
Сколько в гугле программистов на Си++ и скажем на Питоне? Ну примерно, ваша оценка?
wataru Автор
Пользуются, конечно больше народу. Просто пример весьма яркий получился. ФААНГ - имено та ниша, где алгортмы нужны. Помимо TensorFlow, очевидно алгоритмическими проектами являются libvpx, libwebrtc, v8, BigTable, всякие системы статистического анализа и еще куча вещей, которые я называть не могу. Не так очевидно, но такими являются и другие проекты, например, практически весь хром. Я, вот, работаю с медиа в хроме. Всякие mediaStream, getUserMedia и прочее. Даже не кодирование (для этого libvpx уже есть) - а просто протащить видео от камеры до video элемента на странице. И вот мне задачи с литкода попадаются.
Если не считать всякие периодические утилиты на питоне, вроде помошника для бисекта или визуализатора данных AB тестов, которые даже мне приходилось ковырять, то, по моим ощущениям программистов на С++ в 10-20 раз больше.
Plesser
наверное это специфика не сколько ФААНГа сколько компаний которые занимаются больше исследовательскими работами, это имхо
SpiderEkb
У нас 50млн сейчас (плюс-минус). Сотни миллионов бизнес-операций в сутки.
Про остальное писал тут и тут И все это только про АБС и центральные сервера. Что там происходит на "внешних системах" (которых у нас штук 60 разных) - вообще не в курсе. А там ну никак не меньше всякого происходит.
SpiderEkb
Разработчиков точно меньше. Пользователей... Ну клиентов сейчас в нас 50млн. Т.е. десятки миллионов. Разница не на порядки.
В банке сложность в том, что кроме собственно клиентов и транзакций от них еще куча всякой хтони происходит.
А багрепорты летят или от бизнес-подразделений, или от сопровождения.
SpiderEkb
Ну скажем так - если у вас баг, какова вероятность того, что в течении недели вам регулятор не выкатит штраф с шестью-семью нулями?
А если в банке вдруг платежи (ну баг же...) регулярно пошли в строну кого-то, кто фигурирует в списках росфинмониторинга, то тут под "финансирование террористической деятельности" попасть как дважды-два... А это уже может быть и не штраф, а лишение лицензии (в пределе).
Тот же финмон не может проверять каждую из сотен миллионов проводок. Поэтому есть "сито" - проверки в рамках контроля платежей. Которые пропускают сразу то, что не вызывает подозрений и отправляют на ручной контроль/авторизацию то, что по каким-то признакам не проходит проверки.
Проверок этих достаточно много. Работать они должны предельно быстро. Цена ошибки очень высока...
И это всего лишь один кусочек логики. Достаточно небольшой в общей куче того, что тут творится.
wataru Автор
Это очень интересный момемнт, спасибо. В моей работе - примерно 0. У нас с вами все-таки сильно разные ситуации.
SpiderEkb
Я не скажу что за каждый баг сразу расстреливают, но в целом неприятности могут быть достаточно крупными. По каким-то серьезным багам собирается "комиссия по инцидентам"...
Много сейчас идет "дефектов производительности" от сопровождения - старые модули по времени начинают вылезать за допустимое временное окно - надо переделывать, придумывать что-то более эффективное, а это всю логику поднимать с нуля, бизнес-требования уточнять (где на чем скроить можно), часто возникают какие-то попутные задачки типа "а вот тут мы витрину сделаем чтобы по исторической таблице не шарить постоянно" - значит надо ведение витрины прикручивать...
В целом тянуть 2-3 разноплановых задачи параллельно - уже норма. В каждой своя логика, свои подходы и решения.
В целом не готов меряться у кого толще/длиннее, просто везде свои заморочки.
wataru Автор
Нет, я его сам придумал. Он на самом деле простой. В принципе, его можно было бы и нагуглить. Но именно знание алгоритмов позволило остановиться и подумать, а можно ли здесь побыстрее чем за квадрат сделать.
Потом, вот именно в этом примере относительно просто догадаться, что ключевые слова "moving max" или "sliding window max". Но это, опять же, потому что я видел задачи вроде "moving average". А вот когда мне пришлось динамическое программирование писать раньше - вот тот алгоритм вообще никак не нагуглить.
И главное, чтобы найти готовый алгоритм и его реализовать, нужно обладать некоторой квалификацией. Это не то же самое, что вызвать функцию из библиотеки. Так-то, почти любой кусок вашего кода можно найти на stack overflow, но вы же чем-то отличаетесь от войти-вайтишника после курсов "до мидла с нуля за 2 недели"? Хоть они тоже способны скопировать найти код в интернете.
Plesser
Ну так с чего вы взяли что "обычный" программист это не сделает?
Вам пример из жизни, я пару раз наступвл на грабли при собеседовании с алгоритмическим программированием. Ну ок, я решил больше в эти игры не играть (стресс когда тикают часики и на тебя смотрят те кто проводит собеседование, то ещё удовольствие). Там где я сейчас работаю постоянно требуются решать финансовые задачи связанные с придумыванием алгоритмов. И заказчики довольны. Моё знание как бизнес работает с их стороны помогает мне решать задачи без проблем.
Как вы думаете буду я соглашаться на алгоритмические собеседования в будущем или буду думать ну их нафиг?
wataru Автор
Обычный программист вообще знает слова "moving max"? Как он нагуглит алгоритм-то без них? А как он будет гуглить решение проблемы, где нужно динамическое программирование? Никак - только впендюрит полный перебор.
Plesser
Ну то есть вы решили за него. За программиста. Ок. Кстати а Chatgpt решит вашу задачку?
wataru Автор
Если знать ключевые слова, то да. Если спросить про "max in a moving window" - то решает. Если же спросить про "надо на каждой итерации получить максимальное среди последних K чисел" - то он генерирует абсолютный бред (использует heap для поиска k-ого по величине числа). И это для широко известной простой задачи - если спрашивать про что-то чуть более специфичное, то оно ну никак не справляется.
Я задавал ему другую встреченную мною в проде задачу, которую сейчас даю на интервью - GPT4 вообще ее даже не понял.
Потом, "обычному программисту" в этом случае chatGPT использовать вообще, категорически, нельзя! Оно может сгаллюционировать какую-то странную ошибку, которую не обладающий багажом знаний и опыта решения именно алгоритмических задач человек, ну никак не сможет заметить. И если этот правдоподобный, да с убедительными комментариями код попадет в прод - то пиши пропало.
Plesser
ChatGPT вообще нельзя использовать любому программисту, потому что он быстро программиста приучит к лени и тогда будет весело
motoroller95
chatGPT. мне недавно надо было в массиве дат с пропусками заполнить пропуски нулями (статистику вывести в таблице и графиком). ну я бы и сам написал, конечно, однако чатГПТ выдал мне оптимальное за O(n) решение (не знаю можно ли сделать сложнее). вряд ли я стал от этого хуже программистом.
UPD: можно сложнее. мне почему-то сразу в голову пришло отсортировать за n*log(n) а потом уже пропуски заполнять. но чатгпт предложил этого не делать и вместо него юзануть хешмапу
sgjurano
Это егэшная задачка по информатике, btw. Сдавал недавно (так вышло) - мне вот ровно она попалась, за 15 минут не уложился решить, сейчас интереса ради попробовал на leetcode - полчаса ушло с учётом вспоминания синтаксиса С++.
Хз насколько это вообще показательно, очень уж сильно зависит успешность решения таких задачек от набитости руки и состояния в моменте - в итоге алгоритмические секции просто проверяют насколько у человека натренирован конкретно этот навык, и корелляция с успешностью выполнения рабочих задач тут отнюдь не полная.
UPD: почитал решения, можно за линию сделать оказывается, у меня было решение за O(nlogk) - забавная задачка :)
Ravager
del
mvv-rus
И вы опять хотите, небось, чтобы человек на собесе эту задачу решил где-то за полчаса?
В принципе, задача решается довольно очевидно: сохраняется отсортированый список (массив или что там ещё) значений из первоначального окна, а потом при сдвиге этот отсортированный список корректиуется, значение с бывшей левой границы убирается, а значение с новой правой- добавляется в отсортированный список. Но есть нюансы:
Например, там опять условие есть неудобное - что размер окна может быть порядка размера всего массива. То есть пузырьком или простыми вставками поддерживать порядок после сдвига окна не получится, нужно как-то ещё корректировать сортировку, менее очевидным способом (вставка в дерево? ОК, пошли тогда деревья крутить и красить, потому что балансировка дерева в поцессе уехать может: случайность данных в массиве-то никто не гарантирует) А всё это - время на написание, и всё из того же получаса.
Ну и требуется больше оверхеда по памяти. Если ограничений на оверхед по памяти нет, то все нормально, а если есть?
PS
Вообще-то - в слове AFAIK: в древних ЭВМ память делилась на слова.
Alexandroppolus
Всех этих ужасов там не надобно, а только лишь такие факты: очередь можно на двух стеках, стек умеет в максимум/минимум.
wataru Автор
А еще можно хранить дек из убывающих чисел - тех элементов, которые являются максимумом или могут им в будущем стать. При добавлении нового элемента вытесняем меньшие его с конца. При сдвиге окна удаляем первый элемент, если он из окна выпал. По ощущениям, код чуть проще двух стеков.
wataru Автор
Нет, я бы эту задачу не давал на собесе. Она hard помечана, кстати.
На интервью не просят писать деревья! Используйте стандартную библиотеку. Можно поддерживать, например, multiset элементов в окне, если вам так хочется. А там вам остается только вставить в стандартную структуру новый элемент из окна, да удалить старый. И уметь брать там максимум. Вот такие вот знания как раз очень полезны в работе, когда вы не просто абстрактно знаете про деревья, а умеете применять стандартную библиотеку правильно.
Но вообще, тут можно и быстрее и проще: надо хранить в окне только те элементы которые могут быть максимумом. Это маскимальный сейчас элемент. Потом максимальный правее него и т.д. Они образуют двусвязный список или дек из убывающих элементов. При добавлении нового элемента с конца удаляются меньшие его. Они никогда больше не станут максимумом, ибо в окне правее их уже есть что-то большее. При сдвиге окна первый элемент может выпасть - его надо удалить. В ответ всегда выдаем первый элемент.
mvv-rus
Годная оптимизация! Мне она вчера в голову не пришла. В таком случае пропадает необходимость вставки в середину, т.е. можно обойтись беез деревьев, их покрасок и вращений. Рубим хвост в точке вставки - и всё!
В двусвязном списке долго(O(n)) искать точку, куда попадает вставляемый элемент и где надо рубить хвост. Я бы предпочел хранить список в отсортированном массиве и искать точку размещения добавляемого элемента бинарным поиском бинарным поиском по нему. А чтобы не двигать элементы массива - иметь индексы головы и хвоста, которые увеличиваются/уменьшаются по модулю размера массива.
Но, собственно, после этого замечания обсуждать болльше нечего.
wataru Автор
Не надо искать точку. Элементы всегда вставляются в конец (обрубая хвост).
Вот пример: Окно длины 3. Числа {1,4,3,2,5,2,3,1}.
Добавляем в окно 1: {1}
Добавляем в окно 4: {4} (вытеснили 1)
Добавляем 3: {4, 3}
Удаляем 1: {4,3} (не поменялось - оно было уже раньше удалено)
Добавляем 2: {4,3,2}
Удаляем 4: {3,2}
Добавляем 5: {5} (высеснили все)
и т.д.
Еще раз, идея - храним только максимум, потом то число, которое станет максимумом после того, как текущий максимум выйдет из окна, потом следующее, когда это второе выйдет из окна и т.д. Очевидно, они образуют убывающую последовательность.
Последнее число в окне всегда хранится в деке. При отрезании элементов слева просто второй кандидат в максимумы становится первым, третий - вторым и т.д. При добавлении нового числа справа какие-то числа перестанут быть кандидатами.
mvv-rus
Вопрос в том - какие именно перестанут? Иными словам - как найти точку, в которой рубить хвост. Она вообще-то поиском ищется. А бинарный поиск быстрее последовательного.
wataru Автор
Все, что меньше добавляемого числа. Не надо искать точку, надо делать pop_back(), пока на конце число меньшее. Тут не нужен бинарный поиск, потому что элементы все-равно надо удалять.
Несмотря на то, что тут есть вложенный цикл - амортизационно это работает за O(1) на сдвиг окна, потому что каждый элемент удалится максимум один раз.
Edit: Бинпоиск даже медленнее работает! С ним у вас будет O(n log w) сравнений, без него - просто O(n). Но даже если забить на ассимптотику и у вас w - маленькая константа, то с бинпоиском у вас будет n log w + 2*n сравнений, без него - 2*n.
mvv-rus
Опять хорошая, годная оптимизация за счет далеко не сразу приходящего в голову игварианта. Но - она не про знание алгоритмов, а про общую сообразительность, скорее (а у меня с ней при 37,5 нынче плоховато). Которую на собесе толком не проверить.
Но раз вы такую задачу на собесе не рекомендуете - то это вне темы обсуждения вашей статьи. Думаю, тема закрыта.
SpiderEkb
А кольцевой буфер там не подойдет? В принципе очень похоже получается...
Alexandroppolus
Это он и есть.
SpiderEkb
Тут скорее не деревья, а что-то типа SkipList лучше подойдет
werevolff
Расскажите нам, пожалуйста, что такое ФААНГ, и какое отношение вы имеете к нему?
wataru Автор
ФААНГ - нарицательное название ИТ-гигантов (пошло от Фейсбук, Амазон, Апл, Нетфликс, Гугл). Пошло вообще-то с биржи и изнчально был критерий - капитализация. Сейчас этим термином называются все такие большие компании характирезующиеся в стреднем высокой зарплатой, большим штатом и работой с огромным количеством данных. В целом термин не очень строгий. Мое отношение к нему: я работаю в гугле.