Recursive function challenge

Question

Problem statement

Given a list of float numbers, and four operators +, -, *, / with flat preference, find the maximum value by inserting operator between each consecutive pair of numbers.

For example, given the array [1, 12, -3], the maximum number 33 can be found using 1 - 12 * (-3), since all operators have flat preference, so 1 - 12 * (-3) will be handled from left to right, first operation is 1 - 12 with value -11, and then second operation is -11 * (-3) = 33.

Common interview question

Recursive function is the most common mock interview question. I have practiced recursive function again and again to be interviewer and interviewee from March 2017 to Jan. 2018 over 150 mock interviews, I have learned so many things in the problem solving of recursive function through so many peers.

Usually the recursive function can be written in 10 minutes after a lot of practice, in my opinion. I almost make all possible mistakes in those practice, and then I start to learn where to discipline myself, and go through the rituals, which are to find base case and solve the problem only once before inductive step.

The algorithm was hard for me to figure out in the anonymous mock interview last week, since I have never worked on the exactly same algorithm before. I got a rating of 2 out 4 since major hint was given to me. The recursive function should be designed to return both maximum and minimum numbers.

The second problem is the order to design the recursive function. For example, the test case [1, 12, -3] is calculated by mistake like the following: 1 - (12 * (-3)) = 37 in my mock interview, my recursive solution breaks the constraint of flat precedence.

After mock interview

I continued to write the algorithm after mock interview and it took me extra 30 minutes, but the answer is 37 instead of 33. I reversed the order of input array, the result is still wrong. So I spent over 30 minutes to redesign the recursive function, calculate the result with 33. I learn one algorithm through the anonymous interview, and I am really grateful to have the chance to go through the learning process. This algorithm quickly becomes my favorite algorithm in the last few days, and the algorithm has not been included major discussion panel on Leetcode.com up to January 29, 2018.

Code review

The code is written in C# programming language. Please share your advice, help me to improve the solution.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace FindMaximumNumber
{
    /*
    Keyword:
    Given a list of float number, and 
    four operator: +, -, *, / arithmetic opeators, 
    insert an operator between each consecutive pair of numbers    
    Ask you to solve the problem:
    Find maximimum value -> greedy algorithm    
    Constraints:
    equal precedence order - 1 + 2 * 3 = 1 + 6 = 7 - No
                             1 + 2 * 3 = 3 * 3 = 9 - Yes
    evaluation order is from left to right 
    -> scan the float number from left to right 

    Major hint: 
    1, 12, -3, maximum number is 1 - 12 * (-3) = 33
         [1, 12]    
       /  /  \    \
     -11 13  1/12 12  -> Design the recursive with a problem 
                         include maximum and minimum value.
    */
    class Program
    {
        static void Main(string[] args)
        {
            RunTestcase();
        }        

        public static void RunTestcase()
        {
            var input = new double[] { 1, 12, -3 };

            var result = GetMaxNumber(input);
            Debug.Assert(result[0] == 33);
        }
        /// <summary>
        /// First number in the return array is the maximum value and
        /// the second one is the minimum value.  
        /// </summary>
        /// <param name="numbers"></param>
        /// <returns></returns>
        public static double[] GetMaxNumber(double[] numbers)
        {
            if (numbers == null || numbers.Length == 0)
            {
                return new double[] { };
            }

            return GetMaxNumberHelper(numbers, 1, new double[] { numbers[0], numbers[0] });
        }

        /// <summary>
        /// Recursive function is designed to fit for flat precedence, 
        /// in other words, the calculation is processed from left to right
        /// instead of right to left. 
        /// [1, 12, -3] will be handled 1 [+,-,*,/] 12 first, and then
        /// max/min [+,-,*,/] -3
        /// </summary>
        /// <param name="numbers"></param>
        /// <param name="startIndex"></param>
        /// <param name="firstKNumbers">process first K numbers first
        ///  and then apply recursive solution</param>
        /// <returns></returns>
        public static double[] GetMaxNumberHelper(double[] numbers, int startIndex, double[] firstKNumbers)
        {
            if (startIndex >= numbers.Length)
            {
                return firstKNumbers;
            }

            var length = numbers.Length;

            var visit = numbers[startIndex];

            var fourOperations = calculateFourOperations(firstKNumbers, visit);

            var current = new double[] { fourOperations.Max(), fourOperations.Min() };

            return GetMaxNumberHelper(numbers, startIndex + 1, current);
        }

        /// <summary>
        /// calculate using four operators +, -, *, /
        /// </summary>
        /// <param name="maxMin"></param>
        /// <param name="number2"></param>
        /// <returns></returns>
        private static double[] calculateFourOperations(double[] maxMin, double number2)
        {
            var addition  = maxMin[0] + number2;
            var addition2 = maxMin[1] + number2;

            var subtraction  = maxMin[0] - number2;
            var subtraction2 = maxMin[1] - number2;

            var multiplication  = maxMin[0] * number2;
            var multiplication2 = maxMin[1] * number2;

            var division  = maxMin[0] / number2;
            var division2 = maxMin[1] / number2;

            return new double[] { addition, addition2, subtraction, subtraction2, multiplication, multiplication2, division, division2 };
        }
    }
}

Answer 1

Guard clauses in GetMaxNumber

Well done for considering dodgy/edge-case input. However...

The spec you provide says nothing about what to do with a null or empty list. This is a design decision. If you can't make a design decision, then you should document the fact that you've overlooked it as clearly as possible by violently throwing an ArgumentException when either condition is reached. Returning an empty list is about as unhelpful as this could possibly be.

There are only 2 things I could possibly imagine being the 'correct' behaviour: return zero (meaningful output); or throw (violently reject the input).

Naming

• GetMaxNumber returns more than one number

• no idea what the variable name visit is meant to evoke

• firstKNumbers is really misleading: perhaps "currentMaxMin" or something? The parameter documentation is even less helpful: what is K? how do I process them? what does it meant to apply recursive solution?!

• number2 isn't terribly meaningful, rhs might be better, or even rightHandSide/Operand

Misc

• I would make the maxMin array a custom (immutable) data-type, especially given you are returning it as part of the public API. Presently you are explicitly documenting which way round they are (which is good), but an array is considerably more powerful than just a Pair, and you don't need (and aren't using) any of that power. thing.Max is much clearer than thing[0].

• The spec says nothing about returning the minimum number (granted the spec isn't especially clear)

• Is there a good reason why GetMaxNumberHelper is public? It isn't obvious what any of the arguments are without understanding the code and it doesn't have any guard clauses: hide it away.

• I would be inclined to implement this iteratively (rather than recursively), should someone decide to feed thousands of numbers into it, but that's probably not terribly important.

• length is never used in GetMaxNumberHelper

• I'd feel more comfortable passing an IReadOnlyList<double> to this API: you have no reason to modify, and are not modifying it, so give the consumer options and reassure them that you aren't going to mangle their data. (You could even rearrange it to take an IEnumerable<double> with a bit of effort)

Answer 2

This is kind of an algorithm review rather than a code review, so it should go into comments space. However, it is too long for a comment.

The problem description says the operations are performed from left to right, so all possible operations on numbers at positions 0 through N-1 should be analyzed prior to analyzing operations with argument at position N. Hence the general outline would look like:

    partialResult(numbers, N)
    {
        return partialResult(numbers, N-1) plus/minus/times/divided numbers[N];
    }

When we multiply or divide by a negative number[N], the maximum and minimum swap, so we need a partial result to contain both the possible maximum and minimum value from the subproblem. This can be achieved by returning a two-doubles structure or just by passing two reference parameters:

    void calcPartialResult(double[] numbers, int N, double& minResult, double& maxResult)
    {
        calcPartialResult(numbers, N-1, minResult, maxResult);

        double[] newResults = {
            minResult plus/minus/times/divided numbers[N],
            maxResult plus/minus/times/divided numbers[N] };

        minResult = newResults.Min();
        maxResult = newResults.Max();
    }

Of course we need to identify and handle a base case! A base case is a single number, which is itself its maximum and minimum value:

    void calcPartialResult(double[] numbers, int N, double& minResult, double& maxResult)
    {
        if(N == 0) {
            minResult = maxResult = numbers[0];
            return;
        }

        calcPartialResult(numbers, N-1, minResult, maxResult);

        double[] newResults = {
            minResult plus/minus/times/divided numbers[N],
            maxResult plus/minus/times/divided numbers[N] };

        minResult = newResults.Min();
        maxResult = newResults.Max();
    }

Finally we can use our helper:

    double GetMaxNumber(double[] numbers)
    {
        if(numbers == null || numbers.Length == 0)
            throw ArgumentException;

        double minResult, maxResult;
        calcPartialResult(numbers, numbers.Length-1, minResult, maxResult);

        return max(minResult, maxResult);
    }

Credits to @VisualMelon for throwing ArgumentException.

Answer 3

Naming Conventions

• GetMaxNumber: Since you are evaluating expressions, call it EvaluateMaximum.
• GetMaxNumberHelper: -helper is an acceptable class name, but not method name. Use an overload of EvaluateMaximum instead.
• visit: This is the name of a method in the visitor pattern. Don't use it as a variable name. Use number instead.
• maxMin: This is an ambigious name. Use span or interval instead.
• number2: Unnecessary postfix. Use number instead.
• numbers.Length == 0: I would prefer !numbers.Any().
• calculateFourOperations: Don't camelcase method names. CalculateFourOperations

---

Guard Conditions

If numbers is null, the specification is not met, so throw a ArgumentNullException. If it has no elements, I would opt for returning the pair new[] { double.NaN, double.NaN }. You are letting the caller know the evaluation could not be performed on their input.

if (numbers == null || numbers.Length == 0)
{
    return new double[] { };
}

if (numbers == null)
    throw new ArgumentNullException(nameof(numbers));
if (!numbers.Any())
{
    return new [] { double.NaN, double.NaN };
}

I am also missing overflow and divide by zero handling in your expressions.

var division  = maxMin[0] / number2;  // <- what if number2 is 0?

---

Recursion

Using startIndex and incrementing it, seems more like a code smell to me. It's more of a hidden loop than recursion.

 public static double[] GetMaxNumberHelper(double[] numbers, int startIndex, ..)
 {
     // .. startIndex + 1
 }

---

Expressions

You could specify your expressions (addition, subtraction, multiplication, division) as a seperate method. CalculateFourOperations could then call these expressions on its input. The advantage is two-fold:

• reuse existing expression more than once
• overflow, divide by zero checks can be executed on a single expression

 private static double[] calculateFourOperations(double[] maxMin, double number2)
 {
      var addition  = maxMin[0] + number2;
      var addition2 = maxMin[1] + number2;
      // ..
 }

---

Proposed Solution

I present an alternative solution for evaluating these expressions. My steps are described bottom-up.

A new struct Span stores the Min and Max value pairs. This way we can avoid double[] for these pairs.

 public struct Span
 {
      public double Min { get; }
      public double Max { get; }
      public Span(double min, double max)
      {
          Min = min;
          Max = max;
      }
      public static Span NaN => new Span(double.NaN, double.NaN);
      public static Span Zero => new Span(0d, 0d);
      // .. hashcode, equals, tostring ..
 }

Evaluating an expression handles overflow and divide by zero. I have decided to use double.NaN when these errors occur. Later on, I ignore these values and continue the flow with the other values. This is a design decision. The sytax I use is an IIFE (known in the javascript world). This helps with the stacktrace when the try-catch clause is inside the outer function.

  private static double EvaluateExpression(Func<double> expression)
  {
        return (new Func<double>(() =>
        {
            try
            {
                return expression();
            }
            catch
            {
                return double.NaN;
            }
        }
        ))();
  }

Now we can evaluate all of our expressions against an input and the next number.

private static Span EvaluateSpan(double current, double number)
{
      var evaluations = new Func<double>[] {
            () => current + number,
            () => current - number,
            () => current * number,
            () => current / number
      }.Select(e => EvaluateExpression(e)).Where(n => !double.IsNaN(n));
      return new Span(evaluations.Min(), evaluations.Max());
}

The next step is to perform the evaluations on both branches of the current Min and Max. A Queue is an ideal collection for this kind operation. We then calculate the new current based on both branches.

private static Span EvaluateSpan(Span current, Queue<double> numbers)
{
     if (!numbers.Any())
         return current;
     var number = numbers.Dequeue();
     var s1 = EvaluateSpan(current.Min, number);
     var s2 = EvaluateSpan(current.Max, number);
     current = new Span(Math.Min(s1.Min, s2.Min), Math.Max(s1.Max, s2.Max));
     return EvaluateSpan(current, numbers);
}

All our helper methods have been created. The public API contains a method to get the caller the Span and two overloads: one for Max and one for Min.

public static Span EvaluateSpan(IEnumerable<double> numbers)
{
      if (numbers == null)
          throw new ArgumentNullException(nameof(numbers));
      var queue = new Queue<double>(numbers);
      if (!queue.Any())
          return Span.NaN;
      var number = queue.Dequeue();
      var current = new Span(number, number);
      return EvaluateSpan(current, queue);
}

public static double EvaluateMaximum(IEnumerable<double> numbers)
{
      return EvaluateSpan(numbers).Max;
}

public static double EvaluateMinimum(IEnumerable<double> numbers)
{
      return EvaluateSpan(numbers).Min;
}

---

Test Scenario

 [TestMethod]
 public void RunTestcase()
 {
      var input = new double[] { 1, 12, -3 };

      Assert.AreEqual(33, EvaluateMaximum(input));
 }