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

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**

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**

## Tasks

1. **Prime Number of Set Bits in Binary Representation**

Given two integers

LandR, 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,

21written in binary is10101which has 3 set bits. Also, 1 is not a prime.)

Example 1:Input:L = 6, R = 10Output:4Explanation: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 = 15Output:fiveExplanation: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**

**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 Cof integers represented byA, find the maximum possible sum of a non-empty subarray ofC…Here, a

circular arraymeans the end of the array connects to the beginning of the array. (Formally,C[i] = A[i]when0 <= i, and C[i+A.length] = C[i] when i> = 0.)

Also, a subarray may only include each element of the fixed bufferAat most once. (Formally, for a subarrayC[i], C[i+1], …, C[j], there does not existi <= k1, k2 <= jwithk1% A.length = k2% A.length.)

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

Example 2:Input:[5,-3,5]Output:tenExplanation:Subarray [5,5] has maximum sum 5 + 5 = 10

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

Example 4:Input:[3,-2,2,-3]Output:3Explanation:Subarray [3] and [3,-2,2] both have maximum sum 3

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

Note:`-30000 <= A[i] <= 30000`

1 <= A.length <= 30000

**Transfer****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 , and**

**C[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 [3] 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 [3] 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 (labeled0, 1, 2, ..., N-1) is given as graph.

graph.length = N, andj! = iis in the listgraph[i]exactly once, if and only if nodesiandjare 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:4Explanation:One possible path is [1,0,2,0,3]

Example 2:Input:[[1],[0,2,4],[1,3,4],[2],[1,2]]Output:4Explanation:One possible path is [0,1,4,2,3]

Note:`1 <= graph.length <= 12`

0 <= graph[i].length < graph.length

**Transfer****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],[0],[0],[0]]**Output:** 4**Explanation:** one of the possible ways is [1,0,2,0,3]

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