Привет-привет! Мы вновь подготовили Вам подборку интересных вопросов и задачек с собеседований в ведущие IT-компании! Кстати, ответы на задачки из прошлого выпуска уже опубликованы.
![](https://habrastorage.org/r/w1560/webt/v4/uw/-3/v4uw-3tbna7tdnl7qkhwhtcjlee.png)
Выпуски будут появляться каждую неделю — следите за обновлениями! Рубрика выходит при поддержке рекрутингового агентства Spice IT.
На этой неделе мы собрали задачи с собеседований в Нидерландскую компанию Philips.
1. Poison and Rat
2. 5 Pirates and 100 Gold Coins
1. Factorials of large numbers
2. Diameter of Binary Tree
3. Black and White
![](https://habrastorage.org/webt/v4/uw/-3/v4uw-3tbna7tdnl7qkhwhtcjlee.png)
Выпуски будут появляться каждую неделю — следите за обновлениями! Рубрика выходит при поддержке рекрутингового агентства Spice IT.
На этой неделе мы собрали задачи с собеседований в Нидерландскую компанию Philips.
Вопросы
1. Poison and Rat
There are 1000 wine bottles. One of the bottles contains poisoned wine. A rat dies one hour after drinking the poisoned wine. How many minimum rats are needed to figure out which bottle contains poison in hour.
Перевод
Есть 1000 бутылок вина. Одна из бутылок содержит отравленное вино. Крыса умирает через час после того, как выпьет отравленное вино. Сколько минимум крыс нужно, чтобы за час выяснить, какая бутылка содержит яд.
2. 5 Pirates and 100 Gold Coins
There are 5 pirates, they must decide how to distribute 100 gold coins among them. The pirates have seniority levels, the senior-most is A, then B, then C, then D, and finally the junior-most is E.
Rules of distribution are:
- The most senior pirate proposes a distribution of coins.
- All pirates vote on whether to accept the distribution.
- If the distribution is accepted, the coins are disbursed and the game ends.
- If not, the proposer is thrown and dies, and the next most senior pirate makes a new proposal to begin the system again.
- In case of a tie vote the proposer can has the casting vote
Rules every pirates follows:
- Every pirate wants to survive
- Given survival, each pirate wants to maximize the number of gold coins he receives.
What is the maximum number of coins that pirate A might get?
Перевод
Есть 5 пиратов, они должны решить, как распределить 100 золотых монет между ними. У пиратов есть уровни старшинства, самый старший — это A, затем B, затем C, затем D, и, наконец, самый младший — это E.
Правила распределения монет таковы:
Правила, которым следуют все пираты:
Какое максимальное количество монет может получить пират А?
Правила распределения монет таковы:
- Самый старший пират предлагает разделение монет. (сколько монет получит каждый)
- Все пираты голосуют за то, чтобы принять разделение монет.
- Если разделение монет принимается, монеты выплачиваются и игра заканчивается.
- Если нет, то претендент выбрасывается и умирает, а следующий самый старший пират делает новое предложение, чтобы начать систему снова.
- В случае равенства голосов кандидат может иметь решающий голос.
Правила, которым следуют все пираты:
- Каждый пират хочет выжить.
- Учитывая выживание, каждый пират хочет максимизировать количество золотых монет, которые он получает.
Какое максимальное количество монет может получить пират А?
Задачи
1. Factorials of large numbers
Given an integer, the task is to find factorial of the number.
Input:
The first line of input contains an integer T denoting the number of test cases.
The first line of each test case is N,the number whose factorial is to be found
Output:
Print the factorial of the number in separate line.
Constraints:
1 ≤ T ≤ 100
1 ≤ N ≤ 1000
Example:
Input
3
5
10
2
Output
120
3628800
2
Перевод
Есть целое число, задача состоит в том, чтобы найти факториал этого числа.
Ввод:
Первая строка входных данных содержит целое число T, обозначающее количество тестов.
Первая строка каждого теста — N, число, факториал которого должен быть найден
Выход:
Выведите факториал числа в отдельной строке.
Ограничения:
Пример:
Ввод
Выход:
Ввод:
Первая строка входных данных содержит целое число T, обозначающее количество тестов.
Первая строка каждого теста — N, число, факториал которого должен быть найден
Выход:
Выведите факториал числа в отдельной строке.
Ограничения:
1 ≤ T ≤ 100
1 ≤ N ≤ 1000
Пример:
Ввод
3
5
10
2
Выход:
120
3628800
2
2. Diameter of Binary Tree
Given a Binary Tree, find diameter of it.
+The diameter of a tree is the number of nodes on the longest path between two leaves in the tree. The diagram below shows two trees each with diameter nine, the leaves that form the ends of a longest path are shaded (note that there is more than one path in each tree of length nine, but no path longer than nine nodes).
Input Format:
First line of input contains the number of test cases T. For each test case, there will be only a single line of input which is a string representing the tree as described below:
1. The values in the string are in the order of level order traversal of the tree where, numbers denotes node values, and a character “N” denotes NULL child.
2. For example:
For the above tree, the string will be: 1 2 3 N N 4 6 N 5 N N 7 N
Output Format:
For each testcase, in a new line, print the diameter.
Your Task:
You need to complete the function diameter() that takes node as parameter and returns the diameter.
Constraints:
1 <= T <= 100
1 <= Number of nodes <= 100
1 <= Data of a node <= 100
Example:
Input:
2
1 2 3
10 20 30 40 60
Output:
3
4
Explanation:
Testcase1: The tree is
The diameter is of 3 length.
Testcase2: The tree is
The diameter is of 4 length.
Перевод
Есть бинарное дерево, найдите его диаметр.
+ Диаметр дерева — это число узлов на самом длинном пути между двумя листьями дерева. На диаграмме ниже показаны два дерева, каждое диаметром девять, листья, образующие концы длинного пути, затенены (обратите внимание, что в каждом дереве длиной девять есть более одного пути, но нет пути длиннее девяти узлов).
![](https://habrastorage.org/r/w1560/webt/wi/zr/yb/wizrybgkdmujf90pt35gbhxczgq.png)
Входной формат:
Первая строка ввода содержит количество тестов T. Для каждого теста будет только одна строка ввода, представляющая собой строку, представляющую дерево, как описано ниже:
1. Значения в строке находятся в порядке обхода уровня дерева, где числа обозначают значения узлов, а символ “N” обозначает нулевой дочерний элемент.
2. Например:
Для приведенного выше дерева строка будет: 1 2 3 N N 4 6 N 5 N N 7 N
Выходной формат:
Для каждого теста в новой строке выведите диаметр.
Ваша задача:
Вам нужно выполнить функцию diameter(), которая принимает node в качестве параметра и возвращает диаметр.
Ограничения:
Пример:
Ввод:
Выход:
Объяснение:
Тест 1: дерево выглядит так:
![](https://habrastorage.org/r/w1560/webt/p0/vu/vb/p0vuvbnw9l_jaq9lc0-ddwolltk.png)
Диаметр составляет 3.
Тест 2: дерево выглядит так:
![](https://habrastorage.org/r/w1560/webt/hy/8w/u0/hy8wu0wzzhz7h8-p6t-hy3u3ve4.png)
Диаметр составляет 4 длины.
+ Диаметр дерева — это число узлов на самом длинном пути между двумя листьями дерева. На диаграмме ниже показаны два дерева, каждое диаметром девять, листья, образующие концы длинного пути, затенены (обратите внимание, что в каждом дереве длиной девять есть более одного пути, но нет пути длиннее девяти узлов).
![](https://habrastorage.org/webt/wi/zr/yb/wizrybgkdmujf90pt35gbhxczgq.png)
Входной формат:
Первая строка ввода содержит количество тестов T. Для каждого теста будет только одна строка ввода, представляющая собой строку, представляющую дерево, как описано ниже:
1. Значения в строке находятся в порядке обхода уровня дерева, где числа обозначают значения узлов, а символ “N” обозначает нулевой дочерний элемент.
2. Например:
![](https://habrastorage.org/webt/cc/eu/52/cceu52uwfopzizqft8ooc7dk4ia.png)
Для приведенного выше дерева строка будет: 1 2 3 N N 4 6 N 5 N N 7 N
Выходной формат:
Для каждого теста в новой строке выведите диаметр.
Ваша задача:
Вам нужно выполнить функцию diameter(), которая принимает node в качестве параметра и возвращает диаметр.
Ограничения:
1 < = T <= 100
1 < = количество узлов < = 100
1 < = Данные узла <= 100
Пример:
Ввод:
2
1 2 3
10 20 30 40 60
Выход:
3
4
Объяснение:
Тест 1: дерево выглядит так:
![](https://habrastorage.org/webt/p0/vu/vb/p0vuvbnw9l_jaq9lc0-ddwolltk.png)
Диаметр составляет 3.
Тест 2: дерево выглядит так:
![](https://habrastorage.org/webt/hy/8w/u0/hy8wu0wzzhz7h8-p6t-hy3u3ve4.png)
Диаметр составляет 4 длины.
3. Black and White
How many ways are there to place a black and a white knight on an N * M chessboard such that they do not attack each other? The knights have to be placed on different squares. A knight can move two squares horizontally and one square vertically (L shaped), or two squares vertically and one square horizontally (L shaped). The knights attack each other if one can reach the other in one move.
Input:
The first line contains the number of test cases T. Each of the next T lines contains two integers N and M which is size of matrix.
Output:
For each testcase, print the required answer, i.e, number of possible ways to place knights.
Constraints:
1 <= T <= 100
1 <= N, M <= 105
Example:
Input:
3
2 2
2 3
4 5
Output:
12
26
312
Explanation:
Testcase 1: We can place a black and a white knight in 12 possible ways such that none of them attracts each other.
Перевод
Сколько существует способов поставить черного и белого коня на N * M шахматную доску так, чтобы они не нападали друг на друга? Кони должны быть размещены на разных площадях. Конь может перемещаться на два квадрата по горизонтали и один квадрат по вертикали (L-образная форма), или два квадрата по вертикали и один квадрат по горизонтали (L-образная форма). Кони атакуют друг друга, если один из них может добраться до другого за один ход.
Ввод:
Первая строка содержит количество тестов T. Каждая из следующих T строк содержит два целых числа N и M, которые являются размером доски.
Выход:
Для каждого теста выведите требуемый ответ, то есть количество возможных способов размещения рыцарей.
Ограничения:
Пример:
Ввод:
Выход:
Объяснение:
Тест 1: мы можем расположить черного и белого коней 12 возможными способами таким образом, чтобы ни один из них не мог напасть друг на друга.
Ввод:
Первая строка содержит количество тестов T. Каждая из следующих T строк содержит два целых числа N и M, которые являются размером доски.
Выход:
Для каждого теста выведите требуемый ответ, то есть количество возможных способов размещения рыцарей.
Ограничения:
1 < = T <= 100
1 <= N, M < = 105
Пример:
Ввод:
3
2 2
2 3
4 5
Выход:
12
26
312
Объяснение:
Тест 1: мы можем расположить черного и белого коней 12 возможными способами таким образом, чтобы ни один из них не мог напасть друг на друга.
Ответы
Вопрос 1
Мы должны выяснить это в течение часа. Нам нужно 10 крыс, чтобы найти отравленную бутылку. Результат основан на двоичной системе счисления. Мы получаем 10, используя Log2(1000).
Идея состоит в том, чтобы пронумеровать бутылки от 1 до 1000 и написать на бутылке соответствующие им двоичные числа. Каждой крысе присваивается позиция в двоичных числах, написанных на бутылках. Давайте возьмем пример. Крыса 1 представляет первый бит в каждой бутылке, крыса 2 представляет второй бит и так далее. Если крысы с номерами 5, 7 и 9 умирают, то бутылка с номером 42 (двоичная 0000101010) отравлена.
Идея состоит в том, чтобы пронумеровать бутылки от 1 до 1000 и написать на бутылке соответствующие им двоичные числа. Каждой крысе присваивается позиция в двоичных числах, написанных на бутылках. Давайте возьмем пример. Крыса 1 представляет первый бит в каждой бутылке, крыса 2 представляет второй бит и так далее. Если крысы с номерами 5, 7 и 9 умирают, то бутылка с номером 42 (двоичная 0000101010) отравлена.
Вопрос 2
Ответ — 98.
1. Рассмотрим ситуацию, когда A, B и C умирают, остаются только D и E. Е знает, что он ничего не получит (D является старшим и сделает распределение (100, 0). Таким образом, E будет найдено с чем-либо большим, чем 0.
2. Рассмотрим ситуацию, когда A и B умирают, а C, D и E остаются. D знает, что он ничего не получит (C сделает распределение (99, 0, 1), а E проголосует за C).
3. Рассмотрим ситуацию, когда A умирает. B, C, D и E остаются. Чтобы выжить, B нужно дать только 1 монету D. Поэтому распределение (99, 0, 1, 0)
4. Точно так же A знает о пункте 3, поэтому ему просто нужно дать 1 монету C и 1 монету E, чтобы получить их в пользу. Так что распределение-это (98, 0, 1, 0, 1).
Идея основана на том факте, что B распределит, если А умрет (B всегда хотел бы, чтобы a умер). Если A дает больше монет 2 людям, чем B дал бы, то А выигрывает.
1. Рассмотрим ситуацию, когда A, B и C умирают, остаются только D и E. Е знает, что он ничего не получит (D является старшим и сделает распределение (100, 0). Таким образом, E будет найдено с чем-либо большим, чем 0.
2. Рассмотрим ситуацию, когда A и B умирают, а C, D и E остаются. D знает, что он ничего не получит (C сделает распределение (99, 0, 1), а E проголосует за C).
3. Рассмотрим ситуацию, когда A умирает. B, C, D и E остаются. Чтобы выжить, B нужно дать только 1 монету D. Поэтому распределение (99, 0, 1, 0)
4. Точно так же A знает о пункте 3, поэтому ему просто нужно дать 1 монету C и 1 монету E, чтобы получить их в пользу. Так что распределение-это (98, 0, 1, 0, 1).
Идея основана на том факте, что B распределит, если А умрет (B всегда хотел бы, чтобы a умер). Если A дает больше монет 2 людям, чем B дал бы, то А выигрывает.
Задача 1
Как вариант:
using namespace boost::multiprecision;
int main()
{
int t;
cin >> t;
while (t--)
{
cpp_int n, res = 1;
cin >> n;
while (n != 1)
{
res = res * n;
n = n - 1;
}
cout << res << "\n";
}
return 0;
}
Задача 2
int find(Node* root, int &h)
{
if (root == NULL) return 0;
int lh = find(root->left, h);
int rh = find(root->right, h);
h = max(h, lh + rh + 1);
return max(lh, rh) + 1;
}
int diameter(Node* root)
{
int h = -1;
find(root, h);
return h;
}
Задача 3
#include <iostream>
#include <cstdint>
typedef unsigned __int128 uint128_t;
/**
* O(1) solution to https://practice.geeksforgeeks.org/problems/black-and-white/0
*/
int main()
{
unsigned t;
uint64_t n, m, upper, lower;
uint128_t res;
std::cin >> t;
while (t--)
{
std::cin >> n >> m;
res = n*m; // total ways to choose first knight
res *= (n*m-1); // now total ways to choose both knights
if (n>1 && m>1)
res -= 4*(2*n*m-3*n-3*m+4); // remove any collisions
// the rest is just for printing a uint128_t
upper = (uint64_t)(res/1000000000000000000);
lower = (uint64_t)(res%1000000000000000000);
if (upper)
{
std::cout << upper;
uint64_t digitChecker = 100000000000000000;
while (lower/digitChecker == 0 && digitChecker)
{
std::cout << 0;
digitChecker /= 10;
}
}
std::cout << lower << std::endl;
}
return 0;
}