## StartUp Interview Question for SDE-2s

• 2

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
3
of 3 vote

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

Above 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.

Comment hidden because of low score. Click to expand.
0

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?

Comment hidden because of low score. Click to expand.
0

@SKD - Edited...

Comment hidden because of low score. Click to expand.
1
of 1 vote

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+")"+" " );
}

}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

Comment hidden because of low score. Click to expand.
0

i think the river flows between the above and below bank of the city

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#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;
}

~``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include<stdio.h>
#include<stdlib.h>

main(int argc ,char *argv[])
{
int bridges[] = {{7,5},{4,3},{3,2},{6,4},{2,6},{1,1},{5,7}};
int (*arr);
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])
{
printf("%d %d\n", *arr[i], arr[i]);
}
i++;
}

}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.