Почему перестал? Практически никто не находит правильное решение без подсказки. Просто решение – запросто, а вот правильное…
Задача: Дан массив 100 на 100 of byte. Нужно предложить алгоритм определения, есть ли в этом массиве повторяющиеся элементы. Алгоритм должен работать правильно и максимально быстро. Язык реализации значения не имеет.
Если тип – байт, то ответ ВСЕГДА ЕСТЬ ПОВТОРЫ. То есть алгоритм такой: return true;
:)
И чего, реально никто не дает ответ?
А сколько бит в байте?
"В суперкомпьютерах, вследствие используемой адресации, один байт содержит 32 бита." (С) Википедия
Так что ответ на задачку не так уж и прост.
Тоже может быть. Уточнения про суперкомпьютер не запрашивал вообще никто.
В задаче написано byte, что в 99,9999% систем означает 8 бит.
Если рассматривать байт равный 32 битам, то решение было бы модификацией однопроходного алгоритма сортировки со вспомогательным массивом, но это, скорее всего, большинство опрашиваемых и предлагали.
Владимир?
Да, решения с сортировкой и доп. массивом предлагают часто.
На счет 99,9999% я бы посомневался. Потому что есть еще и разнообразные однокристалки, микроконтроллеры и прочее.
Смотрите, например, http://en.wikipedia.org/wiki/Byte
Там упоминается возможный размер байта от 16 до 40 бит именно касательно микроконтроллеров и других специализированных процессоров.
Кстати, примерно каждый второй не готов назвать формулу вычисления максимального значения Int32.
А вопрос "хоть приблизительно, сколько разных(!) значений может быть в double" вызвал вообще суровые споры :)
Int32.MaxValue – Представляет наибольшее возможное значение типа Int32. Это поле является константой. http://msdn.microsoft.com/ru-ru/library/system.in…
Это "жжжжж" не спроста. Видно и тут нет универсального ответа без ссылки на железную архитектуру. :-)
Кажись, вообще существует только один универсальный ответ на вопросы жизни, вселенной, и всего такого :)
А формулу 2^n знать все-таки полезно.
Однозначно. Если не можешь показать, что ты знаешь ответ на вопрос, хотя бы умудрись показать, что ты видишь в вопросе что-то большее, чем вопрошающий :-)
Крайне редко, из ответивших с ходу могу вспомнить только двух человек за 12 лет.
С подсказками типа "Сколько разных значений может храниться в байте?" – гораздо чаще.
Возможно, особенность в том, что я задавал ее устно, а не письменно.
Задачка забавная. Но, правда не понятно, что она конкретно проверяет.
Умение вслушиваться в постановку задачи.
Поведение в ситуации, когда начальство требует непонятного и нелогичного: \”как это есть что-то быстрее чем асмовский scan!??\”
Вопрос off-topic? Часто подобные задачи встречаются в реальной промышленной практике? Вообще часто встречаются задачи с единственным ограничением "максимально быстро"?
Очень редко. Может, у кого-то иначе, но у меня обычно задачи типа "состыковать библиотеку А с библиотекой B в среде C" или "найди и исправь баг. Вот тебе мегабайт кода.". Проверить это на собеседовании за разумное время – я не знаю как. Поэтому задаю вопросы, которые позволяют косвенно что-то определить.
Это exactly тот ответ, который я ожидал услышать – предложенная задача относится к разряду спортивного/олимпиадного программирования, когда надо с жесткими ограничениями, наплевать как по качеству кода, сделать функциональность, проходящую 20-50 тестов. Это тоже очень интересные задачи, которые требуют незаурядных программистских способностей – но других! которые редко применяются в промышленной практике, если только программист не занимается разработкой принципиально новых алгоритмов…
Мне кажется можно задавать практические задачи на собеседовании примерно так…
Представьте себе, что библиотека делает то, то, и то… Если вам необходимо портировать эту библиотеку под такую-то среду/платформу на что бы Вы в первую очередь обратили внимание?
Или так…
Есть код, который делает вот это и вот это… есть вот такая ошибка. В каком направлении, вы бы начали искать?
Приятно видеть конструктивную идею, спасибо. О применимости смогу сказать точно только после того как найду/увижу/напишу сам пример.
"Есть код, который делает вот это и вот это… есть вот такая ошибка." – это отлично, это куда ближе к практической применимости. Хорошо бы вообще составить библиотеку примеров.
Спасибо, буду пробовать, как это реализовать на практике без больших вложений.
эволюция ответа:
sort + compare -> XOR -> return true
Уффф
я правильно решил
Хм, не совсем очевидно условие задачи.
Толи проверяется наличие совпаданий среди 10000 байт
толи среди 100 строк по 100 байт.
первое – очевидно: true.
второе – сложнее.
Ни один из опрашиваемых такой вопрос не задал. Вопрос, кстати, вполне валидный. Но наличие совпадений таки среди 10000 байт.
Нужно сгенерировать массив и просто вывести его на экран, визуально определить повторы будет наиболее быстро и просто!
Или в виду очевидности правильного решения задачи, просто генерировать массив и сразу выводить надпись СОВПАДЕНИЯ ЕСТЬ…это наиболее быстрый и адекватный способ решения.
Это новая идея, буду думать :)
a1 xor a2 xor a3 xor …
если получили где-то ноль – все, этот элемент повторяется
(1 xor 2 xor 1) == 2 ?