Find the longest subsequence in a given array of numbers in O(n)

Question

chennavarri · Accepted Answer

//Given an array of numbers find the longest subsequence
//Using hash_maps :: complexity O(n)

#include 
#include 
#include 
#include 
#include 
#include 

using namespace __gnu_cxx;
using namespace std;

void itoa(int i,string *s){
std::stringstream out;
out , eqstr> myHash;
int main()
{
	myHash array;
	int inputArr[20] = {1,43,4,5,6,17,12,163,15,16,7,18,19,20,122,124,125,126,128,100};
	int seqSize = 0;
	vector longSeq;
	vector tempLongSeq;

	for(int i=0;ifirst);seqSize=1;
	++it;
	int data;
	//Iterate through each element and check if it is the next in sequence
	for (; it != array.end(); ++it) {
        	data =  it->first;
		if(data==(tempLongSeq[tempLongSeq.size()-1]+1)){
			tempLongSeq.push_back(data);
			seqSize++;
		}else{ //sequence ended
			if(seqSize>longSeq.size()){ //if the current sequence is longest then store it else 
				longSeq.clear();
				longSeq = tempLongSeq;
			}
			tempLongSeq.clear();
			tempLongSeq.push_back(data);
			seqSize=1;
		}
	}
	cout<

chennavarri · Answer

Hey guys... the above code needs changes. if values are greater than 193 than it should fail because of hash_map's bucket_count.. anyways.. use map instead of hash_map. which is sorted. but this gives a complexity of O(nlogn)

bulbosaur · Answer

How about:

Traverse the array,
have an initial index of start of sequence, and update the end index each time the next element is in sequence. If the sequence ends, check the difference between start/end, and if it is greatest so far than save those two indices and length of sequence.

Hari · Answer

Question - Should only the successive sequence of numbers be taken into account or sequence of numbers formed from the numbers in any position?

Amazon

Pergunta de entrevista da empresa Amazon

Respostas da entrevista

Empresas seguidas

Buscas de vagas