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

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

Spice IT Recruitment corporate blog Entertaining tasks Programming *
На этой неделе мы отобрали вопросы и задачи, встречающиеся соискателям на собеседованиях на должность инженера-разработчика в Ebay.

КДПВ

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


Вопросы


  1. Days of month using 2 dice
    How can you represent days of month using two 6 sided dice? You can write one number on each face of the dice from 0 to 9 and you have to represent days from 1 to 31, for example for 1, one dice should show 0 and another should show 1, similarly for 29 one dice should show 2 and another should show 9.

    Перевод
    Как бы вы представили дни месяца с помощью 2-х шестигранных кубиков? Вы можете написать числа от 0 до 9 на каждой грани кубика, при этом Вам необходимо обозначить числа от 1 до 31. Например для 1-го числа, один кубик может быть повернут гранью с «0», а другой — с «1»; аналогично для числа 29 — один кубик с «2», второй — с «9».

  2. Blindfolded and coins
    You are blindfolded and 10 coins are place in front of you on table. You are allowed to touch the coins, but can’t tell which way up they are by feel. You are told that there are 5 coins head up, and 5 coins tails up but not which ones are which.

    Can you make two piles of coins each with the same number of heads up? You can flip the coins any number of times.


    Перевод
    У Вас завязаны глаза, а на столе перед Вами 10 монет. Вам разрешено их трогать, но на ощупь Вы не можете сказать какой стороной они повернуты. Также утверждается, что 5 монет лежат орлом вверх, 5 — решкой.

    Как сделать 2 стопки с равным количеством монет, повёрнутых орлом вверх? Вы можете переворачивать монеты неограниченное число раз.


Задачи


  1. Tug of War
    Given a set of n integers, divide the set in two subsets of n/2 sizes each such that the difference of the sum of two subsets is as minimum as possible. If n is even, then sizes of two subsets must be strictly n/2 and if n is odd, then size of one subset must be (n-1)/2 and size of other subset must be (n+1)/2.

    For example, let given set be {3, 4, 5, -3, 100, 1, 89, 54, 23, 20}, the size of set is 10. Output for this set should be {4, 100, 1, 23, 20} and {3, 5, -3, 89, 54}. Both output subsets are of size 5 and sum of elements in both subsets is same (148 and 148).
    Let us consider another example where n is odd. Let given set be {23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4}. The output subsets should be {45, -34, 12, 98, -1} and {23, 0, -99, 4, 189, 4}. The sums of elements in two subsets are 120 and 121 respectively.

    Перевод
    Дан набор n целых чисел, необходимо разделить его на 2 подмножества, размерностью n/2 каждое, так, чтобы разница между суммами этих подмножеств была минимальной. Если n чётное, тогда размеры подмножеств должны быть ровно n/2, если же n — нечётное, тогда размер одного подмножества должен быть (n-1)/2, второго — (n+1)/2.

    Например:
    Вход: {3, 4, 5, -3, 100, 1, 89, 54, 23, 20}
    Выход: {4, 100, 1, 23, 20} и {3, 5, -3, 89, 54}. Размеры обоих подмножеств — 5, а суммы равны 148.

    Вход: {23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4}
    Выход: {45, -34, 12, 98, -1} и {23, 0, -99, 4, 189, 4}. Суммы подмножеств 120 и 121 соответственно.

  2. Maximum sum such that no two elements are adjacent
    Given an array of positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array. So 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should return 15 (sum of 3, 5 and 7).Answer the question in most efficient way.

    Examples:

    Input: arr[] = {5, 5, 10, 100, 10, 5}
    Output: 110

    Input: arr[] = {1, 2, 3}
    Output: 4

    Input: arr[] = {1, 20, 3}
    Output: 20

    Перевод
    Дан массив положительных чисел, найдите максимальную сумму подпоследовательности с условием, чтобы никакие 2 элемента подпоследовательности не находились в соседних ячейках массива. Так, 3 2 7 10 должно вернуть 13 ( сумма 3 и 10), а 3 2 5 10 7 должно вернуть 15 (сумма 3 5 7). Код должен быть максимально эффективным.

    Примеры:

    Вход: arr[] = {5, 5, 10, 100, 10, 5}
    Выход: 110

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

    Вход: arr[] = {1, 20, 3}
    Выход: 20


  3. Program to find amount of water in a given glass
    There are some glasses with equal capacity as 1 litre. The glasses are kept as follows:
                       1
                     2   3
                  4    5    6
                7    8    9   10
    

    You can put water to only top glass. If you put more than 1 litre water to 1st glass, water overflows and fills equally in both 2nd and 3rd glasses. Glass 5 will get water from both 2nd glass and 3rd glass and so on.
    If you have X litre of water and you put that water in top glass, how much water will be contained by jth glass? Write a program to find it.

    Example. If you will put 2 litre on top.
    1st – 1 litre
    2nd – 1/2 litre
    3rd – 1/2 litre

    Перевод
    Несколько банок емкостью 1 литр выстроены пирамидой вот так:
    
                       1
                     2   3
                  4    5    6
                7    8    9   10
    

    Вы можете наливать воду только в самую верхнюю банку. При переполнении банки вода начнёт равномерно переливаться в нижние (2 и 3). Банка 5 будет получать воду из 2 и 3 банок и т.д.
    Если у Вас есть X литров воды, которую вы выльете в верхнюю банку, сколько воды попадёт в банку j? Напишите программу для решения этого вопроса.

    Пример. Если вылить 2 литра, то:
    1ая – 1 литр
    2ая – 1/2 литра
    3я – 1/2 литра

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

Решения


  1. Вопрос 1
    Ответ был быстро найден.

  2. Вопрос 2
    Rsa97 предложил верное решение.

  3. Задача 1
    Исходный вариант решения:
    #include <iostream>
    #include <stdlib.h>
    #include <limits.h>
    using namespace std;
    
    // function that tries every possible solution by calling itself recursively
    void TOWUtil(int* arr, int n, bool* curr_elements, int no_of_selected_elements,
                 bool* soln, int* min_diff, int sum, int curr_sum, int curr_position)
    {
        // checks whether the it is going out of bound
        if (curr_position == n)
            return;
    
        // checks that the numbers of elements left are not less than the
        // number of elements required to form the solution
        if ((n/2 - no_of_selected_elements) > (n - curr_position))
            return;
    
        // consider the cases when current element is not included in the solution
        TOWUtil(arr, n, curr_elements, no_of_selected_elements,
                  soln, min_diff, sum, curr_sum, curr_position+1);
    
        // add the current element to the solution
        no_of_selected_elements++;
        curr_sum = curr_sum + arr[curr_position];
        curr_elements[curr_position] = true;
    
        // checks if a solution is formed
        if (no_of_selected_elements == n/2)
        {
            // checks if the solution formed is better than the best solution so far
            if (abs(sum/2 - curr_sum) < *min_diff)
            {
                *min_diff = abs(sum/2 - curr_sum);
                for (int i = 0; i<n; i++)
                    soln[i] = curr_elements[i];
            }
        }
        else
        {
            // consider the cases where current element is included in the solution
            TOWUtil(arr, n, curr_elements, no_of_selected_elements, soln,
                      min_diff, sum, curr_sum, curr_position+1);
        }
    
        // removes current element before returning to the caller of this function
        curr_elements[curr_position] = false;
    }
    
    // main function that generate an arr
    void tugOfWar(int *arr, int n)
    {
        // the boolen array that contains the inclusion and exclusion of an element
        // in current set. The number excluded automatically form the other set
        bool* curr_elements = new bool[n];
    
        // The inclusion/exclusion array for final solution
        bool* soln = new bool[n];
    
        int min_diff = INT_MAX;
    
        int sum = 0;
        for (int i=0; i<n; i++)
        {
            sum += arr[i];
            curr_elements[i] =  soln[i] = false;
        }
    
        // Find the solution using recursive function TOWUtil()
        TOWUtil(arr, n, curr_elements, 0, soln, &min_diff, sum, 0, 0);
    
        // Print the solution
        cout << "The first subset is: ";
        for (int i=0; i<n; i++)
        {
            if (soln[i] == true)
                cout << arr[i] << " ";
        }
        cout << "\nThe second subset is: ";
        for (int i=0; i<n; i++)
        {
            if (soln[i] == false)
                cout << arr[i] << " ";
        }
    }
    
    // Driver program to test above functions
    int main()
    {
        int arr[] = {23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4};
        int n = sizeof(arr)/sizeof(arr[0]);
        tugOfWar(arr, n);
        return 0;
    }
    


  4. Задача 2
    Вариант решения:
    #include<stdio.h>
    
    /*Function to return max sum such that no two elements
     are adjacent */
    int FindMaxSum(int arr[], int n)
    {
      int incl = arr[0];
      int excl = 0;
      int excl_new;
      int i;
    
      for (i = 1; i < n; i++)
      {
         /* current max excluding i */
         excl_new = (incl > excl)? incl: excl;
    
         /* current max including i */
         incl = excl + arr[i];
         excl = excl_new;
      }
    
       /* return max of incl and excl */
       return ((incl > excl)? incl : excl);
    }
    
    /* Driver program to test above function */
    int main()
    {
      int arr[] = {5, 5, 10, 100, 10, 5};
      int n = sizeof(arr) / sizeof(arr[0]);
      printf("%d n", FindMaxSum(arr, n));
      return 0;
    }
    


  5. Задача 3
    Вариант решения:
    // Program to find the amount of water in j-th glass
    // of i-th row
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    // Returns the amount of water in jth glass of ith row
    float findWater(int i, int j, float X)
    {
        // A row number i has maximum i columns. So input
        // column number must be less than i
        if (j > i)
        {
            printf("Incorrect Inputn");
            exit(0);
        }
    
        // There will be i*(i+1)/2 glasses till ith row 
        // (including ith row)
        float glass[i * (i + 1) / 2];
    
        // Initialize all glasses as empty
        memset(glass, 0, sizeof(glass));
    
        // Put all water in first glass
        int index = 0;
        glass[index] = X;
    
        // Now let the water flow to the downward glasses 
        // till the row number is less than or/ equal to i (given row) 
        // correction : X can be zero for side glasses as they have lower rate to fill
        for (int row = 1; row <= i ; ++row)
        {
            // Fill glasses in a given row. Number of 
            // columns in a row is equal to row number
            for (int col = 1; col <= row; ++col, ++index)
            {
                // Get the water from current glass
                X = glass[index];
    
                // Keep the amount less than or equal to
                // capacity in current glass
                glass[index] = (X >= 1.0f) ? 1.0f : X;
    
                // Get the remaining amount
                X = (X >= 1.0f) ? (X - 1) : 0.0f;
    
                // Distribute the remaining amount to 
                // the down two glasses
                glass[index + row] += X / 2;
                glass[index + row + 1] += X / 2;
            }
        }
    
        // The index of jth glass in ith row will 
        // be i*(i-1)/2 + j - 1
        return glass[i*(i-1)/2 + j - 1];
    }
    
    // Driver program to test above function
    int main()
    {
        int i = 2, j = 2;
        float X = 2.0; // Total amount of water
    
        printf("Amount of water in jth glass of ith row is: %f",
                findWater(i, j, X));
    
        return 0;
    }
    


Tags: spiceitзанимательные задачиitренировка
Hubs: Spice IT Recruitment corporate blog Entertaining tasks Programming
Total votes 7: ↑6 and ↓1 +5
Comments 27
Comments Comments 27

Top of the last 24 hours

Information

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