5
\$\begingroup\$

Please review this code, considering I put emphasis on constraining space complexity at the expense of execution speed (accepting additional branching).

  • Can you see cases that prove the algorithm incorrect?
  • Could you improve its execution speed without increasing space complexity?
  • Could you make it more readable?

Method signature from Codility (i.e. strange capitalised parameter name).

Definition of "magnitude pole": available online (e.g. https://stackoverflow.com/questions/15397637/interview-find-magnitude-pole-in-an-array)

import java.util.Arrays;
public class MagnitudePole {
  public int solution(int[] A) {
    final int notFound = -1;
    final int minimumArrayLength = 2;
    if (A.length < minimumArrayLength) {
      return notFound;
    }
    int magnitudePole = 0;
    boolean isPoleValid = true;
    int highestSeen = A[magnitudePole];
    for (int i = 1; i < A.length; i++) {
      final int currentValue = A[i];
      if (currentValue < A[magnitudePole]) {
        isPoleValid = false;
      } else if (currentValue > A[magnitudePole]) {
        if (currentValue > highestSeen && !isPoleValid) {
          isPoleValid = true;
          magnitudePole = i;
        }
      } else {
        if (currentValue < highestSeen) {
          isPoleValid = false;
        } else {
          isPoleValid = true;
          magnitudePole = i;
        }
      }
      highestSeen = Math.max(currentValue, highestSeen);
    }
    return isPoleValid ? magnitudePole : notFound;
  }
}
\$\endgroup\$
1
\$\begingroup\$

Style

final int notFound = -1;
final int minimumArrayLength = 2;

These two fields can be better placed as private static final fields, instead of inside the method. On a related note, you may also want to consider turning this into an "utility class" and have the method as static too:

public class MagnitudePole {

    private static final int notFound = -1;
    private static final int minimumArrayLength = 2;

    private MagnitudePole() {
        // empty
    }

    // using an arguably better-sounding name... MagnitudePole.solveFor(int[])
    public static int solveFor(int[] A) {
        // ...
    }
}

For the currentValue > A[magnitudePole] else-if condition, you can join that with the inner if:

There's a bug here all right... The else should only be done on the original outer condition, so if the inner ifconditions fail it shouldn't reach there. Slightly edited the code block so as not to invalidate the comments on this part. :)

if (currentValue < A[magnitudePole]) {
    isPoleValid = false;
} else if (currentValue > A[magnitudePole] && currentValue > highestSeen && !isPoleValid) {
    isPoleValid = true;
    magnitudePole = i;
} else {
    /* this should only be reached when
        currentValue <= A[magnitudePole],
        bug in preceding else-if! */
}

Finally, in the else part, you can also re-order the conditions around as such:

} else {
    isPoleValid = currentValue >= highestSeen;
    if (isPoleValid) {
      magnitudePole = i;
    }
}

Logic + unit testing

You perform a check for the array to contain at least two elements, which means single-element arrays are conveniently bypassed. Do you actually want to consider them as magnitude poles, since all the LHS and RHS elements ("none", or \$\emptyset\$) are equal to it? :)

I will also suggest writing unit tests as a means of documenting what are the expected outputs for various inputs - valid, invalid, and edge cases in all. The slight benefit is that you can safely optimize your logic later on, and have a safety mechanism to ensure the modifications still work per expectation.

\$\endgroup\$
  • \$\begingroup\$ Thanks for your review :) I prefer your merged if formulation; I should turn on static code analysis before posting next time, as tools like PMD are good at highlighting opportunities for simplified conditionals. Your re-ordered else is way better and I should have spotted the code smell of the repeated isPoleValid = ... You have a fine eye for detail, I appreciate that. Re: logic -> I just made that assumption based on the Codility problem description, notice the "minimumArrayLength" boundary. I agree though that one should think about edge cases deeply, beyond the common code paths.. \$\endgroup\$ – Maroloccio Oct 7 '15 at 16:28
  • \$\begingroup\$ Re: unite testing -> you know I just rewrote that if as you did and it is giving me different results for input values: 1) [1, 3, 2]; 2) [1, 3, 5, 4]; 3) [1, 2, 4, 3]. What do you think? \$\endgroup\$ – Maroloccio Oct 7 '15 at 16:46
  • \$\begingroup\$ Yes, thinking about it, I think your "merged logic" is incorrect. It looked promising, but it has a bug :( You don't want to "fall through" the else if the second part of the condition fails, right? \$\endgroup\$ – Maroloccio Oct 7 '15 at 16:48
  • 1
    \$\begingroup\$ @Maroloccio thanks for spotting the bug! Updated my answer... Another reason why unit testing is important. :D \$\endgroup\$ – h.j.k. Oct 7 '15 at 22:59
  • \$\begingroup\$ Actually, I do have unit testing for this and... that's what caught the anomaly in the test cases I highlighted. I should have included it for clarity, review and regression avoidance, you were right. \$\endgroup\$ – Maroloccio Oct 7 '15 at 23:16

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.