Yahoo Google Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
A simple way of finding the longest increasing subsequence is to use the Longest Common Subsequence (Dynamic Programming) algorithm.
1. Make a sorted copy of the sequence A, denoted as B. O(nlog(n)) time.
2. Use Longest Common Subsequence on with A and B. O(n2) time.
Credit goes to
www . algorithmist . com / index . php / Longest_Increasing_Subsequence
None of the solutions on this page appear to work for the case where the sequence is not contiguous. Here are 2 solutions to that problem. First a brute force 2^n solution that loops through the set of all subsequences.
static int[] naiveMaximumSortedSubsequence(int arr[]) {
ArrayList<Integer> maxSubsequence = new ArrayList<Integer>();
ArrayList<Integer> subsequence = new ArrayList<Integer>();
naiveMaximumSortedSubsequence2(maxSubsequence, subsequence, arr, 0);
int result[] = new int[maxSubsequence.size()];
for (int i = 0; i < maxSubsequence.size(); ++i) {
result[i] = maxSubsequence.get(i);
}
return result;
}
static void naiveMaximumSortedSubsequence2(ArrayList<Integer> maxSubsequence, ArrayList<Integer> subsequence, int arr[], int i) {
if (i == arr.length) {
if (isSorted(subsequence) && subsequence.size() > maxSubsequence.size()) {
maxSubsequence.clear();
for (int v : subsequence) {
maxSubsequence.add(v);
}
}
return;
}
else {
subsequence.add(arr[i]);
naiveMaximumSortedSubsequence2(maxSubsequence, subsequence, arr, i+1);
subsequence.remove(subsequence.size() - 1);
naiveMaximumSortedSubsequence2(maxSubsequence, subsequence, arr, i+1);
}
}
static boolean isSorted(ArrayList<Integer> arr) {
for (int i = 1; i < arr.size(); ++i) {
if (arr.get(i) < arr.get(i-1)) {
return false;
}
}
return true;
}
Next a n^2 solution that works as follows.
Create a list L of candidate subsequences.
For each number X in sequence
Find candidate subsequence C of maximum length that X can be appended to
Create new candidate subsequence that is a copy of C
Append X to C
Add C to L
static class Candidate {
public int value;
public int size;
public Candidate previous;
@Override
public String toString() { return String.valueOf(value) + "," + size; }
}
// Still O(n^2)
static int[] maximumSortedSubsequence(int arr[]) {
int iterationCount = 0;
LinkedList<Candidate> candidates = new LinkedList<Candidate>();
for (int v : arr) {
int maxLength = 0;
Candidate candidateWithMaxLength = null;
for (Candidate candidate : candidates) {
if (candidate.value <= v) {
if (candidate.size > maxLength) {
maxLength = candidate.size;
candidateWithMaxLength = candidate;
}
}
++iterationCount;
}
Candidate newCandidate = new Candidate();
newCandidate.previous = candidateWithMaxLength;
newCandidate.value = v;
newCandidate.size = 1 + (candidateWithMaxLength != null ? candidateWithMaxLength.size : 0);
candidates.add(newCandidate);
System.out.print("// " + v + ": ");
for (Candidate candidate : candidates) {
while (candidate != null) {
System.out.print(candidate.value + ",");
candidate = candidate.previous;
}
System.out.print("; ");
}
System.out.print(" iterations=" + iterationCount + "\n");
}
// Find candidate with the max length.
int maxLength = 0;
Candidate candidateWithMaxLength = null;
for (Candidate candidate : candidates) {
if (candidate.size > maxLength) {
maxLength = candidate.size;
candidateWithMaxLength = candidate;
}
}
// Convert ArrayList to int[]
int result[] = new int[candidateWithMaxLength.size];
for (int i = result.length - 1; i >= 0; --i) {
result[i] = candidateWithMaxLength.value;
candidateWithMaxLength = candidateWithMaxLength.previous;
}
return result;
}
My solution might be similar to some others since this is a standard DP problem. Basically have 2 arrays:
(1) max[i] stores the maximum number of elements in the longest subsequence ending with arr[i]
(2) prev[i] stores the index of the previous element in the longest subsequence ending with arr[i]
So basically we just need to iterate through the array, update the 2 arrays above, and then keep traversing the "prev" array until we can't anymore.
static LinkedList<Integer> longest(int[] arr) {
int len = arr.length;
int max[] = new int[len];
int prev[] = new int[len];
for(int i=0; i<len; i++) {
max[i] = 1;
prev[i] = i;
for(int j=0; j<i; j++) {
if(arr[j] < arr[i] && max[j] + 1 > max[i]) {
max[i] = max[j] + 1;
prev[i] = j;
}
}
}
LinkedList<Integer> sequence = new LinkedList<Integer>();
int index = len-1;
while(true) {
sequence.add(0, arr[index]);
if(prev[index] == index)
break;
index = prev[index];
}
return sequence;
}
List<int> longestSequence(List<int> list){
if(list == null || list.size()==0) return null;
List<int> longest = new LinkedList<>();
List<int> current = new LinkedList<>();
int previous = 0;
for(int elem: list){
if( current.size() == 0 || elem >= current.getLast()){
current.add(elem);
}
else{
if(current.size() > longest.size() ){
longest = current;
}
current = new LinkedList<>();
current.add(elem);
}
}
if(current.size() > longest.size() ){
longest = current;
}
return longest;
}
O(n)
the above is meant to return the longest subsequence of increasing consecutive numbers.
the solution would be different if the numbers don't have to be consecutive.
input: list: [1,2,3,1,5,6,7,3]
return: [1,5,6,7]
void subsequence(const int *list, int size) {
if (size == 0 || size == 1)
return;
int *M = new int[size];
int *Post = new int[size];
for (int i=0; i<size; i++) {
M[i] = 1;
Post[i] = -1;
}
M[size-1] = 1;
Post[size-1] = -1;
int front = 0;
int longest = 0;
for (int i=size-2; i>=0; i--) {
int max = 0;
for (int j=i+1; j<size; j++) {
if (list[j] >= list[i] && max < M[j]+1) {
max = M[j]+1;
Post[i] = j;
if (longest < max) {
longest = max;
front = i;
}
}
}
}
while(front != -1) {
cout <<list[front]<<endl;
front = Post[front];
}
delete M;
delete F;
}
#include <bits/stdc++.h>
using namespace std;
int main()
{
int i,t,n,a,mx,lb;
vector<int> v,res;
cin>>t;
while(t--)
{
cin>>n;
v.clear();
res.clear();
while(n--)
{
cin>>a;
v.push_back(a);
}
n=v.size();
res.push_back(v[0]);
mx=v[0];
for(i=1;i<n;i++)
{
if(v[i]>mx)
res.push_back(v[i]);
else if(v[i]<mx)
{
lb=lower_bound(res.begin(),res.end(),v[i])-res.begin();
res[lb]=v[i];
}
mx=res[res.length()-1];
}
cout<<"The Longest Increasing Sequence is :\n";
for(i=0;i<res.size();i++)
cout<<res[i]<<' ';
cout<<"\nLength of the LIS found = "<<res.size();
}
}
/// @param a the array containing the numbers we are checking
/// @param indices[out] The indices(inclusive) the function will return
/// @return true if the finding is successful, false otherwise
bool find(const vector<int>& a, pair<int, int>& indies)
{
if (a.empty()) return false;
indies.first = 0;
indies.second = 0;
for (int i = 0, j = 0; j < a.size(); ++j)
{
if (a[j] > a[j - 1])
{
if (j - i > indies.second - indies.first)
{
indies.first = i;
indies.second = j;
}
}
else
{
i = j;
}
}
return true;
}
public static void findLongest(int[] array_) {
int start = 0;
int startIndex = 0;
int endIndex = 0;
for (int i = 0; i < array_.length-1; i++) {
if (array_[i] > array_[i+1]) {
if (i - start > endIndex - startIndex) {
startIndex = start;
endIndex = i;
}
start = i+1;
}
}
System.out.println("array range is " + array_[startIndex] + " to " + array_[endIndex]);
}
missed corner case..
public static void findLongest(int[] array_) {
int start = 0;
int startIndex = 0;
int endIndex = 0;
for (int i = 0; i < array_.length-1; i++) {
if (array_[i] > array_[i+1]) {
if (i - start > endIndex - startIndex) {
startIndex = start;
endIndex = i;
}
start = i+1;
}
}
// to cover the case where the sequence is at the end
if (array_.length-1 - start > endIndex - startIndex) {
startIndex = start;
endIndex = array_.length-1;
}
System.out.println("array range is " + array_[startIndex] + " to " + array_[endIndex]);
}
why i < array_.length-1 and not just i < array_.length
in addition, why did you have to saperate the corner case? could it be in the loop?
Python Solution for Subsequence (non-contiguous)
Many of the solutions on this page are solving the trivial problem of contiguous runs in a list. A subsequence can actually have gaps, which makes this a bit more challenging, but you can do it NlogN time. My solution is actually N-squared, but the linear search can be fairly trivially converted to a binary search.
# This solves the LSS problem--longest sorted subsequence.
def test():
a = [7,8,1,5,4,6,9]
assert LSS(a) == [1,4,6,9]
def LSS(a):
if len(a) == 0:
return []
# candidate_maxes is an array of
# the max value of a sorted subsequence
# of length n, where n is the index
# of the current element
candidate_maxes = [a[0]]
predecessor = {}
for elem in a[1:]:
if elem > candidate_maxes[-1]:
# This is the case where our new element
# extends the longest subsequence so far.
predecessor[elem] = candidate_maxes[-1]
candidate_maxes.append(elem)
else:
# Do a linear search to see if we
# can make one of our previous subsequences
# easier to extend. For a large N, we could
# convert this to a binary search.
for i in range(len(candidate_maxes)):
if elem < candidate_maxes[i]:
candidate_maxes[i] = elem
if i > 0:
predecessor[elem] = candidate_maxes[i-1]
break
i -= 1
elem = candidate_maxes[-1]
result = [elem]
while elem in predecessor:
elem = predecessor[elem]
result.append(elem)
result.reverse()
return result
test()
#include <iostream>
#include <cmath>
#include <vector>
#include <ext/hash_map>
using namespace std;
int merge(__gnu_cxx::hash_map<int, int>& map, int left, int right)
{
int newMax = map[left] + map[right];
map[left] = newMax;
map[right] = newMax;
return newMax;
}
int findLongestSequence(vector<int>& a)
{
int max = 0;
__gnu_cxx::hash_map<int, int> map;
for (int i = 0; i < a.size(); i++)
{
if (map[a[i]]) continue;
map[a[i]] = 1;
// update the neighbours
if (map[(a[i]-1)]) //left neighbor
{
int retval = merge(map, a[i]-1, a[i]);
if (retval > max) max = retval;
}
if (map[a[i]+1]) // right neighbor
{
int retval = merge(map, a[i], a[i]+1);
if (retval > max) max = retval;
}
}
return max;
}
int main()
{
vector<int> b(5);
b[0] = 6;
b[1] = 55;
b[2] = 5;
b[3] = 4;
b[4] = 3;
b[5] = 99;
int ret = findLongestSequence(b);
cout << "ret = " << ret << endl;
//expect = 4
}
The possible reason that someone (not me) to down vote this one might be the wrong output. But anyway this is well-know problem "Longest increasing subsequence" you can google it. The complexity is O(nlogn). Beware it is not easy to make it right. This is mine version
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
#define STRICTLY_INCREASING 1
template<typename T>
std::vector<T> LIS(const std::vector<T>& v) {
typedef T value_type;
typedef std::pair<value_type, int> value_pos_type;
typedef std::vector< value_pos_type > value_pos_vector_type;
typedef typename value_pos_vector_type::iterator best_iterator_type;
size_t n = v.size();
std::vector<int> p(n);
std::vector< value_pos_type > best;
value_pos_type cur = std::make_pair(std::numeric_limits<value_type>::min(), -1);
best.push_back(cur);
for (int i=0; i< n; ++i) {
#ifdef STRICTLY_INCREASING
value_pos_type cur = std::make_pair(v[i], 0);
best_iterator_type it = lower_bound(best.begin(), best.end(), cur);
cur.second = i;
#else
value_pos_type cur = std::make_pair(v[i], i);
best_iterator_type it = upper_bound(best.begin(), best.end(), cur);
#endif
if (it == best.end()) {
p[i] = best.back().second;
best.push_back(cur);
} else {
best_iterator_type pIt = it-1;
p[i] = pIt->second;
*it = cur;
}
}
std::vector<value_type> ret(best.size() - 1);
int f = best.back().second;
for (int i = ret.size()-1; i >=0; --i) {
ret[i] = v[f];
f = p[f];
}
return ret;
}
int main(int agrc, char** argv) {
int a[] = {5,6,3,4,1,9,9,8,9,5 };
//int a[] = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};
std::vector<int> v(a, a + sizeof(a) / sizeof(a[0]));
std::vector<int> res = LIS(v);
for (int i=0; i < res.size(); ++i )
std::cout << res[i] << ' ';
std::cout << std::endl;
}
Your code is finding the longest non-decreasing subsequence. The statement says strictly increasing. A valid result for the example is 3, 4, 8, 9.
There are simple trick to turn it from non-decreasing to strictly increasing by changing from upper bound (to find something strictly larger hence the previous might be equal) to lower bound (to find something at least equal or larger hence the previous is strictly smaller). My edited code reflect that idea
Code
// Binary search
int GetCeilIndex(int A[], int T[], int l, int r, int key) {
int m;
while( r - l > 1 ) {
m = l + (r - l)/2;
if( A[T[m]] >= key )
r = m;
else
l = m;
}
return r;
}
int LongestIncreasingSubsequence(int A[], int size) {
int *tailIndices = new int[size];
int *prevIndices = new int[size];
int len;
memset(tailIndices, 0, sizeof(tailIndices[0])*size);
memset(prevIndices, 0xFF, sizeof(prevIndices[0])*size);
tailIndices[0] = 0;
prevIndices[0] = -1;
len = 1; // it will always point to empty location
for( int i = 1; i < size; i++ ) {
if( A[i] < A[tailIndices[0]] ) {
// new smallest value
tailIndices[0] = i;
} else if( A[i] > A[tailIndices[len-1]] ) {
// A[i] wants to extend largest subsequence
prevIndices[i] = tailIndices[len-1];
tailIndices[len++] = i;
} else {
// A[i] wants to be a potential condidate of future subsequence
// It will replace ceil value in tailIndices
int pos = GetCeilIndex(A, tailIndices, -1, len-1, A[i]);
prevIndices[i] = tailIndices[pos-1];
tailIndices[pos] = i;
}
}
cout << "LIS of given input" << endl;
for( int i = tailIndices[len-1]; i >= 0; i = prevIndices[i] )
cout << A[i] << " ";
cout << endl;
delete[] tailIndices;
delete[] prevIndices;
return len;
}
#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
#define ARRAY_SIZE(A) sizeof(A)/sizeof(A[0])
// Binary search (note boundaries in the caller)
// A[] is ceilIndex in the caller
int CeilIndex(int *A, int *table, int l, int r, int key) {
int m;
while( r-l > 1 ) {
m = l + (r-l)/2;
(A[table[m]] >= A[key] ? r : l) = m; // ternary expression returns an l-value
}
return r;
}
int LongestIncreasingSubsequenceLength(int A[], int size, int *result) {
// Add boundary case, when array size is one
int *tailTable = new int[size];
int *parentIndex = new int[size];
int len, pos; // always points empty slot
int i;
memset(tailTable, 0, sizeof(tailTable[0])*size);
memset(parentIndex, -1, sizeof(parentIndex[0])*size);
tailTable[0] = 0;
len = 1;
for(i = 1; i < size; i++ ) {
if( A[i] < A[tailTable[0]] )
// new smallest value
{
tailTable[0] = i;
parentIndex[i] = -1;
}
else if( A[i] > A[tailTable[len-1]] )
// A[i] wants to extend largest subsequence
{
tailTable[len] = i;
parentIndex[i]=tailTable[len-1];
len++;
}
else
// A[i] wants to be current end candidate of an existing subsequence
// It will replace ceil value in tailTable
{
pos= CeilIndex(A, tailTable, -1, len-1, i);
tailTable[pos] = i;
parentIndex[i]=tailTable[pos-1];
}
}
i=tailTable[len-1];
for (int j=len-1;j>=0 && i!=-1;j--){
result[j]=A[i];
i=parentIndex[i];
}
delete[] tailTable;
delete[] parentIndex;
return len;
}
int main() {
//int A[] = { 2, 5, 3, 7, 11, 8, 10, 13, 6 };
int A[] = {5,2,6,3,4,1,9,8,9,5,6,7};
int n = ARRAY_SIZE(A);
int x;
int *result= new int[n];
printf("Length of Longest Increasing Subsequence is %d\n",
x=LongestIncreasingSubsequenceLength(A, n, result));
cout<<"result"<<endl;
for(int i=0;i<x;i++)
cout<<result[i]<<" ";
cout<<endl;
return 0;
}
geeksforgeeks.org/construction-of-longest-monotonically-increasing-subsequence-n-log-n/
- Amit July 31, 2013