Question 1: Given an array, please get the length of the longest arithmetic sequence. The element order in the arithmetic sequence should be same as the element order in the array. For example, in the array {1, 6, 3, 5, 9, 7}, the longest arithmetic sequence is 1, 3, 5, and 7, whose elements have same order as they are in the array, and the length is 4.
Every pair of two adjacent numbers in an arithmetic sequence has exactly same difference.
There are n(n-1)/2 pairs out of an array with n elements. These pairs can be categorized into a set of groups, of which each group of pairs have the same difference.
Difference -1: (6, 5)
Difference 2: (1, 3), (3, 5), (5, 7)
Difference 3: (6, 9)
Therefore, a hash table can be defined for the groups. The key in the hash table is the difference of pairs, and the value in the hash table is a list of pairs with same difference.
The pairs are sorted according to their first elements.
Complete code at http://ideone.com/jxRDkd
Every pair of two adjacent numbers in an arithmetic sequence has exactly same difference.
There are n(n-1)/2 pairs out of an array with n elements. These pairs can be categorized into a set of groups, of which each group of pairs have the same difference.
Difference -1: (6, 5)
Difference 2: (1, 3), (3, 5), (5, 7)
Difference 3: (6, 9)
Therefore, a hash table can be defined for the groups. The key in the hash table is the difference of pairs, and the value in the hash table is a list of pairs with same difference.
The pairs are sorted according to their first elements.
Complete code at http://ideone.com/jxRDkd
private static int Analyze(Dictionary<int, List<Pair>> hashTable, intlengthOfNumbers)
{
int maxLength = 0;
foreach(var key in hashTable.Keys)
{
int[] lengths = new int[lengthOfNumbers];
for (int i = 0; i < lengthOfNumbers; ++i)
{
lengths[i] = 1;
}
foreach(Pair pair in hashTable[key])
{
lengths[pair.Second] = lengths[pair.First] + 1;
}
foreach(var length in lengths)
{
if(length > maxLength)
{
maxLength = length;
}
}
}
return maxLength;
}
public static int GetMaxLengthOfArithmeticSequence(int[] numbers)
{
var hashTable = BuildHashTable(numbers);
return Analyze(hashTable, numbers.Length);
}
Question 2: Given an array, please get the length of the longest arithmetic sequence. The element order in the arithmetic sequence is not necessarily same as the element order in the array. For example, in the array {1, 6, 3, 5, 9, 7}, the longest arithmetic sequence is 1, 3, 5, 7, and 9, and the length is 5.
Analysis: Different from the previous problem, there are no limitations on the order of arithmetic sequence. Consequently, we can sort the array before we try to get the maximal length of arithmetic sequences.
Question 3: Given an array, please get the length of the longest consecutive sequence. A consecutive sequence is an arithmetic sequence with common difference 1. The element order in the consecutive sequence is not necessarily same as the element order in the array. The solution should not cost more than O(n) time and space if the length of the input array is n. For example, in the array {1, 6, 3, 5, 9, 7}, the longest consecutive sequence is 5, 6, and 7 whose length is 3.
O(n) time and space
A consecutive can’t have duplicated elements. A hash set, of which every element is unique, can be built from the input array. When a number is located in the set, we try to locate its consecutive neighbors.
private static int AnalyzeHashSet(HashSet<int> set)
{
int maxCount = 0;
while(set.Count > 0)
{
int number = set.First();
int count = 0;
int toDelete = number;
while(set.Remove(toDelete))
{
count++;
toDelete++;
}
toDelete = number - 1;
while(set.Remove(toDelete))
{
count++;
toDelete--;
}
if(count > maxCount)
{
maxCount = count;
}
}
return maxCount;
}
Read full article from Coding Interview Questions: No. 53 - Longest Arithmetic Sequence