Google Interview Question
Country: United States
Can you please explain what upper_bound does? Does it give max of all three numbers? Also I do no see LEOS initialized anywhere, how does it work? You are assigning *it = A[k]; but it not used anywhere, what is the use? Can you please rewrite in c# or Java..
if it takes n log n, Isn't it easier to just sort it with quick sort, then scan it from beginning to the end? It is also n log n and you can save memory usage by doing it in-place with quicksort.
@hiuhchan: The relative order of numbers must be preserved. Sorting violates that.
@Explain: Hi, explanation can be found by this link: capacode.com/?p=419
That link also gives how to reconstruct the sub-sequence itself.
I am just lazy to copy-paste :D.
The code is in C++ and it's working fine. LEOS is built on the fly, no need to initialize, *it = A[k] means change the position pointing by iterator it to A[k].
Probably you may want to look at the link for details.
Classic dynamic programming. Here's a python solution.
def longestSubsequence(sequence):
longestSub = []
longestSubIndex = 0
for i in range(0, len(sequence)):
longestSub.append([sequence[i]])
for j in range(i - 1, -1, -1):
if sequence[i] > sequence[j] and len(longestSub[j]) + 1 > len(longestSub[i]):
longestSub[i] = longestSub[j] + [sequence[i]]
if len(longestSub[longestSubIndex]) < len(longestSub[i]):
longestSubIndex = i
return [] if len(longestSub) == 0 else longestSub[longestSubIndex]
print longestSubsequence([-1, 2, 100, 100, 101, 3, 4, 5, -7])
we could have mutiple longest increasing sequences
if the the requirement is to find all oof them , the solution should be a dfs the time complexity is 2^n
if we only need to find one of them ,dp is enough
what we need to do is to use another array to track , the array will save the index right before the current index
after done ,we iterate the array and get the longest string
public String getLongestStr (int[] nums){
if (nums == null || nums.length == 0) {
return "" ;
}
int max = Integer.MIN_VALUE ;
int [] dp = new int [nums.length] ;
int [] track = new int [nums.length] ;
Arrays.fill(track, -1);
int start = 0 ;
Arrays.fill(dp, 1);
for (int i = 1 ; i < nums.length ; ++i) {
for (int j = 0 ; j < i ; ++j) {
if (nums[i] > nums[j]) {
if (dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1 ;
track[i] = j;
}
}
if (dp[i] > max) {
max = dp[i] ;
track[i] = j ;
start = i ;
}
}
}
StringBuilder rst = new StringBuilder ();
int index = start ;
rst.append(nums[start]) ;
while (track[index] != -1) {
index = track[index];
rst.append(nums[index]) ;
}
rst.reverse() ;
return rst.toString();
}
// Longest increasing subsequence
// TIME: O(n*log(n))
// SPACE: O(n)
#include <iostream>
// input
//const int L = 9;
//int a[L] = {-1, 2, 100, 100, 101, 3, 4, 5, -7};
const int L = 16;
int a[L] = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};
// output
int b[L+1] = {0};
int le = 0;
// STRICTLY INCREASING subsequence:
// --------------------------------
int M[L+1] = {0}; // M[j] -> index of a, such that a[M[j]] is
// smallest a with the sub-sequence of the
// lenght j ending at index M[j]
int P[L+1] = {-1};// P[k] -> index of a, such that a[P[k]] is
// predecessor of a[k] in the longest
// increasing sub-sequence
// M ( 0, ..., le ) -> index in a
// P ( index in a ) -> previous index in a
int main() {
for (int i = 0; i < L; ++i) {
int lb = 0;
int ub = le;
while (lb < ub) {
int mid = lb + (ub - lb) / 2;
if (a[i] <= a[M[mid]]) {
ub = mid;
} else {
lb = mid + 1;
}
}
// j = le
M[lb] = i;
if (lb > 0) {
P[i] = M[lb-1];
}
if (lb == le) {
++le;
}
}
int k = M[le-1];
for (int i = le-1; i >= 0; --i) {
b[i] = a[k];
if (i > 0) {
k = P[k];
}
}
for (int i = 0; i < le; ++i) {
std::cout << (i == 0 ? "" : " ") << b[i];
}
std::cout << std::endl;
}
We can solve this by memoization. For the given array "a", we will create a 2d array called "val" which will tell us information about the corresponding index at a. For every index in val, there are 2 values- one is a pointer which points to the most previous value that is both lower than the current value we are looking at and has the most previous values in a subsequence. The second one tells us the number of values in the subsequence that the current element is in.
For example, given:
[1,10,4,5,6, 11]
vals[1][0] = 0 (10 points to 1) -> vals[1][1] = 2
vals[2][0] = 0 (4 points to 1) -> vals[2][1] = 2
vals[5][0] = 4 (11 points to 6 and not 10 because the subsequence at 6 is bigger than that of 10) vals[5][1] = 5
We just basically need to go through all of the indices in the array from left to right and populate vals.
Then, we can check which of the second values in vals is maximum. Here, we just unwind the sequence by following the pointers. Use a stack here to add to a String and the print out b.
getB(int[] a) {
int[][] vals = new int[a.length][2]; //0 index is the pointer, 1 index is the number of previously visited
for (int i = 0; i < a.length; i++) {
vals[i][0] = -1;
}
for (int i = 0; i < a.length; i++) {
checkBackwards(a, vals, i);
}
int maxValElement, maxValIndex;
maxValElement = maxValIndex = 0;
for (int j = 0; j < vals.length; j++ ) {
if (vals[j][1] > maxValElement) {
maxValIndex = j;
maxValElement = vals[j][1];
}
}
unWind(a, vals, maxValIndex);
}
checkBackwards(int[] a, int[][] vals, int currentElement) {
int maxElement, maxIndex;
maxElement = maxIndex = 0;
for (int i = currentElement; i >= 0; i--) {
if (a[i] < a[currentElement] && vals[i][1] > maxElement) {
maxElement = vals[i][1]
maxIndex = i;
}
}
vals[currentElement][0] = maxIndex;
vals[currentElement][0] = vals[maxIndex][1] + 1;
}
public void unWind(int[] a, int[][] vals, int element) {
Stack s = new Stack;
int currentVal = element;
while(vals[currentVal][0] != -1) {
s.push(a[currentVal]);
currentVal = vals[currentVal][0];
}
s.push(a[currentVal]);
while (s.size() > 0) {
System.out.print(s.pop()+", ");
}
}
This is very similar to "qaz" problem, it can be solved using "merge sort", in each step, when merging, find out how much the length of the the first half can be increased when the second half comes in, here the c++ code; look for "updating counts", that's where the counts are updated,
#include "stdafx.h"
#include <vector>
#include <conio.h>
struct data_t
{
int value;
int old_count;
int new_count;
};
void merge(std::vector<data_t> * values, int low, int high, int mid)
{
std::vector<data_t> temp;
int i, j;
//----------------------------------------------------------------------------------------
//updating counts
for ( i = mid ; i >= low ; i-- )
{
values->at(i).new_count = 0;
}
i = low;
j = mid + 1;
int junk;
while (i <= mid && j <= high)
{
if ( values->at(i).value < values->at(j).value)
{
i++;
}
else
{
if ( ( j == high ) || ( values->at(j).value != values->at(j+1).value ) )
if ( i > low )
if ( values->at(i).value != values->at(j).value )
{
values->at(i-1).new_count++;
}
j++;
}
}
while ( (j <= high) )
{
if ( ( j == high ) || ( values->at(j).value != values->at(j+1).value ) )
if ( i > low )
if ( ( values->at(i).value != values->at(j).value ) || ( i > mid ) )
{
values->at(i-1).new_count++;
}
j++;
}
int total = 0;
for ( i = mid ; i >= low ; i-- )
{
total += values->at(i).new_count;
values->at(i).old_count += total;
}
//-------------------------------------------------------------------------------------
//Merging
i = low;
j = mid + 1;
while (i <= mid && j <= high)
{
if ( values->at(i).value < values->at(j).value)
{
temp.push_back( values->at(i) );
i++;
}
else
{
temp.push_back( values->at(j) );
j++;
}
}
while (i <= mid)
{
temp.push_back( values->at(i) );
i++;
}
while (j <= high)
{
temp.push_back( values->at(j) );
j++;
}
for (i = low; i <= high; i++)
{
values->at(i) = temp[ i - low];
}
}
void mergesort(std::vector<data_t> * values, int low, int high)
{
int mid;
if (low < high)
{
mid=(low+high)/2;
mergesort(values,low,mid);
mergesort(values,mid+1,high);
merge(values,low,high,mid);
}
return;
}
int _tmain(int argc, _TCHAR* argv[])
{
std::vector<data_t> values;
data_t data;
data.old_count = 0;
data.new_count = 0;
data.value = -1; values.push_back( data );
data.value = 2; values.push_back( data );
data.value = 100; values.push_back( data );
data.value = 100; values.push_back( data );
data.value = 100; values.push_back( data );
data.value = 100; values.push_back( data );
data.value = 100; values.push_back( data );
data.value = 100; values.push_back( data );
data.value = 100; values.push_back( data );
data.value = 101; values.push_back( data );
data.value = 3; values.push_back( data );
data.value = 4; values.push_back( data );
data.value = 5; values.push_back( data );
data.value = -7; values.push_back( data );
for ( size_t i = 0 ; i < values.size() ; i++ )
{
printf("%d ", values[i].value );
}
printf("\n");
mergesort( &values, 0, values.size() - 1 );
for ( size_t i = 0 ; i < values.size() ; i++ )
{
printf("%d(%d) ", values[i].value, values[i].old_count+1 );
}
printf("\n");
getch();
return 0;
}
A simple one using ArrayDeque in Java ?
public int[] liss(int[] A) {
ArrayDeque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < A.length; i++) {
if (stack.isEmpty() || A[i] > stack.peek()) {
stack.push(A[i]);
} else if (A[i] == stack.peek()) {
continue;
} else {
if (A[i] < stack.peekLast())
continue;
while (stack.peek() > A[i]) {
stack.pop();
}
stack.push(A[i]);
}
}
int[] result = new int[stack.size()];
for (int i = result.length - 1; i >= 0; i--) {
result[i] = stack.pop();
}
return result;
}
I'm not sure this would work with the following input:
{ 1, 2, 4, 5, 6, 7, 3 }
Before the 3, the stack would look like this:
1, 2, 4, 5, 6, 7
But then the 3 would pop all the elements down to the 2 off the stack, so it would return:
1, 2, 3
we could have mutiple longest increasing sequences
if the the requirement is to find all of them , the solution should be a dfs the time complexity is 2^n
if we only need to find one of them ,dp is enough
what we need to do is to use another array to track , the array will save the index right before the current index
after done ,we iterate the array and get the longest string
public String getLongestStr (int[] nums){
if (nums == null || nums.length == 0) {
return "" ;
}
int max = Integer.MIN_VALUE ;
int [] dp = new int [nums.length] ;
int [] track = new int [nums.length] ;
Arrays.fill(track, -1);
int start = 0 ;
Arrays.fill(dp, 1);
for (int i = 1 ; i < nums.length ; ++i) {
for (int j = 0 ; j < i ; ++j) {
if (nums[i] > nums[j]) {
if (dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1 ;
track[i] = j;
}
}
if (dp[i] > max) {
max = dp[i] ;
track[i] = j ;
start = i ;
}
}
}
StringBuilder rst = new StringBuilder ();
int index = start ;
rst.append(nums[start]) ;
while (track[index] != -1) {
index = track[index];
rst.append(nums[index]) ;
}
rst.reverse() ;
return rst.toString();
}
At first, find the index in subarray, using the length to update the output. Time complexity is O(logn) to find the index for each element, so, the time complexity is O(n*logn) totally.
class Solution:
def indexFind(self,target,A):
A = sorted(A)
left = 0
right = len(A)-1
if len(A) ==0 or target<A[0]:
return []
if target>A[right]:
return A
while(left<right):
mid = (left+right)/2
if A[mid]<target:
left = mid+1
else:
right = mid
if A[right]== target:
return A[:right]
else:
return A[:right] + [target]
def dy(self,A):
if len(A)==0:
return 0
maxLength = 0
for i in range(len(A)):
B = self.indexFind(A[i],A[:i])
if len(B)==0:
length = 0
else:
length = len(B)
maxLength = max(length,maxLength)
if maxLength ==len(B):
output = B
return output
Sorry to first reply, please ignore the previous reply. The code should be:
class Solution:
def indexFind(self,target,A):
A = sorted(A)
left = 0
right = len(A)-1
if len(A) ==0 or target<A[0]:
return []
if target>A[right]:
return A
while(left<right):
mid = (left+right)/2
if A[mid]<target:
left = mid+1
else:
right = mid
if A[right]== target:
return A[:right]
else:
return A[:right] + [target]
def dy(self,A):
if len(A)==0:
return 0
maxLength = 0
for i in range(len(A)):
B = self.indexFind(A[i],A[:i])
print B
if len(B)==0:
length = 0
else:
length = len(B)
maxLength = max(length,maxLength)
if maxLength ==len(B):
output = B
return output
This gives the correct result. Not sure if it is correct? Comments?
static int get_min_greater_than(const std::vector<int>& items, size_t nStart, int valToBeGreaterThan)
{
int nLeastGreaterThan = valToBeGreaterThan;
for(size_t x = nStart, n = items.size(); x < n; ++x)
{
const int v = items[x];
if(v > valToBeGreaterThan)
{
if(nLeastGreaterThan == valToBeGreaterThan || v < nLeastGreaterThan)
nLeastGreaterThan = v;
}
}
return nLeastGreaterThan;
}
std::vector<int> find_subseq2(const std::vector<int>& items)
{
std::vector< std::list<int> > all;
std::list< std::list<int> > allExtras;
for(size_t x = 0, n = items.size(); x < n; ++x)
{
bool bInserted = false;
const int v = items[x];
for(std::vector< std::list<int> >::iterator i = all.begin(), e = all.end(); i != e; ++i)
{
std::list<int>& thisList = *i;
if(v > *thisList.rbegin())
{
const int nMinGreaterThan = get_min_greater_than(items, x, *thisList.rbegin());
if(v != nMinGreaterThan)
{
// we should be able to add
std::list<int> extra;
extra.insert(extra.end(), thisList.begin(), thisList.end());
allExtras.push_back(extra);
}
thisList.push_back(v);
bInserted = true;
}
}
all.insert(all.end(), allExtras.begin(), allExtras.end());
if(!bInserted)
{
// wasn't part of any existing sequence
all.resize(all.size()+1);
std::list<int>& thisList = all[all.size()-1];
thisList.push_back(v);
}
}
size_t nMaxSize = 0, nMaxPosition = 0;
for(size_t x = 0, n = all.size(); x < n; ++x)
{
if(all[x].size() > nMaxSize)
{
nMaxSize = all[x].size();
nMaxPosition = x;
}
}
std::vector<int> res;
if(all.size())
{
std::list<int>& thisList = all[nMaxPosition];
res.insert(res.end(), thisList.begin(), thisList.end());
}
return res;
}
Seems to work on multiple data sets:
int main()
{
std::vector<int> vals;
//int values[] = {-1,2,100,100,101,3,4,5,-7};
int values[] = {-1,2,100,100,101,3,4,5,-7,1,2,3,4,5,6,300,-200,7,8,9};
for(int x = 0; x < sizeof(values)/sizeof(values[0]); ++x)
vals.push_back(values[x]);
std::vector<int> res = find_subseq2(vals);
getchar();
My Python code:
a = [5, 2, 100, 100, 101, 2, 4, 5, -7]
stack = []
stack2 = []
# given index i, return list of indexes for future trip
def find_next(i):
val = a[i]
list = []
for j in range(i+1, len(a)):
if a[j] > val:
list.append(j)
return list
def dfs(i):
global stack
global stack2
print ("BEGIN: on index and val", i, a[i])
stack.append(a[i])
if len(stack) > len(stack2):
print ("##########new longest sequence")
print (stack)
stack2 = stack[:]
l = find_next(i)
for j in l:
dfs(j)
print ("END: returning from index and val", i, a[i])
stack.pop()
### end of dfs(i)
print ("INPUT list: ", a)
for i in range(len(a)):
dfs(i)
print (stack2)
a = [5, 2, 100, 100, 101, 2, 4, 5, -7]
stack = []
stack2 = []
# given index i, return list of indexes for future trip
def find_next(i):
val = a[i]
list = []
for j in range(i+1, len(a)):
if a[j] > val:
list.append(j)
return list
def dfs(i):
global stack
global stack2
print ("BEGIN: on index and val", i, a[i])
stack.append(a[i])
if len(stack) > len(stack2):
print ("##########new longest sequence")
print (stack)
stack2 = stack[:]
l = find_next(i)
for j in l:
dfs(j)
print ("END: returning from index and val", i, a[i])
stack.pop()
### end of dfs(i)
print ("INPUT list: ", a)
for i in range(len(a)):
dfs(i)
print (stack2)
Python
a = [5, 2, 100, 100, 101, 2, 4, 5, -7]
stack = []
stack2 = []
# given index i, return list of indexes for future trip
def find_next(i):
val = a[i]
list = []
for j in range(i+1, len(a)):
if a[j] > val:
list.append(j)
return list
def dfs(i):
global stack
global stack2
print ("BEGIN: on index and val", i, a[i])
stack.append(a[i])
if len(stack) > len(stack2):
print ("##########new longest sequence")
print (stack)
stack2 = stack[:]
l = find_next(i)
for j in l:
dfs(j)
print ("END: returning from index and val", i, a[i])
stack.pop()
### end of dfs(i)
print ("INPUT list: ", a)
for i in range(len(a)):
dfs(i)
print (stack2)
a = [5, 2, 100, 100, 101, 2, 4, 5, -7]
stack = []
stack2 = []
# given index i, return list of indexes for future trip
def find_next(i):
val = a[i]
list = []
for j in range(i+1, len(a)):
if a[j] > val:
list.append(j)
return list
def dfs(i):
global stack
global stack2
print ("BEGIN: on index and val", i, a[i])
stack.append(a[i])
if len(stack) > len(stack2):
print ("##########new longest sequence")
print (stack)
stack2 = stack[:]
l = find_next(i)
for j in l:
dfs(j)
print ("END: returning from index and val", i, a[i])
stack.pop()
### end of dfs(i)
print ("INPUT list: ", a)
for i in range(len(a)):
dfs(i)
print (stack2)
a = [5, 2, 100, 100, 101, 2, 4, 5, -7]
stack = []
stack2 = []
# given index i, return list of indexes for future trip
def find_next(i):
val = a[i]
list = []
for j in range(i+1, len(a)):
if a[j] > val:
list.append(j)
return list
def dfs(i):
global stack
global stack2
print ("BEGIN: on index and val", i, a[i])
stack.append(a[i])
if len(stack) > len(stack2):
print ("##########new longest sequence")
print (stack)
stack2 = stack[:]
l = find_next(i)
for j in l:
dfs(j)
print ("END: returning from index and val", i, a[i])
stack.pop()
### end of dfs(i)
print ("INPUT list: ", a)
for i in range(len(a)):
dfs(i)
print (stack2)
I use hash function to solve this problem. Run time, O(n) (BTW, I did not handle the fact that there are two sequences or more with the same length)
a = [-1, 2, 100, 100, 100, 3, 4, 5, -7]
hash = {}
for i in a:
if i not in hash:
hash[i] = 1
j = i - 1
while j in hash:
hash[j] += 1
j -= 1
max = 0
key = 0
for j in hash:
if hash[j] > max:
max = hash[j]
key = j
for k in range(0, hash[key]):
print key + k
package algo.dynamicprog;
import java.util.Arrays;
public class LongestIncreasingSubSequenceInteger {
public static void main(String[] args) {
int[] a = { 4, 2, 100, 100, 101, 3, 4, 5, 6, 9, -7 };
System.out.println(Arrays.toString(a)); // Print the input
int[] r = new int[a.length]; // Store the DP result.
int mh = 0; // Track the max sequence higest index;
int max = 0; // Track the max sequence length;
for (int j = 1; j < a.length; j++) {
for (int i = j - 1; i >= 0; i--) {
if (a[j] > a[i]) {
r[j] = r[i] + 1;
break;
} else {
// else reduce DP problem (--i) where a[j]>a[i]
}
}
if (r[j] > max) { // Track the max
max = r[j];
mh = j;
}
}
// Time to print the results [4, 2, 100, 100, 101, 3, 4, 5, 6, 9, -7]
System.out.println(Arrays.toString(r)); // [0, 0, 1, 1, 2, 1, 2, 3, 4,
// 5, 0]
int k = mh;
while (k >= 0) {
System.out.print(a[k] + " "); // The reverse sequence printed 9 6 5
// 4 3 2
int x = r[k];
if (x == 0) break;
while (x - 1 != r[--k]); //empty loop
}
}
}
import java.util.*;
import java.io.*;
public class Sub {
private static class Node {
public int n;
public ArrayList<Node> children;
public Node(int n) {
this.n = n;
this.children = new ArrayList<Node>();
}
public void add(Node node) {
Boolean found = Boolean.FALSE;
for (Node child : this.children) {
if (child.n < node.n) {
child.add(node);
found = Boolean.TRUE;
}
}
if (!found) {
this.children.add(node);
}
}
public ArrayList<Node> longest() {
ArrayList<Node> l = null;
for (Node child : this.children) {
ArrayList<Node> lChild = child.longest();
if (l == null || lChild.size() > l.size()) {
l = lChild;
}
}
if (l == null) {
l = new ArrayList<Node>();
}
l.add(0, this);
return l;
}
}
public static void main(String args[]) {
int numbers[] = { -1, 2, 100, 100, 101, 3, 4, 5, -7 };
Node head = new Node(Integer.MAX_VALUE);
for (int i = 0; i < numbers.length; i++) {
head.add(new Node(numbers[i]));
}
ArrayList<Node> longest = head.longest();
StringBuffer buf = new StringBuffer();
for (int i = 1; i < longest.size(); i++) {
if (i > 1) {
buf.append(",");
}
buf.append(Integer.toString(longest.get(i).n));
}
System.out.println(buf.toString());
}
}
Given the array A, we build an array c[i] such that c[i] is the longest increasing subsequence ending at index i. c[i] can be iteratively built up, which yields the following solution using dynamic programming. This produces the actual subsequence, not just its length:
def longest_increasing_subsequence(seq):
# c[i] is the longest increasing subsequence
# ending at index i in seq.
N = len(seq)
c = [[] for i in range(0, N+1)]
c[0] = [seq[0]]
len_max_so_far = 1
max_so_far = c[0]
for i in range(1, N):
precursors = [c[j] for j in range(0, i) if seq[j] < seq[i]]
if precursors:
c[i] = max(precursors, key=len) + [seq[i]]
else:
c[i] = [seq[i]]
if len(c[i]) > len_max_so_far:
len_max_so_far = len(c[i])
max_so_far = c[i]
return max_so_far
A tree structure is able to solve this issue.It is binary ordered tree. Here is the insertion and deletion operations, when visiting each element of given array in order.
Insertion
- Give x, Find the node, y, that is one of following cases. And insert x as a child of y
* y is a leaf node and less than x
* y is not a leaf node but its child is greater than x
- If y is the root, then insert as its left node
Deletion after insertion of x
- If y is not a left node and x has a sibling z (must be greater than x)
* Delete z, if z has no children
- x has a counterpart, z, at the same level at the right branch,
* Delete x, if x > z and z has child/children,
- Compare x with its sibling z
* Delete the right branch up to the common ancestor of x and z, if x is less
than z and x's ancestors are less than z's ancestor at each level
Two examples [-1, 2, 100, 100, 101, 3, 4, 5, -7] and [10, 8, 6, 10, 2, 10 , 6, 14, 4, 9, 5, 13, 3, 11, 7, 15, 80, 9, 10, 10, 10, 10] are solved by hand. The detailed steps and reasoning are provided in this blog: cpluspluslearning-petert.blogspot.co.uk/2015/05/data-structure-and-algorithm-find.html
Put it in a binary tree with the first node acting as the root. The longest branch to the right is the longest sub sequence.
Iterate through the array and put values into binary tree. Increase the count for each insertion that passes through a node. O(n)
Traverse the list from the head.right to whatever node has the highest count add that node to an array. O(h)
return array
This can be solved with a binary search tree, it might not be balanced but it's fine.
Step 1: build a BST
Step 2: evaluate the different depth from the root to the right side.
Left side does not count because they all represent elelents that
came after the root and are smaller.
Step 3: when returning in the recursion from the left side of a subnode, if
the right side depth is smaller (shorter list) then the left (longer list),
return the left list otherwise add current node to right list and return it.
Step 3 algorithm:
List<TreeNode> count(TreeNode node) {
if(null == node) {
List<TreeNode> list = new List<TreeNode>();
return list;
}
List<TreeNode> right = count(node.right);
List<TreeNode> left = count(node.left);
if(right.length >= left.length) {
right.add(node);
return right;
else
return left;
}
[50, 30, 31, 32, 60] and [50, 60, 30, 31, 32] will have the same BST. So this will not be a correct solution
[50, 30, 31,32, 60] and [50, 60, 30, 31, 32] have the same BST, so BST based solution will not be a correct solution.
This is longest increasing sub-sequence. It can be solved using dynamic programming.
The best implementation I know so far runs in O(nlogn) time.
If we are only required to find the length of the longest increasing sub-sequence, code can be short as following:
- ninhnnsoc February 24, 2015#include <iostream> #include <algorithm> using namespace std; int A[] = {10, 8, 6, 10, 2, 10, 6, 14, 4, 9, 5, 13, 3, 11, 7, 15, 80, 9, 10, 10,10,10}; int N = sizeof(A)/sizeof(int); vector<int> LEOS; vector<int>::iterator it; //----------------------------------------------- // Change upper_bound() into lower_bound() to get strictly increasing subsquence! void LISS(){ for(int k=0; k<N; k++){ it = upper_bound(LEOS.begin(), LEOS.end(), A[k]); if (it == LEOS.end()) LEOS.push_back(A[k]); else *it = A[k]; }; cout <<"Length of the LIS is: "<<LEOS.size()<<endl; }; //----------------------------------------------- int main(){ LISS(); return 0; } Follow this link for more details: http www capacode.com/?p=419