8
\$\begingroup\$

I had an half an hour interview with Microsoft for an intern position. I was asked to generate a list of alternatively positioned odd and even number out of an array of unsorted integers. I guess it was below the interviewer expectations since I did not get the offer. Can any one give me some hints on improving my code?

import java.util.ArrayList;


public class EvenOddArray {

private int min(int n, int m)
{
    int min;
    if (n > m){
        min = m;
    }
    else {
        min = n;
    }
    return min;
}


public ArrayList<Integer> generateEvenOddArray(int[] list)
{
    ArrayList<Integer> oddList = new ArrayList<Integer>();
    ArrayList<Integer> evenList = new ArrayList<Integer>();
    ArrayList<Integer> resultList = new ArrayList<Integer>();

    for (int number : list) {
        if (number%2 == 0){
            evenList.add(number);
        }
        else {
            oddList.add(number);
        }

    }


    int numberOfEvenNumbers = evenList.size();
    int numberOfOddNumbers = oddList.size();
    int minOfOddAndEven = min(numberOfEvenNumbers,numberOfOddNumbers);
    ArrayList<Integer> longestList = getLongestList(evenList,oddList);

    int i ;
    for (i = 0; i < minOfOddAndEven; i++) {
        resultList.add(2*i,oddList.get(i) );
        resultList.add(2*i+1,evenList.get(i));          
    }
    if(longestList != null ){
        for (int j = i; j < longestList.size(); j++) {
            resultList.add(longestList.get(j));
        }
    }
    return resultList;


}
private ArrayList<Integer> getLongestList(ArrayList<Integer> listone,
        ArrayList<Integer> listTwo) {
    if (listone.size()<listTwo.size()){
        return listTwo;
    }
    else if (listone.size()>listTwo.size()){
        return listone;
    }
    return null;
}
\$\endgroup\$
4
  • \$\begingroup\$ in your min(int, int) method, what if n = m? Then neither is the min. \$\endgroup\$
    – Max
    Nov 18 '13 at 8:26
  • \$\begingroup\$ @user1021726 If n == m then both are the min, and therefor it does not matter which one gets returned. \$\endgroup\$ Nov 18 '13 at 13:06
  • 1
    \$\begingroup\$ @Andre, right now, I believe 0 would be returned instead of m or n. \$\endgroup\$
    – konijn
    Nov 18 '13 at 21:08
  • 1
    \$\begingroup\$ - Does the given array contain duplicate elements or only unique values? - Resultant array would be sorted or unsorted ? \$\endgroup\$
    – Ravi Kumar
    Nov 19 '13 at 3:43
10
\$\begingroup\$
  1. You probably should have used Math.min(). Even if it was requested by the interviewer to not use anything else besides ArrayList, min can be written much more concise as

    return n <= m ? n : m
    

    (1 line of code vs. 8)

  2. This loop is little bit ugly:

      for (i = 0; i < minOfOddAndEven; i++) {
        resultList.add(2*i,oddList.get(i) );
        resultList.add(2*i+1,evenList.get(i));          
    }
    

    While I think it should work (don't have a Java compiler handy to try) it's a bit confusing to add the numbers at specified indices. I think it is legal to call add(index, item) where index == size() which should add an element to the end of the list. So your code happens to work but you need to look twice to make sure. It's totally unnecessary to do this. You could have simply done:

    for (i = 0; i < minOfOddAndEven; i++) {
        resultList.add(oddList.get(i));
        resultList.add(evenList.get(i));          
    }
    

    Same result but cleaner.

  3. Copying the remainder of the list could have been done with subList:

    if (longestList != null)
    {
        resultList.addAll(longestList.subList(minOfOddAndEven, longestList.size());
    }
    
  4. Overall I think the interviewer might have wanted to see the use of iterators. You could have greatly simplified your code with this:

    Iterator<Integer> odds = oddList.iterator();
    Iterator<Integer> evens = evenList.iterator();
    
    while (odds.hasNext() || evens.hasNext())
    {
         if (odds.hasNext())
         {
             resultList.Add(odds.next());
         }
         if (evens.hasNext())
         {
             resultList.Add(evens.next());
         }
    }
    

    This way you iterate over both lists at once and don't have to implement the "which list is longer and then copy the remainder part"

\$\endgroup\$
1
\$\begingroup\$

<!Joke> You didn't get the job because you were using Java in Microsoft :P </Joke>

Now the serious part...

  • First thing to keep in mind when you are writing a production code or any code that would be reviewed by someone else, keep it precise and well documented. I mean, on seeing the below code someone have to make a stack in his head how it is working

    int i ;
    for (i = 0; i < minOfOddAndEven; i++) {
        resultList.add(2*i,oddList.get(i) );   // why 2*i ?
        resultList.add(2*i+1,evenList.get(i)); // why 2*i+1 ?         
    }
    if(longestList != null ){
        for (int j = i; j < longestList.size(); j++) { // why starting form i ?
            resultList.add(longestList.get(j));
        }
    }
    

    See what was I talking about. Throw some comment why are you doing this. Also a good Javadoc will fulfil the cause.

  • getLongestList can be shorten as

    return listone.size() > listTwo.size() ? listone : listTwo;
    

    though I prefer firstList instead of listone and secondList instead of listTwo. I don't know why are you returning null, if two lists are same listTwo will be returned and that won't hamper the logic.

  • You should know polymorphism is a vital part of OOP language so instead of

    ArrayList<Integer> oddList = new ArrayList<Integer>();
    

    use

    List<Integer> oddList = new ArrayList<Integer>();
    
  • Creating the evenList and oddList should be done in a helper method.

  • I don't know why I feel like you should provide a constructor to the class. A constructor with parameter as the array.

  • Lots of redundant newline makes the code bigger than the original. Get rid of those.


Algorithm wise optimization

With your algorithm

Space Complexity

O(n) [ for the array []list ]

+

O(n/2) [ for oddList in average case ]

+

O(n/2) [ for evenList in average case ]

+

O(n) [ for resultList ]

+

O(n/2) [ for longestList in average case ]

Time Complexity

O(n) [ for generating oddList and evenList ]

+

O(n) [ for generating resultList ]

Now you can optimize it with partitioning algorithm. Then create the resultList with alternate indexing odd and even numbers. "A picture is worth a thousand words"...

enter image description here

With optimized algorithm

Space complexity

O(n) [ for the array list ]

+

O(1) [ for swapping ]

+

O(n) [ for resultList ]

Time Complexity

O(n) [ partitioning ]

+

O(n) [ generating resultList ]


As a last note. I think you should contact your interviewer and ask why didn't he like your code politely. If he is a good interviewer he will definitely contact you back, if he doesn't don't worry at least you tried.

Good luck!

\$\endgroup\$

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.