Выпуск#9: ITренировка — актуальные вопросы и задачи от ведущих компаний03.02.2018 19:18

Мы подготовили для вас новый сет задач и вопросов, задаваемых на собеседованиях в ведущих 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: 2
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: 4

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}
Выход: 2
Исходны массив должен быть — {2, 3, 6, 12, 15. 18}. Мы получим входной массив, если повернем исходный 2 раза.

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

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


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

© Habrahabr.ru