## TP Interview Question

• 0

Country: United States
Interview Type: Phone Interview

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

this is longest increasing sequence problem, time complexity is O(n^2).

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

@eugene.yarovoi : Can you please give the algorithm for that?

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

Find longest increasing subsequence where you have the index as well for the elements which contributes to the subsequence.
Now the numbers which do not belong to this subsequnce are the one which needs to be removed

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

Hi,
I have a few doubts regarding the problem.
1) Suppose our array is 123476345.Now there are three sorted sub array
1234 76 345 Here '5' can also come with first array.like 12345.

2) Suppose our array is 1234765.Now there are two sorted sub array
1234 765 now again '5' can come with 1234 also.
so what is the correct position of 5?

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

Rachit, he was asking subsequence not substring. To me sequence implied non-contiguity. so, in your first example the answer is 12345. That's also the answer in (2)

Now, how to do it in linear time?

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

Probably he is asking for the longest increasing subsequence so whichever is longest we have to take that

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

``````/*
array - input array
start - starting index of array
end - ending index of array
subStart - starting index of the longest subsequence
subEnd - ending index of the longest subsequence
*/
void subseq(int* array, int start, int end, int* subStart, int *subEnd)
{
int bestStart = start; /* current longest sequence's start index */
int bestEnd = start; /* current longest sequence's end index */

*subStart = start;
*subEnd = start;

while(1) {
bestStart = start;
/* continue as long as the elements are non-decreasing */
while((start < end) && (array[start] <= array[start+1]))
{
start++;
}
bestEnd = start;

/* did we find a subsequence longer than the current one? */
if((bestEnd - bestStart) > (*subEnd - *subStart))
{
*subStart = bestStart;
*subEnd = bestEnd;
}
start++;

/* we are done if the current subsequence is longer than the remaining number of elements. */
if((*subEnd-*subStart) >= (end-start))
break;
}
}``````

Complexity is linear.

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

I think your code returns the longest sub array instead of sub sequence.

Consider the following input.

Input: 20 24 28 49 5 50 51 62

Expected output: 20 24 28 49 50 51 62

Your code will return 20 24 28 49.

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

``Approach 1: (Time Complexity: O(n2), Space complexity: O(n))``

1) Do a linear traversal and store the indices of the array where array[current] > array[next] in a new array
2) In the array of indices, Loop from first index and check if array[currentIndex] < array[currentIndex+2]
3) If yes, remove currentIndex+1 and currentLongest sub sequence is from left till nextIndex (after removing currentIndex+1)
4) Repeat the steps 2,3 till all combinations are covered (like a nested for loop)

CurrentLength is compared with maximumLength at the end of each inner loop and store the indexes to be removed if current > maximum

Eg:

Input array: 20 24 28 49 5 50 51 62 4 70

Array of indices where array[current] > array[next]: 3, 7

Iteration 1:
if array < array => 49 < 50 = yes
currentLength = current(0) + length ((3-0)+1)+((7-5)+1)=7 (subtracting each set of indices and adding one to it)

if array < array => 62 < 70 = yes
currentLength = current(7) + length ((array.length-9)+1)=8 (subtracting each set of indices and adding one to it)

Repeat such iterations starting from each element in the indices array.

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

``````Approach 2: (Time Complexity: O(n), Space Complexity: O(1))
Note: This approach works ONLY when the last element of the array is the largest element.``````

1) Start from the tail of the array and iterate till start
2) if array[left] > array[right], remove the current element from maximum subsequence

Eg:

Input array: 20 24 28 49 5 50 51 62 4 70

Indices where array[left] > array[right]: 8, 4

When we remove these indices, we get the largest possible sorted sub sequence.

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

That's not necessarily true. When you're deleting 5 and 4, how do you know those numbers couldn't be used as some part of some even longer increasing subsequence?

I can perhaps give counterexamples if you clarify the exact meaning of "left" and "right" in your proposed solution.

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

@eugene.yarovoi

Left and Right are merely pointers which point initially to the last and last but one position of the array and we iterate till they reach 1st and 2nd position.

Can you please post the dataset for which this algorithm might fail? Will help in altering the algo...

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

Input array: 20, 24, 28, 49, 5, 6, 7, 8, 9, 10, 11, 50, 51, 62, 4, 70

here your algorithm will remove index of numbers 5 and 4.
And the result is not sorted too.

Here the numbers to be removed are 20, 24, 28, 49 and 4

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

@asenthilkumargce
My algorithm will actually remove all elements to the left element 4. The result will be sorted. But as you pointed it's not the largest possible sorted sub sequence. Thanks for pointing it out.

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

There is a simple logic to solve this, follow the below steps

2) keep moving as long as it is in increasing order
3) The moment an item is skipped, store the first skipped index and move on by skipping any drops and inserting only increasing values to array A as step2 only

Now if there is an item skipped, start another iteration with that skipped index value saving it to array B and keep moving as long as it is in increasing order by dropping lower values and adding sequence values to Array B.

Return larger of Array A or B

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

time Complexity = O(n), space complexity = O(n)

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

I don't understand the precise steps you are proposing. Could you clarify and give an argument for the correctness?

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.