Иногда (ну, совсем иногда) меня спрашивают о том, какие мои любимые вопросы при проведении собеседований. Конечно раскрывать секреты нет смысла, но один занимательный пример хотел бы привести. Он демонстрирует три важных для программиста качества: осведомленность, логическое мышление и внимание к деталям. Пример касается доступа к элементам массива. Т.е. темы в которой начинающий программист обычно уверен на 100%.
Итак простая задача, например, на Java. Необходимо создать квадратный целочисленный массив большого размера (порядка 10000 х 10000) и инициализировать его элементы значениями равными сумме индексов. Легко говорит начинающий и пишет такой код:

int g[][] = new int[n][n];
for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
        g[i][j] = i + j; 
    }
}

Все правильно, все работает. Но более «умный» претендент заметит, что массив симметричный и мы напрасно вычисляем n² элементов. Достаточно перебирать только один треугольник, а значение элементов второго треугольника выставлять симметрично. Так мы экономим n(n-1)/2 сложений, что для больших n должно дать какой-то заметный эффект. Предположим, что этот товарищ даже обратил внимание на главную диагональ и написал разумный код вида:

int g[][] = new int[n][n];
for(int i = 0; i < n; i++) {
    g[i][i] = i + i;
    for(int j = 0; j < i; j++) {
        g[j][i] = g[i][j] = i + j; 
    } 
}

Чего мы добились? Вычислительных операций стало существенно меньше. А как со скоростью работы программы?
Зафиксируем время работы первого варианта. Получится что-то порядка 0,2 сек. Радостно потирая руки запускаем второй вариант… Но программа что-то не заканчивает работу… А, вот! Наконец!
Но что за странный результат? 8 секунд! Где же наша экономия?

В этот момент самое время предложить соискателю объяснить ситуацию и поискать способ все же ускорить инициализацию. А у Вас получится?

На всякий случай код программки с тестом времени лежит здесь. Поэкспериментируйте. Поставьте, например, n=512 или 256. Почему ситуация изменилась? Полагаете из-за степени двойки? Тогда проверьте 1024, 2048, 4096.

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