MTS 1

Given an array ARR of N integers and an integer S. The task is to find whether there exists a subarray(positive length) of the given array such that the sum of elements of the subarray equals to S or not. If any subarray is found, return the start and end index (0 based index) of the subarray. Otherwise, consider both the START and END indexes as -1.

Note:

If two or more such subarrays exist, return any subarray.

For Example: If the given array is [1,2,3,4] and the value of S is equal to 7. Then there are two possible subarrays having sums equal to S are [1,2,3] and [3,4].

You are given a Binary Tree of 'n' nodes.

The Top view of the binary tree is the set of nodes visible when we see the tree from the top.

Find the top view of the given binary tree, from left to right.

Example :

Input: Let the binary tree be:

Output: [10, 4, 2, 1, 3, 6]

Explanation: Consider the vertical lines in the figure. The top view contains the topmost node from each vertical line.

You have been given a sorted array/list 'arr' consisting of ‘n’ elements. You are also given an integer ‘k’.

Now, your task is to find the first and last occurrence of ‘k’ in 'arr'.

Note :

1. If ‘k’ is not present in the array, then the first and the last occurrence will be -1. 
2. 'arr' may contain duplicate elements.

Example:

Input: 'arr' = [0,1,1,5] , 'k' = 1

Output: 1 2

Explanation:
If 'arr' = [0, 1, 1, 5] and 'k' = 1, then the first and last occurrence of 1 will be 1(0 - indexed) and 2.

Given two sorted arrays 'a' and 'b' of size 'n' and 'm' respectively.

Find the median of the two sorted arrays.

Median is defined as the middle value of a sorted list of numbers. In case the length of list is even, median is the average of the two middle elements.

The expected time complexity is O(min(logn, logm)), where 'n' and 'm' are the sizes of arrays 'a' and 'b', respectively, and the expected space complexity is O(1).

Example:

Input: 'a' = [2, 4, 6] and 'b' = [1, 3, 5]

Output: 3.5

Explanation: The array after merging 'a' and 'b' will be { 1, 2, 3, 4, 5, 6 }. Here two medians are 3 and 4. So the median will be the average of 3 and 4, which is 3.5.

You are given ‘N’ 2-D matrices and an array/list “ARR” of length ‘N + 1’ where the first ‘N’ integers denote the number of rows in the Matrices and the last element denotes the number of columns of the last matrix. For each matrix, the number of columns is equal to the number of rows of the next matrix. You are supposed to find the minimum number of multiplication operations that need to be performed to multiply all the given matrices.

Note :

You don’t have to multiply the matrices, you only have to find the minimum number of multiplication operations.

For Example :

ARR = {2, 4, 3, 2}

Here, we have three matrices with dimensions {2X4, 4X3, 3X2} which can be multiplied in the following ways:
a. If the order of multiplication is (2X4, 4X3)(3X2), then the total number of multiplication operations that need to be performed are: (2*4*3) + (2*3*2) = 36

b. If the order of multiplication is (2X4)(4X3, 3X2), then the total number of multiplication operations that need to be performed are  (2*4*2) + (4*3*2) = 40

You are given a binary tree, where the data present in each node is an integer. You have to find whether the given tree is symmetric or not.

Symmetric tree is a binary tree, whose mirror image is exactly the same as the original tree.

For Example: