Software Engineer

There are 'N' number of subjects and the ith subject contains subject[i] number of problems. Each problem takes 1 unit of time to be solved. Also, you have 'K' friends, and you want to assign the subjects to each friend such that each subject is assigned to exactly one friend. Also, the assignment of subjects should be contiguous. Your task is to calculate the maximum number of problems allocated to a friend is minimum. See example for more understanding.

For Example:

If N = 4, K = 2 and subjects = {50,100,300,400}
Assignment of problems can be done in the following ways among the two friends.
{} and {50,100,300,400}. Time required = max(0, 50+100+300+400) = max(0, 850) = 850
{50} and {100,300,400}. Time required = max(50, 100+300+400) = max(50, 800) = 800
{50, 100} and {300,400}. Time required = max(50+100, 300+400) = max(150, 700) = 700
{50,100,300} and {400}. Time required = max(50+100+300, 400) = max(450, 400) = 400
{50,100,300, 400} and {}. Time required = max(50+100+300+400, 0) = max(850, 0) = 850

So, out of all the above following ways, 400 is the lowest possible time.

You are given an array “A” of N integers. Your task is to find the maximum element in all K sized contiguous subarrays from left to right.

For Example:

If A = [3, 2, 3], and K = 2.
Then max of [3, 2] = 3 and max of [2, 3] = 3
So, the answer will be [3, 3]

If A = [3, 2, 3, 5, 1, 7] and K = 3.
Then max of [3, 2, 3] = 3 
Then max of [2, 3, 5] = 5 
Then max of [3, 5, 1] = 5 
Then max of [5, 1, 7] = 7 
So  the answer will be [3, 5, 5, 7]

Follow Up :

Can you solve the problem in O(N) time complexity and O(K) space 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.

Introduce yourself, why do you want to join the company, what do you know about the company etc.