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

Вариант для 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 так красиво не получится. За отсутствием собственно указателей. Но близко к этому будет вариант с запуском навстречу двух счетчиков массива...

Эта задачка применялась, как минимум, на собеседованиях в 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--;
        }
    }
}

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

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

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