SDE - 1

Given an array of integers ‘ARR’. Let Ck be defined as an array obtained after cyclically shifting 'K' elements towards the right.

The power of an array is defined as follows.

Power(k) = 0 * Ck[0] + 1 * Ck[1] + ... + (n - 1) * Ck[n - 1].

You have to find the maximum value among Power(0), Power(1), Power(2), ……., Power(n - 1).

You have been given a binary tree, you are supposed to return the root values of all the duplicate subtrees. For each duplicate subtree, you only need to return the root value of any one of them.

Two subtrees are duplicate if and only if they have the same structure with the same node values.

For example:

In the below binary tree :

The duplicate subtrees are {{2, 3}, {3}} and we have to just return the root values of each duplicate subtree, so the output is {2, 3}.

You are given an 'N' * 'M' sized binary-valued matrix 'MAT, where 'N' is the number of rows and 'M' is the number of columns. You need to return the maximum size (area) of the submatrix which consists of all 1’s i.e. the maximum area of a submatrix in which each cell has only the value ‘1’.

In the above image, areas in green, red, and violet color are all submatrices of the original 4x4 matrix.

Note:

1. Binary valued matrix has only two values in each cell : 0 and 1.
2. A submatrix is a matrix formed by selecting certain rows and columns from a larger matrix.
3. The area of a matrix with 'h' rows and 'w' columns is equal to 'h' * 'w'. 

You are given a binary tree whose each node is associated with some integer value. You have to break this tree into two parts by removing exactly one edge. You also have to maximise the product of the sum of the integers associated with each node in both parts.

For Example:

Consider the above example, if we break the tree by removing the edge between nodes that has integers 5 and 6 then we get the maximum product of the sum of integers on nodes i.e. ( (6 + 4 + 1) * (5 + 1 + 3 + 2) ) = 121.

Note:

The answer may be very large so, you have to take the modulo with 10^9 + 7.

You are given 'N' jobs with their start time 'Start', end time 'End' and profit 'Profit'. You need to tell the maximum profit you can obtain by performing these jobs such that no two jobs overlap.

Note:

The start time of one job can be equal to the end time of another.

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.

Given an adjacency list representation of a directed graph with ‘n’ vertices and ‘m’ edges. Your task is to return a list consisting of Breadth-First Traversal (BFS) starting from vertex 0.

In this traversal, one can move from vertex 'u' to vertex 'v' only if there is an edge from 'u' to 'v'. The BFS traversal should include all nodes directly or indirectly connected to vertex 0.

Note:

The traversal should proceed from left to right according to the input adjacency list.

Example:

Adjacency list: { {1,2,3},{4}, {5}, {},{},{}}

The interpretation of this adjacency list is as follows:
Vertex 0 has directed edges towards vertices 1, 2, and 3.
Vertex 1 has a directed edge towards vertex 4.
Vertex 2 has a directed edge towards vertex 5.
Vertices 3, 4, and 5 have no outgoing edges.

We can also see this in the diagram below.

BFS traversal: 0 1 2 3 4 5

Ninja wants to try some sweets in a sweet shop. There are ‘N’ types of sweets available at that shop. Each sweet has a sweetness level and expiry date. Ninja is fond of sweets, so he sets a specific sweetness level ‘X’ and is only likely to buy the sweets having a sweetness level greater than equal to ‘X’. But Ninja also wants fresher sweets, so he only buys having expiry date strictly greater than ‘Y’. Can you help Ninja to find the number of sweets suitable for him to buy?

You are given two arrays, ‘SWEET’ and ‘EXPIRY’, both having ‘N’ values corresponding to the sweetness and expiry date of ith sweet. Ninja will ask ‘Q’ queries with ‘X’ as the minimum sweetness level and ‘Y’ as the minimum expiry date. Your task is to answer all ‘Q’ queries and tell the number of sweets satisfying the given condition for each query.

For Example

For the given if N = ‘5’, ‘SWEET’ = [1,3,6,7,2] and ‘EXPIRY = [10,7,2,6,4].
And the query is ‘X’=2  and  ‘Y’ =6 ,then the number of sweets satisfying the condition is only 1 (having sweetness 3 and expiry date 7). 

Given an array/list of length ‘n’, where the array/list represents the boards and each element of the given array/list represents the length of each board. Some ‘k’ numbers of painters are available to paint these boards. Consider that each unit of a board takes 1 unit of time to paint.

You are supposed to return the area of the minimum time to get this job done of painting all the ‘n’ boards under a constraint that any painter will only paint the continuous sections of boards.

Example :

Input: arr = [2, 1, 5, 6, 2, 3], k = 2

Output: 11

Explanation:
First painter can paint boards 1 to 3 in 8 units of time and the second painter can paint boards 4-6 in 11 units of time. Thus both painters will paint all the boards in max(8,11) = 11 units of time. It can be shown that all the boards can't be painted in less than 11 units of time.