# Issue # 30: IT training – current issues and challenges from leading companies

Hello! Here we are! Today we have a jubilee article at number 30!
We again prepared for you a selection of interesting questions and tasks from interviews at leading IT companies! Answers to problems from the previous issue have already been published. Issues will appear every week – stay tuned! The heading is supported by a recruiting agency. Spice IT.

This week we collected tasks from interviews in the American company Visa.

## Questions

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.

Transfer

100 prisoners in prison stand in line facing one way. Each prisoner wears a black or red hat. A prisoner can see the caps of all prisoners in front of him in line, but cannot see his hat and the caps of prisoners standing behind him.
The jailer will ask for the color of the caps of each prisoner, starting with the last prisoner in the line. If the prisoner says the right color, then they will have mercy on him, otherwise they will execute him. How many prisoners can be saved if they are allowed to discuss the strategy before the jailer asks for the colors of his hats.
Suggest this strategy.

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?

Transfer

In the country, all families want a boy. They continue to bear children until the birth of the boy. 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```

Transfer

Given an integer Ndenoting the number of cuts that can be made on the pancake. Find the maximum number of pieces that can be obtained by making N cuts.

Input data:

The first line of input contains a single integer T, indicating the number of tests. Then the T tests follow. Each test consists of one line. The first line of each test consists of an integer N.

Exit:

In accordance with each test case, in a new line print the maximum number of parts that can be formed by performing N cuts.

Limitations:

```1 ≤ T ≤ 100 1 ≤ N ≤ 106```

Example:
entrance

```2 5 3```
Exit
```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 neighbors. For corner elements, we need to consider only one neighbor.

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.

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.

Transfer

Given an array A of N integers. The task is to find the peak element in it.
An array element is peak if it is not less than its neighbors. For corner elements, we need to consider only one neighbor.

Note. There may be several peak elements, in which case you can return any valid index.

Input format:

The first line of input contains an integer T, indicating the number of tests. Then the T tests follow. Each test case contains an integer N. Then the next line contains N space-separated array values.

Limitations:
```1 <= T <= 100 1 <= N <= 100 1 <= A [] <= 1000```

Example:
Input data:

```2 3 1 2 3 2 3 4```
Exit:
```3 4```

Explanation:
Test case 1:
in this array 3 is the peak element.
Test example 2: 4 is a peak element.

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```

Transfer

Consider a large party where a guest entry and exit time log is kept. Find the time when the guests will be maximum guests. Please note that registry entries are not in any order.

Input data:

The first line of input contains an integer T, indicating the number of tests. Then the T tests follow. Each test case contains an integer n denoting the size of the input and output array. Then the next two lines contain an array of inputs and outputs, respectively.

Exit:

Print the maximum number of guests and the time at which the maximum number of guests at the party.

Limitations:
```1 <= Т <= 10 ^ 5 1 <= N <= 10 ^ 5 1 <= запись [I], выход [I] <= 10 ^ 5```

Example:
Input data:

```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```

Exit:
```3 5 7 40```

Answers to the tasks will be given during the next week - have time to solve it. Good luck