Сейчас, после длительного перерыва, активно пошел найм новых людей, уже в мою новую группу. И тут обнаружилась обратная сторона выкладывания задач в блог — некоторые кандидаты приходят уже «подготовленными» благо, при определенной сноровке, обнаружить мой блог несложно.
Но, хорошая часть, плохим кандидатам это не помогает... 🙂
Вчера, обсуждая с очередным кандидатом, на должность тестера в нашу команду, задачу про разворот строчки, мне на ум пришло новое забавное решение этой задачки.
Вариант для C/C++. Увлеченно используем арифметику указателей.
char* reverse(char *s) {
char *s0, *s1;
for (s1 = s; *(s1) != '\0'; s1++);
s1--;
for (s0 = s; s0 < s1; s0++ && s1--) {
char c = *(s0);
*(s0) = *(s1);
*(s1) = c;
}
return s;
}
Сравнивая производительность с предыдущими вариантами, надо обратить внимание на два момента:
На Java так красиво не получится. За отсутствием собственно указателей. Но близко к этому будет вариант с запуском навстречу двух счетчиков массива...
Дан массив нечётной длины. Известно, что все элементы массива, кроме одного, имеют пару. Необходимо найти элемент не имеющий пары.
Для нахождения ответа необходимо последовательно выполнить операцию XOR со всеми элементами массива. Результатом и будет непарный элемент.
Достаточно простая задача на знание свойств бинарных операций.
Решение этой задачи потребует большего количества программирования. Поэтому её имеет смысл давать интересным кандидатам, как домашнее задание. Если хотите посмотреть как человек реально пишет код. Кроме того, задача содержит внутри себя возможность для выбора решения из нескольких возможных. Посмотреть на то увидит ли кандидат разные возможности и чем будет руководствоваться при выборе, так же интересно.
Мне её давали на собеседовании в Exigen.
Реализовать интерфейс для банкомата. Устройство получает запросы через стандартный ввод и отправляет ответы в стандартный вывод. Все команды возвращают OK, в случае успеха, и ERROR, в случае ошибки.
Задачка, которую используют на собеседования в Microsoft. Исключительно на сообразительность.
В комнате есть три лампочки. В другой комнате есть три выключателя, включающие эти лампочки.
Как, за один поход в первую комнату, узнать какой выключатель включает какую лампочку?
Включаем первый выключатель и ждем некоторое время, затем выключаем. Включаем еще один выключатель и идём в первую комнату. Лампочка, включаемая вторым выключателем горит. Лампочка, включаемая первым выключателем, теплая.
NB: Очевидно, что задача применима только к лампочкам накаливания.
Задачка классическая и очень простая. Посему имеет смысл ее использовать только для совсем уж начинающих программистов.
Хотя меня как-то недавно тоже попросили ее решить 🙂
Развернуть строку символов. Как вариант, можно попросить развернуть массив.
Решений опять же много. Предлагаю все решения, где для разворота массива понадобился еще один массив считать незачётом. Можно это требование внести в условие, но, ИМХО, лучше посмотреть не предложит ли вдруг кандидат подобного решения и уже потом ввести это дополнительное ограничение. Единственным оправданием можно считать вопрос о том необходимо ли сохранить исходную строчку. Но это замечание не относится к Java, т.к. там придется выносить символы из строки в массив. И этот массив, очевидно, беречь нам ни к чему.
Краше всего на C/C++, где строчки — те же самые массивы. Будем использовать такую милую любому настоящему программисту на C арифметику указателей.
void reverseString(char *str)
{
int i = 0;
int len = strlen(str)-1;
for (; i <= len/2; i++)
{
char c = *(str+i);
*(str+i) = *(str+len-i);
*(str+len-i) = c;
}
}
На Java, как я говорил, выглядит менее элегантно, т.к. со строкой нельзя работать, как с массивом. И получатеся нечто вроде:
String reverseString(String s) {
char []str = s.toCharArray();
int len = str.length-1;
for (int i = 0; i <= len/2; i++) {
char c = str[i];
str[i] = str[len-i];
str[len-i] = c;
}
return new String(str);
}
Эта задачка применялась, как минимум, на собеседованиях в Sun Microsystems. Задачка миленькая, несложная, на сообразительность.
Отсортировать массив, состоящий только из единиц и двоек.
Решений, как у большинства задачек много. Приведем некоторые.
В третьем варианте что-то вроде:
public void sort12(int []array) {
int i = 0;
int j = array.length-1;
for (; i<j; i++) {
// Сортируем по возрастанию
if (array[i] == 2) {
for (; array[j] == 2; j--);
array[i] = 1;
array[j] = 2;
j--;
}
}
}
Первый вариант представляется самым оптимальным, с точки зрения производительности: сравнений нет, все действия с массивом последовательные. В нём как раз проявляется сообразительность 🙂
Второй вариант похуже, но тоже ничего.
Третий вариант видится близким ко второму, на достаточно небольших массивах (влезающих в кэш) и похуже на больших массивах.
Вот я не понимаю!
Почему подавляющее большинство HR'ов или нанимающих менеджеров не звонит и не пишет проинтервьюированному кандидату об отказе, если он не подошел?!
Что это? Гипертрофированное чувство собственной важности, корона на мозг давит или просто разгильдяйство?
Это ведь так просто! Сделал шаблон вида: «Здравствуйте. <бла-бла-бла> К сожалению, Вы нам не подошли. <бла-бла-бла>. С уважением, я» и отправляешь его. Отправка занимает секунд 10, приблизительно. Зато, если что-то изменится вы сможете спокойно к этому человеку подъехать снова и он не расскажет своим друзьям, что в компании XXX работают одни YYY. А вдруг у него друзья — мегакрутые специалисты, которые вам край как нужны?
Добрее надо быть к людям и они к вам потянутся!
Работа с людьми, создание и поддержание имиджа — это вообще кропотливая работа, состоящая из мелочей. И «сохранив» сегодня минуту, поправляя корону и не отправив человеку вежливый отказ, никогда не знаешь чем такая «экономия» аукнется завтра.
Hibernate — достаточно популярный пакет для упрощения работы с базой данных. Упрощение достигается путем автоматизации мапинга объектов в базу данных. Таким образом программисту не надо писать SQL запросы, а можно напрямую сохранять и загружать экземпляры классов.
Но, как обычно, в каждой бочке мёда найдётся своя ложка дёгтя. Суть одной из проблем в том, как хранятся и представляются связи между объектами.
Есть две таблицы — People и Events. Между ними установлена связь «Многие ко многим», т.е. один человек может пойти на много событий и на одно событие пойдет много людей.
В Java, с использованием Hibernate, это будет реализовано следующим образом:
public class Man {
private String name;
private Vector events;
}
public class Event {
private String name;
private Vector people;
}
Проверяем задумывается ли человек к чему ведут его действия на более низком уровне. И как у него это получается.
В последнее время, на собеседованиях с новыми кандидатами, мне нравится использовать задачку про генератор кода. Подсмотрел я эту задачку на сайте Яндекса.
Существует генератор кода на разных языках, реализованный следующим образом:
public class Generator {
private final int language;
// Language constants
public static final int JAVA = 1;
public static final int C = 2;
public static final int CPP = 3;
public Generator(int language) {
this.language = language;
}
public void generateIF() {
switch (language) {
case JAVA:<Код, генерирующий Java>
break;
case C:<Код, генерирующий C>
break;
case CPP:<Код, генерирующий C++>
break;
}
public void generateFOR() {
switch (language) {
case JAVA:<Код, генерирующий Java>
break;
case C:<Код, генерирующий C>
break;
case CPP:<Код, генерирующий C++>
break;
}
}<И так далее>
}
Проверяем умение кандидата работать с ООП и способность видеть несовершенство чужого кода.