SDE - 1

Given a linked list containing N nodes where each node is associated with a certain value. The list is the representation of the level order traversal of a binary tree, you need to construct a complete binary tree from the given list and return its root.

Note

1. A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes at the last level are as far left as possible.
2. All the node values are positive.
3. The size of the linked list is greater than 1.
4. The end of the linked list is represented by -1.

You are given a string S which represents a number. You have to find the smallest number strictly greater than the given number which contains the same set of digits as of the original number i.e the frequency of each digit from 0 to 9 should be exactly the same as in the original number.

For example:

If the given string is 56789, then the next greater number is 56798. Note that although 56790 is also greater than the given number it contains 1 '0' which is not in the original number and also it does not contain the digit '8'.

Note:

The given string is non-empty.

If the answer does not exist, then return -1.

The given number does not contain any leading zeros.

You have given a 2-dimensional array ‘ARR’ with ‘N’ rows and ‘M’ columns in which each element contains only two values,i.e., 0 and 1. Your task is to convert the given matrix into the Good matrix in which if an element is 0, you need to set all elements values present in its entire row and column to 0.

For example:

Consider ARR = [[1 , 0 , 1] ,
                [1 , 1 , 1] , 
                [1 , 1 , 1]], 
the Good matrix after updating the given matrix as described in the question is  
                [[0 , 0 , 0] , 
                 [1 , 0 , 1] , 
                 [1 , 0 , 1]]. 
Since ARR[0][1] is 0, we need to set all element’s values present in 0-th row and 1-th column to 0.

Note :

You do not need to print the matrix. Just change in the given input.

You have been given an array of ‘N’ distinct integers which is sorted in ascending order and then rotated to the left by an unknown which you don’t know beforehand. For a given integer ‘X’, your task is to find the index of ‘X’ in the given array if it exists.

Please note that the sorted array A : [2, 3, 6, 8, 9, 11, 15] might become [6, 8, 9, 11, 15, 2, 3] after rotating it twice to the left.

You are given an array “A” of N integers. Your task is to find the maximum element in all K sized contiguous subarrays from left to right.

For Example:

If A = [3, 2, 3], and K = 2.
Then max of [3, 2] = 3 and max of [2, 3] = 3
So, the answer will be [3, 3]

If A = [3, 2, 3, 5, 1, 7] and K = 3.
Then max of [3, 2, 3] = 3 
Then max of [2, 3, 5] = 5 
Then max of [3, 5, 1] = 5 
Then max of [5, 1, 7] = 7 
So  the answer will be [3, 5, 5, 7]

Follow Up :

Can you solve the problem in O(N) time complexity and O(K) space complexity?

You are given an array containing 'N' points in the plane. The task is to find out the distance of the closest points.

Note :

Where distance between two points (x1, y1) and (x2, y2) is calculated as [(x1 - x2) ^ 2] + [(y1 - y2) ^ 2].

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