Given two sides of a river having the same cities labeled in characters, find the maximum number of non-crossing bridges that can be connected between the same labels on opposite sides. For example, Side 1: A B C D, Side 2: D C A B. Bridges connecting A to A, etc., need to be made, but bridges cannot cross each other. A 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.

Housing.com Software Engineer interview questions & answers

Popular interview questions of Software Engineer