от ·14 комментариев

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

Вариант для 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;
}

Сравнивая производительность с предыдущими вариантами, надо обратить внимание на два момента:

  • фактически первый цикл — это вычисление длины строки, т.е. быстрее или медленнее это место, по сравнению со strlen, зависит от реализации strlen. Не знаю что конкретно там обычно написано, спекулировать не буду. Но думается, что что-то типа того и написано 🙂 С другой стороны, если вдруг окажется, что strlen работает быстрее чем просто поиск конца, в цикле, то никто не мешает нам написать конструкцию вида s1 = s+strlen (s). А дальше продолжить делать как тут.
  • Во время самого обмена значениями мы заметно сокращаем количество вычислений, т.к. вместо s+i и s+len-i, на каждом присваивании, мы все указатели вычисляем один раз, на проход.

На Java так красиво не получится. За отсутствием собственно указателей. Но близко к этому будет вариант с запуском навстречу двух счетчиков массива...

от ·7 комментариев

Задача

Дан массив нечётной длины. Известно, что все элементы массива, кроме одного, имеют пару. Необходимо найти элемент не имеющий пары.

Решение

Для нахождения ответа необходимо последовательно выполнить операцию XOR со всеми элементами массива. Результатом и будет непарный элемент.

Что проверяем

Достаточно простая задача на знание свойств бинарных операций.

от ·1 комментарий

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

Мне её давали на собеседовании в Exigen.

Задача

Реализовать интерфейс для банкомата. Устройство получает запросы через стандартный ввод и отправляет ответы в стандартный вывод. Все команды возвращают OK, в случае успеха, и ERROR, в случае ошибки.

Читать далее

от ·3 комментария

Задачка, которую используют на собеседования в Microsoft. Исключительно на сообразительность.

Задача

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

Как, за один поход в первую комнату, узнать какой выключатель включает какую лампочку?

Решение

Включаем первый выключатель и ждем некоторое время, затем выключаем. Включаем еще один выключатель и идём в первую комнату. Лампочка, включаемая вторым выключателем горит. Лампочка, включаемая первым выключателем, теплая.

NB: Очевидно, что задача применима только к лампочкам накаливания.

от ·13 комментариев

Задачка классическая и очень простая. Посему имеет смысл ее использовать только для совсем уж начинающих программистов.

Хотя меня как-то недавно тоже попросили ее решить 🙂

Задача

Развернуть строку символов. Как вариант, можно попросить развернуть массив.

Решение

Решений опять же много. Предлагаю все решения, где для разворота массива понадобился еще один массив считать незачётом. Можно это требование внести в условие, но, ИМХО, лучше посмотреть не предложит ли вдруг кандидат подобного решения и уже потом ввести это дополнительное ограничение. Единственным оправданием можно считать вопрос о том необходимо ли сохранить исходную строчку. Но это замечание не относится к 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);
}

от ·9 комментариев

Эта задачка применялась, как минимум, на собеседованиях в Sun Microsystems. Задачка миленькая, несложная, на сообразительность.

Задача

Отсортировать массив, состоящий только из единиц и двоек.

Решения

Решений, как у большинства задачек много. Приведем некоторые.

  1. Сложить все  элементы массива и вычесть из суммы длину массива. Результатом будет количество двоек в массиве. Далее массив заливается нужным количеством последовательных двоек и единиц.
  2. Посчитать количество единиц и двоек, пройдя по массиву. Далее опять заливаем массив нужным количеством двоек и единиц.
  3. Запускаем в цикле два счетчика, сближающихся с противоположных концов массива. Меняем местами соответствующие значения, по необходимости.

В третьем варианте что-то вроде:

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--;
        }
    }
}

Первый вариант представляется самым оптимальным, с точки зрения производительности: сравнений нет, все действия с массивом последовательные. В нём как раз проявляется сообразительность 🙂

Второй вариант похуже, но тоже ничего.

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

от ·Нет комментариев

Hibernate — достаточно популярный пакет для упрощения работы с базой данных. Упрощение достигается путем автоматизации мапинга объектов в базу данных. Таким образом программисту не надо писать SQL запросы, а можно напрямую сохранять и загружать экземпляры классов.

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

Задача

Есть две таблицы — People и Events. Между ними установлена связь «Многие ко многим», т.е. один человек может пойти на много событий и на одно событие пойдет много людей.

В Java, с использованием Hibernate, это будет реализовано следующим образом:

public class Man {
    private String name;
    private Vector events;
}
public class Event {
    private String name;
    private Vector people;
}

Вопросы

  1. Где проблема?
  2. Как бороться?
  3. Для всех ли случаев поможет lazy loading?

Ожидаемые ответы

  1. Проблема в том, что Hibernate будет загружать объект Man (или Event) целиком, включая все события, на которые пойдет человек. События, в свою очередь будут загружать людей, которые будут в них учавствовать. Таким образом, захотев посмотреть имя одного человека, мы имеем шанс загрузить все содержимое базы данных, с соответствующим влиянием на производительность приложения и сервера, объём памяти и загрузку каналов передачи.
  2. Правильный ответ на этот вопрос имеется в третьем вопросе и называется lazy loading. Включение этой опции позволяет загружать связи лишь при первом к ним обращении.
  3. К сожалению, даже lazy loading не решает проблему загрузки ненужных данных до конца. Например, мы хотим добавить одно новое событие к человеку и все остальные события, куда он собирается, нам безразличны. Но в момент добавления события мы обращаемся к вектору, т.е. тут же будут загружены все события. С этой бедой уже так просто не поборешься 🙁

Что проверяем

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

от ·13 комментариев

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

Задача

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

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;
        }
    }<И так далее>
}

Вопросы

  1. Что не нравится в коде и почему?
  2. Как изменить?

Ожидаемые ответы

  1. Должна не нравиться повторяемость кусков кода и их влияние на производительность. А так же, трудности с расширением подобной реализации на новые языки.
  2. Необходимо выделить общего предка или интерфейс, который будет определять список методов, для генератора каждого языка. Затем для каждого языка реализовать отдельный класс.

Что проверяем

Проверяем умение кандидата работать с ООП и способность видеть несовершенство чужого кода.