Interactive Brokers Interview Question
Software Engineer / Developerssuppose length[i] is the length of the longest increasing subsequence ending at index i.
length[0] = 1
for all index from 1 to n-1
if array[i] > array[i-1] then length[i] = length[i-1]+1 because we are extending the sequence ended at index (i-1) by 1
else length[i] = 1 because we are starting new sequence from ith index.
find greatest length[i] for all i and is the answer required. similarly can be done for decreasing subsequence. time O(n)
public static void findArray(int[] array){
int maxStartingPos = -1;
int tempMaxStartingPos = -1;
int maxLength = -1;
int tempMaxLength = -1;
for(int i = 0; i < array.length-1; i++){
int fist = array[i];
int second = array[i+1];
if(fist<=second){
if( (tempMaxStartingPos+tempMaxLength)==i){
tempMaxLength++;
}else{
tempMaxStartingPos = i;
tempMaxLength = 1;
}
}else{
if(maxLength<tempMaxLength){
maxLength=tempMaxLength;
maxStartingPos = tempMaxStartingPos;
}
}
}
System.out.println("Max Elements");
for(int i = maxStartingPos; i<=maxStartingPos+maxLength;i++){
System.out.print(array[i]);
}
}
This works for ascending
void findSubsequence(int [] A, int n)
{
// A is the input array
// n is the size of array
int maxAsc = 0;
int maxDsc = 0;
int indexAsc = 0;
int indexDsc = 0
int maxLenAsc = 0;
int maxLenDsc = 0;
if (n == 0) std::cout<<"empty";
if(n == 1) std::cout<< A[0];
for(int i = 1; i < n ; i++)
{
if(A[i] < A[i-1])
{
max = A[i];
maxDsc++;
if (maxLenDsc < maxDsc)
{
indexDsc = i;
}
}
else
{
maxLenDsc = maxDsc;
maxDsc = 0;
}
if(A[i] > A[i-1])
{
max = A[i];
maxAsc++;
if (maxLenAsc < maxAsc)
{
maxLenAsc = maxAsc;
indexAsc = i;
}
}
else
{
maxAsc = 0;
}
}
if (maxLenAsc > maxLenDsc)
{
for(int i = (indexAsc - maxLenAsc); i < indexAsc ; i ++)
{
std::cout<<A[i];
}
else
{
for(int i = (indexDsc - maxLenDsc); i < indexDsc ; i ++)
{
std::cout<<A[i];
}
}
}
}
#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;
int main(){
vector<int> numbers;
int n, num, i;
int start_index, end_index, max = 0, count = 0;
//User Input
cin>>n;
for( i = 0 ; i<n ; i++) {
cin>>num;
numbers.push_back(num);
}
//--------For Ascending---------------------------------------------------------------------------
for( i = 0 ; i<n ; i++){
if(numbers[i] == numbers[i - 1] + 1){
count++;
if(max<count){
start_index = i - count;
max = count;
end_index = i;
}
}
else{
count = 0;
}
}
cout<<"---------------------------------------\n";
cout<<"Longest Ascending Sequence:\n";
cout<<"Length: "<<max + 1<<"\n";
cout<<"Start index:"<<start_index<<", End Index:"<<end_index<<"\n";
for(i = start_index ; i<=end_index ; i++){
cout<<numbers[i]<<" ";
}
cout<<"\n";
//--------For Descending--------------------------------------------------------------------------
count = 0;
max = 0;
start_index = 0;
end_index = 0;
for( i = 0 ; i<n ; i++){
if(numbers[i] == numbers[i - 1] - 1){
count++;
if(max<count){
start_index = i - count;
max = count;
end_index = i;
}
}
else{
count = 0;
}
}
cout<<"---------------------------------------\n";
cout<<"Longest Descending Sequence:\n";
cout<<"Length: "<<max + 1<<"\n";
cout<<"Start index: "<<start_index<<", End Index: "<<end_index<<"\n";
for(i = start_index ; i<=end_index ; i++){
cout<<numbers[i]<<" ";
}
cout<<"\n";
cout<<"---------------------------------------\n";
return 0;
#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;
int main(){
vector<int> numbers;
int n, num, i;
int start_index, end_index, max = 0, count = 0;
//User Input
cin>>n;
for( i = 0 ; i<n ; i++) {
cin>>num;
numbers.push_back(num);
}
//--------For Ascending---------------------------------------------------------------------------
for( i = 0 ; i<n ; i++){
if(numbers[i] == numbers[i - 1] + 1){
count++;
if(max<count){
start_index = i - count;
max = count;
end_index = i;
}
}
else{
count = 0;
}
}
cout<<"---------------------------------------\n";
cout<<"Longest Ascending Sequence:\n";
cout<<"Length: "<<max + 1<<"\n";
cout<<"Start index:"<<start_index<<", End Index:"<<end_index<<"\n";
for(i = start_index ; i<=end_index ; i++){
cout<<numbers[i]<<" ";
}
cout<<"\n";
//--------For Descending--------------------------------------------------------------------------
count = 0;
max = 0;
start_index = 0;
end_index = 0;
for( i = 0 ; i<n ; i++){
if(numbers[i] == numbers[i - 1] - 1){
count++;
if(max<count){
start_index = i - count;
max = count;
end_index = i;
}
}
else{
count = 0;
}
}
cout<<"---------------------------------------\n";
cout<<"Longest Descending Sequence:\n";
cout<<"Length: "<<max + 1<<"\n";
cout<<"Start index: "<<start_index<<", End Index: "<<end_index<<"\n";
for(i = start_index ; i<=end_index ; i++){
cout<<numbers[i]<<" ";
}
cout<<"\n";
cout<<"---------------------------------------\n";
return 0;
This is in Java but it work
void printLongestIncSub(int a[])
{
int max = -1;
int c = 0;
int end = 0;
int strt=0;
for (int i = 1; i < a.length; i++) {
if (a[i - 1] < a[i]) {
c++;
if (max < c) {
max = c;
end = i;
strt=end-max;
}
} else {
c = 0;
}
}
System.out.println("Longest Ascending Subsequence");
for(int i=strt;i<=end;i++)
{
System.out.print(a[i]+" ");
}
}
Sort the vector first, and then looking fo the longest subsequence?
- Zero June 25, 2011The solution works, but not the one that interviwer expects...