Мысли вслух

Задача

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

Решение

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

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

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

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

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

Задача

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

(далее...)

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

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

Задача

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

Решение

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

Задача

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

Решения

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

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

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

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

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