[Занимательные задачки, Программирование] Выпуск#40: ITренировка — актуальные вопросы и задачи от ведущих компаний
Автор
Сообщение
news_bot ®
Стаж: 6 лет 9 месяцев
Сообщений: 27286
Привет-привет! С вами (не)регулярная рубрика ITренировка. Соскучились? Мы тоже!
Вернёмся к вам на еженедельной основе осенью, а пока же ловите от нас подборку задачек с собеседований в норвежскую компанию Opera Software!
Рубрика выходит при поддержке рекрутингового агентства Spice IT.
Вопросы
1. Chinchillas Relations
A young pair of chinchillas (one of each sex) is placed on an island. A pair of chinchillas does not breed until they are 2 months old. After they are 2 months old, each pair of chinchillas produces another pair each month (See pic below). Find a recurrence relation for the number of pairs of chinchillas on the island after n months, assuming that no chinchillas ever die.
Перевод
SPL
Молодая пара шиншилл (по одной от каждого пола) помещается на остров. Пара шиншилл не размножается, пока им не исполнится 2 месяца. После того, как им исполняется 2 месяца, каждая пара шиншилл производит еще одну пару каждый месяц (см. рис выше). Найдите рекуррентное отношение для числа пар шиншилл на острове через n месяцев, предполагая, что ни одна шиншилла никогда не умрет.
2. Priests in Temple
There are 20 priests in a temple. One day, Lord Shiva appears before them and tells them that some of them have sinned, and that a black spot would appear on the forehead of all the priests who have sinned. The priests are not allowed to look into a mirror or communicate with each other. When any priest finds out that there is a spot on his forehead, he should leave the temple on that day itself. At least 1 priest has sinned. How can a priest find out whether he has a spot on his forehead. What would be the pattern of the priests leaving the temple?
Перевод
SPL
В храме есть 20 священников. Однажды Господь Шива появляется перед ними и говорит им, что некоторые из них согрешили, и что черное пятно появится на лбу всех священников, которые согрешили. Священникам не разрешается смотреть в зеркало или общаться друг с другом. Когда любой священник узнает, что у него на лбу есть пятно, он должен покинуть храм в этот же день. По крайней мере, один священник согрешил. Как может священник узнать, есть ли у него пятно на лбу? Каков будет порядок выхода священников из храма?
Задачи
1. Prime Number of Set Bits in Binary Representation
Given two integers L and R, find the count of numbers in the range [L, R] (inclusive) having a prime number of set bits in their binary representation.
(Recall that the number of set bits an integer has is the number of 1s present when written in binary. For example, 21 written in binary is 10101 which has 3 set bits. Also, 1 is not a prime.)
Example 1:
Input: L = 6, R = 10
Output: 4
Explanation:
6 -> 110 (2 set bits, 2 is prime)
7 -> 111 (3 set bits, 3 is prime)
9 -> 1001 (2 set bits, 2 is prime)
10->1010 (2 set bits, 2 is prime)
Example 2:
Input: L = 10, R = 15
Output: 5
Explanation:
10 -> 1010 (2 set bits, 2 is prime)
11 -> 1011 (3 set bits, 3 is prime)
12 -> 1100 (2 set bits, 2 is prime)
13 -> 1101 (3 set bits, 3 is prime)
14 -> 1110 (3 set bits, 3 is prime)
15 -> 1111 (4 set bits, 4 is not prime)
Note:
L, R will be integers L <= R in the range [1, 10^6].
R — L will be at most 10000.
Перевод
SPL
Даны два целых числа L и R, найдите количество чисел в диапазоне [L, R] (включительно), имеющих простое число из набора битов в их двоичном представлении.
(Напомним, что число битов набора, которое имеет целое число, — это число 1s, присутствующее при записи в двоичном коде. Например, 21 записано в двоичном коде — 10101, которое имеет 3 набор битов. Кроме того, 1 — это не простое число.)
Пример 1:
Вход: L = 6, R = 10
Выход: 4
Объяснение:
6 — > 110 (2 набора битов, 2 — простое число)
7 — > 111 (3 набора битов, 3 — простое число)
9 — > 1001 (2 набора битов, 2 — простое число)
10->1010 (2 набора битов, 2 — простое число)
Пример 2:
Вход: L = 10, R = 15
Выход: 5
Объяснение:
10 -> 1010 (2 набора битов, 2 — простое число)
11 — > 1011 (3 набора битов, 3 — простое число)
12 — > 1100 (2 набора битов, 2 — простое число)
13 -> 1101 (3 набора битов, 3 — простое число)
14 — > 1110 (3 набора битов, 3 — простое число)
15 — > 1111 (4 набора битов, 4 не являются простым числом)
Примечание:
L, R будут целыми числами L <= R в диапазоне [1, 10^6].
R-L будет не более 10000.
2. Maximum Sum Circular Subarray
Given a circular array C of integers represented by A, find the maximum possible sum of a non-empty subarray of C.
Here, a circular array means the end of the array connects to the beginning of the array. (Formally, C = A when 0 <= i < A.length, and C[i+A.length] = C when i >= 0.)
Also, a subarray may only include each element of the fixed buffer A at most once. (Formally, for a subarray C, C[i+1], ..., C[j], there does not exist i <= k1, k2 <= j with k1 % A.length = k2 % A.length.)
Example 1:
Input: [1,-2,3,-2]
Output: 3
Explanation: Subarray [3] has maximum sum 3
Example 2:
Input: [5,-3,5]
Output: 10
Explanation: Subarray [5,5] has maximum sum 5 + 5 = 10
Example 3:
Input: [3,-1,2,-1]
Output: 4
Explanation: Subarray [2,-1,3] has maximum sum 2 + (-1) + 3 = 4
Example 4:
Input: [3,-2,2,-3]
Output: 3
Explanation: Subarray [3] and [3,-2,2] both have maximum sum 3
Example 5:
Input: [-2,-3,-1]
Output: -1
Explanation: Subarray [-1] has maximum sum -1
Note:
-30000 <= A <= 30000
1 <= A.length <= 30000
Перевод
SPL
Дан круговой массив С целых чисел, представленных A, найдите максимально возможную сумму непустого подмассива C.
Здесь круговой массив означает, что конец массива соединяется с началом массива. (Формально C = A, 0 <= i < A.length, иC[i+A.length] = C, когда i >= 0.)
Кроме того, подмассив может включает в себя только каждый элемент фиксированного буфера А не более одного раза. (Формально для подмассива C, C[i+1],..., C[j], не существует i <= k1, k2 <= j с k1 % A.length = k2 % A.length.)
Пример 1:
Входные данные: [1, -2,3, -2]
Выход: 3
Пояснение: Подмассив [3] имеет максимальную сумму 3
Пример 2:
Вход: [5,-3,5]
Выход: 10
Пояснение: Подмассив [5,5] имеет максимальную сумму 5 + 5 = 10
Пример 3:
Входные данные: [3,-1,2, -1]
Выход: 4
Пояснение: Подмассив [2, -1,3] имеет максимальную сумму 2 + (-1) + 3 = 4
Пример 4:
Входные данные: [3,-2,2,-3]
Выход: 3
Пояснение: Подмассивы [3] и [3,-2,2] имеют максимальную сумму 3
Пример 5:
Входные данные: [-2,-3, -1]
Выход: -1
Пояснение: Подмассив [-1] имеет максимальную сумму -1
Примечание:
-30000 <= A <= 30000
1 <= A.length <= 30000
3. Shortest Path Visiting All Nodes
An undirected, connected graph of N nodes (labeled 0, 1, 2, ..., N-1) is given as graph.
graph.length = N, and j != i is in the list graph exactly once, if and only if nodes i and j are connected.
Return the length of the shortest path that visits every node. You may start and stop at any node, you may revisit nodes multiple times, and you may reuse edges.
Example 1:
Input: [[1,2,3],[0],[0],[0]]
Output: 4
Explanation: One possible path is [1,0,2,0,3]
Example 2:
Input: [[1],[0,2,4],[1,3,4],[2],[1,2]]
Output: 4
Explanation: One possible path is [0,1,4,2,3]
Note:
1 <= graph.length <= 12
0 <= graph.length < graph.length
Перевод
SPL
Неориентированный связный граф из N узлов (помеченных 0, 1, 2, ..., N-1) задается в виде графика.
graph.length = N и j != i находится в списке graph ровно один раз, если и только если узлы i и j соединены.
Выведите длину кратчайшего пути, который посещает каждый узел. Вы можете начинать и останавливаться на любом узле, вы можете повторно просматривать узлы несколько раз, и вы можете повторно использовать ребра.
Пример 1:
Входная информация: [[1,2,3],[0],[0],[0]]
Выход: 4
Пояснение: один из возможных путей — [1,0,2,0,3]
Пример 2:
Входная информация: [[1],[0,2,4],[1,3,4],[2],[1,2]]
Выход: 4
Пояснение: один из возможных путей — это [0,1,4,2,3]
Примечание:
1 <= graph.length <= 12
0 <= graph.length < graph.length
Ответы на задачи будут даны в течение следующей недели — успейте решить. Удачи!
===========
Источник:
habr.com
===========
Похожие новости:
- [Data Mining, Big Data, Data Engineering] Быстрый старт и низкий потолок. Что ждет молодых Data Science-специалистов на рынке труда
- [Машинное обучение, Искусственный интеллект] Подвергаем модель GPT-3 тесту Тьюринга (перевод)
- [Программирование, Геоинформационные сервисы, Математика, Визуализация данных, Научно-популярное] Гидродинамическое моделирование (CFD) на рельефе с помощью MantaFlow и визуализация результатов в ParaView
- [Java, Программирование, Проектирование и рефакторинг, Разработка под Android, Совершенный код] Руководство Google по форматированию кода на Java (перевод)
- [Машинное обучение, Разработка под Arduino] Как настроить автоматическую съемку при улыбке за полчаса с помощью HUAWEI ML Kit
- [Искусственный интеллект, Машинное обучение] Deep Learning — как это работает? Часть 4
- [Алгоритмы, Искусственный интеллект, Обработка изображений] МТИ и Microsoft обучили алгоритм находить скрытые параллели между картинами
- [Программирование микроконтроллеров] Особенности RTC M41T56
- [Анализ и проектирование систем, Высокая производительность, Компиляторы, Программирование] Как реализованы JIT-компиляторы (перевод)
- [Open source, Информационная безопасность, Учебный процесс в IT] 1000 и 1 способ обойти Safe Exam Browser
Теги для поиска: #_zanimatelnye_zadachki (Занимательные задачки), #_programmirovanie (Программирование), #_spiceit, #_zanimatelnye_zadachi (занимательные задачи), #_itrenirovka (itренировка), #_sobesedovanija (собеседования), #_obuchenie (обучение), #_poisk_raboty (поиск работы), #_poisk_v_shirinu (поиск в ширину), #_krotchajshij_put (кротчайший путь), #_algoritm_kadane (алгоритм Кадане), #_blog_kompanii_spice_it_recruitment (
Блог компании Spice IT Recruitment
), #_zanimatelnye_zadachki (
Занимательные задачки
), #_programmirovanie (
Программирование
)
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 23:44
Часовой пояс: UTC + 5
| Автор | Сообщение |
|---|---|
|
news_bot ®
Стаж: 6 лет 9 месяцев |
|
|
Привет-привет! С вами (не)регулярная рубрика ITренировка. Соскучились? Мы тоже!  Вернёмся к вам на еженедельной основе осенью, а пока же ловите от нас подборку задачек с собеседований в норвежскую компанию Opera Software! Рубрика выходит при поддержке рекрутингового агентства Spice IT. Вопросы 1. Chinchillas Relations A young pair of chinchillas (one of each sex) is placed on an island. A pair of chinchillas does not breed until they are 2 months old. After they are 2 months old, each pair of chinchillas produces another pair each month (See pic below). Find a recurrence relation for the number of pairs of chinchillas on the island after n months, assuming that no chinchillas ever die.
 ПереводSPLМолодая пара шиншилл (по одной от каждого пола) помещается на остров. Пара шиншилл не размножается, пока им не исполнится 2 месяца. После того, как им исполняется 2 месяца, каждая пара шиншилл производит еще одну пару каждый месяц (см. рис выше). Найдите рекуррентное отношение для числа пар шиншилл на острове через n месяцев, предполагая, что ни одна шиншилла никогда не умрет.
2. Priests in Temple There are 20 priests in a temple. One day, Lord Shiva appears before them and tells them that some of them have sinned, and that a black spot would appear on the forehead of all the priests who have sinned. The priests are not allowed to look into a mirror or communicate with each other. When any priest finds out that there is a spot on his forehead, he should leave the temple on that day itself. At least 1 priest has sinned. How can a priest find out whether he has a spot on his forehead. What would be the pattern of the priests leaving the temple?
ПереводSPLВ храме есть 20 священников. Однажды Господь Шива появляется перед ними и говорит им, что некоторые из них согрешили, и что черное пятно появится на лбу всех священников, которые согрешили. Священникам не разрешается смотреть в зеркало или общаться друг с другом. Когда любой священник узнает, что у него на лбу есть пятно, он должен покинуть храм в этот же день. По крайней мере, один священник согрешил. Как может священник узнать, есть ли у него пятно на лбу? Каков будет порядок выхода священников из храма?
Задачи 1. Prime Number of Set Bits in Binary Representation Given two integers L and R, find the count of numbers in the range [L, R] (inclusive) having a prime number of set bits in their binary representation.
(Recall that the number of set bits an integer has is the number of 1s present when written in binary. For example, 21 written in binary is 10101 which has 3 set bits. Also, 1 is not a prime.) Example 1: Input: L = 6, R = 10 Output: 4 Explanation: 6 -> 110 (2 set bits, 2 is prime) 7 -> 111 (3 set bits, 3 is prime) 9 -> 1001 (2 set bits, 2 is prime) 10->1010 (2 set bits, 2 is prime) Example 2: Input: L = 10, R = 15 Output: 5 Explanation: 10 -> 1010 (2 set bits, 2 is prime) 11 -> 1011 (3 set bits, 3 is prime) 12 -> 1100 (2 set bits, 2 is prime) 13 -> 1101 (3 set bits, 3 is prime) 14 -> 1110 (3 set bits, 3 is prime) 15 -> 1111 (4 set bits, 4 is not prime) Note: L, R will be integers L <= R in the range [1, 10^6]. R — L will be at most 10000. ПереводSPLДаны два целых числа L и R, найдите количество чисел в диапазоне [L, R] (включительно), имеющих простое число из набора битов в их двоичном представлении.
(Напомним, что число битов набора, которое имеет целое число, — это число 1s, присутствующее при записи в двоичном коде. Например, 21 записано в двоичном коде — 10101, которое имеет 3 набор битов. Кроме того, 1 — это не простое число.) Пример 1: Вход: L = 6, R = 10 Выход: 4 Объяснение: 6 — > 110 (2 набора битов, 2 — простое число) 7 — > 111 (3 набора битов, 3 — простое число) 9 — > 1001 (2 набора битов, 2 — простое число) 10->1010 (2 набора битов, 2 — простое число) Пример 2: Вход: L = 10, R = 15 Выход: 5 Объяснение: 10 -> 1010 (2 набора битов, 2 — простое число) 11 — > 1011 (3 набора битов, 3 — простое число) 12 — > 1100 (2 набора битов, 2 — простое число) 13 -> 1101 (3 набора битов, 3 — простое число) 14 — > 1110 (3 набора битов, 3 — простое число) 15 — > 1111 (4 набора битов, 4 не являются простым числом) Примечание: L, R будут целыми числами L <= R в диапазоне [1, 10^6]. R-L будет не более 10000. 2. Maximum Sum Circular Subarray Given a circular array C of integers represented by A, find the maximum possible sum of a non-empty subarray of C.
Here, a circular array means the end of the array connects to the beginning of the array. (Formally, C = A when 0 <= i < A.length, and C[i+A.length] = C when i >= 0.) Also, a subarray may only include each element of the fixed buffer A at most once. (Formally, for a subarray C, C[i+1], ..., C[j], there does not exist i <= k1, k2 <= j with k1 % A.length = k2 % A.length.) Example 1: Input: [1,-2,3,-2] Output: 3 Explanation: Subarray [3] has maximum sum 3 Example 2: Input: [5,-3,5] Output: 10 Explanation: Subarray [5,5] has maximum sum 5 + 5 = 10 Example 3: Input: [3,-1,2,-1] Output: 4 Explanation: Subarray [2,-1,3] has maximum sum 2 + (-1) + 3 = 4 Example 4: Input: [3,-2,2,-3] Output: 3 Explanation: Subarray [3] and [3,-2,2] both have maximum sum 3 Example 5: Input: [-2,-3,-1] Output: -1 Explanation: Subarray [-1] has maximum sum -1 Note: -30000 <= A <= 30000 1 <= A.length <= 30000 ПереводSPLДан круговой массив С целых чисел, представленных A, найдите максимально возможную сумму непустого подмассива C.
Здесь круговой массив означает, что конец массива соединяется с началом массива. (Формально C = A, 0 <= i < A.length, иC[i+A.length] = C, когда i >= 0.) Кроме того, подмассив может включает в себя только каждый элемент фиксированного буфера А не более одного раза. (Формально для подмассива C, C[i+1],..., C[j], не существует i <= k1, k2 <= j с k1 % A.length = k2 % A.length.) Пример 1: Входные данные: [1, -2,3, -2] Выход: 3 Пояснение: Подмассив [3] имеет максимальную сумму 3 Пример 2: Вход: [5,-3,5] Выход: 10 Пояснение: Подмассив [5,5] имеет максимальную сумму 5 + 5 = 10 Пример 3: Входные данные: [3,-1,2, -1] Выход: 4 Пояснение: Подмассив [2, -1,3] имеет максимальную сумму 2 + (-1) + 3 = 4 Пример 4: Входные данные: [3,-2,2,-3] Выход: 3 Пояснение: Подмассивы [3] и [3,-2,2] имеют максимальную сумму 3 Пример 5: Входные данные: [-2,-3, -1] Выход: -1 Пояснение: Подмассив [-1] имеет максимальную сумму -1 Примечание: -30000 <= A <= 30000 1 <= A.length <= 30000 3. Shortest Path Visiting All Nodes An undirected, connected graph of N nodes (labeled 0, 1, 2, ..., N-1) is given as graph.
graph.length = N, and j != i is in the list graph exactly once, if and only if nodes i and j are connected. Return the length of the shortest path that visits every node. You may start and stop at any node, you may revisit nodes multiple times, and you may reuse edges. Example 1: Input: [[1,2,3],[0],[0],[0]] Output: 4 Explanation: One possible path is [1,0,2,0,3] Example 2: Input: [[1],[0,2,4],[1,3,4],[2],[1,2]] Output: 4 Explanation: One possible path is [0,1,4,2,3] Note: 1 <= graph.length <= 12 0 <= graph.length < graph.length ПереводSPLНеориентированный связный граф из N узлов (помеченных 0, 1, 2, ..., N-1) задается в виде графика.
graph.length = N и j != i находится в списке graph ровно один раз, если и только если узлы i и j соединены. Выведите длину кратчайшего пути, который посещает каждый узел. Вы можете начинать и останавливаться на любом узле, вы можете повторно просматривать узлы несколько раз, и вы можете повторно использовать ребра. Пример 1: Входная информация: [[1,2,3],[0],[0],[0]] Выход: 4 Пояснение: один из возможных путей — [1,0,2,0,3] Пример 2: Входная информация: [[1],[0,2,4],[1,3,4],[2],[1,2]] Выход: 4 Пояснение: один из возможных путей — это [0,1,4,2,3] Примечание: 1 <= graph.length <= 12 0 <= graph.length < graph.length Ответы на задачи будут даны в течение следующей недели — успейте решить. Удачи! =========== Источник: habr.com =========== Похожие новости:
Блог компании Spice IT Recruitment ), #_zanimatelnye_zadachki ( Занимательные задачки ), #_programmirovanie ( Программирование ) |
|
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 23:44
Часовой пояс: UTC + 5