Software Engineer

You are given an unsorted array containing ‘N’ integers. You need to find ‘K’ largest elements from the given array. Also, you need to return the elements in non-decreasing order.

Given a graph, check whether the graph is bipartite or not. Your function should return true if the given graph's vertices can be divided into two independent sets, ‘U’ and ‘V’ such that every edge (‘u’, ‘v’) either connects a vertex from ‘U’ to ‘V’ or a vertex from ‘V’ to ‘U’.

You are given a 2D array ‘edges’ which contains 0 and 1, where ‘edges[i][j]’ = 1 denotes a bi-directional edge from ‘i’ to ‘j’.

Note:

If edges[i][j] = 1, that implies there is a bi-directional edge between ‘i’ and ‘j’, that means there exists both edges from ‘i’ to ‘j’ and to ‘j’ to ‘i’.

For example

Given:
‘N’ = 3
‘edges’ = [[0, 1, 1], [0, 0, 1], [0,0,0]]. 

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

You have been given an N-ary tree ‘N’ nodes with node ‘1’ as head of the tree. Encode the above N-ary tree into a binary tree such that if only the encoded binary tree was given to you, you could restore the N-ary tree from the encoded binary tree. You also need to write a function that could decode a given binary tree and return a N-ary tree as in input format.

Note:

There is no restriction on how you encode/decode the N-ary tree.

Example:

N-ary Tree is given as follows:-
6
1 -1 2 3 4 -1 5 -1 6 -1 -1 -1 -1
The above N-ary tree and its encoded binary tree can be represented as follows:-

The above binary tree can be represented as follows in their level order traversal:-
1
2 -1
5 3
-1 -1 6 4
-1 -1 -1 -1

You are given a string ‘S’ of lowercase English letters. Your task is to partition this string into as many parts as possible so that all the occurrences of the same letter appear in exactly one of the partitions.

For example:

"qvmwtmzzse" is the given string. We can make the first two partitions as ‘q’, ‘v’, but ‘m’ can not be an individual partition because there is another occurrence of m  at index 6. So, the minimum length of the third partition is from index 3 to 6 and the partition is "mwtm". Similarly, the next partitions are "zz", ‘s’, ‘e’.