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 };
        }
    }
}
  • After I posted the question here, I also learn the algorithm every day by asking 5 times in the anonymous mock interview as an interviewer last 8 days. I like to share three more version of code, and share my learning of the algorithm and how to make one really good algorithm for mock interview. One is brute force solution, hard to write; One is the optimal solution with time complexity O(n), n is number of operator, easy to write. This recursive solution has some issues and needs memoization, dynamic programming perfectly cache the result and solve the problem quick and perfect. – Jianmin Chen Feb 7 at 18:35
  • On Feb. 1, the interviewee wrote a recursive with very good structure to fit for flat preferecence, with issue to deal with minimum subproblem. gist.github.com/jianminchen/ce4f7422862704bd6dc278c451fd6346 – Jianmin Chen Feb 7 at 18:37
  • On Feb. 6, 2018, I gave to another developer, he chose to write dynamic programming solution. And each step there are 4 possible solution, with 4 possible operators, there are 16 cases to write. So after the complaint from the previous mock interview, I decided to give the hint right away, lead the interviewee to the optimal solution, to keep maximum and minimum only. The optimal solution time complexity is O(n). The python code is easy to follow: gist.github.com/jianminchen/f3d6e68002b4d5b35c87439a7c88d734 – Jianmin Chen Feb 7 at 18:40
  • On Feb. 5, the interviewee wrote a brute force solution with production ready code in mock interview in less than 30 minutes. Here is the code of brute force I rewrote based on his code. The time complexity is O(N^4). gist.github.com/jianminchen/dc6b840cd325dc75e2703547bbed3720 But the interviewee complained that the interviewer should lead the interviewee to the optimal solution. I tried to learn the brute force solution and I did not know the optimal solution using dynamic programming. I like the brute force solution most and it is very hard to write in less than 30 minutes. – Jianmin Chen Feb 7 at 18:55
  • I gave the algorithm to 9 people so far in mock interview as an interviewer before Feb.15 2018, and then last two of them gave me very good feedback. The optimal solution is to understand that there are too many intermediate results, and the subproblems to get maximum value should also include finding minimum value algorithm. In my words to give out the hint, just take risk to keep maximum and minimum value, later after mock interview you can prove that in theory of math, it is true that maximum value can be generated using those two values each intermediate steps. – Jianmin Chen Feb 19 at 19:26
up vote 5 down vote accepted

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)

  • Excellent code review. I really appreciated your contribution. – Jianmin Chen Jan 31 at 4:03
  • Can you tell me your most favorite recursive algorithm? Why do you like the algorithm and make it your favorite? – Jianmin Chen Jan 31 at 5:24
  • 1
    I couldn't say; I don't spend much time with different algorithms! (I mostly just apply heuristic search to everything: coming up with heuristics is always good fun) – VisualMelon Jan 31 at 10:47

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.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.