Don’t Be A BRUTE, Be GREEDY!

Leave a reply

Recently I was conducting a few interviews for my company. I was generally impressed with the  candidates and their abilities to “think on their feet.”

One of the things that I like to explore during the interview is how the candidate handles improving on a “brute force” solution. In general I think its good if you come up with a solution that works and then go back and discuss with the interviewer how you might improve the solution to make it more efficient for time and space.

Normally it doesn’t matter so much because even the most basic PC’s these days have very fast processors and you probably aren’t dealing with enormous sets of data. Nevertheless it’s an interesting exercise to challenge yourself to see if you can improve your code and get the max efficiency out of your logic.

Oh No!

As a quick refresher “computer scientists” express the efficiency of an algorithm using “Big O” notation. Its an easy way to describe how many passes an algorithm might have to iterate over a set/list/array etc . . .

Key points to know about Big O

  1. Know the order of best to worse:  O(1), O(n), O(log n), O(n^2), O(2^n)
  2. Drop Constants –  ex if you are looping through a list 4 times it’s still basically O(n)

One technique that I find useful for eliminating unnecessary loops is a “greedy” algorithm.

What’s really cool is that it can sometimes be used to turn a nested loop algorithm O(n^2) into a single loop solution. i.e. a single pass through the list O(n).

For large lists of data the efficiency difference between an O(n) solution and an O(n^2) can be huge!

So Whats the Problem?

The main value in the “greedy” approach is that you can get an answer efficiently by iterating through a list of data once. I have boiled down the main concepts to these:

  1. Initialize your “test”, “target” and your “so far” variables outside the loop.
  2. Evaluate your “test” value using the current “so far” in the beginning of the loop.
  3. Evaluate your “target” using the “test” and the “so far” values.
  4. Re-assign your “so far” value at the end of the loop.

To illustrate the technique assume you have an array of positive numbers and you want to determine what is the max difference between two of the numbers. Additionally, the max difference must be between two numbers where the index of the first number in the equation is greater than the index of the second. (i.e. You’re not allowed to sort the array)

Sample input array of numbers :  { 13, 18, 1, 6, 2, 9 }

The answer for max (sequential) difference would be: 8
index [5]  – index[2] = 8   // Where index[5] = 9 and index[2] = 1

You probably did this “in your head” by scanning the list, recognizing that the number “1” was the smallest number and then you saw that “9” was the greatest number afterwards.

You were doing the greedy method intuitively! Isn’t the brain amazing?

Approach Cautiously with Brute Force

When tackling this kind of question in an interview you should strive to solve it straightforwardly and then look to see how you can improve on it.

This is what people call the “brute force” method. It just gets it done correctly even if it ends up doing a lot of extra work.

public int GetMaxSeqDiff(int[] nums)
{
    int maxdiff = 0;

    // Go through every number from first to last
    for (int i = 0; i < nums.Length; i++)
    {
        // get a number
        int currentVal = nums[i];

        // And get diffs with all the FOLLOWING numbers
        for (int y = i + 1; y < nums.Length; y++)
        {
            int otherVal = nums[y];

            // See what diff would be 
            int testDiff = otherVal - currentVal;

            // see if testDiff is the MAX diff and then capture it
            maxDiff = Math.Max(maxDiff, testDiff);
        }
    }

    return maxDiff;
}

This definitely works, but as soon as you see nested loops ( On^2) you should take another look and see if its possible to eliminate the inner loop.

It’s So Nice To Be GREEDY!

Think back to how you solved this when figuring it out just looking at it. A key to the strategy was that you scanned the list quickly and found that the number “1” (index[2]) was the smallest number in the list. Once you identified the smallest number you knew you had one piece of the equation.

Algorithm: Max Sequential Diff = max number(with index > index of min number)  – min number

The min number is a great example of what I call the “so far” number. What I mean is as you traverse the list and examine each number you store what the min number is “so far.”

public static int GetMaxSeqDiff(int[] nums)
{
   // Default your "So Far", "Test" and "Target" vals
   int minNumSoFar = nums[0]; // The first num is the min num "so far"  
   int maxDiff = nums[1] - minNumSoFar; // Default your target/return val 
   int testDiff = 0;
            
   // You can start the loop from 1 since you already
   // have set minValueSoFar to nums[0] 
   for(int i = 1; i < nums.Length; i++)
   {
      // Greedy Step 1 = Get your test val 
      // in the BEGINNING of the LOOP  
      testDiff = nums[i] - minNumSoFar;
      
      // Greedy Step 2 = Test for your target result
      maxDiff = Math.Max(maxDiff, testDiff);
                
      // Greedy Step 3 = THE KEY STEP !!!!
      // Update your "So Far" AT THE END of the LOOP
      minNumSoFar = Math.Min(nums[i], minNumSoFar);
   }
   return maxDiff;
}

Pretty cool, right? One Loop!

Have fun and keep coding!

Leave a Reply