Codenation / Trilogy Innovations Test Experience April 2022 Online

Problem 1Dr. Betra has become bored with his research on human hair. So he decided to breed pigeons.He bought N pigeons from the shop. The shopkeeper advised him to make s...

Problem 1 Dr. Betra has become bored with his research on human hair. So he decided to breed pigeons. He bought N pigeons from the shop. The shopkeeper advised him to make sure that the pigeons were not facing each other at any point in time. Dr. Betra forgot about this and placed the pigeons in a row to feed them, tell Dr. Betra the minimum number of pigeons should he pick up and switch the direction towards which it is facing. L denotes a pigeon at ith index is facing a pigeon at (i - 1)th index, while R denotes a pigeon at ith index is facing a pigeon at (i + 1)th index.

Constraints 1 <= N <= 10 5 Input Format The first argument is a string A denoting the direction each pigeon is facing.

Output Format Returns a single integer denoting the minimum number of pigeons direction must Dr. Betra switch.

Example Input Input 1: A = LLLLLL Input 2: A = RLLLLL Example Output Output 1: 0 Output 2: 1 Example Explanation Explanation 1: All the pigeons are facing left. So the configuration is already good.

Explanation 2: We only need to switch the direction of the first pigeon to make sure no two pigeons are facing each other. Problem 2 Carl and Bernhard were trying to solve a problem, but they were stuck on graph theory this time. The problem is as follows: Given a tree A nodes given in the form of a 2D array B, where each row consists of two integers denoting the presence of an edge between the two integers. Also, given another 2D array C of Q queries, each row consists of 3 integers -U, V, and W. Find out the closest node to W on the path from U to V, where a path between the two nodes means a subtree in the form of a line graph with the two nodes as endpoints. Process each query and return an array denoting the answer to each query.

Constraints 2 <= A <= 10 5 1 <= Q <= 10 5 1 <= B[i][0], B[i][1] <= N (B[i][0] != B[i][1]) |B| = A - 1 1 <= U, V, W <= N (U != V)

Input Format The first argument is the integer A, denoting the number of nodes in the tree. The second argument is the 2D array B, denoting the edge of the tree. The third argument is the 2D integer array C, denoting the queries.

Output Format Returns an integer array denoting the answers to each query.

Example Input Input 1: A = 6 B = [ [1, 2], [1, 3], [1, 4], [3, 5], [3, 6]] C = [ [2, 5, 6], [5, 2, 6]]

Input 2: A = 6 B = [ [1, 2], [1, 3], [1, 4], [3, 5], [3, 6]] C = [ [2, 5, 1], [2, 5, 4]]

Example Output Output 1: [3, 3]

Output 2: [1, 1]

Example Explanation Explanation 1: The given tree is: 1 / | \ 4 3 2 / \ 5 6 The order of the U and V does not matter. So nodes 5, 3, 2, 1, and 2 lie in the required path. Node 3 is closest to 6. Problem 3 You are given an array B of positive integers of size 2xA. There are A rounds in total. In each round, you have to choose any two integers from the array and delete them. Your score in each round will be GCD(nums1, nums2) * round-number where num1 and num2 are the numbers you have chosen and round-number is the current round. Your total score will be the summation of the score that you have obtained in every round. Task: Determine the maximum total score The round-number starts from 1 and GCD(x, y) denotes the greatest common divisor of x and y.

Constraints 1 <= A <= 10 1 <= B[i] <= 10 9 Input format The first argument is integer A which denotes the number of rounds. The second argument is an array of integers B of 2xA size.

Output format Return the maximum score which you can obtain from the given array.

Example Input Input 1: A = 2 B = [3, 4, 9, 5]

Input 2: A = 3 B = [8, 5, 6, 25, 6, 16]

Example output:

Output 1: 7 Output 2: 41 Example explanation Explanation 1: The rounds can be placed as shown below: Round_number 1: Select num1 = 4 , num2 = 5. So the value of gcd(4, 5) * round_number equal to 1 * 1 = 1. Round_number 2: Select num1 = 3, num2 = 9. So the value of gcd(3, 9) * round_number equals to 3 * 2 = 6. Therefore the maximum total score equals = 1 + 6 = 7.

Explanation 2: The rounds can be placed as shown below: Round_number 1: Select num1 = 5 , num2 = 25. So the value of gcd(5, 25) * round_nuumber equal to 5 * 1 = 5. Round_number 2: Select num1 = 6, num2 = 36. So the value of gcd(6, 6) * round_number equals to 6 * 2 = 12. Round_number 3: Select num1 = 8 and num2 = 16 so the value of gcd(8,1 6) * round_number equals to 8 * 3 = 24. Therefore the maximum total score equals = 5 + 12 + 24 = 41.