С интересом читаю Гришу в ФБ. Вместо ответа комментарием на вопросы про алгоритмы сортировки (https://goo.gl/pPcJEd), напишу пост, так чуть удобнее, букв много. Речь в посте Гриши шла про то, нужно ли пытать кандидатов алгоритмами, которые давно уже никто не пишет на этих языках (и он верно объясняет почему).
В TEAMIDEA я выбрал три задачки, которые давал почти всем программистам на собеседовании. Иногда все собеседование состояло в обсуждении этих задачек (вообще пул задачек у меня был больше, но эти три вылезали чаще).
Первая задачка – про то, как искать по миллиону текстовых документов. Т.е. нужно написать свой поиск с нуля. Вводишь три слова – находишь три сотни документов, где эти три слова есть.
Мне ее интересно обсуждать, потому что я сам когда-то писал поиск и знаю связанные с этим сложности. Оцениваю задачу как легкую, но если кандидат с ней справляется – есть “продолжения”, вроде “а как быть, если слов несколько, вам же пересекать множества документов по каждому слову надо, а множества большие”, а также про постраничный просмотр и fuzzy search. Минимум кандидат должен был догадаться про пары WordId -> PageId, и даже это не выходило у 50% по резюме хороших специалистов.
Вторая задачка – про сокращатель урлов. Вводишь в форму урл – дает нечто короткое. Вводишь короткое – редиректит на длинный. Нужно продумать проект и найти технические риски, придумать архитектуру и алгоритмы. Оцениваю задачу как легкую.
В этой задачке полезно знать про биты и байты, кодировки. Решение на самом деле дико простое – надо сохранить урл в NoSQL, а индекс перевести в 65-ричную систему, он же и будет коротким урлом.
Эту задачу вообще в таком виде единицы решали. Что только не придумывал народ…
Третья задачка – про сжатие данных. Постановка ее открытая – есть текст на русском, нужно, чтобы он занимал меньше байт. Но при этом без потерь. Пойдут любые способы. Сложность аналогичная первой.
Многие пытаются заменять частые сочетания букв на айдишники, но правда, ломаются уже на том, сколько бит нужно на этот айдишник. До решения с плавающим числом бит на айдишник не додумывался никто. До алгоритма Хаффмана не додумывался никто. Лемпель-Зив процентов на 10 угадывали, но в целом тоже плохо. В лучшем случае сжимали текст, убирая лишние биты (раз текст на русском), что уже тоже неплохо.
Почему эти три? Теоретически к ним можно было заранее подготовиться, но, слава богу, ни разу компании, которые присылали программистов, не выясняли и не передавали детали следующим. Не знаю, плюс это для них или минус 🙂 Даже, если бы кто-то заранее прочел про поиск или сжатие, это, может, дало бы и плюсы, т.к. нельзя все знать, но сам факт подготовки к собеседованию добавляет очков.
Каждая задача не имеет одного правильного ответа. Можно придумать разные способы ее решения, и я оценивал насколько у человека работает техническая фантазия и насколько широк кругозор. Насколько он умеет рассуждать и насколько он умеет доказывать свою точку зрения.
Grigoriy Dobryakov, какой-то процент приходящих давал ответы в стиле “ну как, я возьму Solr и библиотеку сжатия данных”. Это лучше, чем ничего, особенно, если человек ЗНАЕТ или ИСПОЛЬЗОВАЛ это всё, но практически во всех этих случаях они не способен объяснить, как это работает внутри. Иногда – вообще.
За редкими исключениями эта система никогда не давала сбой:)
Being in America 