## StartUp Interview Question

SDE-2s**Country:**India

**Interview Type:**In-Person

It would be better if you mention that we need to sort the above bank cities with respect to lower banks.

By the way, can you please tell how did you come up with the solution?

import java.util.HashMap;

import java.util.Map;

/**

* @author shashi

*

*Constructing Bridges:

A River that cuts through a set of cities above and below it. Each city above the river is matched with a city below the river.

Construct as many Non-Crossing Bridges as possible.

Input:

Above Bank >> 7 4 3 6 2 1 5

Below Bank >> 5 3 2 4 6 1 7

are given in pairs: (7,5) (4,3) (3,2) (6,4) (2,6) (1,1) (5,7)

Output:

(1,1) (3,2) (4,3) (6,4) (7,5)

*/

public class RiverBridge {

public static void main(String []args)

{

//get the above and below banks

int aboveBank[]={7 ,4, 3, 6, 2, 1, 5};

int belowBank[]={ 5, 3, 2, 4, 6, 1, 7};

//now create a Map for storing Pairs

Map<Integer, Integer> myMap=new HashMap<Integer, Integer>();

//base condition

if(aboveBank.length !=belowBank.length)

{

//River flow is not correct way

System.out.print("Your river is not flowing in correct way");

}

//if not

for(int i=0;i<aboveBank.length-1;i++)//you can also use below.length

{

if(aboveBank[i]>=belowBank[i])

{

//pair for bridge is founded so add to map

myMap.put(aboveBank[i], belowBank[i]);

}

}

//now print map elements

for(Map.Entry<Integer, Integer> entry:myMap.entrySet())

{

int key=entry.getKey();

int val=entry.getValue();

System.out.print("("+key+","+val+")"+" " );

}

}

}

Anyone can explain me how its 5?

Above Bank >> 7 4 3 6 2 1 5

Below Bank >> 5 3 2 4 6 1 7

Output:

(1,1) (3,2) (4,3) (6,4) (7,5)

How we making bridge here, i think same city should be connected with bridge...

Someone can explain then its good

i am thinking only 3 bridge are possible

(1,1) (4,4) ( 6,6)

or

(3,3),(2,2),(1,1)

```
package com.ixo.data.dataprocessor;
import java.util.Comparator;
import java.util.List;
import org.apache.commons.lang3.ArrayUtils;
import org.apache.commons.lang3.StringUtils;
import org.apache.commons.lang3.tuple.Pair;
public class BridgeProblem {
public static void PrintMaxBridgeCount(List<Pair<Integer, Integer>> bridgeList) {
bridgeList.sort(new Comparator<Pair<Integer, Integer>>() {
@Override
public int compare(Pair<Integer, Integer> left, Pair<Integer, Integer> right) {
return left.getLeft() - right.getLeft();
}
});
//dp struct
int[] cmax = new int[bridgeList.size()];
int[] prevNodes = new int[bridgeList.size()];
for(int n = 0; n < bridgeList.size(); n++) {
int max = 1;//when no other
int prevNode = -1;
Pair<Integer, Integer> nthItem = bridgeList.get(n);
for (int i = 0; i < n; i++) {
//CRUX: consider only those items which will include nth item
//IMP FOR DP
if (nthItem.getRight() >= bridgeList.get(i).getRight()) {
if (cmax[i] >= max) {
max = cmax[i] + 1;
prevNode = i;
}
}
}
cmax[n] = max;
prevNodes[n] = prevNode;
}
System.out.println("max bridges:" + cmax[bridgeList.size()-1]);
String bridgesToConstruct = StringUtils.join(prevNodes, ",");
System.out.println("Bridges:" + bridgesToConstruct);
}
}
```

```
#include<stdio.h>
int main()
{
int above_bank[]={7,4,3,6,2,1,5};
int below_bank[]={5,3,2,4,6,1,7};
int len_a, len_b, i;
for(len_a=0; above_bank[len_a];len_a++);
printf("len of a=%d\n",len_a);
for(len_b=0; above_bank[len_b];len_b++);
printf("len of b=%d\n",len_b);
if(len_a != len_b)
{
printf("not possible\n");
return 0;
}
for(i=0;i<len_a; i++)
{
if(above_bank[i] >= below_bank[i])
printf("pair is %d ,%d\n",above_bank[i], below_bank[i]);
}
return 0;
}
~
```

```
#include<stdio.h>
#include<stdlib.h>
main(int argc ,char *argv[])
{
int bridges[][2] = {{7,5},{4,3},{3,2},{6,4},{2,6},{1,1},{5,7}};
int (*arr)[2];
int i= 0;
int count = 0;
arr = bridges;
while(*arr[i])
{
count++;
i++;
}
printf("No of bridges pairs %d\n",count);
i =0;
arr = bridges;
while(*arr[i])
{
if(*arr[i] >= arr[i][1])
{
printf("%d %d\n", *arr[i], arr[i][1]);
}
i++;
}
}
```

Its an Longest Increasing Sub-Sequence Dynamic programming Problem with O(N log N) solution.

- R@M3$H.N December 25, 2014Above Bank >> 7 4 3 6 2 1 5

Below Bank >> 5 3 2 4 6 1 7

Pairs >> (7,5) (4,3) (3,2) (6,4) (2,6) (1,1) (5,7)

Sort the pairs based on Lower Bank Cities as Below:

Above Bank >> 1 3 4 6 7 2 5

Below Bank >> 1 2 3 4 5 6 7

Now the Problem reduces to finding the LIS from the Cities in Above Bank >> 1 3 4 6 7 2 5

which is 1 3 4 6 7

So, the Output with corresponding Lower Bank Cities will be

(1,1) (3,2) (4,3) (6,4) (7,5)

EDIT:

If we have the elements sorted by their Below Bank, then we can tell if two pairs are orderable by <=, by just looking at their positions in the Above Bank.

If the first pair(1,1) is to the left of the second pair(3,2), we immediately know that the second elements of the first pair(1) is less than the second element of the second pair(2), since we've sorted them by the second coordinate.

We then have this pair of elements can have Bridge built together if and only if the first element of the first pair(1) is less than the first element of the second pair(3).

Consequently, if we want to find a set of Bridges that can be built together, we're looking for an Increasing Sub-Sequence of the Cities in Above Bank, since in that case both the first and second elements of the pairs are increasing as we move from the left to the right.

Finding the longest increasing subsequence then solves this problem.

Complexity:

Sort the pairs by their Below Bank = O(N log N)

Find the LIS in O(N log N)

So, this is an O(N log N) solution.