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.
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?
Tasks
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.
(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 [3] has maximum sum 3Example 2:
Input: [5,-3,5]
Output: ten
Explanation: Subarray [5,5] has maximum sum 5 + 5 = 10Example 3:
Input: [3,-1,2,-1]
Output: 4
Explanation: Subarray [2,-1,3] has maximum sum 2 + (-1) + 3 = 4Example 4:
Input: [3,-2,2,-3]
Output: 3
Explanation: Subarray [3] and [3,-2,2] both have maximum sum 3Example 5:
Input: [-2,-3,-1]
Output: -1
Explanation: Subarray [-1] has maximum sum -1Note:
-30000 <= A[i] <= 30000
1 <= A.length <= 30000
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
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 (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
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!