Pull to refresh
0
Spice IT Recruitment
ИТ-специализированное кадровое агентство

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

Reading time 4 min
Views 8.3K
Продолжаем публиковать интересные задачи от ведуших IT-компаний.

КДПВ
В подборку попали задачи, задаваемые на собеседованиях (обычно на должность инженера-разработчика) в Yahoo! Предлагаем Вам попробовать свои силы и постараться решить задачи самостоятельно — тогда вопросы на собеседовании вряд ли застанут Вас врасплох.

Вопросы


  1. Total distance travelled by bee
    Two trains are on same track and they are coming toward each other. The speed of first train is 50 KMs/h and the speed of second train is 70 KMs/h. A bee starts flying between the trains when the distance between two trains is 100 KMs. The bee first flies from first train to second train. Once it reaches the second train, it immediately flies back to the second train … and so on until trains collide. Calculate the total distance traveled by the bee. Speed of bee is 40 KMs/h.

    Перевод
    Два поезда на одном пути едут навстречу друг другу. Скорость первого поезда — 50 км/ч, скорость второго — 70 км/ч. Пчела начинает летать между поездами, когда расстояние между ними равно 100 км. Пчела летит от первого поезда ко второму. Когда достигнет второго, немедленно летит обратно к первому… и продолжает так летать, пока поезда не столкнутся.
    Посчитайте дистанцию, пройденную пчелой, если её скорость 40 км/ч.

  2. Poisoned wine
    The King of a small country invites 240 senators to his annual party. As a tradition, each senator brings the King a bottle of wine. Soon after, the Queen discovers that one of the senators is trying to assassinate the King by giving him a bottle of poisoned wine. Unfortunately, they do not know which senator, nor which bottle of wine is poisoned, and the poison is completely indiscernible. However, the King has 5 prisoners he plans to execute. He decides to use them as taste testers to determine which bottle of wine contains the poison. After drinking the poisoned wine, one dies within 24 hours. The King needs to determine which bottle of wine is poisoned in 2 days so that the festivities can continue as planned. How can the King administer the wine to the prisoners to ensure that 48 hours from now he is guaranteed to have found the poisoned wine bottle?

    Перевод
    Король небольшой страны пригласил 240 сенаторов на ежегодное празднование. По традиции, каждый сенатор преподносит королю бутылку вина. Однако, вскоре королева узнала, что один из сенаторов пытается отравить короля, подарив ему отравленную бутылку вина. К несчастью, они не знают, ни кто этот сенатор, ни что за бутыль отравлена, к тому же, яд невозможно обнаружить. В королевской тюрьме есть 5 заключенных, приговоренных к скорой смерти. Король решает с их помощью вычислить отравленную бутылку вина. Яд подействует только через 24 часа — выпивший его умирает. Королю необходимо выявить, какая бутылка отравлена, за 2 дня, чтобы продолжить запланированные мероприятия. Как он может распределить вино между заключенными, чтобы гарантированно найти отравленную бутылку за 48 часов?

Задачи


  1. Largest subarray with equal number of 0s and 1s
    Given an array containing only 0s and 1s, find the largest subarray which contain equal number of 0s and 1s.

    Examples:
    Input: arr[] = {1, 0, 1, 1, 1, 0, 0}
    Output: 1 to 6 (Starting and Ending indexes of output subarray)

    Input: arr[] = {1, 1, 1, 1}
    Output: No such subarray

    Input: arr[] = {0, 0, 1, 1, 0}
    Output: 0 to 3 Or 1 to 4

    Перевод
    Дан массив, содержащий нули и единицы. Необходимо найти наибольший подмассив, содержащий одинаковое количество 0 и 1.

    Примеры:
    Вход: arr[] = {1, 0, 1, 1, 1, 0, 0}
    Выход: 1 to 6 (Индексы входного массива)

    Вход: arr[] = {1, 1, 1, 1}
    Выход: No such subarray

    Вход: arr[] = {0, 0, 1, 1, 0}
    Выход: 0 to 3 Or 1 to 4

  2. Count total set bits
    Given a positive integer n, count the total number of set bits in binary representation of all numbers from 1 to n.

    Examples:

    Input: n = 3
    Output: 4

    Input: n = 6
    Output: 9

    Input: n = 7
    Output: 12

    Input: n = 8
    Output: 13

    Перевод
    Дано положительное целое число n, необходимо вычислить сумму битов всех чисел от 1 до n в двоичном представлении.

    Примеры:
    Вход: n=3
    Выход: 4

    Вход: n=6
    Выход: 9

    Вход: n=7
    Выход: 12

    Вход: n=8
    Выход: 13

  3. Find the repeating and the missing
    Given an unsorted n-sized array of integers. Array elements are in range from 1 to n. One number from set {1, 2, …n} is missing and one number occurs twice in array. Find these two numbers.

    Examples:

    arr[] = {3, 1, 3}
    Output: 2, 3 // 2 is missing and 3 occurs twice

    arr[] = {4, 3, 6, 2, 1, 1}
    Output: 1, 5 // 5 is missing and 1 occurs twice


    Перевод
    Дан неотсортированный массив целых чисел размерностью n. Элементы массива — последовательность чисел от 1 до n. Одно число в последовательности пропущено и одно — повторяется. Необходимо найти эти числа.

    Примеры:

    arr[] = {3, 1, 3}
    Output: 2, 3 // 2 пропущено, 3 повторяется

    arr[] = {4, 3, 6, 2, 1, 1}
    Output: 1, 5 // 5 пропущено, 1 повторяется



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

Решения


  1. Вопрос 1
    Верный ответ был найден — 33, 3 км.

  2. Вопрос 2
    Решение состоит в том, чтобы пронумеровать бутылки числом в троичной системе, где каждый разряд соответствует действию каждого заключенного по отношению к бутылке:
    0 — не пил,
    1 — выпил в первый день
    2 — выпил во второй день.
    Так, например бутыль с кодом 11201 будет означать, что 1,2 и 5 заключенные выпили в первый день, третий заключенный выпил во второй день, а четвертый не пил — соответственно, если 1,2 и 5 умерли в первый день, а третий во — второй день, то эта бутыль отравлена.
    Всего уникальных комбинаций 3^5 = 243, т.е. по состоянию заключенный к истечению 48 часов можно будет однозначно определить какая бутыль отравлена.

    Решение тоже было предложено в комментариях.

  3. Задача 1
    Решение предполагает последовательное суммирование значений, причём, 0 рассматриваются как "-1". Один из вариантов был предложен тут

  4. Задача 2
    Вариант верного решения был предложени в комментарии

  5. Задача 3
    Один из вариантов решения — пройтись по массиву, используя абсолютное значение элемента как индекс и меняя знак у элемента под этим индексом. Тогда индекс элемента, который уже был помечен отрицательным — является повторяющимся значением.

    За второй проход нужно найти положительное значение:

    #include<stdio.h>
    #include<stdlib.h>
     
    void printTwoElements(int arr[], int size)
    {
        int i;
        printf("\n The repeating element is");
     
        for(i = 0; i < size; i++)
        {
            if(arr[abs(arr[i])-1] > 0)
                arr[abs(arr[i])-1] = -arr[abs(arr[i])-1];
            else
                printf(" %d ", abs(arr[i]));
        }
     
        printf("\nand the missing element is ");
        for(i=0; i<size; i++)
        {
            if(arr[i]>0)
                printf("%d",i+1);
        }
    }
     
    /* Driver program to test above function */
    int main()
    {
        int arr[] = {7, 3, 4, 5, 5, 6, 2};
        int  n = sizeof(arr)/sizeof(arr[0]);
        printTwoElements(arr, n);
        return 0;
    }


    Сложность алгоритма — О(n).

Tags:
Hubs:
+11
Comments 49
Comments Comments 49

Articles

Information

Website
www.spiceit.ru
Registered
Founded
2009
Employees
31–50 employees
Location
Россия