О разнице взглядов на привычные вещи

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

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

Пригласили мы его на интервью. Спрашиваю у него, какими проектами он занимался.

• Тем-то и тем-то. Драйвера, системное программирование.

• Отлично, а почему вы занимаетесь системным программированием?

• Ну, меня этому научили.

• Гм. Вот я, например, занимаюсь системным программированием, потому что мне это нравится. А вы – потому что вас этому научили?

• Ну да! Меня этому научили и я всю жизнь этим успешно занимался.

«Вот те раз, подумал Штирлитц». Ну ладно, подумалось, что тут такого? Ну, зарабатывает на жизнь себе человек системным программированием, ну и что?

Продолжаем разговор. Он вполне отвечает на вопросы, - видно, что он знает о чем говорит, причем, знает, похоже, из практического опыта. Хотя мы явно говорим на разных языках – от него сложно сходу получить ответ на мало-мальски общий вопрос. Он предпочитает думать о проблемах на конкретных примерах. Ну ладно, ничего особенного пока. Хотя немного странно. От Senior SDE ожидаешь умения обобщать.

Доходим до рисования кода на доске. Задача (тут я немного упрощаю): есть два произвольных бинарных дерева. Нужно сказать является ли второе дерево поддеревом первого дерева. В лоб это решается рекурсивным обходом дерева и рекурсивным сравнением в каждом узле дерева. Задача на внимательность – нужно постараться не пропустить граничных условий. А дальше следует дискуссия в таком вот ключе:

• (Он) А каков алгоритм построения дерева?

• (Я) Произвольное бинарное дерево, произвольной глубины. Выбирайте наиболее удобную структуру данных.

• Нет, но каков, все-таки, алгоритм построения дерева? Я знаю Infix, Postfix and Prefix алгоритмы построения дерева. Ведь зная алгоритм, я могу оптимизировать поиск.

• Правильно, зная алгоритм либо порядок узлов в дереве можно оптимизировать поиск. Однако, в данном случае, про дерево известно только то, что оно произвольное бинарное дерево. Я согласен, что в результате получится менее эффективный алгоритм, но таковы условия задачи.

• Но я должен знать алгоритм, иначе эту задачу невозможно решить!

• (Сдаюсь). Ну, хорошо. Алгоритм построения дерева такой. Есть случайная (намек!) строка символов. Алгоритм берет каждый из символов в цикле и на каждой итерации вызывает генератор случайных чисел. Если тот возвращает 1, то символ вставляется как левый дочерний узел. Если возвращается 2 – как правый. Если соответствующий дочерний узел существует, то алгоритм спускается на один узел вниз в соответствующую сторону и снова вызывается генератор случайных чисел.

• Да, но этот алгоритм сгенерирует разные деревья для одних и тех же данных!

• Совершенно верно.

• Но тогда нельзя решить поставленную задачу.

• Я уверен, что можно. Смотрите, сначала мы обходим все дерево рекурсивно и в каждом узле сравниваем поддерево с правым деревом.

Я думал, что уж после этого дискуссия перейдет в более знакомое русло, но не тут-то было. Мы каким-то образом снова съехали к алгоритму построения дерева, вместо алгоритма его обхода.

• (Он) Я никогда не сталкивался с такой задачей. Разве у нее есть практическое применение?

• (Я) Вообще-то это выдуманная задача, но представьте, что вам нужно определить входит ли определенный кусок XML в произвольный XML файл, скачанный из интернета.

• Но по XML можно построить грамматику, которая описывает правила построения этого XML файла!

• Правильно. Грамматика произвольного XML позволяет любой порядок узлов и любую вложенность. Что, с точки зрения исходной задачи, эквивалентно грамматике произвольного бинарного дерево (для педантов, - XML не бинарное дерево. :-) )

• (после пару минут разговора) Мне такая задача не встречалась. Может если бы в книге мне встретилась такая задача…

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