SDE - 1

You are given a two-dimensional matrix of integers of dimensions N*M, where each cell represents the number of coins in that cell. Alice and Bob have to collect the maximum number of coins. The followings are the conditions to collect coins:

Alice starts from top left corner, i.e., (0, 0) and should reach left bottom corner, i.e., (N-1, 0). Bob starts from top right corner, i.e., (0, M-1) and should reach bottom right corner, i.e., (N-1, M-1).

From a point (i, j), Alice and Bob can move to (i+1, j+1) or (i+1, j-1) or (i+1, j)

They have to collect all the coins that are present at a cell. If Alice has already collected coins of a cell, then Bob gets no coins if goes through that cell again.

For example :

If the matrix is 
0 2 4 1
4 8 3 7
2 3 6 2
9 7 8 3
1 5 9 4

Then answer is 47. As, Alice will collect coins 0+8+3+9+1 = 21 coins. Bob will collect coins 1+7+6+8+4 = 26 coins. Total coins is 21+26 = 47 coins.

You have been given an array/list 'WORDS' of 'N' non-empty words, and an integer 'K'. Your task is to return the 'K' most frequent words sorted by their frequency from highest to lowest.

Note:

If two words have the same frequency then the lexicographically smallest word should come first in your answer.

Follow up:

Can you solve it in O(N * logK) time and O(N) extra space? 

You are given an ‘N’ x ‘M’ matrix ‘MAT’ and an integer ‘K’. Your task is to find the maximum sum of a rectangle in the matrix which is less than or equal to ‘K’.

For Example:

You are given ‘MAT’= [[1, 2],[3, 4]] and ‘K’ = 8. 

Then the answer will be 7 (the sum of the red rectangle).

You are given a matrix ‘MAT’ consisting of ‘N’ rows and ‘M’ columns. Let (i, j) represent the cell at the intersection of the ith row and the jth column. Each cell of the matrix ‘MAT’ has either integer 0 or 1. For each cell in ‘MAT’, you have to find the Manhattan distance of the nearest cell from this cell that has the integer 0. The nearest cell will be the cell having the minimum Manhattan distance from it.

Manhattan distance between two cells, (p1, q1) and (p2, q2) is |p1 - p2| + |q1 - q2|.

You should return a matrix consisting of ‘N’ rows and ‘M’ columns, where the cell (i, j) represents the Manhattan distance of the nearest cell from the cell (i, j) in ‘MAT’ that has integer 0.

Note

1. There is at least one cell having the integer 0 in the given matrix.

Example:

Consider the following 2*3 matrix ‘MAT’:
                 [0, 1, 1]
                 [0, 1, 1]

Here, the nearest cell having the integer 0 from the cell (0, 0) is the cell (0, 0) itself. The Manhattan distance between them is |0 - 0| + |0 - 0| = 0.

The nearest cell having the integer 0 from the cell (0, 1) is cell (0, 0). The Manhattan distance between them is |0 - 0| + |1 - 0| = 1.

The nearest cell having the integer 0 from the cell (0, 2) is cell (0, 0). The Manhattan distance between them is |0 - 0| + |2 - 0| = 2.

The nearest cell having the integer 0 from the cell (1, 0) is cell (1, 0) itself. The Manhattan distance between them is |1 - 1| + |0 - 0| = 0.

The nearest cell having the integer 0 from the cell (1, 1) is cell (1, 0). The Manhattan distance between them is |1 - 1| + |1 - 0| = 1.

The nearest cell having the integer 0 from the cell (1, 2) is cell (1, 0). The Manhattan distance between them is |1 - 1| + |2 - 0| = 2.
Thus we should return matrix:

                [0, 1, 2]
                [0, 1, 2]

1. Why Dunzo?

2. Where do you see yourself after 5 years?