SDE - 1

You are given a string 'str' of length 'N'.

Your task is to return the longest palindromic substring. If there are multiple strings, return any.

A substring is a contiguous segment of a string.

For example :

str = "ababc"

The longest palindromic substring of "ababc" is "aba", since "aba" is a palindrome and it is the longest substring of length 3 which is a palindrome. 

There is another palindromic substring of length 3 is "bab". Since starting index of "aba" is less than "bab", so "aba" is the answer.

You are given an array of integers 'ARR' of length 'N' and an integer Target. Your task is to return all pairs of elements such that they add up to Target.

Note:

We cannot use the element at a given index twice.

Follow Up:

Try to do this problem in O(N) time complexity. 

You are given an array, ‘COORDINATES’ that represents the integer coordinates of some points on a 2D plane. Your task is to find the minimum cost to make all the points connected where the cost of connecting two points: (x1, y1) and (x2, y2) is equal to the manhattan distance between them, i.e., |x1 - x2| + |y1 - y2|.

Note:

1) An element of the ‘COORDINATES’ array is a pair of ‘X' and ‘Y’ coordinates of a point, i.e., COORDINATES[i] =  (Xi, Yi).

2) |DISTANCE| represents the absolute value of distance.

3) All points are considered to be connected if there is exactly one simple path between two points.

4) According to Wikipedia, a simple path is a path in a plane that does not have repeating points.

You are given an array 'ARR' of integers of length N. Your task is to find the first missing positive integer in linear time and constant space. In other words, find the lowest positive integer that does not exist in the array. The array can have negative numbers as well.

For example, the input [3, 4, -1, 1] should give output 2 because it is the smallest positive number that is missing in the input array.

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.

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

1. Push(num): Push the given number in the stack.
2. Pop: Remove and return the top element from the stack if present, else return -1.
3. Top: return the top element of the stack if present, else return -1.
4. getMin: Returns minimum element of the stack if present, else return -1.

For Example:

For the following input: 
1
5
1 1
1 2
4
2
3

For the first two operations, we will just insert 1 and then 2 into the stack which was empty earlier. So now the stack is => [2,1]
In the third operation, we need to return the minimum element of the stack, i.e., 1. So now the stack is => [2,1]
For the fourth operation, we need to pop the topmost element of the stack, i.e., 2. Now the stack is => [1]
In the fifth operation, we return the top element of the stack, i.e. 1 as it has one element. Now the stack is => [1]

So, the final output will be: 
1 2 1

You are given a 2-D matrix of dimensions 'N' x 'M', each row of the matrix is sorted in non-decreasing order, and each column is sorted in non-decreasing order.

You are also given an integer ‘X’. You are supposed to find whether 'X' is present in the given matrix.

Given a 2D grid having N Rows and M Columns. Each cell of the grid has a character among [ 'U', 'L', 'D', 'R' ] written on it, denoting Up, Left, Down, and Right respectively and indicating the direction in which it is permitted to move from that cell to its neighbor. Your task is to find the minimum number of cells whose direction value is required to be changed so that there exists a path from Top-Left to the Bottom-Right cell by following the directions written on the cells.

For example,

Consider the 2 * 2 grid

Let's call the four cells in the grid as A,B,C,D. In this grid, it is allowed to move from Cell A to Cell B, Cell B to Cell D, Cell C to Cell D and Cell D to Cell C. There are two paths that start from A and ends at D:

1) A->C->D
To follow this path we need to change the value of cell A to “D” and do not need to change the value of cell C. Therefore, the total change for this path is 1.

2) A->B->D
To follow this path we need not to change any of the cell values. Therefore the total changes for this path is 0.

As we can see the minimum changes required to reach the bottom-right cell is Zero therefore the answer is 0 in this case.

You have been given an array/list ‘ARR’ consisting of ‘N’ positive integers. Your task is to return the Next Greater Element(NGE) for every element.

The Next Greater Element for an element ‘X’ is the first element on the right side of ‘X’ in the array 'ARR', which is greater than ‘X’. If no such element exists to the right of ‘X’, then return -1.

For example:

For the given array 'ARR' = [7, 12, 1, 20]

The next greater element for 7 is 12.
The next greater element for 12 is 20. 
The next greater element for 1 is 20. 
There is no greater element for 20 on the right side.

So, the output is [12, 20, 20, -1].

You are given two strings S and X containing random characters. Your task is to find the smallest substring in S which contains all the characters present in X.

Example:

Let S = “abdd” and X = “bd”.

The windows in S which contain all the characters in X are: 'abdd', 'abd', 'bdd', 'bd'. 
Out of these, the smallest substring in S which contains all the characters present in X is 'bd'. 
All the other substring have a length larger than 'bd'.