SDE - Intern

You are given a matrix 'MAT' with ‘N’ rows and ‘N’ columns, and an ant is initially sitting on a coordinate given to you. The ant moves in an interesting way. If the ith row and jth column value are 1, it rotates 90 degrees in the right direction and moves 1 step forward. If the value at the ith row and jth column are 0, it rotates 90 degrees in the left direction and moves 1 step forward.

Your task is to find the final coordinates of the ant.

Note:

The ant initially faces toward the east side. Every time an ant moves from a block, it inverts it, i.e., changes 0 to 1 and 1 to 0.

If the ant exits the matrix just return -1,-1.

For example,

If ‘N’ = 2    
mat[2][2] = {{1, 1},
             {0, 0}}
startingRow = 0 , startingColumn = 0
moves = 1
The ant is initially facing the east side, it will take a right turn and move 1 stop in the south.    
The output will be 1 0.

You are given a string S consisting of lowercase characters only, an index ‘i’ and length ‘len’. Your task is to find the count of all palindromic substrings in the string ‘S’ which start at index ‘i’ and have a length of at least ‘len’.

A string is called palindromic if it reads the same backward as forward. ex "aba" is a palindrome but "abaab" is not a palindrome.

Note: A substring is a contiguous non-empty segment of the string.

For example:

String S = ababa
Index i = 1
len = 3

The answer to the above test case is 2 since there are two substrings that start at index 1 (1 - based indexing) - “aba”, “ababa”. Both these have a length of at least 3.

You are given an array ‘ARR’ having ‘N’ integers. You are also given an integer ‘K’. The task is to count the number of subarrays that have ‘K’ distinct values.

Subarray: A consecutive sequence of one or more values taken from an array.

For Example :

‘N’ = 4, ‘K’ = 2
‘ARR’ = [1, 1, 2, 3]

There are ‘3’ subarrays with ‘2’ distinct elements, which are as follows: [1, 2], [2, 3], [1, 1, 2].
Thus, you should return ‘3’ as the answer.

You are given an array 'arr' containing 'n' non-negative integers.

Your task is to partition this array into two subsets such that the absolute difference between subset sums is minimum.

You just need to find the minimum absolute difference considering any valid division of the array elements.

Note:

1. Each array element should belong to exactly one of the subsets.

2. Subsets need not always be contiguous.
For example, for the array : [1, 2, 3], some of the possible divisions are 
   a) {1,2} and {3}
   b) {1,3} and {2}.

3. Subset-sum is the sum of all the elements in that subset. 

Example:

Input: 'n' = 5, 'arr' = [3, 1, 5, 2, 8].

Ouput: 1

Explanation: We can partition the given array into {3, 1, 5} and {2, 8}. 
This will give us the minimum possible absolute difference i.e. (10 - 9 = 1).

You have been given a Binary Tree of distinct integers and two nodes ‘X’ and ‘Y’. You are supposed to return the LCA (Lowest Common Ancestor) of ‘X’ and ‘Y’.

The LCA of ‘X’ and ‘Y’ in the binary tree is the shared ancestor of ‘X’ and ‘Y’ that is located farthest from the root.

Note :

You may assume that given ‘X’ and ‘Y’ definitely exist in the given binary tree.

For example :

For the given binary tree

LCA of ‘X’ and ‘Y’ is highlighted in yellow colour.

You have been given a long type array/list 'arr’ of size 'n’.

It represents an elevation map wherein 'arr[i]’ denotes the elevation of the 'ith' bar.

Print the total amount of rainwater that can be trapped in these elevations.

Note :

The width of each bar is the same and is equal to 1.

Example:

Input: ‘n’ = 6, ‘arr’ = [3, 0, 0, 2, 0, 4].

Output: 10

Explanation: Refer to the image for better comprehension:

Note :

You don't need to print anything. It has already been taken care of. Just implement the given function.