А мы вот времени зря не теряли и подготовили новую подборку вопросов и задач. Сегодня — задачки с собеседований в 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?
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.
Задачи
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
Входные данные:
Первая строка ввода содержит 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
Входные данные:
Первая строка — количество тестов 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.
Входные данные:
Первая строка ввода содержит целое число 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.
Ответы на задачи будут даны в течение следующей недели — успейте решить. Удачи!
Lofty
Вопрос с Решетом Эратосфена странный, мне кажется не вполне правильно включать в собеседование задачи, успех решения которых зависит только от знания такого не особо часто применимого алгоритма.