Algorithm, Performance and Back to the Basic

I have had some chances to interview people for a Sr. software engineer position.  Sometimes, people don't remember what they learned at a college after working for companies more than 10 years.  I understand all situations and excuses because I may be same.

So, I chose a easier problem and wanted to see how they approach the problem within the first 10 minutes out of 50 minutes given to me.  OK. I got this question from a HackerRank.com, and it was a problem for 15 points, which means a easy problem.

Basically, question is about finding a minimum absolute difference between any two numbers in a array with a size 'n'.  Surprisingly enough, I didn't have any interesting discussion with candidates.  I will talk about very basic algorithm and efficiency here and continue my talk on a Lambda expression or functional programming on the next post.

- Brute-Force Approach
Most developers regardless of their job title can solve the problem using a nested two for loop without even thinking about much.

public int findMinAbsDifferenceLoop(int[] numbers) {
   int min = Integer.MAX_VALUE;
   for(int i=0; i<numbers.length; i++){
      for(int j=i+1; j<numbers.length; j++){
         int diff = Math.abs((numbers[i] - numbers[j]));

         if(min > diff){
            min = diff; 
         }
      }
   }
   return min;
}

Any problem with this simple solution if your interest is simply getting an answer?

Then, what is the big O notation of this algorithm?  Simply O(n^2)!!  What does it mean? As a number of data in the array grows, this execution time grows as fast as a graph of a square of x grows.

- Improvement after a Little Thinking.
Since we need to compare every each two numbers, the previous approach with two loops might be necessary.  But what if the numbers in the array were sorted? Do we still need to compare the first number with the second, third, and fourth number to find a minimum difference? No! Right?

public int findMinAbsDifferenceSorted(int[] numbers) {
   int min = Integer.MAX_VALUE;
   for(int i=1; i<numbers.length; i++){
      int diff = numbers[i] - numbers[i-1];
      if(diff < min){
         min = diff;
      }
   }
   return min;
}

This logic? Simply O(n)!!
What about the expense of the sorting??  Yes, Yes, Yes...!! We should have talked about it even if you were not a software engineer!

There are many different sorting algorithms and each algorithm has a best, a worst, and an average case as shown on this wiki page.  Nevertheless, most people will not have a problem with saying an average of O(n log n).

public int findMinAbsDifferenceSorted(int[] numbers) {
   Arrays.sort(numbers);
   int min = Integer.MAX_VALUE;
   for(int i=1; i<numbers.length; i++){
      int diff = numbers[i] - numbers[i-1];
      if(diff < min){
         min = diff;
      }
   }
   return min;
}

So, this logic has O(n log n) + O(n) --> O(n log n)!

- Execution Time
I created random numbers and this is the execution time on my mac book pro with a processor 2.3 GHz Intel Core i7.

X-axis indicates a number of data in the array starting from 10,000 to 100,000 incremented by 2,000. Y-axis indicates an execution time in millisecond.  Execution time for 100,000 data with the double for loop was 12,627 millisecond, but one with the Sorted data was 6 millisecond.  As you see, the execution time with the sorted data is almost flat on this graph.

I am not patient enough to run more number of data using the inner for loop.  This is execution time for the sorted data, size from 100,000 to 1,000,000 incremented by 20,000.  Although, there are some fluctuated execution time, it took only 78 millisecond to calculate the min difference with 1 million numbers.

Summary
Some people try to solve this problem with O(n) algorithm.  Great! But I will not talk about a better algorithm, because my purpose of this post is asking people to think about the basic and to provide you some refreshment before I talk about the functional programming on the next post.