Longest Arithmetic Progression

Image placeholder 9899Image placeholder 9899Image placeholder 9899

(This question has been seen in the interviews of the following companies: Facebook, Google, Microsoft)
In the array {1, 6, 3, 5, 9, 7}, the longest arithmetic sequence is 1, 3, 5, and 7

Dynamic programming with a map of a map.

public static int llac(int[] array) {
        if(array.length == 0) return 0;
        int max = 1;
        Map> index_to_llac = new HashMap<>(); //Map>
        for(int current = 1; current < array.length; current++) {
            index_to_llac.put(current, new HashMap<>());
            for(int prev = 0; prev < current; prev++) {
                int diff = array[current] - array[prev];
                int length = 2;
                if(index_to_llac.containsKey(prev) && index_to_llac.get(prev).containsKey(diff)) {
                    length = index_to_llac.get(prev).get(diff) + 1;
                Map diff_to_llac = index_to_llac.get(current);
                //if this is a arithmetic progression with [diff] exists before current, add 1 to the length to include current in the progression
                //otherwise, [prev, current] forms a progression of size 2
                diff_to_llac.put(diff, length);
                max = Math.max(length, max);
        return max;

Get one-to-one training from Google Facebook engineers

Top-notch Professionals

Learn from Facebook and Google senior engineers interviewed 100+ candidates.
Most recent interview questions and system design topics gathered from aonecode alumnus.
One-to-one online classes. Get feedbacks from real interviewers.

Customized Private Class

Already a coding expert? - Advance straight to hard interview topics of your interest.
New to the ground? - Develop basic coding skills with your own designated mentor.
Days before interview? - Focus on most important problems in target company question bank.