3
\$\begingroup\$

Return any three descending numbers that appear sequentially in the input such that A[i] > A[j] > A[k] and i < j < k. Since problem description contains 'any', I could not unit test using JUnit.

I'm looking for request code review, optimizations and best practices.

final class DescendingTriplets {

    private final int high;
    private final int mid;
    private final int low;

    DescendingTriplets(int high, int mid, int low) {
        this.high = high; 
        this.mid = mid; 
        this.low = low;
    }

    public int getHigh() {
        return high;
    }

    public int getMid() {
        return mid;
    }

    public int getLow() {
        return low;
    }

    @Override
    public String toString() {
        return "high: " + high + " mid: " + mid + " low: "  + low;
    }
}

public final class ThreeDescending {

    private ThreeDescending() {}

    /**
     * This class is used to save high and mid values.
     */
    private static class State {
        int mid;
        int high;

        State(int low, int high) {
            this.mid = low;
            this.high = high;
        }
    }

    /**
     * Returns any three descending numbers in an array such that they appear one after other in the original sequence.
     * If such numbers dont exist then null is returned
     * 
     * @param a         the input array 
     * @return          object with three descending numbers in squence
     */
    public static DescendingTriplets getDescendingTriplets(int[] a) {
        if (a.length < 3) {
            throw new IllegalArgumentException("The arrays size should atleast be three");
        }

        /*
         * The current state of 'high' and 'mid' values to be used to compare 'min' against.
         */
        State stateCurrent = null;
        /*
         * The state of new 'high' and new 'mid' which we obtain as we travel the array.
         * Once both values(high and mid) are populated, we replace the stateCurrent with the stateInProgress.
         */
        State stateInProgress = null;

        int k = 0;
        // fetch the completedstate,
        for (int i = 0; i < a.length - 1; i++) {
            if (a[i] > a[i + 1]) {
                stateCurrent = new State(a[i + 1], a[i]);
                k = i + 1;
                break;
            }
        }

        for (int j = k + 1; j < a.length; j++) {
            // if smallest
            if (a[j] <= stateCurrent.mid) {
                return new DescendingTriplets(stateCurrent.high, stateCurrent.mid, a[j]);
            }

            // if greater than mid but less than high
            if (a[j] <= stateCurrent.high) {
                if (stateInProgress != null) {
                    stateCurrent = stateInProgress;
                }
                stateCurrent.mid = a[j];
            } else {
                // if greater than high
                if (stateInProgress != null) {
                    if (j > stateInProgress.high) {
                        stateInProgress.high = a[j];
                    } else {
                        stateInProgress.mid = a[j];
                        stateCurrent = stateInProgress;
                    }
                } else {
                    stateInProgress = new State(Integer.MIN_VALUE, a[j]);
                }
            }
        }

        return null;
    }

    public static void main(String[] args) {
        int[] a1 = {5, 14, 3, 2, 1};
        System.out.println(getDescendingTriplets(a1));

        int[] a2 = {4,7,5,1,3,8,9,6,2};
        System.out.println(getDescendingTriplets(a2));
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ sequentially meaning that k = j-1, j = i-1? \$\endgroup\$ – Vogel612 Apr 14 '14 at 8:13
  • 1
    \$\begingroup\$ It appears that the statement Return any three descending numbers that appear sequentially in the input is ambiguous, and can be interpreted multiple ways. The answer I gave does one interpretation of that, but your code does a different interpretation... Down-vote applied. \$\endgroup\$ – rolfl Apr 14 '14 at 13:00
  • \$\begingroup\$ sequentially - wrt my question - does not mean consecutive. Hope that solves doubts. \$\endgroup\$ – JavaDeveloper Apr 14 '14 at 19:43
  • \$\begingroup\$ your algorithm is incorrect. Consider the array {5, 4, 6, 7, 6, 5}. Your program returns 6, 7, 6, which is not descending. \$\endgroup\$ – Red Alert Apr 14 '14 at 23:32
2
\$\begingroup\$

Return any three descending numbers that appear sequentially in the input such that A[i] > A[j] > A[k] and i < j < k. Since problem description contains 'any', I could not unit test using junits.

I think you could create inputs for tests where

  • there is only one of this sequence and check that,
  • there are only a couple of possible sequences and check that the returned one whether exists in the possible return values list or not,
  • there isn't any valid sequence.
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Even simpler than enumerating all possible sequences per input, an unit test could assert 0 <= i < j < k < A.length and A[i] > A[j] > A[k] in the case of one or more possible sequences. \$\endgroup\$ – amon Apr 14 '14 at 7:54
  • \$\begingroup\$ @amon: It should also check the returned values exist in the input array. \$\endgroup\$ – palacsint Apr 14 '14 at 7:58
1
\$\begingroup\$

The code for this one baffles me. I believe you are doing much, much more work than necessary.

The nature of the problem is such that an \$O(n)\$ solution is the best time-complexity one. Your solution is in fact \$O(n)\$, but it is much, much more complicated than necessary.... two loops over the data? Lots of state conditions, and class objects, and conditionals.

Have you considered the simple function (returns the index of the first of the triples, or -1 if there is not one:

public static final int getDescendingTriple(int[] data) {
    int index = 2;
    while (index < data.length
            && (data[index - 2] >= data[index - 1] || data[index - 1] >= data[index]) {
        index++;
    }
    if (index >= data.length) {
        return -1;
    }
    return index - 2;
}

If you want to return the fancy DescendingTriplets then you can construct that from index (if >= 0).

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ I don't think your solution answers the problem. I agree the OP is unclear on this aspect, but what I understood is that the indices don't have to follow each other. I believe the OP just wants i < j < k. \$\endgroup\$ – Joffrey Apr 14 '14 at 12:57
  • 1
    \$\begingroup\$ @Joffrey - I think you may be right. The question is ambiguous (the description and implementation do different things in the asker's question). \$\endgroup\$ – rolfl Apr 14 '14 at 13:01
  • 1
    \$\begingroup\$ agreed that it is ambiguous, let's wait for the OP to answer the comments. \$\endgroup\$ – Joffrey Apr 14 '14 at 13:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.