Given an array of numbers, find the longest consecutive subsequence.

Question

Sigiloso · Accepted Answer

Naive solution: sort the array, then iterate through searching for consecutive subsequences. Use a counter accordingly.

Optimized solution: use hash table to store each array element as an entry, apply lookups to see if an element one more/less exists. Chain these lookups in a recursive function.

Arman · Answer

public static void longestForward(int[] arr)
{
    int subSeqLength = 1;
    int longest = 1;
    int indexStart = 0;
    int indexEnd = 0;

    for (int i = 0; i  longest)//we assign the longest and new bounds
            {
                longest = subSeqLength;
                indexStart = i + 2 - subSeqLength;//make sure the index start is correct
                indexEnd = i + 2;
            }

        } 
        else
            subSeqLength = 1;//else re-initiate the straight length
    }


    for (int i = indexStart; i < indexEnd; i++)//print the sequence
        System.out.println(arr[i] + ", ");        
}

Soft Engineer · Answer

def longestConsecutiveSeq(arr):

	current = []
	longest = []
	for i in range(len(arr)):
		current.append(arr[i])
		for j in range(i+1, len(arr)):
			if (arr[j] > arr[j-1]):
				current.append(arr[j])
			else:
				break;
		if len(current) > len(longest):
			longest = current;
		current = []

	return longest

if __name__ == '__main__':
	a = [1,3,5,2,4,6,8]
	r = longestConsecutiveSeq(a)
	print r

Spotify

Pergunta de entrevista da empresa Spotify

Respostas da entrevista

Empresas seguidas

Buscas de vagas