Задачи с собеседований. Три адекватные задачки на «подумать»

Комментарии (15)

  • 1 июля 2017 в 21:52

    +2

    Дана упорядоченная последовательность чисел от 1 до N. Из нее удалили одно число, а оставшиеся перемешали. Найти удаленное число.

    В первой странная постановка задачи. Нигде не говорится, что оригинальная коллекция доступна.
    Вначале думаешь что доступна только измененная коллекция. И ни про какие суммы и вычитания не думаешь.

    • 1 июля 2017 в 21:59

      +1

      Кому как, я сразу про сумму подумал. Формулировка похожа на школьные задачки, там такого было полно.
    • 1 июля 2017 в 22:10

      +1

      Согласен с Вами.
  • 1 июля 2017 в 21:52

    +2

    Вторую задачу можно решить и другим способом.

    1. Наполнить пятилитровый кувшин водой
    2. Из пятилитрового кувшина наполнить трёхлитровый кувшин (в пятилитровом останется 2 литра воды)
    3. Вылить всю воду из трёхлитрового кувшина и перелить 2 литра воды из пятилитрового кувшина.
    4. Наполнить пятилитровый кувшин водой
    5. Наполнить заполненый на 2 литра трёхлитровый кувшин водой из полного пятилитрового кувшина (потребуется 1 литр воды)

    В итоге, в пятилитровом кувшине останется 4 литра воды.

    • 1 июля 2017 в 22:33

      +2

      Я точно так же решил и у нас с вами 6 действий, а не 8, как у автора :)
      • 1 июля 2017 в 22:43

        +1

        И я почему-то тоже сразу по такому пути пошел
  • 1 июля 2017 в 22:01

    +1

    В Задаче 1, если обе последовательности доступны, то, как вариант, можно решить линейно. Пробежаться по отсортированному списку и сравнивать с i-1 — ым элементом отсортированного. По идее это должно получиться оптимальнее решения предложенного автором.
    • 1 июля 2017 в 22:10

      +1

      Оптимальнее? Вы шутите? Т.е. сначала потратим время на сортировку, потом умножим на два занятую память, а потом проведем N сравнений, это оптимизация? Вместо того, чтобы взять n (n+1)/2 и вычесть из него все имеющиеся числа, и в остатке получить ответ.
      • 1 июля 2017 в 22:16

        +1

        Нет, оптимальнее того, что было предложено изначально как решение. Но и тут я не прав. Мне почему-то показалось, что у нас доступна отсортированная последовательность и хотел предложить как вариант.
    • 1 июля 2017 в 22:10

      +1

      Вы забываете что она ещё и пермешана так что не выйдет
    • 1 июля 2017 в 22:27

      +1

      где оптимальнее-то? в решении автора всего один цикл от 1 до n и единичные арифметические операции. У вас — вложенные циклы и n^2 операций сравнения. или я не понял что вы предлагаете.
      • 1 июля 2017 в 22:56

        +1

        В решени автора логарифм и линейный обход. А у меня только линейный. Но я ошибься, последовательность даётся только одна, неотсортированная, поэтому мой вариант отпадает.
  • 1 июля 2017 в 22:07

    +3

    Вторую задачу решает Брюс Виллис
  • 1 июля 2017 в 22:40

    +1

    Мне для первой задачи первым всплыло решение брутфорсом. Берём 1 — ищем в последовательности; Берём 2 — ищем; Берём 3 — ищем… берём 34234 — не находим.
  • 1 июля 2017 в 23:11

    0

    задачки очень простые и легко решаемы, особенно если прорешивали кучу подобных задач в школьные/университетские годы
    Мне пока самое сложное, что попалось — это задачка посчитать количесво вагонов в составе
    Условие: есть состав вагонов, закольцованный, можно переходить от вагона к вагону, в обоих направлениях. Скажем, что окна закрыты и видите только текущий вагон.
    В каждом вагоне определено понятие света — горит или нет
    У Вас, при заходе на очередной вагон, есть две возможности: посмотреть, горит ли в этом вагоне свет, и включить/выключить свет (без ограничений)
    Вопрос: как посчитать точное количесто вагонов с наименьшим количеством их посещений?

© Habrahabr.ru