Question: Confluent, Recently Asked On-Campus Assessments in IIT-G, October, 2022
0
Entering edit mode

# Question 1

## Bob Navigates a Maze

Bob and Alice have teamed up on a game show. After winning the first round, they now have access to a maze with hidden gold. If Bob can collect all the gold coins and deliver them to Alice's position, they can split the gold. Bob can move horizontally or vertically as long as he stays in the maze, and the cell is not blocked.

The maze is represented by an n xm array. Each cell has a value, where 0 is open, 1 is blocked, and 2 is open with a gold coin. Bob starts at the top left in cell in (row, column) = (0, 0). Alice's position is given by (x,y). Determine the shortest path Bob can follow to collect all gold coins and deliver them to Alice. If Bob can't collect and give all the gold coins, return -1.

Example: maze = [[0,2,1],[1,2,0],[1,0,0]] with Alice at (2,2) is represented as follows:

B represents Bob's starting position at (0,0), and A represents Alice's position (which will also be Bob's final position). As Bob starts at (0,0), he has two possible paths to collect the gold and deliver to Alice: (0, 0) -> (0, 1) -> (1, 1) -> (2, 1) -> (2, 2) and (0, 0) -> (0, 1) -> (1, 1) -> (1, 2) -> (2, 2). Both paths have a length of 4 and could represent the shortest path.

Function Description

Complete the function minMoves in the editor below. The function must return the integer length of Bob's shortest path, or -1 if it's not possible.

minMoves has the following parameter(s):

maze[maze[0][0]...maze[n-1][m-1]]: a 2D array of integers

x: an integer denoting Alice's row coordinate

y: an integer denoting Alice's column coordinate

Constraints:

• 1 <= n,m <= 100
• 0 <= the number of coins <= 10
• 1 <= x < n
• 1 <= y < m

# Question 2

## Paths in Warehouse

There are n players. They have to collect m points. All the players and coins are in 1-D space i.e on a number line. The initial location of all the players is given as the array players where player[i] denotes the location of the ith player. The location of all the points is given as another array point where point[i] denotes the location of the ith point. In one second a player can either move 1 step left or 1 step right or not move at all. A point is considered collected if any of the n players had visited the point's location. The players can move simultaneously and independently of each other every second.

The task is to find the minimum time (in seconds) required to collect all the points if players act optimally.

Note: Locations of players and points are not necessarily given in sorted order.

Example

n = 3, players = [3, 6, 7]

m= 4, points = [2,4,7,9]

All the points can be collected in 2 seconds:

• The first player can collect points at [2] in one second
• The second player can collect points at [4] in 2 seconds
• The third player can collect points at [7,9] in 2 seconds, first collecting the point at 7 and then moving to location 9.

It can be proved that we can't collect all the points in less than 2 seconds. Hence the answer is 2.

Function Description

Complete the function getMinimumTime in the editor below. The function must return an integer, the minimum time required to collect all the points

getMinimumTime has the following parameters:

players[players[0]....players[n-1]]: an array of integers denoting the locations of players

points(points[0]....points[m-1]]: an array of integers denoting the locations of points

Constraints

• 1 <= n,m <= 10^5
• 1 <= players[i], points[i] <= 109

# Question 3

## Closest Random Points

In many real world applications the problem of finding a pair of closest points arises. In the real world, data is usually distributed randomly. Given n points on a plane that are randomly generated with uniform distribution, find the squared shortest distance between pairs of these points.

Example

There are 3 points with x coordinates x = [0, 1, 2] and y = [0, 1, 4]. The points have the xy coordinates (0, 0), (1, 1) and (2, 4). The closest points are (0, 0) and (1, 1), and their squared shortest distance is ((1-0)^2) + ((1-0)^2) = 2.

Function Description

Complete the function closestSquaredDistance in the editor below.

closestSquaredDistance has the following parameter(s):

int x[n]: each x[i] denotes the x coordinate of the ith point int y[n]: each y[i] denotes the y coordinate of the ith point

Returns:

long: a long integer that denotes the squared shortest distance between the pairs of points

Constraints

• 2 <= n
• either n <= 1000 or n = 10^5
• values of x[i] and y[i] are randomly generated with uniform distribution from the range [0, (10^9)-1]

0
Entering edit mode

Question 1:

`Overview`

• There `c` coins. Bob has to start from `(0,0)`, collect all the coins, and reach Alice at `(x,y)`.
• Allowed movements are horizontal and vertical
• Some points are blocked

`Approach:`

• This is a variation of the traveling salesman problem (TSP)
• Take `(0,0)`,`(x,y),` and points that have coins as vertices for the TSP graph
• Here, `(0,0)` and `(x,y)` corresponds to the same starting vertex, such that we get the outgoing edges from `(0,0)` and incoming edges from `(x,y).`
• Find the distance between the above-mentioned vertice points by a BFS on the given matrix from each of those points `O(no of coins * size of matrix)` `=10*100*100`
• For all non-reachable pairs of points, give the distance a very high number (like 1e9)
• Solving TSP has two operations.
• Greedy `O(K!)`, where k is the number of vertices, in our case, `c+1`
• Notice the number of coins is just 10. and the number of permutations in picking up the coins is `10!=3628800`(this is in 1 sec range)
• Example permutation(5 coins) : B->2->3->1->5->4->A.
• 2->3, 4->A are the steps.
• Now go through all permutations and add the distances between each step for each permutation and take the minimum.
• DP is `(2^K)*(K^2)` -

`Complexity:`

• Greedy `O((C+1)!+C*N*M)`
• DP `O((2^(c+1))*((c+1)^2 + C*N*M)`
• `C`, no of coins.
• `N*M`, dimension's of the grid
0
Entering edit mode

Q2)

# Solution for 2

• First of all, it is given that players move simultaneously and independently. So the total time taken to collect all points will be the maximum time taken by individual players to take their points.
• .For example: if there are 3 players(player1,player2,player3) and 5 points (point1,point2,point3,point4,point5) and if player1 takes points point1,point3 in time T1 , player2 takes points point2,point5 in time T2, player3 takes points point4 in time T3, then total time taken by them will be max({T1,T2,T3})
• So our target is to minimize the maximum time taken by individual players.
• Let's represent F(max_time) as is it possible to pick all points such that each friend takes at most max_time to pick up the points they want.
• Now if F(max_time) is possible , then F(X>=max_time) is also possible, and if F(max_time) is not possible, then F(X < =max_time) is also not possible., Now since we have proved that F(max_time) is monotonic function.
• Let's do Binary Search on max_time

# Computing value of F(max_time)

• For this we could use Two-Pointers to find the value of F, where one pointer(i) will be on the player and another(j) on point
• Sort both arrays players and points
• If we are at current point(j) and player(i) then it means that we have covered all the points (1...j-1) using players (1...i-1)
• Now , here we have to handle 2 cases
• If point(j) position is greater than or equal to player(i) position
• So take j pointer to right until points(j) - player(i) < =max_time and after that take (i to right), because player(i) has covered those points which he can within max_time
• Now if player(i) exceeds point(j)
• First of all in this situation player(i) has to take the point(j) because if he cannot cover it then it cannot be covered by player(i+1),player(i+2)....
• Suppose if (player(i) cannot cover point(j), i.e player(i)-point(j) exceeds max_time, then we could directly report F(max_time) as 0
• Now, when we know that it is possible to cover point(j), so here again we have 2 options
• Go to j then move towards right
• This could be done easily by first of all covering all points from j to right until point are less than player(i)
• Then move towards right until possible in remaining_time (i.e(max_time- 2 * (player(i)-point(j))))
• Go right and then come to j
• First cover all points from j to right until point are less than player(i)
• Then move towards right until possible in remaining_time(i.e (max_time-(player(i)-point(j)) )/2 [floor_division])
• Now it will be possible if j pointer covers all the points

# Pseudo Code for F

``````int find_right(int point_pos,int player_pos,int max_time)
{
int R=point_pos;
while((R&lt;m) and ((points[R]-players[player_pos])&lt;=max_time))
R++;
return R;
}

bool F(int max_weight)
{
int i=0,j=0;
while((i&lt;n) and (j&lt;m))
{
if(points[j]&gt;=players[i])
{
while((j&lt;m) and (points[j]-players[i] does not exceed max_time))
j=j+1

i=i+1;
}
else
{

int required_time_left=players[i]-points[j];
if(required_time_left&lt;=max_time)
{
//cover all points &lt;=players[i] from j to right
while((j&lt;m) and (points[j]&lt;=players[i]))
j++;
if(j==m)// covered all return 1
return 1;

int ch1=j,ch2=j;
//go left then go right
//point(j)&lt;------------player(i)
//|
//|
//|------------------------------------&gt;
//round trip takes 2*(player(i)-point(j))
//remaining=max_time-2*(player(i)-point(j))
if(2*required_time_left&lt;=max_time)
{
int move_right=max_time-2*required_time_left;
//find maximum position you could go if move_right time you have
int max_right=find_right(i,j,move_right);
ch1=max_right;
}
//go right then go left
//point(j)            player(i)-----------&gt;
//                                        |
//                                        |
// &lt;---------------------------------------
//Since you have to cover j so first use that time
//and check how much you can go to right with
//remaining time that is max_time-(player(i)-point(j))
//Since you have to do round trip let's suppose you go R towards right
//then total distance=player(i)-point(j)+2*R
//and player(i)-point(j)+2*R&lt;=max_time
//R&lt;=floor((max_time-(player(i)-point(j)))/2);
if(max_time&gt;=required_time_left)
{
int move_right=(max_time - required_time_left)/2;
//find maximum position you could go if move_right time you have
int max_right=find_right(i,j,move_right);
ch2=max_right;
}
j=max(ch1,ch2);
//now move pointer i because player i had covered all the points
//that it can.
i=i+1;
}
else
return 0;
}
}
}
``````