# Issue # 40: IT training – topical issues and challenges from leading companies

Hi Hi! With you (not) a regular heading of IT training. Did you miss? We, too! Let’s come back to you on a weekly basis in the fall, but in the meantime, catch from us a selection of tasks from interviews in the Norwegian company Opera Software!
The rubric is published with the support of a recruiting agency Spice IT

## Questions

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

A young pair of chinchillas (one from each sex) is placed on the island. A pair of chinchillas does not breed until they are 2 months old. After they turn 2 months old, each pair of chinchillas produces another pair every month (see picture above). Find the recurrence for the number of pairs of chinchillas on the island in n months, assuming that no chinchilla ever dies.

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?

Transfer

There are 20 priests in the temple. One day Lord Shiva appears before them and tells them that some of them have sinned and that a black spot will appear on the foreheads of all the priests who have sinned. Priests are not allowed to look in the mirror or communicate with each other. When any priest finds out that he has a stain on his forehead, he must leave the temple on the same day. At least one priest has sinned. How can a priest know if he has a stain on his forehead? What will be the order for the priests to leave the temple?

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: five
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.

Transfer

Given two integers L and R, find the number of numbers in the range [L, R] (inclusive) having a prime number from the set of bits in their binary representation.

(Recall that the number of bits in the set that an integer has is the number 1s that is present when written in binary. For example, 21 is written in binary, 10101, which has 3 sets of bits. Also, 1 is not a prime number .)

Example 1:
Entrance: L = 6, R = 10
Output: 4
Explanation:

6 -> 110 (2 sets of bits, 2 is prime)
7 -> 111 (3 sets of bits, 3 is prime)
9 -> 1001 (2 sets of bits, 2 is prime)
10-> 1010 (2 sets of bits, 2 is prime)

Example 2:
Entrance: L = 10, R = 15
Output: five
Explanation:

10 -> 1010 (2 sets of bits, 2 is prime)
11 -> 1011 (3 sets of bits, 3 is prime)
12 -> 1100 (2 sets of bits, 2 is prime)
13 -> 1101 (3 sets of bits, 3 is prime)
14 -> 1110 (3 sets of bits, 3 is prime)
15 -> 1111 (4 sets of bits, 4 is not prime)

Note:

L, R will be integers L <= R in the range [1, 10^6]...
RL will be no more than 10,000.

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 , 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  has maximum sum 3

Example 2:
Input: [5,-3,5]
Output: ten
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  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```

Transfer

Dan circular array C integers represented A, find the maximum possible sum of a non-empty subarray C...

Here circular array means that the end of the array is connected to the beginning of the array. (Formally C[i] = A[i], 0 <= i , andC[i+A.length] = C[i]when i> = 0.)
In addition, the subarray can only include each element of the fixed buffer A at most once. (Formally for the subarray C[i], C[i+1], ..., C[j], does not exist i <= k1, k2 <= j from k1% A.length = k2% A.length.)

Example 1:
Input data: [1, -2,3, -2]
Output: 3
Explanation: Subarray  has a maximum amount of 3

Example 2:
Entrance: [5,-3,5]
Output: ten
Explanation: Subarray [5,5] has a maximum amount of 5 + 5 = 10

Example 3:
Input data: [3,-1,2, -1]
Output: 4
Explanation: Subarray [2, -1,3] has a maximum sum of 2 + (-1) + 3 = 4

Example 4:
Input data: [3,-2,2,-3]
Output: 3
Explanation: Subarrays  and [3,-2,2] have a maximum amount of 3

Example 5:
Input data: [-2,-3, -1]
Output: -1
Explanation: Subarray [-1] has a maximum sum of -1

Note:
```-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],,,]
Output: 4
Explanation: One possible path is [1,0,2,0,3]

Example 2:
Input: [,[0,2,4],[1,3,4],,[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```

Transfer

Undirected connected graph from N nodes (marked 0, 1, 2, ..., N-1) is set as a graph.

graph.length = N and j! = i is on the list graph[i] exactly once if and only if the nodes i and j connected.

Print the length of the shortest path that each node visits. You can start and stop at any node, you can revisit nodes multiple times, and you can reuse edges.

Example 1:
Input information: [[1,2,3],,,]
Output: 4
Explanation: one of the possible ways is [1,0,2,0,3]

Example 2:
Input information: [,[0,2,4],[1,3,4],,[1,2]]
Output: 4
Explanation: one of the possible ways is [0,1,4,2,3]

Note:
```1 <= graph.length <= 12 0 <= graph[i].length < graph.length```

Answers to the problems will be given within the next week - have time to solve it. Good luck!