SDE - Intern

Ninja is a genius in mathematics. He got an interview call from MIT. During the interview, the professor asked Ninja a challenging question.

Given two integers 'N1' and 'N2', the professor asked Ninja to find the fraction when the first number i.e 'N1' is divided by the second number i.e 'N2'. If the fractional part is repeating, then the repeating part should be enclosed in parentheses.

For example, if 'N1' is 1 and 'N2' is 3 and when we divide 1 by 3 i.e 1/3, the answer is 0.333... Here 3 is repeated infinite times because the remainder never becomes zero in this problem. As we know the fractional part ( i.e 3 ) is repeating, so we have to enclose the repeating part in parentheses. Therefore, the answer is “0.(3)”.

Ninja is stuck in this problem. Can you help Ninja to crack this interview and get admission in MIT?

You have been given a curve whose edges are parallel to either x-axis or y-axis. You need to return another curve which will pass through the midpoints of all the edges of the curve. The curve will be given in the form of a linked list, where each node represents the coordinates of the curve.

The curve to be returned will also be in the form of a linked list, where each node may represent the coordinates of the midpoints of the edges.

Note

1. The coordinates of the curve will be given in non-descending order of x coordinate from start to end of the linked list and for every two adjacent coordinates either the x-coordinate or the y-coordinate will be the same.
2. All the coordinates will be pairwise distinct i.e there are no two coordinates (x1, y1) and (x2, y2) such that x1 = x2 and y1 = y2.
3. The first coordinate and the last coordinate in the input can be assumed as the starting point and the ending point of the curve respectively.
4. You may assume that the starting point and ending point of the curve will be the midpoint of the first edge, and the last edge of the input curve( in the order of input coordinates) respectively.
5. If the coordinates of the midpoint are not whole numbers, you may take the floor value of the coordinates. For example, the midpoint (3.5, 5) will be taken as (3, 5).

You are given an undirected, weighted graph consisting of ‘N’ vertices and ‘M’ edges. Your task is to select 'N' - 1 edge such that a path exists between each pair of vertices and the weight of the spanning tree of the graph is minimum.

A minimum spanning tree is a sub-graph of an undirected connected graph, which includes all the vertices of the graph with a minimum possible sum of the weight of edges.

For Example :

Consider a graph having 4 vertices. These 4 vertices are connected by 5 bidirectional edges given as :
1 --- 2 with weight = 8
2 --- 3 with weight = 6
3 --- 4 with weight = 5
1 --- 4 with weight = 2
1 --- 3 with weight = 4

Now, the best way to choose 3 edges is:
2 --- 3 with weight = 6
1 --- 4 with weight = 2
1 --- 3 with weight = 4
The weight of the minimum spanning tree is 2 + 4 + 6, i.e., 12.

Given a directed graph, check whether the graph contains a cycle or not. Your function should return true if the given graph contains at least one cycle, else return false.

Given an array of ‘N’ integers and ‘Q’ queries. The query is defined as below :-

Given 2 integers ‘l’ and ‘r’ (‘l’ >= 0 and ‘r’ < N) find the maximum subarray sum between ‘l’ to ‘r’ (Inclusive).

Query( ‘l’ ,’r’) = max(arr[i] + arr[i+1] +...arr[j].( i >= ‘l’ and j <= ‘r’)

We are suffering from the Second wave of Covid-19. The Government is trying to increase its vaccination drives. Ninja wants to help the Government to plan an effective method to help increase vaccination following safety measures. Time is running out. Can you help the nation?

You are given two positive integers: ‘n,’ ‘maxVaccines’ denoting the number of days for which this vaccination drive will go on and the total number of vaccines available for the drive, respectively. You have to find the number of vaccines administered each day. You are also given a number ‘dayNumber,’ and we are interested to know the maximum number of vaccines that can be administered on ‘dayNumber’ th day.

The rules of the vaccination drive :

1. There should be a positive number of vaccines administered each day during the vaccination drive.

2. The absolute difference between the number of vaccines in two consecutive days should not exceed 1.

3. The sum of all the elements of the vaccines array does not exceed maxVaccines, that is, you cannot administer more vaccines than what is provided to you.

4. Vaccines administered on ‘dayNumber’ th day should be maximized.