Finding alternating sequence in a list of numbers

Question

Please be brutal and treat this as me coding this up for an interview.

A sequence of numbers is called a zig-zag sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a zig-zag sequence.

For example, 1,7,4,9,2,5 is a zig-zag sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, 1,4,7,2,5 and 1,7,4,5,5 are not zig-zag sequences, the first because its first two differences are positive and the second because its last difference is zero.

Given a sequence of integers, sequence, return the length of the longest subsequence of sequence that is a zig-zag sequence. A subsequence is obtained by deleting some number of elements (possibly zero) from the original sequence, leaving the remaining elements in their original order.

More examples:

1. { 1, 7, 4, 9, 2, 5 }

   Returns: 6

   The entire sequence is a zig-zag sequence.

2. { 1, 17, 5, 10, 13, 15, 10, 5, 16, 8 }

   Returns: 7

   There are several subsequences that achieve this length. One is 1,17,10,13,10,16,8.

3. { 44 }

   Returns: 1

4. { 1, 2, 3, 4, 5, 6, 7, 8, 9 }

   Returns: 2

5. { 70, 55, 13, 2, 99, 2, 80, 80, 80, 80, 100, 19, 7, 5, 5, 5, 1000, 32, 32 }

   Returns: 8

6. { 374, 40, 854, 203, 203, 156, 362, 279, 812, 955, 600, 947, 978, 46, 100, 953, 670, 862, 568, 188, 67, 669, 810, 704, 52, 861, 49, 640, 370, 908, 477, 245, 413, 109, 659, 401, 483, 308, 609, 120, 249, 22, 176, 279, 23, 22, 617, 462, 459, 244 }

   Returns: 36

Worst case: \$O(n^2)\$
Space Complexity: \$O(n)\$

private static int longestAlternatingSequence(int[] values){
        if(values.length == 1){
            return 1;
        }
        int[] difference = new int[values.length-1];
        for(int i = 1; i < values.length; i++){
            difference[i-1] = values[i] - values[i-1];
        }
        int[] calculationsCache = new int[difference.length];
        calculationsCache[0] = 1;
        int max = Integer.MIN_VALUE;
        for(int i = 1; i < difference.length; i++){
            if(difference[i] > 0){
                for(int j = 0; j < i; j++){
                    if(difference[j] < 0){
                        max = Math.max(max, calculationsCache[j]);
                    }
                }
            }else if(difference[i] < 0){
                    for(int j = 0; j < i; j++){
                        if(difference[j] > 0){
                            max = Math.max(max, calculationsCache[j]);
                        }
                    }
             }else{
                   max = 0;
            }
            calculationsCache[i] = max + 1;
         }
        max = Integer.MIN_VALUE;

        for(int value : calculationsCache){
            max = Math.max(max, value);
        }
        return max + 1;
     }

Answer 1

Basically, you approach solves the problem adequately, and I have nothing to say about the existing code in terms of style.

However, I think the general approach might be too costly, in terms of time and space requirements (even though I admit that there is no spec). But since we should treat it as an interview question, then a potential interviewer could ask you how to approach the problem more efficiently: for example, how could you process the array in one pass only?

So here is a possible answer.

Algorithm's complexity

As you said, your current implementation requires:

• linear storage requirement
• quadratic execution time

I have an alternative approach, using constant memory and linear time, which is based on an incremental algorithm: for each element of the array, you can determine the longuest zig-zag subsequence that can be built so-far.

I prototyped the solution using Common Lisp, so here is my version (this could be translated easily as a simple for loop in Java, but this is left as an exercise ;-))

(defun max-zig-zag (sequence)
  (loop
     for last = nil then current
     for current in sequence
     for sign   = 0 then (signum (- current last))
     for match  = t then (or (eql await 0) (eql await sign))
     for await  = 0 then (if match (- sign) await)
     count match))

This approach makes all your test examples pass:

(loop for (expected sequence) in 
     '((6 (1 7 4 9 2 5))
       (7 (1 17 5 10 13 15 10 5 16 8))
       (1 (44))
       (2 (1 2 3 4 5 6 7 8 9))
       (8 (70 55 13 2 99 2 80 80 80 80 100 19 7 5 5 5 1000 32 32))
       (36 (374 40 854 203 203 156 362 279 812 955 600 947 978 46 100 953 670 862 568 188 67 669 810 704 52 861 49 640 370 908 477 245 413 109 659 401 483 308 609 120 249 22 176 279 23 22 617 462 459 244)))
     always (eql expected (max-zig-zag sequence)))

=> T

I acknowledge that this might not be easy to follow through, so I'll try to write a step-by-step explanation.

Main idea

The difficulty in your question is that you allow some elements to be deleted (or, ignored). We are looking for sequences with maximum length, however. The elements that can be ignored are those that do not alternate from previous ones: when you encounter a 2, and then the number 4, you can discard all the following elements that are greater than, or equal to, 4, without reducing the potential length of the subsequence: all numbers above 3 are just intermediate values.

The suggested approach is a greedy count of all the alternations of slopes in the array (*). It is built around a fixed number of variables that are updated at each element, during a unique iteration of the array; in fact, the input array could be an infinite stream of inputs, whereas the count value could be an infinite stream of integers that is updated for each input (and growing when needed).

Derivative

So, the main idea is to look at the shape, or the derivative of your numbers: you take the current value, and the last value, when iterating over the array, and you compute the difference: that gives you the slope.

However, what is interesting is only the sign of this slope: the sign variable always contains the sign of the difference between current and last element, so that a 1 means that current value is higher, and -1 mean that is is lower than the last one.

Matching zig-zags

Initially, you await for any of those sign, either -1 or 1 (which is encoded by zero in the await variable). This first time that sign differs from zero you have a match: you encountered a positive or negative variation of value; so, the new value of await is now the opposite of the current sign: if we saw a positive slope, like 1, we must read until there is a negative one.

The match variable is initially true, and is otherwise true only when the sign variable equals the await variable (or, if await is zero, during the initialization phase).

• When match is false, we skip entries and let await keep its previous value.
• When true, await takes the opposite of current sign, which means that we await for a change in the slope.

Then, match is true whenever we go up after having gone down, and respectively down after having gone up, discarding all continuous sequences of decreasing (or increasing) elements.

Finally, we count the number of matches to have the longuest subsequence.

---

(*) It is based on a data-flow approach (see Lustre, Signal, ...). In fact, the Common Lisp code above could probably easily be rewritten using the SERIES package.

Answer 2

1. Calling the method with an empty array throws a java.lang.NegativeArraySizeException. You should check that and throw an exception with a helpful error message.

2. You could extract out a createDifferenceArray method for better readability:

   private static int[] createDifferenceArray(int[] values) {
       int[] difference = new int[values.length - 1];
       for (int i = 1; i < values.length; i++) {
           difference[i - 1] = values[i] - values[i - 1];
       }
       return difference;
   }