вторник, 1 июня 2010 г.

[work; prog] Так вот о тестовом задании для C++ников

Расскажу подробнее о тестовом задании (условие было опубликовано ранее), которое я давал кандидатам на должность C++ программиста.

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

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

Ловушка первая, она же главная. Условие задачи не гарантирует того, что лицензионная информация всегда находится в начале файла. Да, пример приведен именно такой. Но условие этого не гарантирует.

Фактически, этот тест является главным тестом на внимательность изучения условия задачи. Более-менее опытные разработчики уточняют это в дополнительных вопросах. Такой вопрос – сразу же большой и жирный плюс кандидату. Еще более жирный плюс – если кандидат не задавал вопросов, а сделал универсальное решение сразу.

Поскольку лицензия может находится в любом месте файла, а весь файл не должен загружаться в память целиком, то сразу же вырисовывается чуть ли не единственный способ ее решения: принцип “скользящего окна”. Т.е. из файла считывается N строк, которые и сравниваются с текстом лицензии. Если не совпадают, то одна первая прочитанная строка выбрасывается, а еще одна считывается, и производится новое сравнение. Ничего сложного, имхо.

Еще один большой и жирный плюс можно заработать, если при несовпадении прочитанного из файла фрагмента выбрасывать не одну строку, а несколько. Здесь же принцип точно такой же, как и при поиске подстроки в строке – можно применять и метод Кнута-Морриса-Пратта, например.

Но, поскольку большинство кандидатов условие читают невнимательно, а уточняющие вопросы не задают, то и работающего решения не получают. Интересно при этом, что некоторые и простое сравнение заголовка файла с текстом лицензии умудряются запутать так, что не сразу и разберешься.

Ловушка вторая, тест на максимализм и способность расставлять акценты. Это разбор аргументов командной строки и response-файла. Поскольку реализация response-файла объявлена бонусом, то самоуверенные разработчики сразу же берутся за нее. Изобретая при этом свой собственный маленький велосипед для универсального разбора аргументов (чтобы аргументы командной строки и содержимое response-файла обрабатывались единообразно).

А вот делать этого не следует. Сроки на решение небольшие (для последних вакансий я давал по два дня), если знаний и опыта не хватает, то такую библиотеку сделать не успеешь. Нужно рассчитывать силы и расставлять акценты. Главное что? Работа с лицензией. Вот она и должна быть сделана на пять баллов. И только после этого можно браться за response-файлы. Если получилось – отлично, если нет – ничего страшного, предъявляется минимальный вариант, который, тем не менее, полностью решает исходную задачу.

Как показывает практика, далеко не все могут расставить акценты именно так. Даже были случаи, когда кандидат успевал сделать response-файлы, но не успевал реализовать работу с лицензиями.

Неожиданным для меня явилось еще и то, что даже разбор аргументов командной строки оказался очень хорошим тестом. В частности на склонность людей к хардкодингу и дублированию кода. Очень многие решения грешили большими циклами по содержимому argc, внутри которых были развесистые if-ы с кучей strcmp и зашитыми прямо в код именами аргументов.

В принципе, в response-файлах так же есть маленькая ловушка. Хотя она ни разу не срабатывала (т.к. толком response-файлы никто и не сделал), но она есть: в именах файлов могут быть пробелы. И такие имена в response-файлах нужно задавать в кавычках. А раз так, то нельзя читать response-файл, например, с помощью штатного operator>>(istream&,string&) – будет идти разбиение по пробельным символам.

Ловушка третья, она же маленькая заноза в заднице. Это требование к учету различных концов строк (DOS-овский, Unix-овый и Mac-овый). Это самая настоящая мелочь. Но она определяет, каким образом в памяти должен храниться текст лицензии. И как нужно представлять в памяти фрагмент файла для сравнения.

Поскольку концы строк нужно отрезать при сравнении лицензии, сразу же отпадает возможность искать совпадение с помощью std::string::operator== или memcmp. Строки нужно хранить отдельно, концы строк – отдельно.

Мне казалось, что здесь нет ничего сложного. Ну нужно было сделать структуру, в которой был бы список строк и использованный в них маркер конца строки или же список объектов, в каждом из которых хранится строка и ее маркер. И всех делов. Так ведь нет! Каких только странных комбайнов я не насмотрелся :)

Ловушка четвертая, тестирование. Только считанные единицы соискателей вместе с решением присылают тестовые файлы на которых они проверяли свое решение. Не удивительно, что они не проходили даже поверхностной проверки (например, далеко не все решения могли выполнить цепочку из insert-change-delete). Во время последнего поиска людей первым, кого я взял, был программист, который прислал далеко не самое лучшее решение. Но вместе с решением шел набор тестовых файлов и батник, запустив который можно было эти тесты прогнать. И я взял его, даже не смотря на то, что опыта работы и знаний у него было намного меньше, чем у всех остальных претендентов. Зато задатки правильные :)


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

  • дублирование кода и большие функции (по 100 и более строк);
  • хардкодинг. Суровый и повсеместный. Ладно когда имена аргументов командной строки задаются прямо в strcmp. Так ведь они затем используются для определения режима работы программы, при выдаче сообщений об ошибках и т.д.;
  • слабое знание STL. За счет использования std::ifstream, std::vector, std::string решение данной задачи не представляет сложности. Но если вместо них брать старые-добрые FILE*, самодельные списки с ручным управлением памятью, буфера для строк фиксированного размера и прочие plain-C прелести, то и решения получаются большие, сложные и ненадежные;
  • отсутствие контроля за успешностью операций ввода-вывода. Доходило даже до того, что люди открывали файл и даже не проверяли, открылся ли он;
  • отсутствие устоявшегося стиля кодирования. Хотя это объясняется тем, что многие имели опыт не более 1-2 лет работы. Но даже и опытные разработчики не могли объяснить, почему в одном месте они обозвали переменную в camelCase, а в другом – в lower_case.

Такие дела. Хорошая была задача. Теперь буду придумывать что-нибудь новое :)

Напоследок хочу предупредить тех, кто захочет попробовать практику тестовых задач. На анализ решений вам потребуется время. Иногда много. На некоторые решения у меня уходило часа по три, если не больше. Бывает так, что смотришь в код, чувствуешь, что здесь что-то не так. А точную причину беспокойства понять не можешь. Приходится вникать, писать собственные тесты, гонять программу в разных режимах. Для того, чтобы потом обстоятельно, с уликами на руках, объяснить кандидату что почем ;) Так что не самый легкий это путь отсева претендентов.

27 комментариев:

имя комментирует...

> нужно было сделать структуру, в которой был бы список строк и использованный в них маркер конца строки или же список объектов, в каждом из которых хранится строка и ее маркер

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

eao197 комментирует...

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

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

Однако, я не понимаю решений, в которых конец i-й строки лицензии ищется каждый раз, когда эту строку сравнивают со строкой из файла.

имя комментирует...

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

"не нужно" можно понимать в двух смыслах:

1. не нужно заморачиваться с написанием спец. кода обработки концов строк (достаточно сделать это 1 раз в классе итератора)

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

так вот п.2 при нынешнем железе бессмысленно, т.к. предсказатель переходов сведет оверхед ре-парсинга к нескольким процентам (которые вдобавок утонут в тормозах диска), а вот п.1 имеет смысл

я бы даже предложил сравнить наши 2 подхода на примере функции delete_and_insert(char* del_file_name, char* ins_file_name, char* work_file_name) [если кто-то из указателей NULL, то соответствующее действие не производится; если файл с именем del_file_name оказался пустым, то ошибки нет и он находится в самом начале файла work_file_name]

и в свете этой вашей статьи мне кажется, что у вас к кандидатам были слишком жесткие требования :-)

имя комментирует...

кстати, интересный аспект -- если del-файл заканчивался на конец строки, а ins-файл -- нет, то в результате замены может получиться неудобоваримо или даже вообще неверно, если:

/* old copyright */
#define FOO bar

имя комментирует...

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

"не нужно" можно понимать в двух смыслах:

1. не нужно заморачиваться с написанием спец. кода обработки концов строк (достаточно сделать это 1 раз в классе итератора)

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

так вот п.2 при нынешнем железе бессмысленно, т.к. предсказатель переходов сведет оверхед ре-парсинга к нескольким процентам (которые вдобавок утонут в тормозах диска), а вот п.1 имеет смысл

я бы даже предложил сравнить наши 2 подхода на примере функции delete_and_insert(char* del_file_name, char* ins_file_name, char* work_file_name) [если кто-то из указателей NULL, то соответствующее действие не производится; если файл с именем del_file_name оказался пустым, то ошибки нет и он находится в самом начале файла work_file_name]

и в свете этой вашей статьи мне кажется, что у вас к кандидатам были слишком жесткие требования :-)

имя комментирует...

я написал char* del_file_name пытаясь унифицировать разные подходы (у меня будет FILE*, у вас может быть xxstream), но это неправильно -- надо просто разрешить прототипам быть чуть разными

в функции допустим delete_and_insert(FILE*, FILE*, FILE*) или аналогичной можно не обрабатывать ошибки, и проще будет сравнить подходы

имя комментирует...

* не обрабатывать ошибки несуществующего или нечитаемого файла

eao197 комментирует...

>кстати, интересный аспект -- если del-файл заканчивался на конец строки, а ins-файл -- нет, то в результате замены может получиться неудобоваримо или даже вообще неверно

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

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

eao197 комментирует...

Спецкод по обработке строк нужно будет написать один раз -- при чтении строки из файла (строку читать придется самостоятельно, чтобы стандартные fgets/getline не выбрасывали маркеры). Зачем это делать после чтения при сравнении я не понимаю, даже если принять тезис о том, что железо всегда будет настолько умным и быстрым.

имя комментирует...

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

затем, что вероятно кода будет меньше, он будет более общий (вообще нет нужды в структуре данных "список")

аппаратное предсказание ветвлений у нас уже начиная с первого пентиума; емнип в атомах его выбросили, но это не платформа для девелоперской тачки :-)

eao197 комментирует...

>затем, что вероятно кода будет меньше, он будет более общий (вообще нет нужды в структуре данных "список")

Боюсь, я не понимаю, о чем сейчас идет речь.

имя комментирует...

> А вообще такой вопрос отлично демонстрирует то, как много деталей нужно уточнить даже в простом задании.

что говорит о хорошем качестве самого задания

а вот вариант с итераторами я наверно не поленюсь, сделаю как РОС и запощу ссылку

eao197 комментирует...

>а вот вариант с итераторами я наверно не поленюсь, сделаю как РОС и запощу ссылку

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

имя комментирует...

пописал вариант с итераторами... и подумал, что проще будет конвертнуть лицензию во все 3 кодировки, а дальше сделать окошко величиной в две лицензии и двигать его по файлу, и тупо делать memcmp

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

eao197 комментирует...

>пописал вариант с итераторами... и подумал, что проще будет конвертнуть лицензию во все 3 кодировки, а дальше сделать окошко величиной в две лицензии и двигать его по файлу, и тупо делать memcmp

Этот способ не будет работать на экзотических ситуациях, когда внутри одного файла у концов строк разные маркеры (что бывает при таскании файлов с платформу на платформу).

Да и на больших лицензиях (вроде полного текста GPL) делать тройную копию лицензии как-то...

имя комментирует...

> Да и на больших лицензиях (вроде полного текста GPL) делать тройную копию лицензии как-то...

значит 300К оперативки жалко, а 100К в *каждом* файле не жалко? ну-ну.

имя комментирует...

> Этот способ не будет работать на экзотических ситуациях, когда внутри одного файла у концов строк разные маркеры (что бывает при таскании файлов с платформу на платформу).

вот это я не понял, щас задам вопрос подробнее

имя комментирует...
Этот комментарий был удален автором.
имя комментирует...

> Этот способ не будет работать на экзотических ситуациях, когда внутри одного файла у концов строк разные маркеры (что бывает при таскании файлов с платформу на платформу).

тут можно предположить, что лицензия писалась в одной кодировке внутри себя;

хотя конечно видно отставание от "списка строк", так что надо еще подумать

eao197 комментирует...

>значит 300К оперативки жалко, а 100К в *каждом* файле не жалко? ну-ну.

Ну если это XML-ный дамп чего-нибудь на 100+ Mb, то 100K не жалко. А вот три memcmp блоками по 100K мне кажутся слишком накладными -- боюсь данные будут быстро из кэша процессора вылетать.

По поводу различных концов строк. Вот пример. Был файл в Unix-овом формате. Есть файл лицензии в DOS-овском формате без маркера после последней строки. Эта лицензия один-в-один вставляется в начало файла и тут же добавляется Unix-овый маркер после последней строки лицензии. Получается, что в лицензии (n-1) первых строк с DOS-овским маркером, а n-я строка с Unix-овым.

имя комментирует...

даже если делать из файла список строк, то обрабатывать его надо посимвольно

вывод: последовательно читаем файл посимвольно, конвертируя в формат юникс; держим окошко в 2 лицензии, лицензию имеем 1, тоже конвертную в юникс

сравнение делаем тупым memcmp, если внезапно этого не хватает -- можно прикрутить алгоритм кнута-морриса-пратта, и это к буферу сделать проще, чем к списку строк; да и сам буфер проще, чем список строк, причем существенно

я бы хранил оффсеты в параллельном окошку массиве; 9 объемов лицензии обязаны помещаться в оперативку, т.к. в IDE помещается не меньше 10 файлов :-)

предвижу возражение: в лицензии может оказаться конец строки, а в ее копии в файле -- нет; ну так выбросим последний конец строки в лицензии перед поиском, и будем добавлять его при вставке

имя комментирует...

слушая себя, я начинаю понимать, почему те программы, которые раньше работали на 32М, щас не влезают в 256М :-)

но на практике задачу решать надо все же с памятью в 10 лицензий

имя комментирует...

и с количеством проходов я бы тоже не церемонился: определение кодировки, нахождение позиции лицензии, копирование файла -- каждому по проходу

eao197 комментирует...

>даже если делать из файла список строк, то обрабатывать его надо посимвольно

Не очень понял почему.

>вывод: последовательно читаем файл посимвольно, конвертируя в формат юникс; держим окошко в 2 лицензии, лицензию имеем 1, тоже конвертную в юникс

Да, на первый взгляд это уже должно работать нормально. Только хранить нужно будет две лицензии -- одну исходную (для вставки), вторую -- конвертированную в Unix (для поиска). Поскольку в условии было сказано, что при вставке в лицензии должны использоваться те переводы строк, которые в ней были.

>слушая себя, я начинаю понимать, почему те программы, которые раньше работали на 32М, щас не влезают в 256М :-)

:)

имя комментирует...

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

забыл совсем об этом. почему не стиле всего файла?

(если так, то проход определения кодировки можно исключить)

eao197 комментирует...

>забыл совсем об этом. почему не стиле всего файла?

Ну я же говорил: маленькая заноза в заднице :)
Чтобы не повадно было просто трансформировать все в одно представление -- так вообще нет никакого спортивного интереса :)

имя комментирует...

не вижу никакой сложности в реализации -- наоборот, можно исключить определение кодировки