Given two sides of a river having the same cities labeled in characters. Bridges are to be drawn from one side to another that can connect the same labels but the bridges shudnt cross each other. Find the max no of bridges that can be connected. Eg Side 1: A B C D Side 2: D C A B So bridges connecting A to A etc need to be made. But when A to A is connected above D to D is not possible. Dynamic programming solution exists

Question

Accepted Answer

The maximum number of bridges that can be connected between two sides of a river without crossing each other.

This is a dynamic programming problem.
Create a 2D array to store the maximum number of bridges that can be connected at each position.
Initialize the first row and column of the array with 0.
Iterate through the sides of the river and compare the labels.
If the labels match, update the value in the array by adding 1 to the diagonal element.
If the labels don't match, take the maximum value from the adjacent elements.
The last element of the array will contain the maximum number of bridges that can be connected.

Top Housing.com Software Engineer interview questions & answers

Popular interview questions of Software Engineer