## Deshaw Inc Interview Question for Software Engineer / Developers

Country: India

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

Let A be the original array. Steps are as below:
- Let B=A sorted in increasing order.
- Output the "Longest Common Subsequence" of B from A

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

good idea!!

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

what if the array is [2,4,6,8,10,9,7,5,3] ?

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

@cobra :
picked up this example from wiki .google both terms longest increasing subarray. longest increasing subsequence to understand better.

0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15, …
a longest increasing subsequence is
0, 2, 6, 9, 13, 15.

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

Yes, longest increasing subsequence does not mean sub sequence should be contiguius, it only needs to be some sub set whose elements are in increasing order
1,76,4,24,7,56,9,10,120

here longest increasing sub sequence is 1,4,7,9,10,120
it need not be contiguous

To understand the solution to this problem you can watch this wonderful video on youtube

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

the other possible solutions are,
0 2 6 9 11 15
0 4 6 9 11 15
0 4 6 9 13 15

this can be done by n-ary tree or graph by inserting the element in maximum depth of increasing values

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

this can be done by DP, try using LIS[i]=1+max{LIS[1.....i-1]}... i hv nt included the base cases here...

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

``#include<iostream>``

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

``compiled``

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

nb

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

#include<iostream>
using namespace std;
int main()
{

int a[] = {5,4,10,11,9,13,14,15,8,6};

int count =1, max=1;

for(int i=0; i<10; i++)
{ if(a[i+1]>a[i])
count++;
else
{if(count >= max)
{max=count;
count =1;
}
}
}

cout<<max;
return 0;

}

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

``````public class LongestIncreasingSubsequence {

/**
* Returns index in T for ceiling of s
*/
private int ceilIndex(int input[], int T[], int end, int s){
int start = 0;
int middle;
int len = end;
while(start <= end){
middle = (start + end)/2;
if(middle < len && input[T[middle]] < s && s <= input[T[middle+1]]){
return middle+1;
}else if(input[T[middle]] < s){
start = middle+1;
}else{
end = middle-1;
}
}
return -1;
}

public int longestIncreasingSubSequence(int input[]){
if(input==null || input.length==0)
return 0;
int T[] = new int[input.length];//temporary array to hold the minimum element of length i+1, scanned so far
int R[] = new int[input.length]; // result array, to traverse the longest subsequence
for(int i=0; i < R.length ; i++) {
R[i] = -1;
}
T[0] = 0;// longest subsequence of length 1, will start at index 0 (Initialization).
int len = 0; // longest subsequence length
for(int i=1; i < input.length; i++){
if(input[T[0]] > input[i]){ //if input[i] is less than 0th value of T then replace it there.
T[0] = i;
}else if(input[T[len]] < input[i]){ //if input[i] is greater than last value of T then append it in T
len++;
T[len] = i;
R[T[len]] = T[len-1];
}else{ //do a binary search to find ceiling of input[i] and put it there.
int index = ceilIndex(input, T, len,input[i]);
T[index] = i;
R[T[index]] = T[index-1];
}
}

System.out.println("R: ");
for(int i: R)
System.out.print(i+  "  " );
System.out.println();
System.out.println("T: ");
for(int i: T)
System.out.print(i+  "  " );
System.out.println();

//this prints increasing subsequence in reverse order.
System.out.print("Longest increasing subsequence ");
int index = T[len];
while(index != -1) {
System.out.print(input[index] + " ");
index = R[index];
}

System.out.println();
return len+1;
}

public static void main(String args[]){
//int input[] = {2,5,3,1,2,10,6,7,8};
int input[] = {3, 4, -1, 5, 8, 2, 3, 12, 7, 9, 10};
LongestIncreasingSubsequence lis = new LongestIncreasingSubsequence();
System.out.println("Maximum length " + lis.longestIncreasingSubSequence(input));
}

}``````

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

mentioning Kadane's algorithm on the interview would be enough I guess. It is a known proved algorithms for such kind of DP problems.

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

@cobra
your algo is for longest increasing subarray. longest increasing subsequence can't be done better than O(nlgn) see wiki. :)

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

@joker: oh ok.. can you give me an example?

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.