In today’s post, I am going to share Trilogy Innovations(CodeNation) Coding Round, 5th March. I have collected a few questions and wrote their answers for you guys.
Trilogy Innovations(CodeNation) Coding Round, 5th March Questions
Question 1 – Find The Evil Monsters
Given an array A of N elements representing the monsters and an array B of Q elements representing the heros.
The i-th type of monster is represented by A[i][0], A[i][1] and A[i][2] which means a monster of the i-th type is present at each integer co-ordinate from A[i][0] to A[i][1] and having a strength of A[i][2].
The i-th type of hero is represented by B[i][0] and B[i][1] which means a hero of strength B[i][1] will appear at the integer point B[i][0] after i seconds. When the i-th hero appears it will destroy each and every monster present at B[i][0] and having a strength less than B[i][1].
For each i you have to determine the number of monsters left after the i-th hero has completed their task.
Problem Constraints
- 1 <= N <= 105
- 1 <= Q <= 105
- 1 <= A[i][0] <= A[i][1] <= 105
- 1 <= B[i][0] <= 105
- 1 <= A[i][2] <= 109
- 1 <= B[i][1] <= 109
Question 2 – Minimize Travel Tax
There are A cities connected by A-1 bi-directional roads such that all the cities are connected.
Roads are given by array 2D array B where ith road connects B[i][0] city to B[i][1].
You go on C trips where on the i-th trip you travel from C[i][0] city to C[i][1] city. All the trips are independent of each other.
You have to pay a tax on D[i] on entering or leaving the i-th city. If you pay the tax while entering then you don’t need to pay at the time of leaving.
You can choose some non-adjacent cities and make their tax half.
What can be the minimum sum of taxes you pay for all the C trips? Since the answer can be large, return the remainder after dividing it by 109+7.
Problem Constraints
- 2 <= A <= 105
- 1 <= B[i][0], B[i][1] <= A
- 1 <= C <= 105
- 1 <= C[i][0],C[i][1] <= A
- C[i][0] != C[i][1]
- 1 <= D[i] <= 105
- D= A and D[i] % 2 = 0
Question 3 – Expected Path Length III
You have A natural number from 1 to A, each occuring exactly once. Now, you choose any of the A (each number being equally likely) numbers and do the following procedures:
1. Initialize a variable step = 0.
2. Let X be the current number you have.
3. Randomly choose any divisor of X (each divisor being equally likely). Let it be Y, now replace X by X/Y. Also, increment step by 1.
4. If X is not equal to 1, repeat from 2nd step.
Let expected value of step be represented in the form of a irreducible fraction x/y. Return xy-1 mod (109+7), where y-1 is the modulo multiplicative inverse of y modulo (109 + 7).
NOTE: You only have to consider positive values of Y.
Problem Constraints
- 1 <= A <= 105
Question 4 – Three Subarrays
You are given an array A of N integers. You will have to pick 3 subarrays from the array l1, l2 and I3. The subarray I1 must be a prefix and I3 must be a suffux. The minimum length of each of these subarrays must be 1. An element of the array cannot be present in more than 1 of these subarrays.
Find the maximum sum of all the elements in each of these three subarrays. Since the sum can be large, return the positive remainder after dividing the sum with 109 +7.
Problem Constraints
- 3 <= N <= 105
- -109 <= A[i] <= 109