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

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

Reading time 4 min
Views 9.5K
Мы подобрали новую порцию вопросов и задач, встречающихся соискателям на собеседованиях в ведущие ИТ-компании мира.

КДПВ

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

Вопросы


  1. Black and white balls
    You have 20 white and 13 black balls in a bag. You pull out 2 balls one after another. If the balls are of same color, then you replace them with a white ball – but if they are of different color, you replace them with a black ball. Once you take out the balls, you do not put them back in the bag – so the balls keep reducing. What would be the color of the last ball remaining in the bag?

    Перевод
    У Вас в мешке 20 белых и 13 черных шаров. Вы последовательно вытягиваете по 2 шара. Если они одного цвета — тогда вы заменяете их белым шаром, если же они разных цветов — вы заменяете их черным шаром. Шары в мешок не возвращаются, поэтому их количество там убывает. Каким будет цвет последнего оставшего в мешке шара?

  2. Count the eggs
    The man who delivers eggs to my home everyday, did not turn up one day. So when he came the next morning I demanded an explanation from him. He told me the following story:
    The previous morning when he just came out of the house carrying a basket full of eggs on his head to start his daily rounds and stepped on to the street, a car going full speed brushed against him and knocked down his basket destroying all the eggs. The driver, however, a thorough gentleman admitted his responsibility and offered to compensate him for damages. But peddler could not remember the exact number of eggs he had, but he estimated the number at between 50 and 100. He was also able to tell the gentleman that if the eggs were counted by 2’s and 3’s at a time, none would be left, but if counted by 5’s at a time, 3 would remain, and that he sold the eggs at 10 cent a piece. The gentleman made some quick calculations and paid peddler adequately.
    How much did the gentleman pay for eggs?

    Перевод
    Однажды разносчик, который приносит ежедневно мне свежие яйца, не пришёл. Он появился на следующий день и я попросил его объяснить причину отсутствия. Он рассказал следующую историю:
    Накануне утром он вышел из дома с корзиной, полной яиц, чтобы сделать ежедневный обход улицы. Рядом с ним промчалась на полной скорости машина и задела корзину, так, что все яйца разбились. Водитель, однако, оказался джентельменом и предложил оплатить ущерб. Разносчик не мог вспомнить точное количество яиц в корзине, только то, что их было от 50 до 100. Он также припомнил, что если выбрать по 2 или по 3 яйца, то яиц в корзине бы не осталось, а если по 5, то должно было остаться 3 яйца. Он продавал яйца по 10 центов за штуку. Автомобилист быстро посчитал в уме и отдал разносчику точную сумму за разбитые яйца. Сколько он заплатил?


Задачи


  1. Find median in row wise sorted matrix
    We are given a row wise sorted matrix of size r*c, we need to find the median of the matrix given. It is assumed that r*c is always odd.

    Examples:

    Input:
    1 3 5
    2 6 9
    3 6 9
    Output: Median is 5
    If we put all the values in a sorted array A[] = 1 2 3 3 5 6 6 9 9

    Input:
    1 3 4
    2 5 6
    7 8 9
    Output: Median is 5

    Перевод
    Дана матрица с элементами, отсортированными построчно, размера r*c. Нам необходимо найти медиану матрицы. Предполагается, что r*c всегда нечётное.
    Примеры

    Вход:
    1 3 5
    2 6 9
    3 6 9
    Выход: Медиана — 5
    В виде отсортированного массива: A[] = 1 2 3 3 5 6 6 9 9

    Input:
    1 3 4
    2 5 6
    7 8 9
    Output: Медиана — 5

  2. Smallest single digit expression
    Given a number N and a digit D, we have to form an expression or equation that contains only D and that expression evaluates to N. Allowed operators in expression are +, -, *, and /. Find the minimum length expression that satisfy the condition above and D can only appear in the expression at most 10(limit) times.

    Examples:

    Input: N = 7, D = 3
    Output: 3/3+ 3 + 3
    Explanation: 3/3 = 1, and 1+3+3 = 7
    This is the minimum expression.

    Input: N = 7, D = 4
    Output: (4+4+4)/4 + 4
    Explanation: (4+4+4) = 12, and 12/4 = 3 and 3+4 = 7
    Also this is the minimum expression. Although
    you may find another expression but that
    expression can have only five 4's

    Input: N = 200, D = 9
    Output: Expression not found!
    Explanation: Not possible within 10 digits.

    Перевод
    Дано число N и цифра D. Небходимо составить выражение, дающее в результате N и содержащее только D. Допустимы операции +, -, *, /. Необходимо найти выражение минимальной длины, удовлетворяющее условия, с учётом того, что D может встречаться в выражении не более 10 раз.

    Ввод: N = 7, D = 3
    Вывод: 3/3+ 3 + 3
    Объяснение: 3/3 = 1, and 1+3+3 = 7

    Ввод: N = 7, D = 4
    Вывод: (4+4+4)/4 + 4
    Объяснение: (4+4+4) = 12, and 12/4 = 3 and 3+4 = 7

    Ввод: N = 200, D = 9
    Вывод: Expression not found!
    Объяснение: Невозможно выполнить с ограничением в 10 цифр.

    Прим.: третий пример выглядит как вызов

  3. Minimum swaps to bring them all together
    Given an array of n positive integers and a number k. Find the minimum number of swaps required to bring all the numbers less than or equal to k together.

    Input: arr[] = {2, 1, 5, 6, 3}, k = 3
    Output: 1

    Explanation:
    To bring elements 2, 1, 3 together, swap element '5' with '3' such that final array will be:
    arr[] = {2, 1, 3, 6, 5}

    Input: arr[] = {2, 7, 9, 5, 8, 7, 4}, k = 5
    Output: 2

    Перевод
    Дан массив n целых положительных чисел и число k. Найти количество перестановок, необходимое, чтобы собрать все элементны, меньшие или равные k, рядом.

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

    Объяснение:
    Достаточно поменять 5 и 3 местами:
    arr[] = {2, 1, 3, 6, 5}

    Вход: arr[] = {2, 7, 9, 5, 8, 7, 4}, k = 5
    Выход: 2


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

Решения


  1. Вопрос 1
    Должен остаться черный шар, ответ был найден верно

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

  3. Задача 1
    Простой подход — поместить все элементы матрицы в отсортированных массив и найти медиану. Сложность по времеи и месту — O(r*c).

    Эффективное решение — использовать бинарный поиск. Идея заключается в том, что перед медианой должно быть ровно n/2 чисел, которые меньше, решение было предложено в комментарии.

    Исходный вариант решения:

    // C++ program to find median of a matrix
    // sorted row wise
    #include<bits/stdc++.h>
    using namespace std;
     
    const int MAX = 100;
     
    // function to find median in the matrix
    int binaryMedian(int m[][MAX], int r ,int c)
    {
        int min = INT_MAX, max = INT_MIN;
        for (int i=0; i<r; i++)
        {
            // Finding the minimum element
            if (m[i][0] < min)
                min = m[i][0];
     
            // Finding the maximum element
            if (m[i][c-1] > max)
                max = m[i][c-1];
        }
     
        int desired = (r * c + 1) / 2;
        while (min < max)
        {
            int mid = min + (max - min) / 2;
            int place = 0;
     
            // Find count of elements smaller than mid
            for (int i = 0; i < r; ++i)
                place += upper_bound(m[i], m[i]+c, mid) - m[i];
            if (place < desired)
                min = mid + 1;
            else
                max = mid;
        }
        return min;
    }
     
    // driver program to check above functions
    int main()
    {
        int r = 3, c = 3;
        int m[][MAX]= { {1,3,5}, {2,6,9}, {3,6,9} };
        cout << "Median is " << binaryMedian(m, r, c) << endl;
        return 0;
    }
    


  4. Задача 2
    Вариант решения в комментарии

  5. Задача 3
    Вариант решения в комментарии

Tags:
Hubs:
+9
Comments 42
Comments Comments 42

Articles

Information

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