SDE - 1

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 have been given a binary matrix of size 'N' * 'M' where each element is either 0 or 1. You are also given a source and a destination cell, both of them lie within the matrix.

Your task is to find the length of the shortest path from the source cell to the destination cell only consisting of 1s. If there is no path from source to destination cell, return -1.

Note:

1. Coordinates of the cells are given in 0-based indexing.
2. You can move in 4 directions (Up, Down, Left, Right) from a cell.
3. The length of the path is the number of 1s lying in the path.
4. The source cell is always filled with 1.

For example -

1 0 1
1 1 1
1 1 1
For the given binary matrix and source cell(0,0) and destination cell(0,2). Few valid paths consisting of only 1s are

X 0 X     X 0 X 
X X X     X 1 X 
1 1 1     X X X 
The length of the shortest path is 5.

You are given a string 'S' of length 'N', you need to find the frequency of each of the characters from ‘a’ to ‘z’ in the given string.

Example :

Given 'S' : abcdg
Then output will be : 1 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 

You are given a matrix 'MAT' of size ‘N’ * ‘M’, where ‘N’ is the number of rows and ‘M’ is the number of columns. Value ‘0’ in a cell represents that the cell is set on fire initially, (at time t = ‘0’), and the cells which don’t have fire initially have value = ‘1’, and are called safe cells.

If a cell is on fire, then in one second the fire will expand to its adjacent cells (left, right, top, bottom) if they are not already on fire.

You are given the position of a person as integers ‘X’ and ‘Y’ denoting the cell (‘X’, ‘Y’). In one second the person can move from its current cell to any one of its adjacent cells, provided they are not on fire.

You have to determine if the person can move through the matrix to one of the escape cells without burning himself i.e. without going through the fire cells. If it’s possible, return time taken, else return -1.

Note:

1. Escape cells in this problem are all such cells that lie on the edge of the matrix but not on the corner. i.e all such cells which are in the first row, first column, last row, and last column excluding the four corner cells are considered as valid escape cells.

2. A cell once set on fire continues to remain on fire till the end.

3. Note that rows are indexed from 0 to ‘N’ - 1 and columns are indexed from 0 to ‘M’ - 1.

4. The escape cells may also be initially on fire or can catch fire from some neighboring cell.

You are given an N*M binary matrix, considering for every 0-cell(cell with value = 0) the distance from this cell to its nearest 1-cell(cell with value = 1) is 'di', you need to find the maximum value of 'di' among all values of 'di'. Formally, if the minimum distance from an 'ith' 0-cell to any 1-cell is ‘di’, you need to find max(di), where i belongs to the set of all 0-cells in the matrix.

Distance between cells (i,j) and (a,b) is given as (|i-a| + |j-b|) i.e the manhattan distance is considered here.

Here, the arrows starting from the 0-cell’s point towards their corresponding nearest one cell, and among all of these, the arrow in purple and orange gives the maximum distance, i.e., 2.

Note:

1) Binary matrix of size N*M is a matrix with N rows and M columns, in which all the cells have either value 0 or 1.
2) Nearest 1-cell from a 0-cell is the cell that contains 1 and is at least a distance from the 0-cell being considered among all the other cells. For example consider the matrix {{0,1},{0,1}}. Here the nearest 1-cell for the 0-cell at index(0,0) is the 1-cell at index (0,1) because this cell is at least distance from the 0-cell being considered as the distance from the other 1-cell at index(1,1) is 2, whereas the distance from the 1-cell at index (0,1) is 1.
3) If there are no 1-cells or no 0-cells in the matrix, return -1.

You are given an array consisting of 'N' non-negative integers, and two non-negative integers 'K' and 'M', your task is to find a pair of indices(say i and j) from the array such that ‘i’ ≠ ‘j’, |Ai-Aj| <= 'M', and |i-j| <= 'K', where |a-b| represents the absolute value of a-b.

Note :

1) The array may contain duplicate elements.
2) The size of the array is at least 2.
3) The given array follows 0-based indexing so 0 <= i,j< N.
4) It is guaranteed that there exist at least one such pair of indices.

You are given an arbitrary binary tree. A binary tree is called special if every node of this tree has either zero or two children. You have to determine if the given binary tree is special or not.

If the given binary tree is special, return True. Else, return False to the given function.

Note:

1. A binary tree is a tree in which each node can have at most two children. 
2. The given tree will be non-empty i.e the number of non-NULL nodes will always be greater than or equal to 1.
3. Multiple nodes in the tree can have the same values, all values in the tree will be positive.

You have been given a sentence ‘S’ in the form of a string and a word ‘W’, you need to find whether the word is present in the given sentence or not. The word must be present as a complete string in the sentence and not a substring of some other word.

Note:

1. All the characters in the string and the word are in lowercase.
2. Length of the sentences and the words will always be greater than zero.
3. Words in the sentence will be separated by spaces.

Design and implement a data structure for Least Recently Used (LRU) cache to support the following operations:

1. get(key) - Return the value of the key if the key exists in the cache, otherwise return -1.

2. put(key, value), Insert the value in the cache if the key is not already present or update the value of the given key if the key is already present. When the cache reaches its capacity, it should invalidate the least recently used item before inserting the new item.

You will be given ‘Q’ queries. Each query will belong to one of these two types:

Type 0: for get(key) operation.
Type 1: for put(key, value) operation.

Note :

1. The cache is initialized with a capacity (the maximum number of unique keys it can hold at a time).

2. Access to an item or key is defined as a get or a put operation on the key. The least recently used key is the one with the oldest access time.