четверг, 10 февраля 2011 г.

Головоломка программиста

Алгоритм
Эту задачу вам могут предложить решить во время собеседования при устройстве на работу.
Дан байтовый массив 100 на 100. Предложите самый быстрый алгоритм, который бы определял есть ли в этом массиве совпадающие элементы.
update
Первым правильно ответил Вячеслав.
Ответ
В одном байте можно закодировать 256 значений, а в массиве их должно быть 10000, поэтому совпадения будут в любом случае. Программа не нужна.

Головоломка археолога.
Головоломка филателиста.
Головоломка нумизмата.

5 комментариев:

  1. Завести вспомогательный битовый массив длины 256, в который заносить, встречалось ли уже в основном массиве данное значение байта. Конкретно, если X[A[I,J]]=0, то X[A[I,J]]:=1 и перейти к следующему A[I,J]. Если же X[A[I,J]]=1, то в исходном массиве есть повторяющиеся элементы.

    ОтветитьУдалить
  2. Может быть будут еще варианты?

    ОтветитьУдалить
  3. Может, и будут, но этот вариант требует одного прохода по массиву, а меньше точно не получится.

    ОтветитьУдалить
  4. Хм)) Ну так как различных байтов 256, а в массиве 10000 элементов, то самый быстрый алгоритм проверки состоит из одной операции - return true :)

    ОтветитьУдалить
  5. Задачка конечно была с подвохом :) Совпадение будет в любом случае, проверять не нужно.

    ОтветитьУдалить