longest arithmetic progression mock interview discussion - March 26, 2018 - 10: 35 - 12:05 AM

Longest Arithmetic Progression mock interview

/*
Q1-10:42  
 Given a set of numbers, find the length of the longest arithmetic progression in it.
Given a sorted array, find the longest artithmetic progression 
Examples: numbers = new int[]{1, 3, 4, 5, 7, 8, 9} The length is 5, and the sequence is 1, 3, 5, 7, 9
with increment 2 in each iteration.
 
 for now only positive progression
 no duplicate numbers 
 
1   3   4    5    7    8     9   
1   4   8    13   20   28    37 accumulating

start with brute force
1   3   4    5    7    8     9  
i   j   k
diff is 2
look for next number which is 5

1   3   4    5    7    8     9  
i       j    k
diff is 3 
look for 7

time o(n^3)
space o(n)

1   2  3 4 5 6 ... 1000
i   j
map.containsKey(3)
check if its value/index > greater j
map.containsKey(4)
...
map.containsKey(1000)
still o(n^3)

build table is o(n^2)
     1    3    4     5     7     8      9  
1    x    2    3     4     6     7      8
3         x    1     2     4     5      6
4              x     1     3     4      5
5                    x     2     3      4
7                          x     1      2
8                                x      1
9                                       x

     1    3    4     5     7     8      9  
          2    3     4     6     7      8
               1     2*    4*    5      6*

Julia's analysis: go through your table from line 37 to line 44
Try to find longest arithmetic progression:
2 - showing 4 times -> find 4 numbers 
go through line 37, 1, 3 <- 2
go to line 38, 3, -> 5, gap is 2, sequence 1-> 3 -> 5
go to line 41, 2  5 -> 7, sequence 1->3->5->7
go to line 42, 7 -> 9 , sequence 1-> 3  -> 5 -> 7 -> 9 
that is the answer of dynamic programming 

1, 3,5, 7, 9, 
Look at the subproblem we try to find: 
5, 7, 9, 
Subproblem : 5 -7 = 7 - 9, increment is 2
Subproblem rephrase as: 7 = (5 + 9)/ 2, average - three-term arithmetic progression, 7 is average of 5 and 9 

// base case: 
Any two numbers are arithmetic progression
   1,  3,  4,  5,  7,  8, 9 

1                              2      sequence: (1, 9)
3                              2
4                              2
5                              2
7                              2
8                              2
9                              2


How to find if a sorted array contains an arithmetic progression of length 3?
Arr[i] + arr[k] = 2 * arr[j] and i < j < k 
How do we find the solution, what is time complexity? 
Given you a hint, use two pointer technique -> 
 1,  3,  4,  5,  7,  8, 9 
 I                             k   -> 1+9=10/2, target=5  // julia asking question here?
                 J
If j<target, j++
Else if j>target then not found
If j==target can increase length

Second hint, let us brute force second element j, use two pointer technique applying to i and k. 
For example: 
Base case: j = 6, last element in the array -> 2
for(int middle = 5; middle >= 0; middle--)
{
// two pointer technique for i and k 
Left = middle - 1; 
Right = middle + 1; 
while(left >= 0 && right <= n-1)
{
            Int difference = numbers[left] + numbers[right] - 2 * numbers[middle];

middeValue = arr[5] = 8; 
if(difference < 0)
{
Right++; 
}
Else{
Left--; 
}
}
https://prismoskills.appspot.com/lessons/Dynamic_Programming/Chapter_22_-_Longest_arithmetic_progression.jsp

https://stackoverflow.com/questions/18159911/longest-equally-spaced-subsequence

https://codereview.stackexchange.com/questions/188253/longest-arithmetic-progression-algorithm

http://codercareer.blogspot.com/2014/03/no-53-longest-arithmetic-sequence.html

https://www.geeksforgeeks.org/length-of-the-longest-arithmatic-progression-in-a-sorted-array/

https://practice.geeksforgeeks.org/problems/longest-arithmetic-progression/0


}
0    1        2      3        4      5         6
1,     3,      4,     5,      7,      8,        9 
I                                          mid      k
                                  L               r
                                  7+9-2*8=16-16=0

while building table
hash map of diff key, value is frequency of key occurrences
keep track of most frequent key

use table to build list of progression

     1    3    4     5     7     8      9  
1    x    2    3     4     6     7      8
2
3         x    1     2     4     5      6
4              x     1     3     4      5
5                    x     2     3      4
6
7                          x     1      2
8                                x      1
9                                       x