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

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

Reading time 8 min
Views 12K
Мы подготовили новый выпуск ITренировки с вопросами и задачами от ведущих IT-компаний.

КДПВ

В подборку попали вопросы, встречающиеся на собеседованиях в Adobe (да, вопрос про цвет включён в подборку :). Задачи различного уровня сложности, но все решаемые. Особенно, если Вы уже ответили на вопросы из прошлых выпусков.

Надеемся, что приведённые задачи помогут Вам качественно подготовиться к предстоящим собеседованиями.

Вопросы


  1. 8 marbles
    Let’s say you have 8 marbles and a two-pan balance.
    All of the marbles look the same. Each marble weighs 2.0 grams except for one, which is slightly heavier at 2.05 grams.
    How would you find the heaviest marble if you are only allowed to weigh the marbles 2 times using the balance scale?

    Перевод
    Предположим, у вас 8 стеклянных шариков и чашечные весы. Все шарики выглядят одинаково. Каждый весит 2 грамма, за исключением одного, который чуть тяжелее — 2.05 грамма.
    Как найти самый тяжёлый шарик, если разрешено провести всего 2 взвешивания?

  2. Falling bear
    A bear fell from a height of 10m on the ground in √2 seconds. But somehow, it didn’t get hurt. What is the colour of bear?

    Перевод
    Медведь, падая с высоты 10м, достигает земли за √2 seconds и, почему-то, остаётся без повреждений. Какого цвета медведь?

    Прим: Я некоторое время подумал, и всё-таки заглянул в ответ. Вопрос немного с подвохом, но ответить можно. Решил привести здесь, если такое на собеседованиях встречается.

Задачи


  1. Product of max and min in 2 arrays
    Given two arrays of integers, the task is to calculate the product of max element of first array and min element of second array.

    Ex:
    Input: arr1[] = {5, 7, 9, 3, 6, 2},
    arr2[] = {1, 2, 6, -1, 0, 9}
    Output: max element in first array
    is 9 and min element in second array
    is -1. The product of these two is -9.

    Input: arr1[] = {1, 4, 2, 3, 10, 2},
    arr2[] = {4, 2, 6, 5, 2, 9}
    Output: 20.

    Перевод
    Даны 2 массива целых чисел. Задача — вычислить произведение максимального элемента из первого массива и минимального из второго массива.

    Примеры:
    Даны: arr1[] = {5, 7, 9, 3, 6, 2}, arr2[] = {1, 2, 6, -1, 0, 9}
    Ответ: максимальный элемент первого массива — 9, минимальный элемент второго -1. Произведение -9.

    Даны: arr1[] = {1, 4, 2, 3, 10, 2},
    arr2[] = {4, 2, 6, 5, 2, 9}
    Ответ: 20.

  2. Maximum Chocolates
    You have $15 with you. You go to a shop and shopkeeper tells you price as $1 per chocolate. He also tells you that you can get a chocolate in return of 3 wrappers. How many maximum chocolates you can eat?

    Write a program to find solution for variable inputs. Given following three values, the task is to find the total number of maximum chocolates you can eat.

    money: Money you have to buy chocolates
    price: Price of a chocolate
    wrap: Number of wrappers to be returned for getting one extra chocolate.

    It may be assumed that all given values are positive integers and greater than 1.

    Перевод
    У Вас есть $15. В магазине у продавца Вы узнаёте цену за шоколадку — $1. Продавец также сообщает, что за 3 обертки выдаст вам ещё шоколадку. На какой максимум шоколадок Вы можете рассчитывать?

    Напишите программу для переменных входных данных, задачей которой будет найти максимум шоколадок:

    money: Имеющиеся деньги
    price: Цена за шоколадку
    wrap: Количество обёрток нужное, чтобы получить ещё одну шоколадку.

    Можно считать, что все входные данные являются целыми и больше 1.

  3. Sort array larger than RAM
    Given 2 machines, each having 64 GB RAM, containing all integers (8 byte). You need to sort the entire 128 GB data. You may assume a small amount of additional RAM.

    Перевод
    Имеются 2 компьютера, у каждого по 64 Гб ОЗУ, занятых целыми числами (8 байт). Вам необходимо отсортировать все 128 Гб данных. Можно использовать небольшое количество дополнительной памяти ОЗУ.


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

Решения


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

  2. Вопрос 2
    В оригинале, цвет медведя — белый, поскольку он падал с ускорением 10 м/c2, что может быть на полюсах. Правильное решение было найдено, и предложено несколько альтернативных :)

  3. Задача 1

    Решение с сортировкой массивов не является оптимальным. Простой проход по массивам в поисках min/max лучше:
    // C++ program to find the to calculate
    // the product of max element of first 
    // array and min element of second array
    #include <bits/stdc++.h>
    using namespace std;
     
    // Function to calculate the product
    int minMaxProduct(int arr1[], int arr2[], 
                             int n1, int n2)
    {
        // Initialize max of first array
        int max = arr1[0];
     
        // initialize min of second array
        int min = arr2[0];
     
        int i;
        for (i = 1; i < n1 && i < n2; ++i) {
     
            // To find the maximum element 
            // in first array
            if (arr1[i] > max)
                max = arr1[i];
     
            // To find the minimum element
            // in second array
            if (arr2[i] < min)
                min = arr2[i];
        }
      
        // Process remaining elements
        while (i < n1)
        {
            if (arr1[i] > max)
               max = arr1[i];  
            i++;
        }
        while (i < n2)
        {
            if (arr2[i] < min)
               min = arr2[i];  
            i++;
        }
     
        return max * min;
    }
     
    // Driven code
    int main()
    {
        int arr1[] = { 10, 2, 3, 6, 4, 1 };
        int arr2[] = { 5, 1, 4, 2, 6, 9 };
        int n1 = sizeof(arr1) / sizeof(arr1[0]);
        int n2 = sizeof(arr1) / sizeof(arr1[0]);
        cout << minMaxProduct(arr1, arr2, n1, n2) << endl;
        return 0;
    }


  4. Задача 2
    Решение с рекурсией — не самое оптимальное в данном случае. В оригинальном решении путём наблюдения была выведена формула totalChoc = (choc-1)/(wrap-1) и программа в таком случае приняла вид:
    // Efficient C++ program to find maximum
    // number of chocolates
    #include <iostream>
    using namespace std;
     
    // Returns maximum number of chocolates we can eat
    // with given money, price of chocolate and number
    // of wrapprices required to get a chocolate.
    int countMaxChoco(int money, int price, int wrap)
    {
        // Corner case
        if (money < price)
           return 0;
     
        // First find number of chocolates that
        // can be purchased with the given amount
        int choc = money / price;
     
        // Now just add number of chocolates with the
        // chocolates gained by wrapprices
        choc = choc + (choc - 1) / (wrap - 1);
        return choc;
    }
     
    // Driver code
    int main()
    {
        int money = 15 ; // total money
        int price = 1; // cost of each candy
        int wrap = 3 ; // no of wrappers needs to be
        // exchanged for one chocolate.
     
        cout << countMaxChoco(money, price, wrap);
        return 0;
    }
    


  5. Задача 3
    В качестве решения задачи предлагается External merge sort:

    // C++ program to implement external sorting using 
    // merge sort
    #include <bits/stdc++.h>
    using namespace std;
     
    struct MinHeapNode
    {
        // The element to be stored
        int element;
     
        // index of the array from which the element is taken
        int i;
    };
     
    // Prototype of a utility function to swap two min heap nodes
    void swap(MinHeapNode* x, MinHeapNode* y);
     
    // A class for Min Heap
    class MinHeap
    {
        MinHeapNode* harr; // pointer to array of elements in heap
        int heap_size;     // size of min heap
     
    public:
        // Constructor: creates a min heap of given size
        MinHeap(MinHeapNode a[], int size);
     
        // to heapify a subtree with root at given index
        void MinHeapify(int);
     
        // to get index of left child of node at index i
        int left(int i) { return (2 * i + 1); }
     
        // to get index of right child of node at index i
        int right(int i) { return (2 * i + 2); }
     
        // to get the root
        MinHeapNode getMin() {  return harr[0]; }
     
        // to replace root with new node x and heapify()
        // new root
        void replaceMin(MinHeapNode x)
        {
            harr[0] = x;
            MinHeapify(0);
        }
    };
     
    // Constructor: Builds a heap from a given array a[]
    // of given size
    MinHeap::MinHeap(MinHeapNode a[], int size)
    {
        heap_size = size;
        harr = a; // store address of array
        int i = (heap_size - 1) / 2;
        while (i >= 0)
        {
            MinHeapify(i);
            i--;
        }
    }
     
    // A recursive method to heapify a subtree with root
    // at given index. This method assumes that the
    // subtrees are already heapified
    void MinHeap::MinHeapify(int i)
    {
        int l = left(i);
        int r = right(i);
        int smallest = i;
        if (l < heap_size && harr[l].element < harr[i].element)
            smallest = l;
        if (r < heap_size && harr[r].element < harr[smallest].element)
            smallest = r;
        if (smallest != i)
        {
            swap(&harr[i], &harr[smallest]);
            MinHeapify(smallest);
        }
    }
     
    // A utility function to swap two elements
    void swap(MinHeapNode* x, MinHeapNode* y)
    {
        MinHeapNode temp = *x;
        *x = *y;
        *y = temp;
    }
     
    // Merges two subarrays of arr[].
    // First subarray is arr[l..m]
    // Second subarray is arr[m+1..r]
    void merge(int arr[], int l, int m, int r)
    {
        int i, j, k;
        int n1 = m - l + 1;
        int n2 = r - m;
     
        /* create temp arrays */
        int L[n1], R[n2];
     
        /* Copy data to temp arrays L[] and R[] */
        for(i = 0; i < n1; i++)
            L[i] = arr[l + i];
        for(j = 0; j < n2; j++)
            R[j] = arr[m + 1 + j];
     
        /* Merge the temp arrays back into arr[l..r]*/
        i = 0; // Initial index of first subarray
        j = 0; // Initial index of second subarray
        k = l; // Initial index of merged subarray
        while (i < n1 && j < n2)
        {
            if (L[i] <= R[j])
                arr[k++] = L[i++];
            else
                arr[k++] = R[j++];
        }
     
        /* Copy the remaining elements of L[], if there
           are any */
        while (i < n1)
            arr[k++] = L[i++];
     
        /* Copy the remaining elements of R[], if there
           are any */
        while(j < n2)
            arr[k++] = R[j++];
    }
     
    /* l is for left index and r is right index of the
       sub-array of arr to be sorted */
    void mergeSort(int arr[], int l, int r)
    {
        if (l < r)
        {
            // Same as (l+r)/2, but avoids overflow for
            // large l and h
            int m = l + (r - l) / 2;
     
            // Sort first and second halves
            mergeSort(arr, l, m);
            mergeSort(arr, m + 1, r);
     
            merge(arr, l, m, r);
        }
    }
     
    FILE* openFile(char* fileName, char* mode)
    {
        FILE* fp = fopen(fileName, mode);
        if (fp == NULL)
        {
            perror("Error while opening the file.\n");
            exit(EXIT_FAILURE);
        }
        return fp;
    }
     
    // Merges k sorted files.  Names of files are assumed
    // to be 1, 2, 3, ... k
    void mergeFiles(char *output_file, int n, int k)
    {
        FILE* in[k];
        for (int i = 0; i < k; i++)
        {
            char fileName[2];
     
            // convert i to string
            snprintf(fileName, sizeof(fileName), "%d", i);
     
            // Open output files in read mode.
            in[i] = openFile(fileName, "r");
        }
     
        // FINAL OUTPUT FILE
        FILE *out = openFile(output_file, "w");
     
        // Create a min heap with k heap nodes.  Every heap node
        // has first element of scratch output file
        MinHeapNode* harr = new MinHeapNode[k];
        int i;
        for (i = 0; i < k; i++)
        {
            // break if no output file is empty and
            // index i will be no. of input files
            if (fscanf(in[i], "%d ", &harr[i].element) != 1)
                break;
     
            harr[i].i = i; // Index of scratch output file
        }
        MinHeap hp(harr, i); // Create the heap
     
        int count = 0;
     
        // Now one by one get the minimum element from min
        // heap and replace it with next element.
        // run till all filled input files reach EOF
        while (count != i)
        {
            // Get the minimum element and store it in output file
            MinHeapNode root = hp.getMin();
            fprintf(out, "%d ", root.element);
     
            // Find the next element that will replace current
            // root of heap. The next element belongs to same
            // input file as the current min element.
            if (fscanf(in[root.i], "%d ", &root.element) != 1 )
            {
                root.element = INT_MAX;
                count++;
            }
     
            // Replace root with next element of input file
            hp.replaceMin(root);
        }
     
        // close input and output files
        for (int i = 0; i < k; i++)
            fclose(in[i]);
     
        fclose(out);
    }
     
    // Using a merge-sort algorithm, create the initial runs
    // and divide them evenly among the output files
    void createInitialRuns(char *input_file, int run_size,
                           int num_ways)
    {
        // For big input file
        FILE *in = openFile(input_file, "r");
     
        // output scratch files
        FILE* out[num_ways];
        char fileName[2];
        for (int i = 0; i < num_ways; i++)
        {
            // convert i to string
            snprintf(fileName, sizeof(fileName), "%d", i);
     
            // Open output files in write mode.
            out[i] = openFile(fileName, "w");
        }
     
        // allocate a dynamic array large enough
        // to accommodate runs of size run_size
        int* arr = (int*)malloc(run_size * sizeof(int));
     
        bool more_input = true;
        int next_output_file = 0;
     
        int i;
        while (more_input)
        {
            // write run_size elements into arr from input file
            for (i = 0; i < run_size; i++)
            {
                if (fscanf(in, "%d ", &arr[i]) != 1)
                {
                    more_input = false;
                    break;
                }
            }
     
            // sort array using merge sort
            mergeSort(arr, 0, i - 1);
     
            // write the records to the appropriate scratch output file
            // can't assume that the loop runs to run_size
            // since the last run's length may be less than run_size
            for (int j = 0; j < i; j++)
                fprintf(out[next_output_file], "%d ", arr[j]);
     
            next_output_file++;
        }
     
        // close input and output files
        for (int i = 0; i < num_ways; i++)
            fclose(out[i]);
     
        fclose(in);
    }
     
    // For sorting data stored on disk
    void externalSort(char* input_file,  char *output_file,
                      int num_ways, int run_size)
    {
        // read the input file, create the initial runs,
        // and assign the runs to the scratch output files
        createInitialRuns(input_file, run_size, num_ways);
     
        // Merge the runs using the K-way merging
        mergeFiles(output_file, run_size, num_ways);
    }
     
     
    // Driver program to test above
    int main()
    {
        // No. of Partitions of input file.
        int num_ways = 10;
     
        // The size of each partition
        int run_size = 1000;
     
        char input_file[] = "input.txt";
        char output_file[] = "output.txt";
     
        FILE* in = openFile(input_file, "w");
     
        srand(time(NULL));
     
        // generate input
        for (int i = 0; i < num_ways * run_size; i++)
            fprintf(in, "%d ", rand());
     
        fclose(in);
     
        externalSort(input_file, output_file, num_ways,
                    run_size);
     
        return 0;
    }


Tags:
Hubs:
+15
Comments 55
Comments Comments 55

Articles

Information

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