SDE - 1

You are given an array “arr'' of integers. Your task is to find the contiguous subarray within the array which has the largest product of its elements. You have to report this maximum product.

An array c is a subarray of array d if c can be obtained from d by deletion of several elements from the beginning and several elements from the end.

For e.g.- The non-empty subarrays of an array [1,2,3] will be- [1],[2],[3],[1,2],[2,3],[1,2,3]. 

For Example:

If arr = {-3,4,5}.
All the possible non-empty contiguous subarrays of “arr” are {-3}, {4}, {5}, {-3,4}, {4,5} and {-3,4,5}.
The product of these subarrays are -3, 4, 5, -12, 20 and -60 respectively.
The maximum product is 20. Hence, the answer is 20.

Follow Up:

Can you solve this in linear time and constant space complexity?

You are given an array of size ‘N’. The elements of the array are in the range from 1 to ‘N’.

Ideally, the array should contain elements from 1 to ‘N’. But due to some miscalculations, there is a number R in the range [1, N] which appears in the array twice and another number M in the range [1, N] which is missing from the array.

Your task is to find the missing number (M) and the repeating number (R).

For example:

Consider an array of size six. The elements of the array are { 6, 4, 3, 5, 5, 1 }. 
The array should contain elements from one to six. Here, 2 is not present and 5 is occurring twice. Thus, 2 is the missing number (M) and 5 is the repeating number (R). 

Follow Up

Can you do this in linear time and constant additional space? 

You have been given a text message. You have to return the Run-length Encoding of the given message.

Run-length encoding is a fast and simple method of encoding strings. The basic idea is to represent repeated successive characters as the character and a single count. For example, the string "aaaabbbccdaa" would be encoded as "a4b3c2d1a2".

You are given an array 'ARR' of 'N' positive integers. Your task is to find if we can partition the given array into two subsets such that the sum of elements in both subsets is equal.

For example, let’s say the given array is [2, 3, 3, 3, 4, 5], then the array can be partitioned as [2, 3, 5], and [3, 3, 4] with equal sum 10.

Follow Up:

Can you solve this using not more than O(S) extra space, where S is the sum of all elements of the given array?

Given a binary tree and the value of two nodes, find the distance between the given two nodes of the Binary Tree.

Distance between two nodes is defined as the minimum number of edges in the path from one node to another.

You have been given a non-empty grid ‘mat’ with 'n' rows and 'm' columns consisting of only 0s and 1s. All the rows are sorted in ascending order.

Your task is to find the index of the row with the maximum number of ones.

Note: If two rows have the same number of ones, consider the one with a smaller index. If there's no row with at least 1 zero, return -1.

Example:

Input: 'n' = 3, 'm' = 3, 'mat' = [[1, 1, 1], [0, 0, 1], [0, 0, 0]]

Output: 0

Explanation: The row with the maximum number of ones is 0 (0 - indexed).

You are given three strings 'A', 'B' and 'C'. Check whether 'C' is formed by an interleaving of 'A' and 'B'.

'C' is said to be interleaving 'A' and 'B', if the length of 'C' is equal to the sum of the length of 'A' and length of 'B', all the characters of 'A' and 'B' are present in 'C' and the order of all these characters remains the same in all three strings.

For Example:

If A = “aab”, 'B' = “abc”, 'C' = “aaabbc”
Here 'C' is an interleaving string of 'A' and 'B'. because 'C' contains all the characters of 'A' and 'B' and the order of all these characters is also the same in all three strings.

If 'A' = “abc”, 'B' = “def”, 'C' = “abcdefg”
Here 'C' is not an interleaving string of 'A' and 'B'. 'B'ecause neither A nor 'B' contains the character ‘g’.

Given a Binary Tree, convert this binary tree to a Doubly Linked List.

A Binary Tree (BT) is a data structure in which each node has at most two children.

A Doubly Linked List contains a previous pointer, along with the next pointer and data.

The order of nodes in Doubly Linked List must be the same as Inorder of the given Binary Tree.

The doubly linked list should be returned by taking the next pointer as right and the previous pointer as left.

You need to return the head of the Doubly Linked List.

For the given binary tree :

You need to return the head to the doubly linked list.
The doubly linked list would be: 1 2 3 4 5 and can be represented as: