6
\$\begingroup\$

I am preparing for a coding interview and I have the following questions:

Find the biggest positive number sequence in the Integer Array.

If Input is [1,2,5,6,-7,5,7,8,5,6,7,-6,7,0], then output should be [5,7,8,5,6,7], which is the longest positive digit sequence.

Below is my code for the above program:

public class Test1 {

public static void main(String args[]){
                           //  0     1     2      3     4    5    6     7    8   9   10   11     12   13   14      15
         int numberArray[] = {-2,   -3,   -5,    -6,   -7,  -7,  -8,    9,   0,  -6,  3,  -1,    -2,   0,   -9,    -12};

        /* TEST DATA
         * int numberArray[] = {-2,   -3,   -5,   -6,  -7};                     //DATA WITH ALL NEGATIVE NUMBERS.  EXPECTED OUTPUT is SIZE : 0
         * int numberArray[] = {};                                              //DATA WITH ALL NO VALUES.         EXPECTED OUTPUT is SIZE : 0
         * int numberArray[] = {-2,   -3,    7,   -6,  -7};                     //DATA WITH ONE POSITIVE DATA.     EXPECTED OUTPUT is SIZE : 1
         * int numberArray[] = {-2,    3,   5,     6,  -7,   23,   4,   4,  1}; //DATA WITH VALID VALUES.          EXPECTED OUTPUT is SIZE : 4
         */

        //Initializing all values. At Start, Start And End Index Points to First Location i.e., Index=0;
        int startIndex=0;
        int endIndex=0;

        // Stores the Length of Sequence and Its Start Index
        int validSequenceSize=0;
        int validSequenceStartIndex=0;

        for(int index=0; index<numberArray.length; index++){

                // If series started with Positive Number and StartIndex is '0', Move EndIndex to Next Location.
                // This make sure the StartIndex and End Index are always different.

                if(numberArray[index]>0 && startIndex==0){
                    endIndex=endIndex+1;
                }

                //Setting the Value of End Index. if value is Negative or reached the end of Series, Set the end Index
                if(numberArray[index]<0 || numberArray.length-1==index ){

                        if(startIndex!=endIndex){
                                    endIndex=index;
                                    int difference=endIndex-startIndex;

                                    // Check the difference between Start and End Index of Valid Positive Number Sequence
                                    if(difference>=validSequenceSize && difference!=0){
                                            validSequenceSize=difference;

                                            // if the Last Digit is Positive Number, Increase the  valid Sequence size by 1
                                            if(numberArray[numberArray.length-1]>0 && numberArray.length-1==index){
                                                validSequenceSize=validSequenceSize+1;
                                            }
                                            validSequenceStartIndex=startIndex;

                                    }
                        }


                //Setting value of Start Index after One Set of Calculation is Completed.
                if(endIndex!=numberArray.length-1 && numberArray[index]<0 ){
                    startIndex=endIndex+1;
                }

                }
        }

        //RESULT
        System.out.println("Size of Sequence : "+validSequenceSize);

        if(validSequenceSize>0){
                System.out.println("Valid Sequence Starts at Index[" +validSequenceStartIndex +"]");
                for (int index=validSequenceStartIndex; index<validSequenceStartIndex+validSequenceSize;index++){
                        System.out.println("Values of Biggest Positive Sequence in Index["+index+"] -- "+numberArray[index]);
                }
        }




}
}

Is this the correct approach? I am able to find the sequence, but I am not sure if this is the most efficient. The interview mainly focus on

  1. optimizing the code;
  2. reducing the variable usage;
  3. looping.

Also, would sorting the integer array before proceeding the operation result in better performance?

Please let me know your inputs/thoughts and guide me to optimize the code.

\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Review! Good job on your first question. \$\endgroup\$ – SirPython May 1 '16 at 22:58
3
\$\begingroup\$

Code Style:

  • You should give your class a proper name like PositiveSequenceFinder. Or maybe you can think of something better.
  • Use methods instead of doing everything in the main method. For example int[] findSequence(int[] array) and printSequence(int[] sequence)
  • There are too many comments, some of them not really helpful:
 //  0     1     2      3     4    5    6     7    8   9   10   11     12   13   14      15
 int numberArray[] = {-2,   -3,   -5,    -6,   -7,  -7,  -8,    9,   0,  -6,  3,  -1,    -2,   0,   -9,    -12};
  • Wrong spacing:

    //Setting value of Start Index after One Set of Calculation is Completed.
    if(endIndex!=numberArray.length-1 && numberArray[index]<0 ){
        startIndex=endIndex+1;
    }
    
    }
    

    In my opinion it is more readable if there are spaces between operatos. At least use it consistently (why are there spaces before and after &&?


Algorithm:

You can make it much more simpler. This would be my solution:

import java.util.Arrays;

public class SequenceFinder
{
    private static final int INPUT[] = {-2, -3, -5, -6, -7, -7, -8, 9, 0, -6, 3, -1, -2, 0, -9, -12};

    public static void main(String[] args)
    {
        System.out.println(Arrays.toString(findPositiveSequence(INPUT)));
    }

    public static int[] findPositiveSequence(int[] array)
    {
        int maxSequenceStartIndex = 0;
        int maxSequenceLength = 0;
        int currentSequenceStartIndex = 0;
        int currentSequenceLength = 0;
        for (int i = 0; i < array.length; i++)
        {
            if(array[i] < 0)
            {
                if(currentSequenceLength > maxSequenceLength)
                {
                    maxSequenceLength = currentSequenceLength;
                    maxSequenceStartIndex = currentSequenceStartIndex;
                }
                currentSequenceStartIndex = i + 1;
                currentSequenceLength = 0;
            }
            else
            {
                currentSequenceLength++;
            }
        }

        if(currentSequenceLength > maxSequenceLength)
        {
            maxSequenceStartIndex = currentSequenceStartIndex;
            maxSequenceLength = currentSequenceLength;
        }

        int maxSequenceEndIndex = maxSequenceStartIndex + maxSequenceLength;
        return Arrays.copyOfRange(array, maxSequenceStartIndex, maxSequenceEndIndex);
    }

}

I can't see how sorting the array could be helpful, because the order of the elements is important to the problem. The time complexity of your algorithm is linear, and - correct me if I'm wrong - I don't think it goes any better.

\$\endgroup\$
4
\$\begingroup\$

1 Terminology

What you deal with here, is actually finding a longest positive substring and not a subsequence, since sequences may have "gaps". For example, if we are given a sequence \$S = \langle 1, 2, 3, 4, 5 \rangle\$, \$\langle 2, 3, 4 \rangle\$ is a substring of \$S\$, whereas \$\langle 2, 4, 5 \rangle\$ is not.

2 API design

You should have a separate method for computing the longest positive subsequence outside of main. That way, you can reuse your algorithm. Also, it would be nice if your algorithm returned a class that fully describes the solution.

3 Coding conventions

The indentation of 8 spaces is too much. Consider using 4.

You should always have a space before and after a binary operator. So instead of

if (foo==bar) ...

you should write

if (foo == bar) ...

Also, you should have a space before and after the parenthesized expression. Instead of

for(int i = 0; i < 10; ++i){ ...

you should write

for (int i = 0; i < 10; ++i) { ...

4 Algorithm

You are overkilling it. See below for alternative implementations.

Summa summarum

All in all, I had this in mind:

import java.util.Objects;
import java.util.Random;

public class IntSequenceUtils {

    public static final class PositiveSequence {
        private final int fromIndex;
        private final int toIndex;

        PositiveSequence(final int fromIndex, final int toIndex) {
            this.fromIndex = fromIndex;
            this.toIndex   = toIndex;
        }

        public int getFromIndex() {
            return fromIndex;
        }

        public int getToIndex() {
            return toIndex;
        }

        public int length() {
            return toIndex - fromIndex;
        }

        public String getSequenceString(final int[] array) {
            final StringBuilder sb = new StringBuilder("[");
            final int length = length();

            if (length > 0) {
                sb.append(array[fromIndex]);
            }

            for (int i = fromIndex + 1; i < toIndex; ++i) {
                sb.append(", ").append(array[i]);
            }

            return sb.append("]").toString();
        }

        @Override
        public boolean equals(Object object) {
            if (object == null) {
                return false;
            }

            if (!getClass().equals(object.getClass())) {
                return false;
            }

            PositiveSequence other = (PositiveSequence) object;

            return getFromIndex() == other.getFromIndex() 
                    && getToIndex() == other.getToIndex();
        }

        @Override
        public int hashCode() {
            int hash = 3;
            hash = 59 * hash + this.fromIndex;
            hash = 59 * hash + this.toIndex;
            return hash;
        }
    }

    public static PositiveSequence 
        findLongestPositiveSequenceStartIndex(final int[] array) {
        Objects.requireNonNull(array, "The input array is null.");

        int bestFromIndexSoFar       = 0;
        int bestToIndexSoFar         = 0;
        int maximumLengthSoFar       = 0;
        int currentSubsequenceLength = 0;
        int newFromIndex             = 0;

        for (int i = 0; i < array.length; ++i) {
            if (array[i] < 0) {
                newFromIndex = i + 1;
                currentSubsequenceLength = 0;
            } else if (maximumLengthSoFar < ++currentSubsequenceLength) {
                maximumLengthSoFar = currentSubsequenceLength;
                bestFromIndexSoFar = newFromIndex;
                bestToIndexSoFar   = i + 1;
            }
        }

        return new PositiveSequence(bestFromIndexSoFar, bestToIndexSoFar);
    }

    public static PositiveSequence
        findLongestPositiveSequenceStartIndex2(final int[] array) {
        Objects.requireNonNull(array, "The input array is null.");

        int bestPositiveSequenceLengthSoFar = 0;
        int bestStartIndex                  = 0;

        for (int index = 0; index < array.length; ++index) {
            if (array[index] >= 0) {
                int i = index + 1;

                while (i < array.length && array[i] >= 0) { 
                    i++; 
                }

                if (bestPositiveSequenceLengthSoFar < i - index) {
                    bestPositiveSequenceLengthSoFar = i - index;
                    bestStartIndex = index;
                }

                index += i - index;
            }
        }

        return new PositiveSequence(bestStartIndex, 
                                    bestStartIndex + 
                                            bestPositiveSequenceLengthSoFar);
    }

    public static void main(String args[]) {
        final long seed = System.nanoTime();
        final Random random = new Random(seed);

        System.out.println("Seed = " + seed);

        for (int i = 0; i < 1000; ++i) {
            final int[] ints = random.ints(100).toArray();

            final PositiveSequence seq1 = 
                    findLongestPositiveSequenceStartIndex(ints);

            final PositiveSequence seq2 = 
                    findLongestPositiveSequenceStartIndex2(ints);

            if (!seq1.equals(seq2)) {
                throw new RuntimeException("Algorithms did not agree.");
            }
        }
    }
}

Hope that helps.

\$\endgroup\$
  • \$\begingroup\$ Thank you for providing me your thoughts and excellent code. its clean, clear and helps alot. I will follow those suggestions. \$\endgroup\$ – Cyborgz May 2 '16 at 20:26
  • \$\begingroup\$ Sure. Note that both the algorithms run in linear time as any other algorithm proposed in the answers. Note also that here in a StackExchange community you can always reaccept another answer; it's not set in stone. \$\endgroup\$ – coderodde May 3 '16 at 4:57
1
\$\begingroup\$
public static int[] maxRunOfPositiveNumbers(int[] arr) {
  final int n = arr.length;
  int maxstart = 0;
  int maxlen = 0;
  int i = 0;

  while (i < n) {
    while (i < n && arr[i] <= 0)
      i++;

    int start = i;
    while (i < n && arr[i] > 0)
      i++;
    int len = i - start;

    if (len > maxlen) {
      maxstart = start;
      maxlen = len;
    }
  }
  return Arrays.copyOfRange(arr, maxstart, maxstart + maxlen);
}

This is the code I would expect as an interviewer. No implementation comments, short and readable, and accompanied by a good unit test covering all interesting cases (not shown here).

And no, don’t sort the array before processing it. The caller will not expect the array to be modified, and it would lead to wrong results.

(Edit: changed the return type to int[], actually tested the code)

\$\endgroup\$
  • 1
    \$\begingroup\$ clean and simple. However, code for printing the array sequence is missing.! Thank you \$\endgroup\$ – Cyborgz May 2 '16 at 20:30
  • \$\begingroup\$ I updated my answer. I must have totally misread the original requirement. \$\endgroup\$ – Roland Illig May 2 '16 at 20:43
1
\$\begingroup\$

Here is what I would think, being the interviewer. Don’t take these remarks personally, they are just meant to give you the view from the other side of the job application table.

public class Test1 {

That’s a bad name for a class. I had expected something like IntArrayAnalyzer or IntArrayUtils.

public static void main(String args[]){

Oh, a C programmer. Java programmers would have written String[] args.

There is a space missing between the ) and the {.

                           //  0     1     2      3     4    5    6     7    8   9   10   11     12   13   14      15
         int numberArray[] = {-2,   -3,   -5,    -6,   -7,  -7,  -8,    9,   0,  -6,  3,  -1,    -2,   0,   -9,    -12};

        /* TEST DATA
         * int numberArray[] = {-2,   -3,   -5,   -6,  -7};                     //DATA WITH ALL NEGATIVE NUMBERS.  EXPECTED OUTPUT is SIZE : 0
         * int numberArray[] = {};                                              //DATA WITH ALL NO VALUES.         EXPECTED OUTPUT is SIZE : 0
         * int numberArray[] = {-2,   -3,    7,   -6,  -7};                     //DATA WITH ONE POSITIVE DATA.     EXPECTED OUTPUT is SIZE : 1
         * int numberArray[] = {-2,    3,   5,     6,  -7,   23,   4,   4,  1}; //DATA WITH VALID VALUES.          EXPECTED OUTPUT is SIZE : 4
         */

Why is this test data in the main code? Maybe the applicant never heard of JUnit? That would be a bad sign. My production code should not look like this. The numbers are almost aligned in columns, but only almost. Doesn’t he have an eye for that?

AND WHY IS HE SCREAMING SO LOUD? Maybe a COBOL background?

        //Initializing all values. At Start, Start And End Index Points to First Location i.e., Index=0;

Oh, not a native English speaker. The capitalization of the words looks completely random.

Why does the comment repeat what the code is saying (Index=0)?

        int startIndex=0;
        int endIndex=0;

This seems to be the implementation of the required functionality. Why is it implemented directly in main? If he programs like this, the whole program will probably fit into a single method with 100 local variables, which is completely unmaintainable. I don’t want to have such a programmer in my team.

        // Stores the Length of Sequence and Its Start Index
        int validSequenceSize=0;
        int validSequenceStartIndex=0;

If the variable were named validSequenceLength, the above comment would be completely redundant. Like this, it only wastes screen space.

        for(int index=0; index<numberArray.length; index++){

For simple loops, the variable is usually called i. Deriving from this convention probably means that in this case, the loop variable is more important than usual. It’s ok in this case though, since this variable will influence the result.

                // If series started with Positive Number and StartIndex is '0', Move EndIndex to Next Location.
                // This make sure the StartIndex and End Index are always different.

                if(numberArray[index]>0 && startIndex==0){
                    endIndex=endIndex+1;

A Java programmer who doesn’t know the ++ operator?

                }

                //Setting the Value of End Index. if value is Negative or reached the end of Series, Set the end Index
                if(numberArray[index]<0 || numberArray.length-1==index ){

The above comment is redundant.

                        if(startIndex!=endIndex){

One of the above comments says that startIndex and endIndex are always different, which should mean that this if clause is redundant.

                                    endIndex=index;
                                    int difference=endIndex-startIndex;

                                    // Check the difference between Start and End Index of Valid Positive Number Sequence
                                    if(difference>=validSequenceSize && difference!=0){
                                            validSequenceSize=difference;

                                            // if the Last Digit is Positive Number, Increase the  valid Sequence size by 1

Another redundant comment.

                                            if(numberArray[numberArray.length-1]>0 && numberArray.length-1==index){

In the second condition, numberArray.length-1==index looks unusual, since normally the variable that is currently more interesting or changes more often is written on the left-hand side. So it would be index==numberArray.length-1.

                                               validSequenceSize=validSequenceSize+1;
                                            }
                                            validSequenceStartIndex=startIndex;

                                    }
                        }


                //Setting value of Start Index after One Set of Calculation is Completed.
                if(endIndex!=numberArray.length-1 && numberArray[index]<0 ){
                    startIndex=endIndex+1;
                }

                }

Two closing braces in the same column? He must have forgotten to let his IDE format the code automatically. Just good that we use automatic formatting. Otherwise, the code of the whole team would be a real mess.

        }

        //RESULT
        System.out.println("Size of Sequence : "+validSequenceSize);

        if(validSequenceSize>0){
                System.out.println("Valid Sequence Starts at Index[" +validSequenceStartIndex +"]");

The formatting looks weird. Why should there be brackets around the number? To a programmer reading this, this would look like an array access, which it clearly isn’t. So he is probably not too concerned about readability of the program’s output.

                for (int index=validSequenceStartIndex; index<validSequenceStartIndex+validSequenceSize;index++){
                        System.out.println("Values of Biggest Positive Sequence in Index["+index+"] -- "+numberArray[index]);
                }
        }

So many unneeded empty lines.

}
}

So that’s all the code. Fine. He seems to be a very beginner, otherwise there would be fewer comments, especially the redundant ones. There is no unit test, which also speaks for a beginner. He doesn’t know the ++ operator and doesn’t structure his code. This will mean a long period of training, which will cost me another colleague’s time. I will probably not hire him, since I prefer programmers who are ready for productive work.

\$\endgroup\$
  • \$\begingroup\$ Thanks for taking your time in reviewing entire code and providing all suggestions. very helpful to improve my coding. \$\endgroup\$ – Cyborgz May 3 '16 at 9:48
  • \$\begingroup\$ I'd like to invite you to get rid of the idiotically outdated crack at COBOL. Since the 1985 Standard your source can be however you want to type it, case-wise. I have no sympathy with those who feign eye-deficiencies when they see a couple of capital letters, and no patience with ignorant COBOL digs. \$\endgroup\$ – Bill Woodger May 7 '16 at 8:53
  • \$\begingroup\$ I didn’t know that COBOL can be lowercase nowadays, thanks for that note. Maybe my impression came because of the combination from WITH and DATA and the dot at the end of the sentence. As I said in the first sentence, I wrote down my (almost) immediate thoughts, and that was one of them, so I ’m leaving it as is. In the future, I will think twice before making such a remark. \$\endgroup\$ – Roland Illig May 7 '16 at 17:38

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.