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.
Analysis: Every
pair of two adjacent numbers in an arithmetic sequence has exactly same
difference. For example, 1, 3, 5, and 7 is an arithmetic sequence, and the
pairs (1, 3), (3, 5), and (5, 7) have the same difference 2.
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.
For example, the pairs of numbers in the array {1, 6, 3, 5, 9, 7} can be
categorized into groups:
Difference -1: (6, 5)
Difference 2: (1, 3), (3, 5), (5, 7)
Difference 3: (6, 9)
…
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 code to build the hash table
can be implemented in C# as the following:
internal class Pair
{
public int First { get; set; }
public int Second { get; set; }
}
private static Dictionary<int, List<Pair>> BuildHashTable(int[] numbers)
{
var hashTable = new Dictionary<int, List<Pair>>();
for(int i = 0; i < numbers.Length; ++i)
{
for(int j = i + 1; j < numbers.Length; ++j)
{
Pair pair = new Pair
{
First = i,
Second = j
};
int diff = numbers[j] - numbers[i];
if(hashTable.Keys.Contains(diff))
{
hashTable[diff].Add(pair);
}
else
{
List<Pair> newValue = new List<Pair>();
newValue.Add(pair);
hashTable[diff] = newValue;
}
}
}
return hashTable;
}
In the code above,
the values of the hash table is pairs of indexes, rather than elements
themselves of the array. The pairs are sorted according to their first
elements.
The next step is to get the length of pairs with each
difference. A list of pairs with difference k
is got given a key k in the hash
table. If an element A[i] is mth element is an arithmetic
sequence with a common difference k,
and there is a pair (A[i], A[j]) (j>i) in the list of pairs, the element A[j] should be the m+1thelemement
in the arithmetic sequence.
Therefore, the code to get the max length of all arithmetic
sequences can be implemented as:
private static int Analyze(Dictionary<int, List<Pair>> hashTable, int lengthOfNumbers)
{
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);
}
The source code with unit test cases are shared at: http://ideone.com/jxRDkd.
As mentioned above, there are O(n2) pairs in an array with n elements. Therefore, the time and space efficiencies of this
solution is O(n2) given an
array with n elements.
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. The code is almost same as before, except for
the revision that there is an additional line of code to sort the array, as
listed below:
public static int GetMaxLengthOfArithmeticSequence(int[] numbers)
{
Array.Sort(numbers);
var hashTable = BuildHashTable(numbers);
return Analyze(hashTable, numbers.Length);
}
The source code with unit test cases are shared at: http://ideone.com/lEqNm3.
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.
Analysis: The solution to solve the above problems cost O(n2) time and space. Therefore,
we need a new solution to solve this problem.
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. For
instance, when the number 6 is found in the set, we try to find the number 5
and 7 in the set, and then we get a consecutive sequence 5, 6, and 7.
This solution can be implemented in C# code as listed below:
public static int GetMaxLengthConsecutiveSequence(int[] numbers)
{
HashSet<int> set = BuildHashSet(numbers);
return AnalyzeHashSet(set);
}
private static HashSet<int> BuildHashSet(int[] numbers)
{
var set = new HashSet<int>();
foreach(int number in numbers)
{
set.Add(number);
}
return set;
}
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;
}
Every number in the input array is added into and removed
from the array only once, so the time and space efficiency is O(n) if there are n numbers in the array.
The source code with unit tests is shared at http://ideone.com/0oRqLq.
More coding interview questions are discussed in my book< Coding Interviews: Questions, Analysis & Solutions>. You may find the details of this book on Amazon.com, or Apress.
The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages, please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact him via zhedahht@gmail.com . Thanks.
This comment has been removed by the author.
ReplyDeleteHi,
ReplyDeleteThere is a dynamic programming approach for this problem too.
This comment has been removed by the author.
ReplyDeleteCheck this also this link also for
ReplyDeletec# interview questions @ http://skillgun.com
Informative post about the longest arithmetic sequence. This blog has got many informative posts about the mathematics which were unknown before. Thank you.
ReplyDeletetop essay writing service
I wonder if custom dissertation writing service also provides ideas about arithmetic sequence. I find this very interesting and thinking of doing this in my free time. Honestly I only have just a hint of this sequence and don't have full idea about this but I really wanted to try though.
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteinteresting post. Here you need a professional advice, such people who will help you with paper essay writing as well as with other tasks that will be done for you
ReplyDeleteMarhaba,
ReplyDelete11/10!! Your blog is such a complete read. I like your approach with No. 53 - Longest Arithmetic Sequence. Clearly, you wrote it to make learning a cake walk for me.
I've had a query sitting in my support centre since last week regarding a billing query, it's not quite urgent and I've had no response. AWS Training
I don't have business support as I'm only really exploring the AWS suite for future purposes. Does anyone have any advice on how I can get in touch with someone regards this or is it just a case of waiting for a response? It has been 6 days now.
Very useful post !everyone should learn and use it during their learning path.
Best Regards,
Ajeeth
Hi Mate,
ReplyDelete11/10!! Your blog is such a complete read. I like your approach with . Clearly, you wrote it to make learning a cake walk for me.
We're currently in an infinite loop between sales and support, neither of whom seem to be able to understand a basic issue.
We want to purchase some sizeable reserved instances but are told that the only way to pay is all at once with a credit card. No split payments, no offer to pay by check, no offer to pay by ACH, no offer to pay by wire.
Can someone explain to me how AWS serves enterprises if they only accept consumer methods of payment?
Super likes !!! for this AWS Tutorial USA post. I thinks everyone should bookmark this.
Kind Regards,
ganesh
Salve
ReplyDeleteSeems like I won the lottery here….This is a treasure box of blogs and your folks are like leprechauns! Phenomenal read on No. 53 - Longest Arithmetic Sequence
I have set up a free EC2 instance for testing. I'm an experienced developer, so I'm really surprised I have not been able to figure out how to connect via SSH. The sample command Amazon provides does not work: AWS Tutorial
THANK YOU!! This saved my butt today, I’m immensely grateful.
Thanks and Regards
Ajeeth
Your article is good and meaningful .
ReplyDelete+ hide online
خدمة كتابة السيرة الذاتية الإحترافية says
ReplyDeleteWhere to find best jobs in the world why not visit our website for jobs in saudi arabia other than saudi arabia you can look for jobs in pakistan and where you feel your cv is not professional feel free to use our Professional resume writing services we are here to help you out there in a world where completion is moving fast