Привет!
Сегодня в нашей рубрике задачи с собеседований в LinkedIn.

image

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

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

Слушайте, где удобно v
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?

image
Перевод
Предположим, вы находитесь на игровом шоу, и вам предоставляется выбор из трех дверей: за одной дверью-автомобиль; за другими-козы. Вы выбираете дверь, скажем, №1, и ведущий, который знает, что за дверями, открывает другую дверь, скажем, №3, в которой есть коза. Затем он говорит вам «Хотите ли вы выбрать дверь №2?»
Выгодно ли вам поменять свой выбор?

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?

Перевод
У вас есть 5 банок таблеток. Каждая таблетка весит 10 граммов, за исключением заражённых таблеток, содержащихся в одной банке, где каждая таблетка весит 9 граммов. У вас есть весы, как вы смогли бы определить, в какой банке были зараженные таблетки, всего за одно взвешивание?

Задачи


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».

Перевод
Дана строка S, состоящая из прописных буквенных символов. Верните количество различных подстрок размера 2, которые отображаются в S как смежные подстроки.

Ввод: Первая строка содержит 'T', обозначающее количество тестов. Далее следует описание тестов. Следующие T строк содержат строку S.

Выход: Выведите единственное число — количество различных подстрок размера 2 в строке S.

Ограничения:
1< = T< = 50
1<= / S / < = 100


Пример:
Ввод:

2
ABCAB
XYZ


Выход:
3
2


Пояснение: для «ABCAB» тремя различными подстроками размера 2 являются «AB», «BC» и «CA». Для «XYZ», две отдельные подстроки с размером 2 это «XY» и «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.

Перевод
Дан массив arr[] положительных целых чисел. Найти длину самой длинной подпоследовательности такой, что элементы в подпоследовательности являются последовательными целыми числами, последовательные числа могут быть в любом порядке.

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

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

Ограничения:
1 < = T < = 100
1 < = N < = 105
0 <= a[i] < = 105


Пример:
Ввод:

2
7
2 6 1 9 4 5 3
7
1 9 3 10 4 20 2


Выход:
6
4


Объяснение:
Тест 1:
последовательные номера здесь 1, 2, 3, 4, 5, 6. Эти 6 чисел образуют самый длинный последовательный подзапрос.

Тест 2: 1, 2, 3, 4 — Самая длинная последовательная подпоследовательность.

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

Перевод
Дана строка строчных символов ASCII, найдите все ее отдельные непрерывные палиндромные подстроки.

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

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

Ограничения:
1< = T<=10^5
1< = длина строки<=10^5


Пример:
Ввод:

2
abaaa
geek


Выход:
5
4

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

Комментарии (2)


  1. jmdorian
    18.12.2019 15:12

    Вопросы
    1. Была как-то уже подобная задача, и вроде даже разбирали что вероятность действительно каким-то образом поменяется, хотя по мне это попахивает каким-то парадоксом
    upd. А, ну собственно ответ в самом названии Парадокс Монти Холла
    2. Взять из каждой банки число таблеток, равное ее порядковому номеру и взвесить. недостача в граммах и будет номером банки.


  1. Ketovdk
    19.12.2019 09:44

    у меня есть пробитие 3-ей задачи через sqrt-декомпозицию, но по ощущениям, это далеко от авторского решения (и в целом от ощущения прекрасного)