Привет! Надеемся, вы на УРА отдохнули в новогодние праздники.

image

А мы вот времени зря не теряли и подготовили новую подборку вопросов и задач. Сегодня — задачки с собеседований в VMWare. VMware — американская компания, крупнейший разработчик программного обеспечения для виртуализации. Штаб-квартира расположена в Пало-Альто, Калифорния. Ну что, проверим ваши шансы пройти у них собеседования?

Кстати, ответы на предыдущие задачки уже опубликованы! Сверяйтесь с ними.

Вопросы


1. 1000 Coins and 10 Bags
A dealer has 1000 coins and 10 bags. He has to divide the coins over the ten bags, so that he can make any number of coins simply by handing over a few bags. How must divide his money into the ten bags?

Перевод
У продавца 1000 монет и 10 сумок. Он должен разложить монеты в десять сумок так, чтобы он смог набрать любое количество монет, просто взяв несколько сумок. Как разделить монеты на десять сумок?

2. Maximize probability of White Ball
There are two empty bowls in a room. You have 50 white balls and 50 black balls. After you place the balls in the bowls, a random ball will be picked from a random bowl. Distribute the balls (all of them) into the bowls to maximize the chance of picking a white ball.

Перевод
В комнате две пустые чаши. У вас есть 50 белых шаров и 50 черных шаров. После того, как вы поместите шары в чаши, из случайной чаши будет выбран случайный шар. Распределите все шары по чашам, чтобы максимально увеличить вероятность выбора белого шара.

Задачи


1. Sieve of Eratosthenes
Given a number N, calculate the prime numbers upto N using Sieve of Eratosthenes.

Input:
The first line of the input contains T denoting the number of testcases. T testcases follow. Each testcase contains one line of input containing N.

Output:
For all testcases, in a new line, print all the prime numbers upto or equal to N.

Constraints:
1 <= T<= 100
1 <= N <= 104

Example:
Input:
2
10
35
Output:
2 3 5 7
2 3 5 7 11 13 17 19 23 29 31

Перевод
Дано число N, вычислите простые числа до N, используя Решето Эратосфена.

Входные данные:
Первая строка ввода содержит T, обозначающее количество тестов. Каждый тест содержит одну строку ввода, содержащую N.

Выход:
Для всех тестов в новой строке выведите все простые числа до или равные N.

Ограничения:
1 <= T <= 100
1 <= N <= 104

Пример:
Входные данные:
2
10
35
Выход:
2 3 5 7
2 3 5 7 11 13 17 19 23 29 31

2. Maximum Node Level
Find the level in a binary tree which has the maximum number of nodes. The root is at level 0.

Input:
The first line consists of T test cases. The first line of every test case consists of N, denoting the number of edges in the tree. The second and third line of every test case consists of N, nodes of the binary tree.

Output:
Print the level number with maximum nodes.

Constraints:
1<=T<=100
1<=N<=100

Example:
Input:
2
3
1 2 L 1 3 R 2 4 L
3
1 3 L 1 2 R 2 4 R

Output:
1
1

Перевод
Найдите уровень в двоичном дереве, в котором есть максимальное количество узлов. Корень находится на уровне 0.

Входные данные:
Первая строка — количество тестов T. Первая строка каждого теста состоит из N, обозначающего количество ребер в дереве. Вторая и третья строка каждого теста состоит из N узлов двоичного дерева.

Выход:
Выведите номер уровня с максимальным количеством узлов.

Ограничения:
1 <= Т <= 100
1 <= N <= 100

Пример:
Входные данные:
2
3
1 2 L 1 3 R 2 4 L
3
1 3 L 1 2 R 2 4 R

Выход:
1
1

3. Kth smallest element
Given an array arr[] and a number K where K is smaller than size of array, the task is to find the Kth smallest element in the given array. It is given that all array elements are distinct.

Input:
The first line of input contains an integer T, denoting the number of testcases. Then T test cases follow. Each test case consists of three lines. First line of each testcase contains an integer N denoting size of the array. Second line contains N space separated integer denoting elements of the array. Third line of the test case contains an integer K.

Output:
Corresponding to each test case, print the kth smallest element in a new line.

Constraints:
1 <= T <= 100
1 <= N <= 105
1 <= arr[i] <= 105
1 <= K <= N

Example:
Input:
2
6
7 10 4 3 20 15
3
5
7 10 4 20 15
4

Output:
7
15

Explanation:
Testcase 1: 3rd smallest element in the given array is 7.

Перевод
Дан массив arr[] и число K, где K меньше размера массива. Задача состоит в том, чтобы найти K-й наименьший элемент в данном массиве. Все элементы массива различны.

Входные данные:
Первая строка ввода содержит целое число T, обозначающее количество тестов. Затем следуют тесты T. Каждый тестовый набор состоит из трех строк. Первая строка каждого теста содержит целое число N, обозначающее размер массива. Вторая строка содержит N разделенных пробелом целых чисел, обозначающих элементы массива. Третья строка теста содержит целое число K.

Выход:
В соответствии с каждым тестовым примером выведите k-й наименьший элемент в новой строке.

Ограничения:
1 <= T <= 100
1 <= N <= 105
1 <= обр [я] <= 105
1 <= K <= N

Пример:
Входные данные:
2
6
7 10 4 3 20 15
3
5
7 10 4 20 15
4

Выход:
7
15

Объяснение:
Тест 1: 3-й самый маленький элемент в данном массиве равен 7.

Ответы


Вопрос 1
Мы можем представить любое десятичное число в качестве весов двоичной системы. Например, если мы хотим измерить до 7, достаточно первых трех сумок.
1 = 2^0
2 = 2^1
3 = 2^0 + 2^1
4 = 2^2
5 = 2^2 + 2^0
6 = 2^2 + 2^1
7 = 2^2 + 2^1 + 2^0
...
Это может быть легко обобщено. Мы можем измерить до 2 ^ n - 1.

Соответственно, ответ таков:
1 сумка = 1 монета.
2 сумка = 2 монеты.
3 сумка = 4 монеты.
4 сумка = 8 монет.
5 сумка = 16 монет.
6 сумка = 32 монеты.
7 сумка = 64 монеты.
8 сумка = 128 монет.
9 сумка = 256 монет.
10 сумка = 489 монет (остаток).

Вопрос 2
Во-первых, давайте предположим, что мы разделили шары на банки одинаково, чтобы каждая банка содержала 50 шаров.
Таким образом, вероятность выбора белого шара будет равна = вероятность выбора первой банки * вероятность появления белого шара в первой банке + вероятность выбора второй банки * вероятность появления белого шара во второй банке
(1/2) * (0/50) + (1/2) * (50/50) = 0,5
Так как мы должны максимизировать вероятность, мы увеличим вероятность белого шара в первой банке и оставим вторую вероятность такой же средней, равной 1.
поэтому мы добавляем 49 белых шаров с 50 черными шарами в первой банке и только один белый шар во второй банке
так что вероятность будет сейчас
(1/2)*(49/99)+(1/2)*(1/1)=0.747
Следовательно, вероятность получения белого шара становится 1/2 * 1 + 1/2 * 49/99, что составляет примерно 3/4.

Задача 1
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
{
    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int test = in.nextInt();
        while (test > 0)
        {
            int num = in.nextInt();
            for (int i = 2; i <= num; i++)
            {
                int temp = 0;
                for (int j = 2; j <= Math.sqrt(i); j++)
                {

                    if (i % j == 0)
                    {
                        temp = 1;
                        break;
                    }

                }
                if (temp == 0)
                {
                    System.out.print(i + " ");
                }
            }
            System.out.println();

            test--;
        }
    }
}

Задача 2
class GfG
{
    public static int maxNodeLevel(Node node)
    {
        Queue<Node> q = new LinkedList<>();
        if (node == null)
            return 0;
        q.add(node);
        int max = 0;
        int level = 0;
        int x = 0;
        while (!q.isEmpty())
        {
            int size = q.size();
            if (max < size)
            {
                max = size;
                level = x;
            }
            for (int i = 0; i < size; i++)
            {
                Node curr = q.remove();
                if (curr.left != null)
                    q.add(curr.left);
                if (curr.right != null)
                    q.add(curr.right);
            }
            x++;
        }
        return level;
    }
}

Задача 3
using namespace std;
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n, k;
        cin >> n;
        int a[n];
        for (int i = 0; i < n; i++)
        {
            cin >> a[i];
        }
        int max = a[0], min = a[0];
        for (int i = 0; i < n; i++)
        {
            if (a[i] > max)
                max = a[i];
            if (a[i] < min)
                min = a[i];
        }
        int s = max - min + 1;
        int h[s] = { 0 };
        for (int i = 0; i < n; i++)
        {
            a[i] -= min;
        }

        for (int i = 0; i < n; i++)
        {
            h[a[i]]++;
        }
        cin >> k;
        for (int i = 0; i < s; i++)
        {
            if (h[i] >= 1)
            {
                k--;
            }
            if (k == 0)
            {
                cout << i + min << endl;
                break;
            }
        }
    }
    return 0;
}