03.02.2018 11:29
reci 86 9300 Источник
Мы подготовили для вас новый сет задач и вопросов, задаваемых на собеседованиях в ведущих IT-компаниях.

КДПВ

В подборку вошли задачи для соискателей в Amazon. Вопросы задаются, в том числе и логистические, только не с дронами, а с верблюдами :)
Мы постарались подобрать задачи различного уровня сложости, но, в любом случае, их решение будет хорошим упражнением для мозга.

Вопросы


  1. Transport the bananas
    A person has 3000 bananas and a camel. The person wants to transport maximum number of bananas to a destination which is 1000 KMs away, using only the camel as a mode of transportation. The camel cannot carry more than 1000 bananas at a time and eats a banana every km it travels. What is the maximum number of bananas that can be transferred to the destination using only camel (no other mode of transportation is allowed).
    Перевод
    У человека есть 3000 бананов и верблюд. Он хочет отвезти максимум бананов в пункт назначения, находящийся в 1000 км, используя верблюда в качестве транспорта. Верблюд не может перевозить более 1000 бананов за раз и ест по одному банану за каждый километр пути.
    Какое наибольшее количество бананов удастся доставить таким способом (другие способы перевозки не разрешены)?
  2. Measure forty-five minutes using wires
    How do we measure forty-five minutes using two identical wires, each of which takes an hour to burn. We have matchsticks with us. The wires burn non-uniformly. So, for example, the two halves of a wire might burn in 10 minute and 50 minutes respectively.
    Перевод
    Имеется 2 идентичных шнура, каждый из которых сгорает за час. Спички у нас с собой, шнуры сгорают неравномерно. Так, например, половина может сгореть за 10 минут и оставшаяся половина за 50 минут. Как, используя эти шнуры, нам отсчитать 45 минут?

Задачи


  1. Elephants lifetime
    Given life time of different elephants. Find the period when maximum number of elephants were alive.

    Input: [2005, 2010], [2006, 2015], [2002, 2007]
    Output: [2006, 2007] .
    Перевод
    Дано время жизни нескольких слонов. Найти период, в который жило наибольшее количество слонов.

    Вход: [2005, 2010], [2006, 2015], [2002, 2007]
    Выход: [2006, 2007] .

Pythagorean Triplet
Given an array of integers, write a function that returns True if there is a triplet (a, b, c) that satisfies a^2 + b^2 = c^2.

Example:

Input: arr[] = {3, 1, 4, 6, 5}
Output: True
There is a Pythagorean triplet (3, 4, 5).

Input: arr[] = {10, 4, 6, 12, 5}
Output: False
There is no Pythagorean triplet.
Перевод
Дан массив целых чисел, нужно написать функцию, возвращающую True, если в массиве содержится тройка чисел (a, b, c), так, что a^2 + b^2 = c^2

Пример:

Вход: arr[] = {3, 1, 4, 6, 5}
Выход: True
Пифагорова тройка — (3, 4, 5).

Вход: arr[] = {10, 4, 6, 12, 5}
Выход: False
Пифагоровской тройки в массиве нет.

Anti-clockwise rotated array
Consider an array of distinct integers sorted in increasing order. The array has been rotated (anti-clockwise) k number of times. Given such an array, find the value of k.

Array rotation: 

        *                     *
        0                     1                      
    5        1    =>      0        2
    4        2            5        3
        3                     4

Examples:

Input: arr[] = {15, 18, 2, 3, 6, 12}
Output: 4
Initial array must be {2, 3, 6, 12, 15. 18}. We get the given array after rotating the initial array twice.

Input: arr[] = {7, 9, 11, 12, 5}
Output: 1

Input: arr[] = {7, 9, 11, 12, 15};
Output: 0

Перевод
Предположим, имеется массив целых чисел, отсортированный по возрастанию. Массив был «повернут» против часовой стрелки k раз. Найти k.

Поворот массива означает:

        *                     *
        0                     1                      
    5        1    =>      0        2
    4        2            5        3
        3                     4

Примеры:

Вход: arr[] = {15, 18, 2, 3, 6, 12}
Выход: 4
Исходны массив должен быть — {2, 3, 6, 12, 15. 18}. Мы получим входной массив, если повернем исходный 2 раза.

Вход: arr[] = {7, 9, 11, 12, 5}
Выход: 1

Вход: arr[] = {7, 9, 11, 12, 15};
Выход: 0

Ответы будут даны в течение следующей недели — успейте решить. Удачи!

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


  1. Andy_U
    03.02.2018 16:01
    #10651362
    +1

    Второй вопрос простой:

    1) Сначала зажигаем первую веревку с обоих концов, а вторую с одного.
    2) Когда первая сгорит (а это произойдет ровно через 30 минут!) зажигаем вторую веревку с другого конца. Как догорит, так и 45 минут.


    1. DaneSoul
      04.02.2018 11:39
      #10652018

      Есть другой способ
      Зажигаем первую с двух сторон — она сгорит за 30 минут, затем зажигаем вторую с двух сторон и из центра, т.о. огонь будет идти в 4-х направлениях и веревка сгорит за 15 минут, а в сумме как раз 45 искомых.


      1. Rsa97
        04.02.2018 11:43
        #10652024
        +1

        Не сработает. Поджигание верёвки одновременно с концов и посередине не гарантирует, что каждая половина сгорит за одно и то же время. Первая половина может сгореть за 5 минут, а вторая за 25.


        1. DaneSoul
          04.02.2018 12:07
          #10652062

          Да, согласен, не предусмотрел этот момент


      1. kemply
        05.02.2018 03:07
        #10652816

        Есть ещё другой способ:
        При условии, что обе веревки имеют неравномерные сгорания одинаково, то поджечь первую с обеих сторон, а вторую с обеих сторон и с точно того же места, где догорела первая. Так 30+15=45


        1. Andy_U
          05.02.2018 13:31
          #10653538

          В комменарии автора (где-то ниже ) написано, что концы неотличимы, но, по условиям задачи, веревки одинаковые.

          Но вот чего нет в условии, так это утверждения, что локальная скорость горения веревки не зависит от направления горения. Ну, это кажется очевидным, однако, если таки зависит, то нет никакой гарантии, что веревка, подожженная с двух концов, сгорит за 30 минут.

          Вот тут бы и помогла идентификация концов — 30 мин можно было бы померять положив веревки «навстречу» друг други и зажечь их опять же навстречу друг другу. Как точки горения совпадут так и 30 мин. Потом опять их сдвигаем конец к началу и опять ждем совпадения точек горения. Но вот если концы таки неотличимы, я пока не понимаю, что делать.


  1. IgnisDeus
    03.02.2018 16:14
    #10651380

    3000 бананов
    В итоге получится перевезти 500 бананов, скормить верблюду 2400 и 100 останется в пустыне, если первые 500км каждые 100км провозить все что есть, возвращаясь назад.
    0. 3000 бананов
    100км. 2500 бананов (взял 1000 бананов с отметки 0 привез 900 бананов, взял 100 бананов, поехал на отметку 0, повторил)
    200км. 2000 бананов
    300км. 1700 бананов
    400км. 1400 бананов
    500км. 1100 бананов
    Далее берем 1000 бананов и едем в конечный пункт
    600км. 900 бананов
    700км. 800 бананов
    800км. 700 бананов
    900км. 600 бананов
    1000км. 500 бананов


    1. Andy_U
      03.02.2018 16:33
      #10651398

      А почему это максимум?


    1. Andy_U
      03.02.2018 17:10
      #10651436
      +1

      Ага, можно больше довезти таким способом, а именно:

      1) Тащим бананы на отметку 200 км за 5 ходок, где окажется 3000-200*5=2000 бананов.
      2) Тащим бананы далее на 333 км за 3 ходки до отметки 533 км, где окажется 1001 банан.
      3) Тащим 1000 бананов до конца. Дистанция 467 км. Итого довозим 1000-467 = 533.

      Но я все равно не уверен, что и это — максимум.


      1. zarfaz
        03.02.2018 20:47
        #10651552

        Теоретический максимум - 666 бананов.
        Нам нужно максимизировать удельную стоимость перевозки на один километр.Очевидно, за 2 ходки перевезти не получиться, поэтому рассчитаем решение пренебрегая (пока) краевым условием когда верблюду не нужно возвращаться в последний раз: будем считать, что каждый раз верблюду нужно возвращаться. Допустим х — это один банан (он же километр).

        На х километров возможно перевезти только (1000-2х) бананов, при условии что нужно возвращаться. Стоимость перевозки при этом окажется 2х бананов, которые будут съедены.
        Целевая функция оптимизации — это количество полезной нагрузки делить на количество съеденных бананов.
        f(x)= (1000-2x)/2x -> max
        Берем производную, приравниваем к нулю и находим х

        Это — обычная гипербола, которая стремиться к бесконечности около нуля. Ответ — максимальная производительность при минимальном шаге. Проверим численно:
        Едем на 500 километров — получаем 0 полезной нагрузки и 1000 бананов съедено
        Едем на 1 километр — получаем 998 полезной нагрузки и 2 съеденных банана.
        Получается, все итерационные циклы выгоднее всего делать с минимальным шагом. Допустим, наш минимальный шаг будет 1 (в случае дробного шага результат будет почти таким же — но об этом в конце)

        Дальше — excel, хотя сейчас я понимаю, что можно и мысленно было:
        Этап 1 — перевозим все доступные бананы за 3 ходки на 1 километр за каждый шаг.
        Этап 1. Шаг 1. Перевозим все бананы на 1-ый километр. Расход — 6 бананов за три ходки. Итог — доступно 2994, все находятся на 1-ом километре.
        Этап 1. Шаг 2. Перевозим все доступные бананы с 1-ого на 2-ой километр. Расход — 6 бананов. Итог — доступно 2988, все находятся на 2-ом километре.
        …

        Этап 2. На 167 километре у нас будет доступно 1998 бананов. С этого момента, стоимость перевозки всех бананов на следующий километр будет 4 банана.
        Этап 2. Шаг 1. Перевозим все бананы с 167-ого на 168-ой километр. Расход — 4 банана, итог — доступно 1986 бананов.
        …

        Этап 3. На 666 километре у нас остается 1000 бананов. С этого момента вся модель перестает работать, потому что нам больше не нужно возвращаться. Это то самое краевое условие, которым мы пренебрегли. Берем все бананы и едем до конца.
        Расход — 334 банана, итог — 666 бананов на 1000-ом километре.

        Если бы бананы были бесконечно делимы, то с почти нулевым шагом мы бы перевезли 2/3 всех бананов как предел ряда. Точно ряд сейчас не сформулирую, но думаю ход мысли понятен.


        1. GrigorGri
          03.02.2018 21:17
          #10651574

          "На 666 километре у нас остается 1000 бананов". Почему? На 167 было было 1986. Перевоз на 1км занимает 4 банана. Тогда 986/4=246 км, то есть 1к можно доставить только до 167+246=413км


          1. zarfaz
            03.02.2018 21:46
            #10651600

            Ваша правда, спасибо. В таком случае, ответ 533, который уже был озвучен ранее. Смысл целевой функции сохраняется, получается просто теоретическое обоснование максимального результата


        1. Andy_U
          03.02.2018 21:44
          #10651598

          Этап 1. Шаг 1. Перевозим все бананы на 1-ый километр. Расход — 6 бананов за три ходки. Итог — доступно 2994, все находятся на 1-ом километре.


          Ну, на этом шаге Вы посчитали один лишний банан, потому что, чтобы увезти все 3000 бананов на 1 км верблюд пройдет 5 км — 3 раза туда и 2 обратно.

          Этап 2. На 167 километре у нас будет доступно 1998 бананов. С этого момента, стоимость перевозки всех бананов на следующий километр будет 4 банана.


          На 200-м километре останется 2000 бананов, далее километр будет стоить 3 банана.

          Этап 3. На 666 километре у нас остается 1000 бананов.


          Это как??? 10001 банан останется на отметке 200+333=533 км. Даже если начинать с 200 км…


          1. Suntechnic
            05.02.2018 10:26
            #10653124

            Итого 534/533 банана в зависимости от алгоритма верблюда. Кстати везти можно не по километру, а до точки слома модели. Т.е. первых три перехода в точку 200км, тогда от первой и второй 1000 остается 600, а от третьей 800.
            Далее два перехода в точку 533 км.
            Остается вопрос — нет ли точки где выгодно выбросить часть бананов. Точнее не возвращаться за ними. Имеется ввиду что мы изменим длины переходов как-то таким образом, что при последнем переходе в целевую точку, на предыдущей точке останется бананов столько же сколько стоит доставка из нее. Можно подумать что выбрав такие точки мы можем увеличить полезную загрузку.
            Предположим что есть такой участок в пределах первых 200км и в точку 200км можно прийти не 3, а 2 раза. Но придя два раза, при любой загрузке невозможно получить более 1998 бананов, а у нас уже есть решение которое позволяет получить в этой точке 2000 бананов, что больше. Аналогичные рассуждения можно привести и для точки 533 км. И того максимум это 533 или 534 банана в зависимости от алгоритма верблюда, так как в точке 533 км становится важным ест ли верблюд свой банан авансом.


      1. GrigorGri
        03.02.2018 21:51
        #10651604

        Тут можно было получить 534 банана: не обязательно давать верблюду банан после того как он достиг километра 1000


        1. Andy_U
          03.02.2018 21:53
          #10651608

          Это зависит, от от того, как устроен верблюд: «утром деньги, вечером стулья» или «утром стулья — вечером деньги» :)


          1. GrigorGri
            03.02.2018 22:12
            #10651626

            Если он сперва ест а потом идет, то пре переходе из шага 2 в 3 сьест банан номер 1001 на старте и потратит 466 на остаток пути


            1. Andy_U
              04.02.2018 11:48
              #10652032

              Он еще может только на половине километра его есть. Или непрерывно есть. А по условиям задачи бананы могут ехать только на верблюде. Так что, как повезет.


      1. inpost
        04.02.2018 10:51
        #10651968

        Так-то
        1) 200 км за 5 ходок = 200*5*2, верблюду надо возвращаться и его надо тоже кормить. За 200км мы теряем 2000 бананов, а не 1000.


        1. Andy_U
          04.02.2018 11:44
          #10652026

          Моя «ходка» — это в одну сторону, Т.е верблюду надо пройти 200*5=1000 км и сожрет он при этом именно что 1000 бананов.


          1. inpost
            04.02.2018 19:56
            #10652502

            Согласно задаче у нас есть только 1 верблюд. Чтобы вторую ходку сделать, ему надо вернуться. Это стоит учитывать.


            1. Andy_U
              04.02.2018 19:59
              #10652508

              Все учтено.

              Еще раз, туда 200 км, обратно 200 км, туда 200 км, обратно 200 км, туда 200 км. Итого 5 раз по 200 км. Что не так то?


    1. ADR
      03.02.2018 17:38
      #10651458
      +1

      Если идти по одному километру то получається 533 банана.


      1. Andy_U
        03.02.2018 17:51
        #10651466

        Не понимаю, как так получается, потому что при таком подходе верблюд значительную часть времени будет недогруженным (как решении IgnisDeus), а жрать все равно по банану на километр, в то время как у меня получились те же 533 банана при 100% загрузке верблюда.

        Хотя результаты моего первого шага совпадают с результатом 2-х первых шагов решения IgnisDeus, где верблюд тоже в конце второго шага тащил лишь 500 бананов.


        1. m03r
          03.02.2018 19:54
          #10651516

          А верблюд потребляет бананы только тогда, когда ходит нагруженный? Когда ходит пустой — не потребляет?


          1. Andy_U
            03.02.2018 21:32
            #10651584

            По условиям задачи — всегда. 1 банан на 1 километр.


        1. An_private
          03.02.2018 22:22
          #10651638

          А неважно какой именно отрезок проходить. Важно то, что пока бананов больше 2000 расход 5 бананов на километр. Больше 1000 — 3 банана на километр.
          Следовательно, на первой тысяче бананов верблюд пройдёт 1000/5= 200 км. На второй тысяче — 1000/3= 333.(3) километров. После чего у него останется идти 1000 — 533 = 467 км, на которые он потратит 467 бананов. Значит останется 533 банана. Всё. По сколько именно идти в пределах этих километров значения не имеет.


          1. apapacy
            04.02.2018 02:09
            #10651838

            Этот вариант мне каженся самым простым решением. Если задасться вопросом об оптимальном расстоянии то тут важны точки излома. То есть првое перемещение должно быть 0 < X <=200. Если например перенести на 201 км. то мы потеряем на нем два банана (5 — 3) т.к. ходок на последнем километре будет 5 а могло уже быть три.


        1. andrey6498
          03.02.2018 22:22
          #10651640

          А если взять эталонную дистанцию в районе 300-400кма затем каждую следующую часть переносить на несколько меньшую дистанцию.? Верблюд все равно будет есть в процессе а значит можно будет попутно добирать бананы с чекпоинтов.


        1. sadPacman
          03.02.2018 22:22
          #10651642

          В вашем варианте верблюд будет по дороге съедать свой груз. Полностью он загружен только в начале каждого этапа, а, например, в точке 100км на первом этапе он будет нести 900 бананов.


        1. Rsa97
          04.02.2018 10:51
          #10651970

          Всё просто. Первые 200 км верблюду нужно пройти пять раз, независимо от того, будет он делать ходки по 200 или по одному километру. Следующие 333? километра необходимо пройти три раза, и остаток пути — один раз. Таким образом, пройденное расстояние будет 200?5 + 333??3 + (1000 — 200 — 333?) = 2466? километра. Если за последние ? км верблюду банан не дать, то в конечный пункт прибудет 534 банана.


    1. m03r
      03.02.2018 20:05
      #10651520
      -1

      Как донести 750 бананов
      (считаем, что верблюд не потребляет бананы, не будучи нагруженным)

      1. Берём 1000 бананов, каждый километр один банан съедаем, один кладём. На 500 км поворачиваем назад
      2. Берём 1000 бананов, проходим 500 км (остаётся 500 бананов), раскладываем бананы ещё на 250 бананов ещё на 250 км.
      3. Берём последнюю тысячу бананов, первые 750 км питаемся разложенными бананами, последние 250 съедаем, 750 доносим.


      1. m03r
        03.02.2018 20:23
        #10651536

        И даже 833 ?
        Опять таки, по аналогии с другими решениями — пустой верблюд бананов не потребляет

        1. Идём 333 ? км, оставляем каждый километр по два банана (на отметке 333 ? оставляем две трети банана, треть съедаем), идём назад пустые
        2. Проходим 333 ? на оставленных бананах (один остаётся лежать), далее раскладываем ещё на 500 км вперёд по одному банану на километр
        3. Проходим 833 ? на оставленных бананах, съедаем 166 ? банана на оставшиеся километры, доносим 833 ?


      1. GrigorGri
        03.02.2018 20:30
        #10651540

        С таким предположением можно и больше: двигаемся по 1 км до 333км. Получаем 2001 банан. Выкидываем 1. Движемся на км 833 (сейчас км стоит 2 банана). Получаем 1000. Движемся оставшиеся 167км. Доставляем 834 банана (последний банан верблюду не даем т.к. мы уже у цели).


    1. ikakus
      03.02.2018 22:22
      #10651644

      А на возвращение верблюд не тратит бананы?


    1. ITMatika
      05.02.2018 14:20
      #10653648

      533/534 банана
      Пока бананов больше 2000, расход идёт 5 бананов/км. Проходим 200 км.
      Пока бананов больше 1000, расход идёт 3 банана/км. Проходим ещё 333 км.
      Итого на точке 533 км остаётся 1001 банан и остаётся пройти 467 км.


  1. Andy_U
    03.02.2018 16:25
    #10651386
    +2

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

    А вот если год смерти одного слона совпадает с годом рождения другого слона, тут непонятно, был ли момент времени, что оба слона были живы?


    1. apapacy
      04.02.2018 14:35
      #10652202

      Задача не до конца определена как мне кажется. Но есть пример который показывает как поступать с границами периодов. Поэтому я бы решал так. В сначала пришёлся бы по всем слонам и создал бы массив год -> число слонов. Потом нашёл бы в этом массиве максимум возможно не один и представил уже в виде интервалов. Если быть уже совсем строгим то год рождения и смерти нужно исключать т.к. мы показывает в интервале период о 0101 00:00:00 и рождениеслона в этот момент невероятно.


  1. Andy_U
    03.02.2018 16:51
    #10651414
    +1

    А что такого сложного в третьей задаче? Идем по массиву, как i-й элемент оказался меньше предыдущего, так и все. Если дошли до конца, ответ — 0

    P.S. Ну, можно еще после нахождения k дойти до конца, для проверки валидности входных данных…


    1. tr4rex
      03.02.2018 22:23
      #10651646
      +1

      думаю, что важно упомянуть о том, что решений может быть бесконечно много с периодом, равным длине массива


      1. kardan2
        04.02.2018 11:02
        #10651982

        Думаю, что нет. В примерах к 3-й задачи есть ответы. И в этих ответах (то чего хотят поручить) есть всего 1 значение. Поэтому и мы должны давать 1 значение в качестве ответа.


    1. reci Автор
      04.02.2018 14:19
      #10652180

      Предположим, 2-й элемент оказался меньше предыдущего, тогда каков будет ответ?


      1. kardan2
        04.02.2018 14:35
        #10652204

        Ответ 1.


    1. apapacy
      04.02.2018 15:27
      #10652254

      Наверное предполагалось что будет небольшая оптимизация. Фактически нужно сравнивать границы последовав ателье ости если сортировка нарушена то делить пополам или другим способом и брать отрезок где сортировка опять же нарушена. Пока не останется отрезок длинной два.


  1. kardan2
    04.02.2018 10:51
    #10651972

    Вопрос 2. — Видел задачу в другом месте (хотя сам не решил)
    Задача 3. — Поиск минимума? Или пары рядом стоящих чисел, когда первое больше второго.
    Задача 2. За 1 проход заносим в Хэш значения квадратов элементов. А далее двойным циклом складываем квадраты элементов и проверяем наличие такого же значения в Хэше.
    Задача 1. Необходимо определиться, как интерпретировать [2000,2010],[2010,2020], т.е. случай когда год смерти одного слона совпадает с годом рождения другого слона. Можно ли считать, что [2000,2020] жил ровно 1 слон, или же [2010,2010] жило 2 слона.
    Предположим первое. Заводим Хэш, где год — ключ, а значение — +1 если это дата рождения, -1 если это дата смерти. Если в 1 год родилось 5 слонов, а умерло 2, тогда в хеше будет 5-2=3. Затем выгружаем все не нулевые значения Хэша в массив, сортируем его, и за 1 проход получаем решение. Сложность O(n*lon(n)) за счет сортировки.
    Можно по иному пойти, выгрузить даты рождения в 1 массив, а смерти в другой массив. Отсортировать оба, и совместным прохождением по обоим массивам найти ответ. Сложность та же.

    Про бананы и верблюда ещё думаю.


    1. DaneSoul
      04.02.2018 11:52
      #10652034

      Можно по иному пойти, выгрузить даты рождения в 1 массив, а смерти в другой массив. Отсортировать оба, и совместным прохождением по обоим массивам найти ответ. Сложность та же.

      Если работать с массивами дат, то наглядней перевести их в множества (set в Python) и найти результирующее множество сделав пересечение множеств. Потом берем минимум и максимум из этого результирующего множества.


  1. dmrt
    04.02.2018 12:01
    #10652044

    У меня получилось максимум всего лишь 416 бананов.
    Сначала забрасываем бананы на 250-ый километр в три этапа, итого там будет 1500 бананов, половину мы потеряем, скормили прожорливому верблюду.
    Затем закидываем на 416-ый километр остальные 1000 бананов, потеряв 500 бананов.
    Основная цель — это найти максимальный километр, куда можно закинуть 1К бананов.
    Дальше грузим всю тысячу и идем до конца, в итоге довозим всего лишь 416 бананов.


    1. apapacy
      04.02.2018 14:39
      #10652210

      Если забрасывать бананы сразу на 250км то теряется лишние 100=(250-200)*2 банана


      1. dmrt
        04.02.2018 15:04
        #10652236

        Хотя я чуть неправильно посчитал, на 250 у меня будет 1750.
        Ну да, если на 200-ый, то мы там будем иметь там 2000 бананов.
        Едем на 333 км еще, оставляем на 533-ем 333 банана, возвращаемся, берем 1К, в итоге привозим 533 банана.

        По моей схеме имеем 1750 на 250-ом км.
        Отвозим еще на 250 км, на 500-й 250 бананов, возвращаемся за 1К, едем в конечную точку, подбираем на 500-ом 250 бананов, в итоге получается привезем 500 бананов.

        Да, получается, что на 200-ый лучше сначала.


        1. apapacy
          04.02.2018 15:10
          #10652238

          Важны только точки когда кончается очередная тысяча бананов. То есть можно везти до 200 через несколько перевалочных пунктов


  1. dmrt
    04.02.2018 13:47
    #10652136

    Anti-clockwise rotated array
    По-моему у вас ошибка в примерах ответа: в первом случае ответ — 4, во втором — 1 и в третьем все правильно — 0

    my $arr = [ 15, 18, 2, 3, 6, 12 ]; 

sub get_turn_count
{
    my $arr = shift;
    my @sorted = sort { $a <=> $b } @$arr;

    my $k = 0;
    while( 1 )
    {
        last if( join( ',', @$arr ) eq join( ',', @sorted ) );

        $k++;
        unshift( @$arr, pop( @$arr ) );
    }

    return $k
}

print get_turn_count( $arr ), " \n";


    1. reci Автор
      04.02.2018 14:16
      #10652176

      Вы правы, почему-то мысленно поворачивал по часовой, поэтому не заметил расхождения условий с примером. Исправлено.


    1. Andy_U
      04.02.2018 14:52
      #10652226

      Да, зря я поленился написать код с unit-тестами, в результате чего, чего, честно говоря, тоже «решил» задачу про поворот по часовой стрелке. Т.е. правильный ответ будет что-то типа n-i, где i — результат «моего» вчерашнего алгоритма.

      P.S. Ваш код, наверное (я даже язык не могу угадать) правильный, но сильно неэффективный. Сначала сортировка массива, а потом в цикле еще и циклический сдвиг. Т.е. сложность типа O(N^2). А можно O(N).


      1. dmrt
        04.02.2018 15:11
        #10652240

        Язык Perl.
        Сортировка — это O(log N) один раз.
        А дальше стандартные функции для работы с массивами, со списками добавление элемета в начало массива и выталкивание последнего. Не могу точно сказать какая тут сложность, но если это динамический массив, то тоже O(N) получается.


        1. Andy_U
          04.02.2018 15:19
          #10652248

          Сортировка — это O(log N) один раз.


          Сортировка O(log N)? Скорее O(N*log N). а это уже больше O(N)…

          Ну, стоимость прокрутки массива, если это не плоский массив, а список, действительно может стоить фиксированное время, но уж сравнение двух массивов длиной N на равенство (в прошлый раз не заметил), опять N/2 раз, это уж точно получится O(N^2).


          1. dmrt
            04.02.2018 15:28
            #10652258

            Хотя сортировка — это O(n log n)
            А сравнение двух массивов — это O(2N), причем по сортированному не нужно было мне проходится в цикле каждый раз, можно было бы join его вычислить перед циклом, так что сложность сравнения тут O(N)
            Итого O(n log n) + k * O(N)


            1. Andy_U
              04.02.2018 15:37
              #10652270

              Да, но в худшем случае k=N, в среднем k=N/2. А ответ ищется одним линейным проходом по массиву. Как нашли a[i-1] > a[i], так и ответ нашли (N-i, если индексация начинается с нуля). Если не нашли, ответ 0.


              1. apapacy
                04.02.2018 15:56
                #10652300

                В задаче кажется требовался только ответ с числом в условии. Но линейный проход не обязателен можно искать делением массива пополам.


                1. Andy_U
                  04.02.2018 16:29
                  #10652326

                  А можно на код посмотреть?


                  1. apapacy
                    04.02.2018 16:34
                    #10652330

                    Буду рядом с компьютером напишу. А что есть подозрение что будут проблемы?


                    1. Andy_U
                      04.02.2018 17:06
                      #10652354

                      Были. Я по scientific computing специализируюсь, А тут, вроде и не поиск корня, или экстремума у выпуклой функции, поэтому и самому в голову не пришло, и в Вашем подходе, мягко говоря, засомневался.

                      Только после третьего вашего сообщения решил на всякий случай картинку на бумажке нарисовать и теперь на могу с Вами не согласиться. Действительно O(log N), причем независимо ни от чего. Снимаю шляпу.

                      P.S. А код напишите для фиксации рекорда.


                      1. apapacy
                        04.02.2018 19:19
                        #10652462

                        Код я имел в виду такой. Но теперь я понимаю что Ваш вариант был правильный а мой нет. Весь вопрос как трактовать тексо возрастающая последовательность. Я могу ошибаться но кажется возрастающая и неубывающая это разные вещи. То есть возрастающая не подразумевает повторения значений. Но не сказана что последовательность возрастающая а сказано отсортирована по возрастанию. То есть она неубывающая в строгом смысле. Если значения будут повторяться (неубывающая) то вот такой массив будет проанализировать проще протым перебором при этом от начала и до конца
                        [5,5,5,5,5,5,5,5,5]
                        [5,5,5,5,5,2,5,5,5].

                        Я так понимаю что давая такую задачу тестирующий хочет понять какие у тестируемого будут варианты проверки и будет ли он проходить массив от начала и до конца и остановится ли на первом равестве 5 = 5 значит ротация была 0.

                        Хотя может быть и другой вариант например что в условии сказано что «по возрастанию» значит это буквально равных быть не может.

                        var array = [2,3,6,7,8,9,1]

console.log(rotatedBy(array));

function rotatedBy(array) {
  var left = 0; 
  var right = array.length - 1;
  var middle;
  if (array.length <=1 || array[left] < array[right]) {
    return 0;
  }
  while (right - left > 1 && array[left] > array[right]) {
    middle = Math.floor((left + right) / 2);
    if (array[left] > array[middle]) {
       right = middle;
    } else {
       left = middle;
    }
  }
  return array.length - right;
}


                        1. apapacy
                          04.02.2018 19:23
                          #10652468

                          и кстати для массива [5,5,5,5,5,5,5,5] задача как бы вырождается и вариантов будет от 0 до длины массива минус один. А может быть это тест на адекватность? Если тестируемый начинает задавать тестирующему такие вопросы то он в каждой задаче будет видеть проблемы там где их нет?


                        1. Andy_U
                          04.02.2018 19:33
                          #10652474

                          Все нормально, в условии задачи сказано, что все числа разные.


                          1. apapacy
                            04.02.2018 19:40
                            #10652484

                            Да посмотрел — of distinct integers. Я читал только русский перевод. И немного затормозил на этом.


              1. dmrt
                04.02.2018 16:12
                #10652318

                Да, вы правы, вот так гораздо эффективнее:

                my $arr = [ 15, 18, 2, 3, 6, 12 ]; 

sub get_turn_count
{
    my @arr = @_;
    my $min = List::Util::min( @arr );

    my $k = 0;
    foreach ( @arr )
    {
        if( $arr[ 0 ] == $min and $arr[ - 1 ] != $arr[ 0 ] )
        {
            last;
        }
        unshift( @arr, pop( @arr ) );
        $k++;
    }

    return $k;
}

print get_turn_count( @$arr ), " \n";


    1. ads83
      04.02.2018 21:31
      #10652622

      По условию задачи, массив был отсортирован и потом «повернут» несколько раз. Т.к. он отсортирован, первый элемент — минимальный. Каждый поворот смещает первый элемент на 1 влево (первый раз — в конец массива). Таким образом, за один проход ищем минимальный элемент и запоминаем его позицию. Ответ n-k+1. Отдельно обрабатывается случай когда минимальный — первый элемент, значит поворотов не было (или было n).
      Для поворота в другую сторону ответ k-1.
      P.S. Возможно, я неправильно понял условие задачи, но мне непонятно зачем в решении поворачивать входной массив. Нам ведь не надо восстановить отсортированный? Также мое решение исходит из того, что на входе — корректные данные, т.е. это действительно отсортированный массив, который «повернули». Для восстановления исходного массива достаточно сделать еще один проход (в копию ставим элементы на нужный индекс), для проверки сортировки — тоже один с попарным сравнением с предыдущим элементом.


      1. dmrt
        04.02.2018 22:12
        #10652666

        Да, вы правы, переставлять элементы тут лишнее.

        use List::Util ();

my $arr = [ 15, 18, 2, 3, 6, 12 ]; 

sub get_turn_count
{
    my @arr = @_;
    my $min = List::Util::min( @arr );

    my $k = 0;
    foreach ( 0 .. $#arr )
    {
        if( $arr[ $k ] == $min and $arr[ $k - 1 ] > $el )
        {
            last;
        }
        $k++;
    }

    return scalar( @arr ) - $k;
}

print get_turn_count( @$arr ), " \n";


  1. dmrt
    04.02.2018 16:46
    #10652338

    У меня вопросы по шнурам:
    1. То что одна половина горит 10 мин, а другая 50 мин — это конкретные условия задачи или просто как пример, на самом деле время может отличаться и оно не известно?
    2 Если целиком шнур горит неравномерно, то половины горят равномерно?
    3. Можно ли отличить концы шнуров, т.е. с какой стороны быстрее, а с какой медленнее сразу же, до зажигания?


    1. Andy_U
      04.02.2018 17:10
      #10652356

      1. Функция длины сгоревшей части шнура — монотонно возрастающая непрерывная функция, равная нулю при T=0 и равная длине шнура при T=1 час. Все.
      2. Половины по длине? Нет. См. п.1
      3. Нет. см. п.1


    1. reci Автор
      04.02.2018 18:00
      #10652396

      1. Точное время горения половин неизвестно. Может быть 15/45, например. А могут и равномерно, я думаю.
      2. Нет.
      3. Нет.


      1. dmrt
        04.02.2018 20:05
        #10652514

        И как же нам тогда решать такую задачу прикажите? Может быть вы что-то не договариваете?
        Даже если ее и можно решить, то решение на порядок не очевидней, по сравнению с другими задачами, у них ответ лежит почти на поверхности.


        1. Andy_U
          04.02.2018 20:07
          #10652518

          Так она уже решена. См. первый комментарий.


  1. vesper-bot
    05.02.2018 09:56
    #10653064

    Задачу с массивом можно решить за O(log N) бинарным поиском. Сначала берем первый элемент и средний (в одну из сторон, тут неважно), если средний больше первого, минимум в верхней части массива, если меньше, то в нижней. Продолжаем, пока длина массива не станет 2, тогда тот элемент, что меньше из двух, и будет минимальным. Индексы считаем параллельно нахождению минимума, и выдаем индекс наружу, потом если он 0, то массив не сдвинут, если не ноль, то вычитаем его из длины (так как массив сдвигался влево), получаем ответ.


    1. ads83
      06.02.2018 22:37
      #10656022

      Возможно, я неправильно понял алгоритм, но мне кажется он сломается на примерах {2,3,4,5,1} и {5,1,2,3,4}.

      Проблема с бинарным поиском в том, что числа расположены не монотонно. Например, для {3,4,5,1,2} ряд возрастает до третьего элемента, а потом убывает.

      Поправьте меня, если я ошибся.


      1. Andy_U
        06.02.2018 23:02
        #10656044

        См. код выше:


      1. apapacy
        07.02.2018 01:43
        #10656166

        В данном случае бинарный поиск как раз ищет это расхождение но не прямым перебором а делением отрезка на два. Процесс заканчивается когда отрезок будет иметьровно два элемента. Из них правый элемент это и будет бывший первый эемент списка.


  1. megamih
    05.02.2018 10:55
    #10653162

    Задачу с верёвкой я бы решал «сложением» :)
    Нужно сложить одну верёвку пополам, а вторую — вчетверо.
    Когда первая верёвка полностью сгорит, пройдёт 30 минут. Когда вторая — ещё 15 минут.


  1. vivlav
    05.02.2018 10:55
    #10653164

    Про бананы мне кажется можно проще объяснить, чем через функции. Пока условно предположим, что перевозим максимум на 1 км. потом возвращаемся. На первые километры тратится по 5 бананов на километр (пока не останется 2000, или потратить 1000), затем по 3 (пока не останется 1000 или снова потратить 1000) и дальше по одному.
    Итого первую тысячу (5 бананов на км) мы потратим за 200 км. вторую за 333 (1 банан теряем так как его перевозка дороже его самого) ну и последнюю 1000 везем оставшиеся 467км, значит с тысячи довезем 533.


    1. apapacy
      05.02.2018 12:07
      #10653334

      Расстояния не обязательно кратны километра и нет уверенности что такой ответ действительно максимум и не даёт ключа к решению в общем случае. Например сколько будет от 3007 бананов.


      1. vesper-bot
        05.02.2018 12:47
        #10653430

        сколько будет от 3007 бананов

        На семь бананов при макс.загрузке 1000 проехать удастся только 1км., т.е. привезем на один банан больше (534).


        нет уверенности что такой ответ действительно максимум и не даёт ключа к решению в общем случае.

        Как раз дает, но если расстояния кратны километру. Если не кратны, то вопрос, как мы считаем нецелые бананы, а также как считается половина банана во рту у верблюда при расчете его грузоподъемности. По мне, такие вопросы позволяют "закопать" исходную задачу без какого-либо изменения понимания того, как думает собеседник, решивший задачу в целых числах.


        Почему максимум — а потому, что каждый километр мы преодолеваем, используя наименьшую возможную стоимость километра в бананах, которая зависит от того, сколько неполных тысяч бананов у нас есть на текущий момент. При 3007 бананов их 4, и стоимость километра оказывается 7.


        1. apapacy
          05.02.2018 13:06
          #10653470

          Целый банан не означает целого километра в одну сторону. Это мтожет быть три ходуи по 1/3 километра. Я просто мог немного подготовить данные так чтобы эти части бананов накапливались и у вашего способа получилось расхождение. Но даже не это главное. Главное что в общем методе все решается проще и точнее.


      1. vivlav
        07.02.2018 13:45
        #10656866
        +1

        Согласен — такое объяснение сработает только в целых числах. В случае деления километров и бананов превратиться в:
        Итого первую тысячу (5 бананов на км) мы потратим за 200 км. вторую за 333.(3), ну и последнюю 1000 везем оставшиеся 466.(6) км, значит с тысячи довезем 533,(3). При условии «непрерывного потребления» в конце.


  1. Nick_mentat
    05.02.2018 14:35
    #10653688

    Про бананы прочитал несколько неправильных решений. Почему-то многие забывают кормить верблюда на обратном пути в промежуточных ходках…

    Верблюды
    Моё решение в 444 банана, и я не знаю как больше. Отнесём 333 банана на треть пути, съев треть от тысячи на пути туда, и треть — обратно. Отнесём 444 банана на 444 км, съев 444 банана. Ещё 111 съедим на пути назад до 333 километра, там подбираем оставленые бананы, чтобы хватило добраться до дома. Берём последнюю 1000 бананов и везём на 444 километр, там подсаправляемся до упора и идём на целевую точку. Эфективность веблюда получается меньше 15% =(


    1. Suntechnic
      06.02.2018 13:13
      #10655192

      В чем ошибка такого решения: habrahabr.ru/company/spice/blog/348122/#comment_10653124 (533.5 банана)?


    1. apapacy
      06.02.2018 13:58
      #10655298

      Все верблюды накормлены. Были правда попытки зажать полбанана после работы но это уже наш менталитет. Нести бананы на треть пути сразу невыгодно ту передаются лишние бананы. Первая остановка должна быть максимум на 200 км