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

Привет! А вот и мы! Сегодня у нас юбилейная статья под номером 30!

Мы вновь подготовили Вам подборку интересных вопросов и задачек с собеседований в ведущие IT-компании! Ответы на задачки из прошлого выпуска уже опубликованы.



Выпуски будут появляться каждую неделю — следите за обновлениями! Рубрика выходит при поддержке рекрутингового агентства Spice IT.

На этой неделе мы собрали задачи с собеседований в американскую компанию Visa.

Вопросы

1. 100 Prisoners with Red/Black Hats

100 prisoners in jail are standing in a queue facing in one direction. Each prisoner is wearing a hat of color either black or red. A prisoner can see hats of all prisoners in front of him in the queue, but cannot see his hat and hats of prisoners standing behind him.
The jailer is going to ask color of each prisoner’s hat starting from the last prisoner in queue. If a prisoner tells the correct color, then is saved, otherwise executed. How many prisoners can be saved at most if they are allowed to discuss a strategy before the jailer starts asking colors of their hats.

Перевод

100 заключенных в тюрьме стоят в очереди лицом в одну сторону. Каждый заключенный носит шапку черного или красного цвета. Заключенный может видеть шапки всех заключенных перед ним в очереди, но не может видеть свою шапку и шапки заключенных, стоящие позади него.
Тюремщик будет спрашивать цвет шапки каждого заключенного, начиная с последнего заключенного в очереди. Если заключенный говорит правильный цвет, то его помилуют, в противном случае, казнят. Сколько заключенных можно спасти, если им разрешат обсудить стратегию до того, как тюремщик начнет спрашивать цвета своих шляп.
Предложите эту стратегию.

2. Ratio of Boys and Girls in a Country where people want only boys

In a country, all families want a boy. They keep having babies till a boy is born. What is the expected ratio of boys and girls in the country?

Перевод

В стране все семьи хотят мальчика. Они продолжают рожать детей до рождения мальчика. Каково ожидаемое соотношение мальчиков и девочек в стране?

Задачи

1. The Lazy Caterer's Problem

Given an integer N, denoting the number of cuts that can be made on a pancake, find the maximum number of pieces that can be formed by making N cuts.

Input:
The first line of input contains a single integer T denoting the number of test cases. Then T test cases follow. Each test case consist of one line. The first line of each test case consists of an integer N.

Output:
Corresponding to each test case, in a new line, print the maximum number of pieces that can be formed by making N cuts.

Constraints:

1 ≤ T ≤ 100
1 ≤ N ≤ 106

Example:
Input
2
5
3
Output
16
7

Перевод

Дано целое число N, обозначающее количество разрезов, которые можно сделать на блине. Найти максимальное количество кусков, которые можно получить, сделав N разрезов.

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

Выход:
В соответствии с каждым тестовым примером в новой строке выведите максимальное количество деталей, которое можно сформировать, выполняя N разрезов.

Ограничения:

1 ≤ T ≤ 100
1 ≤ N ≤ 106

Пример:
Вход
2
5
3
Выход
16
7

2. Peak element

Given an array A of N integers. The task is to find a peak element in it.
An array element is peak if it is not smaller than its neighbours. For corner elements, we need to consider only one neighbour.

Note: There may be multiple peak element possible, in that case you may return any valid index.

Input Format:
The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case contains an integer N. Then in the next line are N space separated values of the array.

Output Format:
For each test case output will be 1 if the index returned by the function is an index with peak element.

User Task:
You don't have to take any input. Just complete the provided function peakElement() and return the valid index.

Constraints:
1 <= T <= 100
1 <= N <= 100
1 <= A[] <= 1000

Example:
Input:
2
3
1 2 3
2
3 4
Output:
3
4

Explanation:
Testcase 1: In the given array, 3 is the peak element.
Testcase 2: 4 is the peak element.

Перевод

Дан массив A из N целых чисел. Задача состоит в том, чтобы найти в нем пиковый элемент.
Элемент массива является пиковым, если он не меньше своих соседей. Для угловых элементов нам нужно рассмотреть только одного соседа.

Примечание. Может быть несколько пиковых элементов, в этом случае вы можете вернуть любой действительный индекс.

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

Ограничения:
1 <= T <= 100
1 <= N <= 100
1 <= A [] <= 1000

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

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

3. Maximum Intervals Overlap

Consider a big party where a log register for guest’s entry and exit times is maintained. Find the time at which there are maximum guests in the party. Note that entries in register are not in any order.

Input:
The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case contains an integer n denoting the size of the entry and exit array. Then the next two line contains the entry and exit array respectively.

Output:
Print the maximum no of guests and the time at which there are maximum guests in the party.

Constraints:
1<=T<=10^5
1<=N<=10^5
1<=entry[i],exit[i]<=10^5

Example:
Input:
2
5
1 2 10 5 5
4 5 12 9 12
7
13 28 29 14 40 17 3
107 95 111 105 70 127 74

Output:
3 5
7 40

Перевод

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

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

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

Ограничения:
1 <= Т <= 10 ^ 5
1 <= N <= 10 ^ 5
1 <= запись [I], выход [I] <= 10 ^ 5

Пример:
Входные данные:
2
5
1 2 10 5 5
4 5 12 9 12
7
13 28 29 14 40 17 3
107 95 111 105 70 127 74

Выход:
3 5
7 40

Ответы

Вопрос 1

Максимум 99 заключенных могут быть помилованы, а 100-й заключенный имеет 50-50 шансов на казнь.
Идея состоит в том, что каждый заключенный считает количество красных шляп перед ним.

100-й заключенный говорит, что число красных шляп равно четному. Он может или не может быть спасен, но он передает достаточно информации, чтобы спасти 99-го заключенного.

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

Если 100-й заключенный сказал «Красный» (перед ним должно быть четное количество красных шляп)
а) Если 99-й заключенный видит четное количество красных шляп перед собой, то его цвет черный.
б) Если 99-й заключенный видит перед собой нечетное количество красных шляп, его цвет — красный.

Если 100-й заключенный сказал «черный» (перед ним должно быть нечетное количество красных шляп)
а) Если 99-й заключенный видит четное количество красных шляп перед собой, то его цвет — красный.
б) Если 99-й заключенный видит перед собой нечетное количество красных шляп, то его цвет — черный.

98-й заключенный решает свой ответ на основе ответа 99-го заключенного и использует ту же логику.

Точно так же другие заключенные от 97 до 1 спасены.

Вопрос 2

Предположения: вероятность рождения мальчика или девочки одинакова. Кроме того, вероятность того, что следующий ребенок будет мальчиком, не зависит от истории.

Проблема может быть решена путем подсчета ожидаемого числа девочек до рождения ребенка.
Пусть NG будет ожидаемым количеством девочек до рождения мальчика.

Пусть р будет вероятность того, что ребенок девочка и (1-p) вероятность того, что ребенок мальчик.

NG можно записать в виде суммы следующих бесконечных рядов.

NG = 0*(1-p) + 1*p*(1-p) + 2*p*p*(1-p) + 3*p*p*p*(1-p) + 4*p*p*p*p*(1-p) +.....

Подставляем p = 1/2 и (1-p) = 1/2 в приведенной выше формуле.

NG = 0*(1/2) + 1*(1/2)2 + 2*(1/2)3 + 3*(1/2)4 + 4*(1/2)5 + ...
1/2*NG = 0*(1/2)2 + 1*(1/2)3 + 2*(1/2)4 + 3*(1/2)5 + 4*(1/2)6 + ...

NG - NG/2 = 1*(1/2)2 + 1*(1/2)3 + 1*(1/2)4 + 1*(1/2)5 + 1*(1/2)6 + ...

Используя формулу суммы бесконечной геометрической прогрессии с соотношением менее 1
NG/2 = (1/4)/(1-1/2) = 1/2

NG = 1

Задача 1

Формула, по которой находится ответ: (n + c*c + 2) / 2

int main() {
	int t,n,final;
	cin>>t;
	while(t--){
	   cin>>n;
	   final=(n+(n*n)+2)/2;
	   cout<<final<<endl;
	}
	return 0;
}

Задача 2

// arr: input array
// n: size of array
int peakElement(int a[], int n)
{
    int i;
    for(i=1;i<n-1;i++){
        if(a[i]>a[i-1] && a[i]>a[i+1]){
            return i;
        }
    }
    if(n>1 && a[0]>a[1])
        return a[0];
    if(n-2>=0 && a[n-1]>a[n-2])
    return a[n-1];
}

Задача 3

/*package whatever //do not write package name here */

import java.util.*;
import java.lang.*;
import java.io.*;

class GFG {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		
		while (T > 0) {
		    int N = sc.nextInt();
		    int[] entry = new int[N];
		    int[] exit = new int[N];
		    for (int i = 0; i < N; i++) {
		        entry[i] = sc.nextInt();
		    }
		    
		    for (int i = 0; i < N; i++) {
		        exit[i] = sc.nextInt();
		    }
		    
		    Arrays.sort(entry);
		    Arrays.sort(exit);
		    //System.out.println(Arrays.toString(entry));
		    //System.out.println(Arrays.toString(exit));
		    
		    int counter = 0;
		    int maxCounter = -1;
		    int maxTime = -1;
		    
		    int entryIdx = 0;
		    int exitIdx = 0;
		    
		    while (entryIdx < N && exitIdx < N) {
		        if (entry[entryIdx] <= exit[exitIdx]) {
		            counter++;
		            if (counter > maxCounter) {
		                maxCounter = counter;
		                maxTime = entry[entryIdx];
		            }
		            entryIdx++;
		        } else {
		            counter--;
		            exitIdx++;
		        }
		    }
		    
		    System.out.println(maxCounter + " " + maxTime);   
		    T--;
		}
	}
}