Role: SE
Location: Bangalore
Date: December 1, 2020

Round 1: A simple BFS question.

There are K people standing in a mxn grid. There is a meeting point on the same grid. Also, there are some blocks on the grid, where you cannot step on. The K people can move in all the four orthogonal directions. To move from a point on the grid to its neighbour, it takes 1 unit of time. What is the total time taken by all the people to reach the meeting point.(ie, sum of time taken by each of the K-people)

Solution:
Start BFS from the meeting point and visit all the K people. Just add the time taken.

Follow up:

What if the meeting point is not known? Find the meeting point such the total time taken is minimised.

Solution:

Start BFS from each of the K locations. For each point on the grid, calculate the total time taken to visit by each of the K people. Return the point with the minimum time.

Round 2: DP question

You are given an array of length N and number K(<=N)You can pick numbers from either start or the end of the array. You need to pick K numbers, such that sum of the numbers is maximised.

Solution:

Greedy will not work. You need to ideally pick L entries from the start of the array and K-L entries from the end. Can be done in O(K) time.(where L can be 0,..,K)

Follow up:

Now, additionally you have a multiplier array of size K. Such that the first entry picked gets multiplied by the first number in the multiplier and so on. Now find the maximum possible sum.

Solution:

Stuck. Dont know. Someone can help out in the comments. The same idea as in the previous question might not work.