Задачи на интервью

Лично я считаю, что задавать на интервью программиста около математические задачки или задачи типа «на сообразительность» – это бесполезно (а значит не нужно). Почему? Моя логика крайне проста. Какова цель интервью? Как можно точнее понять, подходит ли вам человек по нужным критериям. А что именно скажет вам о человеке факт того, что он решил или не решил математическо-логическую задачу? Поможет ли это оценить уровень знаний кандидата в матанализе или теории вероятности, алгебре и даже арифметике? Нет. Ибо подобные задачи нельзя классифицировать по сложности, а значит и по ожидаемому уровню знаний, необходимому для их решения.

Например, задача, часто применяемая (не мной) на интервью.

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

Задача для средней школы. Хотя лично мне будет без разницы, решит ее человек или нет. Ибо есть гораздо более конкретные вопросы и задачи, чтобы понять, что человек знает, умеет и любит делать. Обычно использование подобных задач призвано потешить самолюбие самого интервьюера типа «ну я то это решил в свое время!», но вот только не уточняется, за какое время.

В плане именно вопросов-задач, куда полезнее попросить написать небольшой код для обхода дерева (например, для поиска медианы в BST), или поиска кратчайшего пути в графе, или придумать на месте хеш-функцию для каких-то данных, или, например, спросить: до N какого порядка реально решать задачи с O(N^2), а O(N^3), а на кластере? и т.д. Подобные вопросы дают реальный выхлоп, который применим в жизни.

А уж если есть желание «проверить сообразительность», то куда полезнее вопросы на общее представления о мире вокруг и взаимосвязях в нем. Я как-то был реально озадачен, когда меня спросили «А сколько весит Боинг-747?». Я хоть и учился в МАИ, но точной цифры ни разу не знал. Но исходя и элементарных понятий и количестве людей в самолете, грузе, соотношении топлива и массы и т.д. – можно дать оценку, или что более важно, показать умение логически и реально мыслить.

Интервью – это не бенефис интервьюера. Это решение конкретной задачи поиска человека, максимально подходящего вашим требованиям (а неужели у кого-то в требованиях написано «должен уметь решать задачи школьной программы»? если да, это наем учителя средних классов, а не программиста).

Update: В комментариях подсказали полезную ссылку по теме.

Jason Fried, David Heinemeier Hansson, "Rework"

Книга от создателей компании 37 signals и Ruby on Rails о том, как можно вести малый бизнес в IT, не разрывая зад по 10-12 часов в день, а только с 9 до 5, и при этом достойно и даже очень зарабатывать.

Jason Fried, David Heinemeier Hansson, "Rework"



Довольно пафосная книга, состоящая из мини глав, похожих на посты в блоге (эта книга и родилась из блога), но многие ее посылы стоит усвоить. С ними легче и приятнее жить, и во многом ранее скучном и нудном может появиться вдруг смысл. Также книга может подтолкнуть в мир самостоятельной работы на самого себя, например, написание shareware.

Но одна глава мне очень понравилась. Про резюме и сопроводительные письма.

Приведу ее целиком как есть и собственный вольный перевод, если кому надо.

Resumes are ridiculous

We all know resumes are a joke. They're exaggerations. They're filled with "action verbs" that don't mean anything. They list job titles and responsibilities that are vaguely accurate at best. And there's no way to verify most of what's on there. The whole thing is a face.

Worst of all, they're too easy. Anyone can create a decent-enough resume. That's why half-assed applicants love them so much. They can shotgun out hundreds at a time to potential employers. It's another form of spam. They don't care about landing your job; they just care about landing any job.

If someone sends out a resume to three hundred companies, that's a huge red flag right there. There's no way that applicant has researched you. There's no way he knows what's different about your company.

If you hire based on this garbage, you're missing the point of what hiring is about. You want a specific candidate who cares specifically about your company, your products, your customers, and your job.

So how do you find these candidates? First step: Check the cover letter. In a cover letter, you get actual communication instead of a list of skills, verbs, and years of irrelevance. There's no way an applicant can churn out hundreds of personalized letters. That's why the cover letter is a much better test than a resume. You hear someone's actual voice and are able to recognize if it's in tune with you and your company.

Trust you gut reaction. If the first paragraph sucks, the second has to work that much harder. If there's no hook in the first three, it's unlikely there's a match there. On the other hand, if your gut is telling you there's a chance at a real match, then move on to the interview stage.

Перевод:

Резюме – это недоразумение.

Всем известно, что резюме – это ерунда. Одни преувеличения. В них полно «правильных» глаголов, которые ничего не значат. В них перечисляются должности и обязанности, которые в лучшем случае сомнительны. И нет никакой возможности проверить, что за всем этим стоит. Сплошной фарс.

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

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

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

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

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

От себя могу добавить. Всегда стоит писать cover letter, причем вдумчивые и персонализированные. В процессе их написания часто приходит понимание - "а хочу ли сам я там работать?"

Книгу после прочтения я продал назад через Амазон.

Bernard Girard, "The Google Way"

Было интересно почитать про историю Google, посему купил вот эту книгу.

Bernard Girard, The Google Way



Не могу сказать, что мне особо понравилось, хоть фактов в книге предостачно: и про самое начало, и про выход на IPO (работая сейчас в сфере finance, знаю, как обычно инвестиционные банкиры наживаются на процедуре IPO, но Гугл их сильно в этом плане разочаровал, не дав им кусок своего пирога), и про правило 20%, и про систему peer review, и про наличие технической иерархии и про многое другое.

Разок прочитать можно, но не более того. Книгу продал назад через Amazon Market Place.

Задача про гномов

Товарищ рассказал интересную задачку и был очень удивлен, что я ее не слышал.

Поймал людоед несколько гномов (количество в задаче не задается), и сказал, что завтра он всех выстроит в колонну один за другим и оденет всем на головы либо черную, либо белую шапку. Гномы будут стоять так, что каждый будет видеть шапки только тех, кто впереди (последний видит всех, кроме себя, а первый – никого). Свою собственную шапку гномы не видят. Количество черных и белых шапок произвольное (хоть все белые, хоть все черные). Далее людоед, начиная с последнего, будет каждого спрашивать, какая шапка у него на голове. Гном может ответить только одним из двух слов «черная» или «белая». Если ответ неверный, но гном съедается, иначе переходят к следующему. В процессе поедания все пока еще живые гномы слышат, что проиходит сзади, то есть хоть они и не видят товарищей сзади, но слышат – когда кого съели, а кого нет, и также их ответы.

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

Вопрос: что за стратегию придумали гномы?

Задача имеет очень красивое решение, имеющее прямое отношение к компьютерной науке.

Ответ будет позже, если кто вдруг не догадается.

parsetInt() в JavaScript'e

Напоролся на совершенно замечательное поведение в parseInt()'e:

Я думал, что код ниже должен давать мне числа от 0 до 9:

<script>
var n = [ '00', '01', '02', '03', '04', '05', '06', '07', '08', '09' ];
for (var i = 0; i < n.length; ++i)
  document.writeln(parseInt(n[i]));
</script>

Но выводится:

0 1 2 3 4 5 6 7 0 0

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

Правильно надо писать так:

<script>
var n = [ '00', '01', '02', '03', '04', '05', '06', '07', '08', '09' ];
for (var i = 0; i < n.length; ++i)
  document.writeln(parseInt(n[i], 10));
</script>

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

Общий виртуальный десктоп

В крупных конторах с множеством UNIX-программистов, работающих в основном через telnet/ssh/xterm, разумно сделать общий NFS-раздел, который виден всем, и также монтируется сразу на много машин. Во-первых, все имеют доступ практически ко всему в development пространстве, и во-вторых, содержимое моего home каталога всегда одно и то же на всех машинах (не надо вручную копировать файлы с машины на машину).

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

Так вот, только родилась мысль -- а что, если все разработчики будут также "шарить" общий огро-о-о-мный виртуальный десктоп? Захотел что-то передать/показать коллеге -- просто перебросил окно в его "зону видимости".

Идея, конечно, утопичная, но красивая.

Веселые перестановки. Решение (сортировка перестановками соседних элементов)

Итак, мое решение вопроса о приведении одной последовательности к другой, когда можно только переставлять два элемента.

Нас просят привести одну последовательность (исходную) к другой (целевой). То есть логично предположить, что одна последовательность в нужном порядке (целевая), а вторая (исходная) - нет. Так надо просто отсортировать исходную последовательность "в целевую".

Так как целевая последовательность по условию не обязательно отсортированная, то при сортировке "к ней" нельзя просто сравнивать элементы исходной последовательности на больше/меньше, так как в этом случае мы получим на выходе сортировку по правилам системы исчисления. В нашем случае надо принять, что целевая последовательность и есть эталонный отсортированный алфавит, и он задает правила сортировки. При сравнении значений из этого алфавита надо понять, в какой позиции алфавита находится значение и использовать его индекс как ключ сортировки (функция less()).

Теперь, а какой алгоритм сортировки использовать, чтобы для перемещения элементов использовать только обмен соседних элементов (функция swap())? Подходит сортировка вставками, когда на каждом шаге неотсортированный элемент последовательно "пропихивается" вниз к отсортированным. Тут как раз можно обойтись только обменом соседних элементов. Сама функция insertion_sort() является универальной и не зависит от компаратора is_less().

#include <stdlib.h>
#include <stdio.h>

void swap(int* a, int i) {
  int t = a[i];
  a[i] = a[i + 1];
  a[i + 1] = t;
}

#define N 8

const int etalon[] = { 1, 5, 7, 4, 2, 9, 8, 6 };
int from[N] = { 8, 1, 4, 2, 5, 6, 9, 7 };

void insertion_sort(int* a, int n, int (*is_less)(int, int)) {
  int i, j;
  for (i = 1; i < n; ++i) 
    for (j = i - 1; j >= 0 && is_less(a[j + 1], a[j]); j--)
      swap(a, j);
}

void print_array(const char* title, const int* a, int n) {
  int i;
  printf("%9s: ", title);
  for (i = 0; i < n; ++i)
    printf("%d ", a[i]);
  printf("\n");
}

int less(int a, int b) {
  int ia = -1, ib = -1;
  int i;
  for (i = 0; i < N; ++i) {
    if (etalon[i] == a) ia = i;
    if (etalon[i] == b) ib = i;
    if (ia >= 0 && ib >= 0) break;
  }
  return ia < ib;
}

int main() {
  int i, j;

  print_array("Original", from, N);
  insertion_sort(from, N, less);
  print_array("Converted", from, N);
  print_array("Etalon", etalon, N);

  return 0;
}

Запускаем:

 Original: 8 1 4 2 5 6 9 7 
Converted: 1 5 7 4 2 9 8 6 
   Etalon: 1 5 7 4 2 9 8 6 

Вроде работает.

Теперь что со сложностью. Принято считать, что сортировка вставками - это O(N^2) для худшего случая. Так как для сравнения элементов нам приходится искать линейно по эталонной последовательности на каждом шаге, то это еще O(N). В этоге: O(N^3).

Как вариант ускорения, можно изначально сделать отсортированную по значениям копию эталонной последовательности, и хранить не только значение, но его индекс. В этом случае поиск элемента будет уже занимать не O(N), а O(log(N)), и общая сложность будет O(log(N)*N^2).

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

Указание на эти два факта лично я счел бы на однозначно достаточный ответ.