TP Interview Question
Country: United States
Interview Type: Phone Interview
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?
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?
/*
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.
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[3] < array[5] => 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[7] < array[9] => 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.
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.
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.
@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...
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
There is a simple logic to solve this, follow the below steps
1) Start with the first number and insert in array A
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
this is longest increasing sequence problem, time complexity is O(n^2).
- algos May 10, 2013