SDE - 1

Consider a grid consisting of ‘N’ rows and ‘M’ columns. Rows are numbered from 0 to ‘N’-1 and columns are numbered from 0 to ‘M’-1. The cell at the intersection of the ith row and the jth column is represented as (i, j).

Initially a robot is standing at (0, 0). The robot can only move in two directions, ‘Right’ and ‘Down’. I.e if the robot is at (r, c), then it can move to (r, c+1) or (r+1, c). Some cells in the grid are blocked i.e robot cannot step on them.

You are given a matrix ‘GRID[][]’ of size N*M, where GRID[i][j] = 1 if cell (i, j) is blocked otherwise cell (i, j) = 0. Your task is to find the lexicographically smallest path for the robot from (0, 0) to (N-1, M-1). A path is represented as a list of cells in the same order in which the robot should visit. See the example for more clarity.

Note

1. In lexicographical order cell (r1, c1) comes before cell (r2, c2) if either r1 < r2 or (r1 = r2 and c1 < c2).

2. If there is no possible path,  then return a list with a single element [-1, -1].

3. It is guaranteed that cell (0, 0) is not blocked.  

Example:

Consider the following  3*4 grid -:
       [ 
         [0 0 0 0]
         [1 1 0 0]
         [0 1 1 0]
       ] 
There are two possible paths to reach cell (2, 3) from (0, 0).
Path-1 ->  [[0, 0], [0, 1], [0, 2], [0, 3], [1, 3], [2, 3]]
Path-2 ->  [[0, 0], [0, 1], [0, 2], [1, 2], [1, 3], [2, 3]]
Clearly, Path-1 is lexicographically smaller than Path-2.
Thus  we should return list  [[0, 0], [0, 1], [0, 2], [0, 3], [1, 3], [2, 3]]

You are given an array/list 'prices' where the elements of the array represent the prices of the stock as they were yesterday and indices of the array represent minutes. Your task is to find and return the maximum profit you can make by buying and selling the stock. You can buy and sell the stock only once.

Note:

You can’t sell without buying first.

For Example:

For the given array [ 2, 100, 150, 120],
The maximum profit can be achieved by buying the stock at minute 0 when its price is Rs. 2 and selling it at minute 2 when its price is Rs. 150.
So, the output will be 148.

They majorly asked question from project work.

Why should we hire you?