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

Привет-привет! С вами (не)регулярная рубрика 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.

Перевод

Молодая пара шиншилл (по одной от каждого пола) помещается на остров. Пара шиншилл не размножается, пока им не исполнится 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?

Перевод

В храме есть 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.

Перевод

Даны два целых числа 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[i] = A[i] when 0 <= i < A.length, and C[i+A.length] = C[i] when i >= 0.)

Also, a subarray may only include each element of the fixed buffer A at most once. (Formally, for a subarray C[i], 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[i] <= 30000
1 <= A.length <= 30000

Перевод

Дан круговой массив С целых чисел, представленных A, найдите максимально возможную сумму непустого подмассива C.

Здесь круговой массив означает, что конец массива соединяется с началом массива. (Формально C[i] = A[i], 0 <= i < A.length, иC[i+A.length] = C[i], когда i >= 0.)
Кроме того, подмассив может включает в себя только каждый элемент фиксированного буфера А не более одного раза. (Формально для подмассива C[i], 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[i] <= 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[i] 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[i].length < graph.length

Перевод

Неориентированный связный граф из N узлов (помеченных 0, 1, 2, ..., N-1) задается в виде графика.

graph.length = N и j != i находится в списке graph[i] ровно один раз, если и только если узлы 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[i].length < graph.length

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