Как стать автором
Обновить
42.97
Рейтинг
Spice IT Recruitment
ИТ-специализированное кадровое агентство

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

Блог компании Spice IT Recruitment Занимательные задачки Программирование *
На этой неделе мы отобрали вопросы и задачи, встречающиеся соискателям на собеседованиях на должность инженера-разработчика в DELL.

КДПВ


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

Вопросы


  1. Ice bucket challenge
    There are 3 buckets of capacities 8, 5, 3 litres in front of you. The bucket with capacity 8 is completely filled with ice water. You need to divide the 8 litres into 2 portions of 4 litre each using above 3 buckets.
    Перевод
    Перед Вами 3 ведра ёмкостью 8, 5 и 3 л. Ведро на 8 л. полностью заполнено холодной водой. Вам нужно разделить 8 литров на 2 порции по 4 л. используя эти три ведра.

  2. Torch and bridge
    There are 4 persons (A, B, C and D) who want to cross a bridge in night.

    A takes 1 minute to cross the bridge.
    B takes 2 minutes to cross the bridge.
    C takes 5 minutes to cross the bridge.
    D takes 8 minutes to cross the bridge.

    There is only one torch with them and the bridge cannot be crossed without the torch. There cannot be more than two persons on the bridge at any time, and when two people cross the bridge together, they must move at the slower person’s pace

    Can they all cross the bridge in 15 minutes?
    Перевод
    4 человека (A, B, C, D) хотять ночью перебраться через мост.

    A нужна 1 минута чтобы пройти по мосту.
    B нужно 2 минуты.
    C нужно 5 минут.
    D нужно 8 минут.

    У них только один фонарь, без которого нельзя перейти мост. Также, на мосту не может находиться больше 2-х человек, и, когда по мосту идут двое — они идут со скоростью самого медленного ходока.

    Смогут ли они перебраться за 15 минут?

Задачи


  1. Sort an array of 0s, 1s and 2x
    Given an array A[] consisting 0s, 1s and 2s, write a function that sorts A[]. The functions should put all 0s first, then all 1s and all 2s in last.
    Examples:

    Input: {0, 1, 2, 0, 1, 2}
    Output: {0, 0, 1, 1, 2, 2}

    Input: {0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1}
    Output: {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2}

    Перевод
    Дан массив A[], состоящий из 0, 1 и 2. Напишите функцию, сортирующую A[]. Функция должна располагать сначала 0, потом 1, последними — 2.

    Примеры:

    Вход: {0, 1, 2, 0, 1, 2}
    Выход: {0, 0, 1, 1, 2, 2}

    Вход: {0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1}
    Выход: {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2}

  2. Select a random number from stream, using fixed space
    Given a generator producing random numbers. You are allowed to use only O(1) space and the input is in the form of stream, so can’t store the previously seen numbers.

    So how do we select a random number from the whole stream such that the probability of picking any number is 1/n. with O(1) extra space?
    Перевод
    Дан генератор случайных чисел. Позволено использовать только О(1) памяти, входные данные представлены в виде потока, так что нет возможности сохранять предыдущие числа.

    Задача — выбрать случаное число из входящего потока, обеспечив вероятность 1/n, используя только O(1) дополнительной памяти.

  3. Maximize the sum of selected numbers
    Given an array of N numbers, we need to maximize the sum of selected numbers. At each step you need to select a number Ai, delete one occurrence of Ai-1 (if exists), Ai+1 (if exists) and Ai each from the array. Repeat these steps until the array gets empty. The problem is to maximize the sum of selected numbers.

    Note: We have to delete Ai+1 and Ai-1 elements if they are present in the array and not Ai+1 and Ai-1.

    Examples:

    Input: a[] = {1, 2, 3}
    Output: 4
    Explanation: At first step we select 1, so 1 and 2 are deleted from the sequence leaving us with 3.
    Then we select 3 from the sequence and delete it. So the sum of selected numbers is 1+3 = 4.

    Input: a[] = {1, 2, 2, 2, 3, 4}
    Output: 10
    Explanation: Select one of the 2's from the array, so 2, 2-1, 2+1 will be deleted and we are left with {2, 2, 4}, since 1 and 3 are deleted. Select 2 in next two steps, and then select 4 in the last step. We get a sum of 2+2+2+4=10 which is the maximum possible.
    Перевод
    Дан массив из N чисел, нам необходимо выбрать элементы с максимальной суммой. При каждой выборке элемента (Аi), необходимо удалить одно вхождение элемента на единицу меньше и одно вхождение элемента на единицу больше (Ai-1) и (Ai+1) при их наличии и сам элемент. Эти шаги повторяются, пока массив не опустеет. Задача — обеспечить максимальную сумму выбранных элементов.
    Нужно удалять элементы со значением Ai+1 и Ai-1, а не на позиции Аi-1 и Аi+1

    Примеры:

    Вход: a[] = {1, 2, 3}
    Выход: 4
    Объяснение: На первом шаге выбираем 1, следовательно, 1 и 2 удаляются из массива. На следующем шаге забираем оставшуюся 3. Сумма выбранных элементов 1+3 = 4.

    Вход: a[] = {1, 2, 2, 2, 3, 4}
    Выход: 10
    Объяснение: Выбираем одну 2 из массива — удаляются 1 и 3 (2-1 и 2+1, соответственно), остаются {2, 2, 4}. В ходе следующих 2-х шагов выбираем оставшиеся 2 и последним шагом выбираем 4. Итоговая сумма 2+2+2+4 = 10, что является максимально возможной.

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

Решения


  1. Вопрос 1
    Корректное решение предложено в комментарии:
    8 -> 5 (3, 5, 0)
    5 -> 3 (3, 2, 3)
    3 -> 8 (6, 2, 0)
    5 -> 3 (6, 0, 2)
    8 -> 5 (1, 5, 2)
    5 -> 3 (1, 4, 3)
    3 -> 8 (4, 4, 0)

  2. Вопрос 2
    Верное решение было найдено в комментариях.

  3. Задача 1
    Предложили верный вариант решения — сортировка подсчётом. Код может быть, например, таким.

  4. Задача 2
    Алгоритм решения был верно разъяснен в комментарии. Код может быть таким:
    // An efficient C program to randomly select a number from stream of numbers.
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>

    // A function to randomly select a item from stream[0], stream[1], .. stream[i-1]
    int selectRandom(int x)
    {
    static int res; // The resultant random number
    static int count = 0; //Count of numbers visited so far in stream

    count++; // increment count of numbers seen so far

    // If this is the first element from stream, return it
    if (count == 1)
    res = x;
    else
    {
    // Generate a random number from 0 to count - 1
    int i = rand() % count;

    // Replace the prev random number with new number with 1/count probability
    if (i == count - 1)
    res = x;
    }
    return res;
    }

    // Driver program to test above function.
    int main()
    {
    int stream[] = {1, 2, 3, 4};
    int n = sizeof(stream)/sizeof(stream[0]);

    // Use a different seed value for every run.
    srand(time(NULL));
    for (int i = 0; i < n; ++i)
    printf("Random number from first %d numbers is %d \n",
    i+1, selectRandom(stream[i]));
    return 0;
    }


  5. Задача 3
    Правильное решение было предложено, например, тут. Код:
    // CPP program to Maximize the sum of selected
    // numbers by deleting three consecutive numbers.
    #include <bits/stdc++.h>
    using namespace std;

    // function to maximize the sum of selected numbers
    int maximizeSum(int a[], int n) {

    // stores the occurrences of the numbers
    unordered_map<int, int> ans;

    // marks the occurrence of every number in the sequence
    for (int i = 0; i < n; i++)
    ans[a[i]]++;

    // maximum in the sequence
    int maximum = *max_element(a, a + n);

    // traverse till maximum and apply the recurrence relation
    for (int i = 2; i <= maximum; i++)
    ans[i] = max(ans[i - 1], ans[i - 2] + ans[i] * i);

    // return the ans stored in the index of maximum
    return ans[maximum];
    }

    // Driver code
    int main()
    {
    int a[] = {1, 2, 3};
    int n = sizeof(a) / sizeof(a[0]);
    cout << maximizeSum(a, n);
    return 0;
    }


Теги:
Хабы:
Всего голосов 11: ↑11 и ↓0 +11
Просмотры 6.9K
Комментарии Комментарии 44

Информация

Дата основания
2009
Местоположение
Россия
Сайт
www.spiceit.ru
Численность
31–50 человек
Дата регистрации