Две задачки для собеседования разработчиков

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

Задачи на смекалку

Вы стоите на отвесной горе, высота которой 100 метро. У вас есть веревка длиной 80 метров. На скале на высоте примерно 50 метров от земли есть выступ, на который можно встать и закрепиться. Как спуститься вниз?

Были люди, которые знали уже ответ, но делали вид глубоко задумавшегося человека, а потом, о чудо! рождали решение. Многие честно не справлялись с заданием. Но это была все же некая вводная задача.

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

Знание технологий

Второй тип вопросов, которые я задавал, был связан со знанием инструментов, механизмов, технологий, например:

1. Расскажите, что такое инкапсуляция.
2. Как в Java сделать вызов функции из dll-библиотеки, написанной на C++.
3. Какие недостатки у MS SQL Server и MySQL? В чем их принципиальное отличие?

Со временем я отказался и от этих вопросов. На мой взгляд не каждый программист все это в совершенстве должен знать. Да, инкапсуляция — это важный инструмент ООП, но если программист всю жизнь писал без ООП, то что, он теперь плохой? Просто ему не требовалось. Зато он может с ходу написать эффективный алгоритм сжатия строки или драйвер какой-нибудь. Про холивары между разными СУБД я вообще молчу, всегда можно открыть документацию, форумы, и почитать, что да как. То же и про механизмы, не обязательно знать, что откуда и как вызывается, обязательно уметь «найти решение» этого вопроса. Если вы никогда не вызывали функцию из dll — это не повод вас не взять и никак не характеризует вас как толкового или бестолкового. Посмотрите как это делают другие и все у вас получится.

Практические задачи

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

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

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

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

Первая задачка

Есть две таблицы русских words_1 и words_2 с полями (word as VARCHAR, ref as INT), где word — это слово, ref — ссылка (числовой код) на какую-то другую (не важно) таблицу, где перечислены все определения этих слов. В каждой таблице все слова уникальные (без повторов). В первой таблице есть какие-то слова, которых нет во второй, и наоборот, во второй таблице есть какие-то слова, которых нет в первой, но большая часть слов в обоих таблицах одинаковая. Нужно получить единую таблицу со всеми словами и соответствующими им ссылками.

Начальные условия / трудности:

1. для одних и тех же слов ссылки в разных таблицах могут быть разные, т.к. словари были загружены из разных мест;
2. количество слов в каждой таблице сотни тысяч, т.е. алгоритм сравнения «в лоб» все со всеми не подходит, т.к. 100 тысяч х 100 тысяч как минимум даст 10 миллиардов сравнений;
3. если вы разработчик баз данных, то задачу нужно сделать на sql.

Исходные таблицы:

words_1
абажур — 1
кинотеатр — 2
самолет — 3
человек — 4

words_2
кинотеатр — 15
музыка — 16
самолет — 17

Результирующая таблица на основе первой таблицы:

all_words_1
абажур — 1
кинотеатр — 2
музыка — 16
самолет — 3
человек — 4

Результирующая таблица на основе второй таблицы:

all_words_2
абажур — 1
кинотеатр — 15
музыка — 16
самолет — 17
человек — 4

Вторая задачка

Есть таблица defs с полями (def as TEXT, ref as INT), где def — это определение слова, ref — ссылка (числовой код) на само слово из какой-то другой таблицы (не важно). Нужно для каждого слова из словаря удалить все частичные дублирования определений, оставив только самые полные неповторяющиеся.

Начальные условия / трудности:

1. определения могут быть довольно длинными, несколько тысяч знаков;
2. количество записей в таблице — несколько миллионов, если как-то тупо «в лоб» сравнивать полнотекстовые записи друг с другом, то сервер нагнется;
3. если вы разработчик баз данных, то задачу нужно сделать на sql.

Исходная таблица:

refs
животное с большими ушами — 1
животное с большими ушами и длинным носом — 1
большое животное с длинным носом — 1
маленький пушистый зверек — 2
маленький пушистый зверек, который грызет орешки — 2

(Примечание, 1 — это слон, 2 — это белка.)

Результирующая таблица:

clear_refs
животное с большими ушами и длинным носом — 1
большое животное с длинным носом — 1
маленький пушистый зверек, который грызет орешки — 2

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