Задача, которую я перестал задавать на собеседованиях.

Почему перестал? Практически никто не находит правильное решение без подсказки. Просто решение – запросто, а вот правильное…

Задача: Дан массив 100 на 100 of byte. Нужно предложить алгоритм определения, есть ли в этом массиве повторяющиеся элементы. Алгоритм должен работать правильно и максимально быстро. Язык реализации значения не имеет.

Tagged ,

27 комментариев: Задача, которую я перестал задавать на собеседованиях.

  1. Dmitriy Torshin говорит:

    Если тип – байт, то ответ ВСЕГДА ЕСТЬ ПОВТОРЫ. То есть алгоритм такой: return true;
    :)
    И чего, реально никто не дает ответ?

    • Владис говорит:

      А сколько бит в байте?
      "В суперкомпьютерах, вследствие используемой адресации, один байт содержит 32 бита." (С) Википедия
      Так что ответ на задачку не так уж и прост.

      • Тоже может быть. Уточнения про суперкомпьютер не запрашивал вообще никто.

      • Dmitriy Torshin говорит:

        В задаче написано 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 лет.
      С подсказками типа "Сколько разных значений может храниться в байте?" – гораздо чаще.
      Возможно, особенность в том, что я задавал ее устно, а не письменно.

  2. Victor Ronin говорит:

    Задачка забавная. Но, правда не понятно, что она конкретно проверяет.

    • Умение вслушиваться в постановку задачи.

      Поведение в ситуации, когда начальство требует непонятного и нелогичного: \”как это есть что-то быстрее чем асмовский scan!??\”

  3. Вопрос off-topic? Часто подобные задачи встречаются в реальной промышленной практике? Вообще часто встречаются задачи с единственным ограничением "максимально быстро"?

    • Очень редко. Может, у кого-то иначе, но у меня обычно задачи типа "состыковать библиотеку А с библиотекой B в среде C" или "найди и исправь баг. Вот тебе мегабайт кода.". Проверить это на собеседовании за разумное время – я не знаю как. Поэтому задаю вопросы, которые позволяют косвенно что-то определить.

      • Это exactly тот ответ, который я ожидал услышать – предложенная задача относится к разряду спортивного/олимпиадного программирования, когда надо с жесткими ограничениями, наплевать как по качеству кода, сделать функциональность, проходящую 20-50 тестов. Это тоже очень интересные задачи, которые требуют незаурядных программистских способностей – но других! которые редко применяются в промышленной практике, если только программист не занимается разработкой принципиально новых алгоритмов…

        Мне кажется можно задавать практические задачи на собеседовании примерно так…

        Представьте себе, что библиотека делает то, то, и то… Если вам необходимо портировать эту библиотеку под такую-то среду/платформу на что бы Вы в первую очередь обратили внимание?

        Или так…

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

        • Приятно видеть конструктивную идею, спасибо. О применимости смогу сказать точно только после того как найду/увижу/напишу сам пример.
          "Есть код, который делает вот это и вот это… есть вот такая ошибка." – это отлично, это куда ближе к практической применимости. Хорошо бы вообще составить библиотеку примеров.

        • Спасибо, буду пробовать, как это реализовать на практике без больших вложений.

  4. kosiakk говорит:

    эволюция ответа:

    sort + compare -> XOR -> return true

  5. Костяяя говорит:

    Уффф
    я правильно решил

  6. avryabov говорит:

    Хм, не совсем очевидно условие задачи.

    Толи проверяется наличие совпаданий среди 10000 байт

    толи среди 100 строк по 100 байт.

    первое – очевидно: true.

    второе – сложнее.

    • Ни один из опрашиваемых такой вопрос не задал. Вопрос, кстати, вполне валидный. Но наличие совпадений таки среди 10000 байт.

  7. Яков говорит:

    Нужно сгенерировать массив и просто вывести его на экран, визуально определить повторы будет наиболее быстро и просто!

    • Яков говорит:

      Или в виду очевидности правильного решения задачи, просто генерировать массив и сразу выводить надпись СОВПАДЕНИЯ ЕСТЬ…это наиболее быстрый и адекватный способ решения.

    • Это новая идея, буду думать :)

  8. Ilyxa говорит:

    a1 xor a2 xor a3 xor …
    если получили где-то ноль – все, этот элемент повторяется

Leave a Reply

Your email address will not be published.