## Amazon Interview Question for SDE-2s

Country: India

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

O(nlgn) using Activity Selection Problem:

1) Sort the pairs according to their second element --> O(nlgn)
2) Select the first pair from the sorted array and print it. --> O(1)
3) Do following for remaining pairs in the sorted array. --> O(n)
---------------> If the first element of this pair is greater than the 2nd element of previously selected pair then select this pair and print it.

``````public static int LongestChainPairs(Pair[] pairs)
{
Collection.sort(pairs); //Assume that Pair class implements comparable with the compareTo() method such that (a, b) < (c,d) iff b<c
int chainLength = 0;

//select the first pair of the sorted pairs array
pairs[0].print(); //assume print method prints the pair as “(a, b) ”
chainLength++;
int prev = 0;

for(int i=1;i<pairs.length; i++)
{
if(pairs[i].first >= pairs[prev].second)
{
pairs[i].print();
chainLength++;
prev = i;
}
}
return chainLength;
}``````

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

dynamic programming?

``````public static int findChain(int [] [] chain){
int [] dp=new int [chain.length];

dp [0] =1 ;
int max =1 ;

for (int i =1 ; i <chain.length ; ++i){
if (chain[i][0]>chain[i-1][1]){
dp [i]=dp[i]>dp[i-1]+1? dp [i] : dp[i-1]+1;
max=Math.max(dp[i], max);
}
}
return max;``````

}

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

@Scott your assumption is wrong about the array of pairs i.e. the your double array input is already sorted according to 2nd element. What of the array is not sorted. For example : {(50, 90), (5,24), (39,60), (15, 28), (27,40)}. Then you are selecting blindly the first pair as the start of the chain. So, O(n) solution of yours only works if the array is sorted.

isn't the problem is similar to O(nlgn) activity selection problem?

1) Sort the pairs according to their second element --> O(nlgn)
2) Select the first pair from the sorted array and print it. --> O(1)
3) Do following for remaining pairs in the sorted array. --> O(n)
---------------> If the first element of this pair is greater than the 2nd element of previously selected pair then select this pair and print it.

O(nlgn) solution:

``````public static int LongestChainPairs(Pair[] pairs)
{
Collection.sort(pairs); //Assume that Pair class implements comparable with the compareTo() method such that (a, b) < (c,d) iff b<c
int chainLength = 0;

//select the first pair of the sorted pairs array
pairs[0].print(); //assume print method prints the pair as “(a, b) ”
chainLength++;
int prev = 0;

for(int i=1;i<pairs.length; i++)
{
if(pairs[i].first >= pairs[prev].second)
{
pairs[i].print();
chainLength++;
prev = i;
}
}
return chainLength;
}``````

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

@zahidbuet106
why do we need to sort it based on second element only. We can do sorting based on first element also and follow rest of your approach. Whats wrong in that ??

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

@saurabh
Activity selection is a greedy algorithm which requires you to select a job each time according to the earliest finish time. In that sense you need to select the job with earliest finish time as the initial job, not the earliest started job. Also note that (start time, finish time) assumes start time < finish time . I mapped the pair problem as a activity selection problem by considering each pair as a job and first element as the starting time and 2nd element as finishing time because (a, b) exhibits a<b relation similar to start time<finish time in activity selection.I hope this answers your question.

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

@zahidbuet106
thanks buddy,,,, I understood activity selection problem and then this one. :)

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

Same as Longest Common Subsequence problem (just consider the second element in each pair) - can be solved in O(n^2) using dynamic programming.

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

Same as the "Scheduling Problem" in CLRS, which has a greedy algorithm solution.

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

Let's say input is a set of (x1,x2) points. Sort input by x2, then traverse the list and add elements to the chain which satisfy the required condition with regards to the tail of chain.

``````public static List<Pair> formChain(List<Pair> input) {
Collections.sort(input, new PairEndComparator());
for (Pair p : input) {
if (chain.isEmpty() || chain.getLast().e < p.s)
}
return chain;
}

static class PairEndComparator implements Comparator<Pair> {
public int compare(Pair p1, Pair p2) {
return p1.e - p2.e;
}
}``````

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

``````static class Pair {
int s;
int e;
Pair(int s, int e) {
this.s = s;
this.e = e;
}
}``````

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

``````import java.util.Collections;
import java.util.List;

public class Chain {

class Segment implements Comparable<Segment> {

private final int start;
private final int end;
private final String name;

public int getStart() {
return start;
}

public int getEnd() {
return end;
}

public String getName() {
return name;
}

Segment(int start, int end, String name) {
this.start = start;
this.end = end;
this.name = name;
}

@Override
public int compareTo(Segment s) {

if (this.end > s.end) {
return 1;
} else if (this.end == s.end){
return 0;
} else {
return -1;
}

}

}

private final Segment[] segments = {

new Segment( 8, 10, "A" ),
new Segment( 0, 7, "B" ),
new Segment( 11, 12, "C" ),
new Segment( 13, 16, "D" ),
new Segment( 0, 1, "E" ),
new Segment( 2, 15, "F" ),
new Segment( 4, 11, "G" ),
new Segment( 5, 6, "H")
};

public int findChainLength() {

int result = 0;

for (Segment s : segments) {
}

// O(nlogn) - sort segments by their end points:
Collections.sort(tempSegments);
Segment[] sortedSegments = (Segment[])tempSegments.toArray(new Segment[tempSegments.size()]);

int currentSegmentIndex;

currentSegmentIndex = 0;
System.out.print(sortedSegments[currentSegmentIndex].getName());
result++;

// O(n) worst case - scan and augment chain by adding the next
// shortest segment:
for (int index = 1; index < tempSegments.size(); index++) {

if (sortedSegments[index].getStart() > sortedSegments[currentSegmentIndex].getEnd()) {
currentSegmentIndex = index;
result++;

System.out.print(sortedSegments[currentSegmentIndex].getName());
}
}

return  result;
}

public static void main(String[] args) {

Chain myChain = new Chain();

myChain.findChainLength();

return;
}
}``````

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

@us : Where are you using the method formChain() ? As per the question posted, we want to find only the length of the longest possible chain.

In such a case sorting the pairs denoted by P(s,e) in ascending order on P.e would give us the pair P which can act as a start of the segment (since we have found the pair P which would have the smallest P.s value in the entire chain.

Let Q be the queue where we store the parts of the segment.
Let INPUT be the list of sorted pairs.

Then do the following:

``````foreach Pair P in Input:
if(Q.isEmpty || Q.end.s < P.first)
return Q.length as the size of the longest segment``````

The important point to note here is that Q is composed of smaller segments that contribute to the largest segment, hence we effectively have all the possible segments that can be created from the provided input as well as the lengths of such segments.

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

1) Sort the sets on the basis of second number. Set (a,b) should be sorted on 'b'
2) Then, take the series satisfying second condition, that is, out of sets (a,b) & (c,d) b should be less than c.

For example,
(4,5) (7,9) (1,2) (11,15) (3,18)
After sorting it becomes:
(1,2)
(4,5)
(7,9)
(11,15)
(3,18)
It is being assured that in (a,b) a is always less than b.
Now, we can choose elements with respect to second condition as out of two sets, (a,b) & (c,d) b should be less than c.

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

this can be solved like the greedy approach of latest finish time job first.
in that we have to schedule the most no. of jobs which is here analogous to longest chain.
first we sort the pairs according to their second number. then we chose the first pair and then the next pair is next first pair in that sorted list such that its first number is. greater than second number of the previous chosen pair.

Comment hidden because of low score. Click to expand.
-2
of 2 vote

This guy must be interviewing with several companies everyday.

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.