SDE - 1

You are given an array 'arr' of 'N' integers. Your task is to return the total number of distinct subarrays of 'arr' having 'k' odd elements.

Example :

If arr = [3,2,3], and k = 1 
then there are 4 subarrays with 1 odd elements:
[3], [3,2], [2,3] & [3].

A virus travels on a positive number line with a range from 0 to ‘R’ in which it can travel only in the left or right direction. You are given a string ‘PATH’ representing the sequence of moves a virus can move. Your task is to find the number of distinct subsequences of those moves that lead from a given point ‘X’ to point ‘Y’ on the number line. If a virus is present at position ‘P’, then moving in the ‘l’ direction will take it to the ‘P’ - 1 position, whereas moving in the ‘r’ direction will take it to the ‘P’ + 1 position.

Note:

Subsequences are created by deleting 0 or more characters from a sequence without changing the order.

Example:

Let ‘PATH’ be: "rrr"
Let ‘X’ = 1, ‘Y’ = 2, and ‘R’ = 10
Paths are ["r", "r", "r"]. As we have to choose distinct subsequences, so the result is 1.

You have been given weights and values of ‘N’ items. You are also given a knapsack of size ‘W’.

Your task is to put the items in the knapsack such that the total value of items in the knapsack is maximum.

Note:

You are allowed to break the items.

Example:

If 'N = 4' and 'W = 10'. The weights and values of items are weights = [6, 1, 5, 3] and values = [3, 6, 1, 4]. 
Then the best way to fill the knapsack is to choose items with weight 6, 1 and  3. The total value of knapsack = 3 + 6 + 4 = 13.00   

Design and code multilevel parking lot system.

You are given an integer grid of size ‘N’x’M’, and the cell of the grid contains either of the three values:

0 - An empty cell.

1 - A fresh orange.

2 - A rotten orange.

Every minute, any fresh orange adjacent(4-directionally) to a rotten orange becomes rotten.

You must return the minimum time after which no fresh oranges are left. Return -1 if it's impossible to rot all the fresh oranges.

Example:

Input: [[2,1,1],[1,1,0],[0,0,0]]

Output: 2

At T=0, only orange at (0,0) is rotten.
At T=1, oranges at (0,0),(0,1) and (1,0) are rotten.
At T=2, oranges at (0,0),(0,1),(1,0),(0,2) and (1,1) are rotten. 
No fresh oranges are left after T=2.

Discussed on previous rounds. Past company work. Few DS questions on the last round.