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

Если с ходу-с лету решите их все и всерьез задумаетесь о том, чтобы податься в LinkedIn — рекомендуем вам послушать выпуск нашего подкаста.

Он, правда, про продактов, но в нем мы подробно расспрашиваем у Дмитрия Бердникова — Strategy & Operations Director LinkedIn’а про все этапы собеседований в компанию.

Слушайте, где удобно ↓
Apple Подкасты
Google Подкасты
Яндекс.Музыка
Или на странице подкаста

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

Вопросы

1. Monty Hall problem

Suppose you’re on a game show, and you’re given the choice of three doors: Behind one door is a car; behind the others, goats. You pick a door, say No. 1, and the host, who knows what’s behind the doors, opens another door, say No. 3, which has a goat. He then says to you, “Do you want to pick door No. 2?”
Is it to your advantage to switch your choice?

2. Find the Jar with contaminated pills

You have 5 jars of pills. Each pill weighs 10 grams, except for contaminated pills contained in one jar, where each pill weighs 9 grams. Given a scale, how could you tell which jar had the contaminated pills in just one measurement?

Задачи

1. Distinct Substrings

Given a string S consisting of uppercase alphabetic characters. Return the number of different substrings of size 2 that appear in S as contiguous substrings.

Input: The first line contains ‘T’ denoting the number of testcases. Then follows description of test cases. The next T lines contains the string S.

Output: Output the number of different substrings of size 2 in S.

Constraints:
1<=T<=50
1<=|S|<=100

Example:
Input :
2
ABCAB
XYZ

Output:
3
2

Explanation: For «ABCAB», the three distinct substrings of size 2 are «AB», «BC» and «CA». For «XYZ», the two distinct substrings of size 2 are «XY» and «YZ».

2. Longest consecutive subsequence

Given an array arr[] of positive integers. Find the length of the longest sub-sequence such that elements in the subsequence are consecutive integers, the consecutive numbers can be in any order.

Input:
The first line of input contains T, number of test cases. First line of line each test case contains a single integer N.
Next line contains N integer array.

Output:
Print the output of each test case in a seprate line.

Constraints:
1 <= T <= 100
1 <= N <= 105
0 <= a[i] <= 105

Example:
Input:
2
7
2 6 1 9 4 5 3
7
1 9 3 10 4 20 2

Output:
6
4

Explanation:
Testcase 1: The consecutive numbers here are 1, 2, 3, 4, 5, 6. These 6 numbers form the longest consecutive subsquence.

Testcase2: 1, 2, 3, 4 is the longest consecutive subsequence.

3. Distinct palindromic substrings

Given a string of lowercase ASCII characters, find all distinct continuous palindromic sub-strings of it.

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 a string.

Output:
Print the count of distinct continuous palindromic sub-strings of it.

Constraints:
1<=T<=10^5
1<=length of string<=10^5

Example:
Input:
2
abaaa
geek

Output:
5
4

Ответы на задачи будут даны в течение следующей недели — успейте решить. Удачи!