SDE - Intern

You are given a 'M' x 'N' matrix of characters, 'CHARACTER_MATRIX' and a string 'WORD'. Your task is to find and print all occurrences of the string in the given character matrix. You are allowed to search the string in all eight possible directions, i.e. North, South, East, West, North-East, North-West, South-East, South-West.

Note: There should not be any cycle in the output path. The entire string must lie inside the matrix boundary. You should not jump across boundaries, i.e. from row 'N' - 1 to 0 or column 'N' - 1 to 0 or vice versa.

Example:

Consider below matrix of characters,
[ 'D', 'E', 'X', 'X', 'X' ]
[ 'X', 'O', 'E', 'X', 'E' ] 
[ 'D', 'D', 'C', 'O', 'D' ]
[ 'E', 'X', 'E', 'D', 'X' ]
[ 'C', 'X', 'X', 'E', 'X' ]

If the given string is "CODE", below are all its occurrences in the matrix:

'C'(2, 2) 'O'(1, 1) 'D'(0, 0) 'E'(0, 1)
'C'(2, 2) 'O'(1, 1) 'D'(2, 0) 'E'(3, 0)
'C'(2, 2) 'O'(1, 1) 'D'(2, 1) 'E'(1, 2)
'C'(2, 2) 'O'(1, 1) 'D'(2, 1) 'E'(3, 0)
'C'(2, 2) 'O'(1, 1) 'D'(2, 1) 'E'(3, 2)
'C'(2, 2) 'O'(2, 3) 'D'(2, 4) 'E'(1, 4)
'C'(2, 2) 'O'(2, 3) 'D'(3, 3) 'E'(3, 2)
'C'(2, 2) 'O'(2, 3) 'D'(3, 3) 'E'(4, 3)

Given a positive even integer 'K', your task is to find two prime numbers whose sum is equal to 'K'. If there are multiple answers, you may find any.

Example , for K = 4 the pair is ( 2, 2) , For K = 10 the pair is ( 3, 7).

Note :

It is guaranteed that 'K' will always be greater than two.

You are given a N x M matrix of integers, print the spiral path of the matrix.

For example:

You are given an array ‘Arr’ consisting of ‘N’ distinct integers and a positive integer ‘K’. Find out Kth smallest and Kth largest element of the array. It is guaranteed that K is not greater than the size of the array.

Example:

Let ‘N’ = 4,  ‘Arr’ be [1, 2, 5, 4] and ‘K’ = 3.  
then the elements of this array in ascending order is [1, 2, 4, 5].  Clearly, the 3rd smallest and largest element of this array is 4 and 2 respectively.

You are given an integer array 'ARR' of size 'N' and an integer 'S'. Your task is to return the list of all pairs of elements such that each sum of elements of each pair equals 'S'.

Note:

Each pair should be sorted i.e the first value should be less than or equals to the second value. 

Return the list of pairs sorted in non-decreasing order of their first value. In case if two pairs have the same first value, the pair with a smaller second value should come first.

You have a 3 and a 5 litre water container, each container has no markings except for that which gives you it's total volume. You also have a running tap. You must use the containers and the tap in such away as to exactly measure out 4 litres of water. How is this done?

A thief wants to loot houses. He knows the amount of money in each house. He cannot loot two consecutive houses. Find the maximum amount of money he can loot.

You have been given a Binary Tree of integers.

Your task is to print the Right view of it.

The right view of a Binary Tree is a set of nodes visible when the tree is viewed from the Right side and the nodes are printed from top to bottom order.

You are given an 'N * N' matrix of integers where each row and each column is sorted in increasing order. You are given a target integer 'X'.

Find the position of 'X' in the matrix. If it exists then return the pair {i, j} where 'i' represents the row and 'j' represents the column of the array, otherwise return {-1,-1}

For example:

If the given matrix is:
[ [1, 2, 5],
  [3, 4, 9],
  [6, 7, 10]] 
We have to find the position of 4. We will return {1,1} since A[1][1] = 4.

Given a sequence of ‘N’ space-separated non-negative integers A[1],A[2],A[3],......A[i]…...A[n]. Where each number of the sequence represents the height of the line drawn at point 'i'. Hence on the cartesian plane, each line is drawn from coordinate ('i',0) to coordinate ('i', 'A[i]'), here ‘i’ ranges from 1 to ‘N’. Find two lines, which, together with the x-axis forms a container, such that the container contains the most area of water.

Note :

1. You can not slant the container i.e. the height of the water is equal to the minimum height of the two lines which define the container.

2. Do not print anything, you just need to return the area of the container with maximum water.

Example

For the above Diagram, the first red marked line is formed between coordinates (2,0) and (2,10), and the second red-marked line is formed between coordinates (5,0) and (5,9). The area of water contained between these two lines is (height* width) = (5-2)* 9 = 27, which is the maximum area contained between any two lines present on the plane. So in this case, we will return 3* 9=27.

Pay an employee using a gold rod of 7 units