SDE - 1

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

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 are given a matrix ‘MAT’ consisting of ‘N’ rows and ‘M’ columns. Let (i, j) represent the cell at the intersection of the ith row and the jth column. Each cell of the matrix ‘MAT’ has either integer 0 or 1. For each cell in ‘MAT’, you have to find the Manhattan distance of the nearest cell from this cell that has the integer 0. The nearest cell will be the cell having the minimum Manhattan distance from it.

Manhattan distance between two cells, (p1, q1) and (p2, q2) is |p1 - p2| + |q1 - q2|.

You should return a matrix consisting of ‘N’ rows and ‘M’ columns, where the cell (i, j) represents the Manhattan distance of the nearest cell from the cell (i, j) in ‘MAT’ that has integer 0.

Note

1. There is at least one cell having the integer 0 in the given matrix.

Example:

Consider the following 2*3 matrix ‘MAT’:
                 [0, 1, 1]
                 [0, 1, 1]

Here, the nearest cell having the integer 0 from the cell (0, 0) is the cell (0, 0) itself. The Manhattan distance between them is |0 - 0| + |0 - 0| = 0.

The nearest cell having the integer 0 from the cell (0, 1) is cell (0, 0). The Manhattan distance between them is |0 - 0| + |1 - 0| = 1.

The nearest cell having the integer 0 from the cell (0, 2) is cell (0, 0). The Manhattan distance between them is |0 - 0| + |2 - 0| = 2.

The nearest cell having the integer 0 from the cell (1, 0) is cell (1, 0) itself. The Manhattan distance between them is |1 - 1| + |0 - 0| = 0.

The nearest cell having the integer 0 from the cell (1, 1) is cell (1, 0). The Manhattan distance between them is |1 - 1| + |1 - 0| = 1.

The nearest cell having the integer 0 from the cell (1, 2) is cell (1, 0). The Manhattan distance between them is |1 - 1| + |2 - 0| = 2.
Thus we should return matrix:

                [0, 1, 2]
                [0, 1, 2]

You are given a binary tree, in which the data present in the nodes are integers. You are also given an integer X.

Your task is to delete all the leaf nodes with value X. In the process, if the newly formed leaves also have value X, you have to delete them too.

For example:

For the given binary tree, and X = 3:

Ninjas is practicing problems on the linked list. He came across a problem in which he has given a linked list of ‘N’ nodes and two integers, ‘LOW’ and ‘HIGH’. He has to return the linked list ‘HEAD’ after reversing the nodes between ‘LOW’ and ‘HIGH’, including the nodes at positions ‘LOW’ and ‘HIGH’.

You have been given a Binary Tree where the value of each node is either 0 or 1. Your task is to return the same Binary Tree but all of its subtrees that don't contain a 1 have been removed.

Note :

A subtree of a node X is X, plus every node that is a descendant of X.

For Example :

Look at the below example to see a Binary Tree pruning.
Input: [1, 1, 1, 0, 1, 0, 1, 0, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1]

Output: [1, 1, 1, -1, 1, -1, 1, -1, -1, -1, -1]

For example, the input for the tree depicted in the below image would be :

1
2 3
4 -1 5 6
-1 7 -1 -1 -1 -1
-1 -1

Explanation :

Level 1 :
The root node of the tree is 1

Level 2 :
Left child of 1 = 2
Right child of 1 = 3

Level 3 :
Left child of 2 = 4
Right child of 2 = null (-1)
Left child of 3 = 5
Right child of 3 = 6

Level 4 :
Left child of 4 = null (-1)
Right child of 4 = 7
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 6 = null (-1)
Right child of 6 = null (-1)

Level 5 :
Left child of 7 = null (-1)
Right child of 7 = null (-1)

The first not-null node (of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.
The input ends when all nodes at the last level are null (-1).

Note :

The above format was just to provide clarity on how the input is formed for a given tree.

The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:
1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

Stark Industry is planning to organize Stark Expo, for which various departments have to organize meetings to check their preparations. Since Stark Tower has limited rooms available for the meeting, Tony decided to allot a room to each meeting so that all the meetings are organized in the least possible conference rooms, and a the moment, only one meeting will happen in one room. So, he asked JARVIS to allot each meeting a room and tell the minimum number of conference rooms to be reserved. But, since JARVIS was busy rendering another Iron Man suit model, he asked you to help.

You are given an array of integers ARR of size N x 2, representing the start and end time for N meetings. Your task is to find the minimum number of rooms required to organize all the meetings.

Note:

1. You can assume that all the meetings will happen on the same day.
2. Also, as soon as a meeting gets over if some other meeting is scheduled to start at that moment, they can then be allocated that room.

Note:

Try to solve the problem in linear time complexity.

For Example:

Consider there are three meetings scheduled with timings:
1pm - 4pm
3pm - 5pm
4pm - 6pm

At the start of time, meeting 1 will be allotted room 1, which will be occupied till 4 pm hence for meeting 2 we’ll have to provide another room. At 4 pm, meeting 3 can be organized in room 1 because by that time, meeting 1 would have ended. Hence we’ll require two rooms for holding all three meetings.