Amazon Interview Question
InternsCountry: India
Interview Type: Written Test
Yes, This is similar to kadanes algo. Question should have longest contiguous arithmetic sequence for more clarity. In the second example elements are 3,7,11,15,19
it is must continues, otherwise the sample -1 1 3 7 11 15 19 20 21 22 should return 6 instead of 5. So the solution seems simple here,
public static int GetTheLongestContinueArithmeticSequence(int[] input)
{
if (input == null) return 0;
int Steps = 0;
int Maxlen = 2;
int currentLen = 2;
if(input.Length == 1) return 1;
for (int i = 1; i < input.Length; i++)
{
int value = input[i] - input[i - 1];
if( value != Steps)
{
Steps = value;
if (currentLen > Maxlen)
{
Maxlen = currentLen;
currentLen = 2;
}
}
else{
currentLen++;
}
}
return Maxlen;
}
Y the ***? u r posting quesns without forming a meaningful sentence..i m asking u. dnt u knw hw 2 frm a sentnce? Anyway i knew ths questn already?
DNT EVER POST QUES LIKE THIS ANY MORE...U ***
Solution(only concept)
We iterate over the array and find the difference between the consecutive elements and keep track of the longest running count of same difference. If current difference is different than the previous difference then we reset the count. If the length of the longest running difference is k. Then the longest arithmetic sequence is of length k+1.
Code
package com.dsalgo;
public class MaxArithmeticSequence {
public static void main(String[] args) {
int[]arr={2,5,3,6,9,12,15,34,23};
findMaxArithmeticSequence(arr);
}
private static void findMaxArithmeticSequence(int[] arr) {
int maxLength=0;
int currentLength=0;
int prevDiff=0;
for(int i=1;imaxLength)
maxLength=currentLength;
}
else
{
currentLength=2;
prevDiff=arr[i]-arr[i-1];
}
}
System.out.println("max arithmetic sequence length = "+maxLength);
}
}
public class LargestArithmeticSequenceInGiveArray {
int sequenceCount = 0;
int longestSequenceCount = 0;
int a_1 = 0;
int d = 0;
int indexCount = 0;
//a_n = a_1 + (n-1)d
public int findLongestArithmeticSequence(int[] givenArray)
{
if(givenArray.length <3)
{
return longestSequenceCount;
}
for(int i=0; i<givenArray.length;)
{
if(sequenceCount == 0)
{
a_1 = givenArray[i];
d = givenArray[i+1] - a_1;
sequenceCount++;
i++;
}
else if(sequenceCount>0)
{
if(a_1 + (sequenceCount)*d == givenArray[i])
{
sequenceCount++;
i++;
}
else
{
indexCount++;
if(longestSequenceCount < sequenceCount)
{
longestSequenceCount = sequenceCount;
}
sequenceCount=0;
i = indexCount;
}
}
if(i == givenArray.length)
{
if(sequenceCount > longestSequenceCount)
longestSequenceCount = sequenceCount;
}
}
return longestSequenceCount;
}
public static void main(String[] args) {
//-1 1 3 7 11 15 19 20 21 22
int[] givenNumber = new int[10];
givenNumber[0] = -1;
givenNumber[1] = 1;
givenNumber[2] = 3;
givenNumber[3] = 7;
givenNumber[4] = 11;
givenNumber[5] = 15;
givenNumber[6] = 19;
givenNumber[7] = 20;
givenNumber[8] = 21;
givenNumber[9] = 22;
LargestArithmeticSequenceInGiveArray l = new LargestArithmeticSequenceInGiveArray();
System.out.println(l.findLongestArithmeticSequence(givenNumber));
}
}
public class LargestArithmeticSequenceInGiveArray {
int sequenceCount = 0;
int longestSequenceCount = 0;
int a_1 = 0;
int d = 0;
int indexCount = 0;
//a_n = a_1 + (n-1)d
public int findLongestArithmeticSequence(int[] givenArray)
{
if(givenArray.length <3)
{
return longestSequenceCount;
}
for(int i=0; i<givenArray.length;)
{
if(sequenceCount == 0)
{
a_1 = givenArray[i];
d = givenArray[i+1] - a_1;
sequenceCount++;
i++;
}
else if(sequenceCount>0)
{
if(a_1 + (sequenceCount)*d == givenArray[i])
{
sequenceCount++;
i++;
}
else
{
indexCount++;
if(longestSequenceCount < sequenceCount)
{
longestSequenceCount = sequenceCount;
}
sequenceCount=0;
i = indexCount;
}
}
if(i == givenArray.length)
{
if(sequenceCount > longestSequenceCount)
longestSequenceCount = sequenceCount;
}
}
return longestSequenceCount;
}
public static void main(String[] args) {
//-1 1 3 7 11 15 19 20 21 22
int[] givenNumber = new int[10];
givenNumber[0] = -1;
givenNumber[1] = 1;
givenNumber[2] = 3;
givenNumber[3] = 7;
givenNumber[4] = 11;
givenNumber[5] = 15;
givenNumber[6] = 19;
givenNumber[7] = 20;
givenNumber[8] = 21;
givenNumber[9] = 22;
LargestArithmeticSequenceInGiveArray l = new LargestArithmeticSequenceInGiveArray();
System.out.println(l.findLongestArithmeticSequence(givenNumber));
}
}
#include<iostream>
using namespace std;
#include<stdlib.h>
#include<conio.h>
#include<string.h>
#include<math.h>
int glas(int *a,int n)
{
int i,j,k;
if(n==1||n==2)
{
return n;
}
else
{
i=j=k=0;
int d=a[1]-a[0];
int max=-1;
int count=2;
for(int i=1;i<n;)
{
count=2;
while((i+1<n)&&a[i+1]-a[i]==d)
{
count++;
i++;
}
if(max<count)
{
max=count;
}
d=a[i+1]-a[i];
i++;
}
return max;
}
}
int main()
{
int n;
cin>>n;
int *a=new int[n];
for(int i=0;i<n;i++)
cin>>a[i];
cout<<glas(a,n);
getch();
return 0;
}
def find_max_seq(a):
count = 0
cur_count = 0
for i in range(1,len(a)):
if a[i]-a[i-1] == 1:
cur_count += 1
else:
cur_count = 0
if cur_count > count:
count = cur_count
return count+1 if count > 0 else count
if __name__ == '__main__':
print find_max_seq([3,2,5,8])
print find_max_seq([-1,1,3,7,11,15,19,20,21,22])
print find_max_seq([-2,-1,0,1,2,3,7,11,15,19,20,21,22])
This problem can be solved using arithmetic sequence formula too.
a_n = a_1 + (n-1)d
we calculate a_1 and d from first two elements and then go for finding third element. by using the above formula and compare it with the current element of the array. If it matches, then we increment sequenceCount, if not, we reset all the set of variables.
public class LargestArithmeticSequenceInGiveArray {
int sequenceCount = 0;
int longestSequenceCount = 0;
int a_1 = 0;
int d = 0;
int indexCount = 0;
//a_n = a_1 + (n-1)d
public int findLongestArithmeticSequence(int[] givenArray)
{
if(givenArray.length <3)
{
return longestSequenceCount;
}
for(int i=0; i<givenArray.length;)
{
if(sequenceCount == 0)
{
a_1 = givenArray[i];
d = givenArray[i+1] - a_1;
sequenceCount++;
i++;
}
else if(sequenceCount>0)
{
if(a_1 + (sequenceCount)*d == givenArray[i])
{
sequenceCount++;
i++;
}
else
{
indexCount++;
if(longestSequenceCount < sequenceCount)
{
longestSequenceCount = sequenceCount;
}
sequenceCount=0;
i = indexCount;
}
}
if(i == givenArray.length)
{
if(sequenceCount > longestSequenceCount)
longestSequenceCount = sequenceCount;
}
}
return longestSequenceCount;
}
public static void main(String[] args) {
//-1 1 3 7 11 15 19 20 21 22
int[] givenNumber = new int[10];
givenNumber[0] = -1;
givenNumber[1] = 1;
givenNumber[2] = 3;
givenNumber[3] = 7;
givenNumber[4] = 11;
givenNumber[5] = 15;
givenNumber[6] = 19;
givenNumber[7] = 20;
givenNumber[8] = 21;
givenNumber[9] = 22;
LargestArithmeticSequenceInGiveArray l = new LargestArithmeticSequenceInGiveArray();
System.out.println(l.findLongestArithmeticSequence(givenNumber));
}
}
public class LargestArithmeticSequenceInGiveArray {
int sequenceCount = 0;
int longestSequenceCount = 0;
int a_1 = 0;
int d = 0;
int indexCount = 0;
//a_n = a_1 + (n-1)d
public int findLongestArithmeticSequence(int[] givenArray)
{
if(givenArray.length <3)
{
return longestSequenceCount;
}
for(int i=0; i<givenArray.length;)
{
if(sequenceCount == 0)
{
a_1 = givenArray[i];
d = givenArray[i+1] - a_1;
sequenceCount++;
i++;
}
else if(sequenceCount>0)
{
if(a_1 + (sequenceCount)*d == givenArray[i])
{
sequenceCount++;
i++;
}
else
{
indexCount++;
if(longestSequenceCount < sequenceCount)
{
longestSequenceCount = sequenceCount;
}
sequenceCount=0;
i = indexCount;
}
}
if(i == givenArray.length)
{
if(sequenceCount > longestSequenceCount)
longestSequenceCount = sequenceCount;
}
}
return longestSequenceCount;
}
public static void main(String[] args) {
//-1 1 3 7 11 15 19 20 21 22
int[] givenNumber = new int[10];
givenNumber[0] = -1;
givenNumber[1] = 1;
givenNumber[2] = 3;
givenNumber[3] = 7;
givenNumber[4] = 11;
givenNumber[5] = 15;
givenNumber[6] = 19;
givenNumber[7] = 20;
givenNumber[8] = 21;
givenNumber[9] = 22;
LargestArithmeticSequenceInGiveArray l = new LargestArithmeticSequenceInGiveArray();
System.out.println(l.findLongestArithmeticSequence(givenNumber));
}
}
public class LargestArithmeticSequenceInGiveArray {
int sequenceCount = 0;
int longestSequenceCount = 0;
int a_1 = 0;
int d = 0;
int indexCount = 0;
//a_n = a_1 + (n-1)d
public int findLongestArithmeticSequence(int[] givenArray)
{
if(givenArray.length <3)
{
return longestSequenceCount;
}
for(int i=0; i<givenArray.length;)
{
if(sequenceCount == 0)
{
a_1 = givenArray[i];
d = givenArray[i+1] - a_1;
sequenceCount++;
i++;
}
else if(sequenceCount>0)
{
if(a_1 + (sequenceCount)*d == givenArray[i])
{
sequenceCount++;
i++;
}
else
{
indexCount++;
if(longestSequenceCount < sequenceCount)
{
longestSequenceCount = sequenceCount;
}
sequenceCount=0;
i = indexCount;
}
}
if(i == givenArray.length)
{
if(sequenceCount > longestSequenceCount)
longestSequenceCount = sequenceCount;
}
}
return longestSequenceCount;
}
public static void main(String[] args) {
//-1 1 3 7 11 15 19 20 21 22
int[] givenNumber = new int[10];
givenNumber[0] = -1;
givenNumber[1] = 1;
givenNumber[2] = 3;
givenNumber[3] = 7;
givenNumber[4] = 11;
givenNumber[5] = 15;
givenNumber[6] = 19;
givenNumber[7] = 20;
givenNumber[8] = 21;
givenNumber[9] = 22;
LargestArithmeticSequenceInGiveArray l = new LargestArithmeticSequenceInGiveArray();
System.out.println(l.findLongestArithmeticSequence(givenNumber));
}
}
This is a simple dynamic programming problem. It is similar to Kadane's largest subarray sum problem.
}
- Farhang March 24, 2013