Привет!
Сегодня в нашей рубрике задачи с собеседований в LinkedIn.
Если с ходу-с лету решите их все и всерьез задумаетесь о том, чтобы податься в LinkedIn — рекомендуем вам послушать выпуск нашего подкаста.
Он, правда, про продактов, но в нем мы подробно расспрашиваем у Дмитрия Бердникова — Strategy & Operations Director LinkedIn’а про все этапы собеседований в компанию.
Слушайте, где удобно v
Apple Подкасты
Google Подкасты
Яндекс.Музыка
Или на странице подкаста
И кстати, ответы на предыдущие задачки уже опубликованы! Сверяйтесь с ними.
1. Monty Hall problem
2. Find the Jar with contaminated pills
1. Distinct Substrings
2. Longest consecutive subsequence
3. Distinct palindromic substrings
Ответы на задачи будут даны в течение следующей недели — успейте решить. Удачи!
Сегодня в нашей рубрике задачи с собеседований в LinkedIn.
Если с ходу-с лету решите их все и всерьез задумаетесь о том, чтобы податься в 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?
Перевод
Предположим, вы находитесь на игровом шоу, и вам предоставляется выбор из трех дверей: за одной дверью-автомобиль; за другими-козы. Вы выбираете дверь, скажем, №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.
Ограничения:
Пример:
Ввод:
Выход:
Пояснение: для «ABCAB» тремя различными подстроками размера 2 являются «AB», «BC» и «CA». Для «XYZ», две отдельные подстроки с размером 2 это «XY» и «YZ».
Ввод: Первая строка содержит '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: последовательные номера здесь 1, 2, 3, 4, 5, 6. Эти 6 чисел образуют самый длинный последовательный подзапрос.
Тест 2: 1, 2, 3, 4 — Самая длинная последовательная подпоследовательность.
Ввод:
Первая строка ввода содержит 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, обозначающее количество тестов. Затем следуют тесты. Каждый тест содержит строку.
Выход:
Выведите количество отдельных непрерывных палиндромных подстрок этого типа.
Ограничения:
Пример:
Ввод:
Выход:
Ввод:
Первая строка входных данных содержит целое число T, обозначающее количество тестов. Затем следуют тесты. Каждый тест содержит строку.
Выход:
Выведите количество отдельных непрерывных палиндромных подстрок этого типа.
Ограничения:
1< = T<=10^5
1< = длина строки<=10^5
Пример:
Ввод:
2
abaaa
geek
Выход:
5
4
Ответы на задачи будут даны в течение следующей недели — успейте решить. Удачи!
jmdorian
upd. А, ну собственно ответ в самом названии Парадокс Монти Холла
2. Взять из каждой банки число таблеток, равное ее порядковому номеру и взвесить. недостача в граммах и будет номером банки.
Ketovdk
у меня есть пробитие 3-ей задачи через sqrt-декомпозицию, но по ощущениям, это далеко от авторского решения (и в целом от ощущения прекрасного)