6
\$\begingroup\$

I did this code for an interview. Can you tell me how it looks? I didn't get the job, so I'm wondering what I could do better in my code.

/**
 * TASK 1: IMPLEMENT: C - binomial coefficient
 *
 * C(n,k) = n! / [ k! (n - k)! ]
 * Where x! is the factorial of x  
 *
 * Use a recursive solution. If needed, you can implement helper functions.
 */

function C(n,k) {
    "use strict";

/**
 * ~~OMID~~
 * The code is not linted, or refactored on purpose.
 * Tested with node 0.10.32. 
 */

/**
 * factorial() returns the factorial 
 * of any none-negative number.
 * @param {integer}
 */ 
    function factorial(number) {

        var result = 1; 

        if(number < 0){
          return; 
        } else if (number <= 1) {
          return  result;
        }
        else {
          result = number * factorial(number-1);
        }
        return result; 
      } 
    // Testing numerality of parameteres, n and k  
    if(isNaN(parseFloat(n)) && isFinite(n) && isNaN(parseFloat(n)) && isFinite(n)) {
        return;
    }
    else {
/**
 * Implementing the formula. 
 * C(n,k) = n! / [ k! (n - k)! ]
 */
      return  (factorial(n)/factorial(k)*factorial(n-k));
    }
}

/**
 * TASK 2: IMPLEMENT: Tests for function C
 *
 * Write a set of tests, that validate your binomial coefficient function.
 * Write as many test cases as you feel is needed.
 */

(function testBinomialCoefficient() {

    var tests = {

        example: function() {
            var pass = typeof C === "function";
            return {
                success: pass,
                message: (!pass) ? 'Expected C to be a function' : ''
            };
        },
                normalInteger: function() {
                        var pass = C(5, 4) === 5;
                        return {
                                success: pass,
                                message: (!pass) ? 'C(5,4) Should be equal to 5': ' '
                        };

                },
                negativeInput: function() {
                        var pass = isNaN(C(-5, 4));
                        return {
                                success: pass,
                                message: (!pass) ? 'Negative input must result in NaN': ' '
                        };

                },
                smallerSecondParam: function() {
                        var pass = isNaN(C(10, 19));
                        return {
                                success: pass,
                                message: (!pass) ? 'Second parameter should be smaller': ' '
                        };

                },
    };

    //  ---- You shouldn't change the code below this line  ----

    for (var test in tests) {
        var result = tests[test].apply(undefined);
        if (result.success) {
            console.log("Passed: " + test);
        } else {
            console.log("Failed: " + test + ", Message: " + result.message);
        }
    }

    //  ---- You shouldn't change the code over this line  ----

})();
\$\endgroup\$
  • \$\begingroup\$ If you are not going to use big integers, you might as well replace the factorial function by an array, because 21! is already too big to fit in a 64 bit integer. The interviewer should be made aware that his arbitrary requirement makes the solution very far from optimal :) \$\endgroup\$ – b0fh Mar 15 '16 at 10:17
5
\$\begingroup\$

The code demonstrates some nice effort towards writing good code, so a professional mindset. However, it does have issues, which I'll explain below.

1. Testing input arguments

I believe that you could have done without that, as the point of the exercise is not to check the parameters, but rather to calculate properly the binomial coefficient.

Anyway, your test condition isNaN(parseFloat(n)) && isFinite(n) && isNaN(parseFloat(n)) && isFinite(n) has issues. Firstly, it only tests the value n, and not the value k (this is a typo, but your following tests have not found it, meaning your tests are incomplete). Secondly, you do not check for positive integers. Thirdly, you convert the variables into numbers (fine), but still use the original values thereafter. Finally, if the test fails, then you should probably do something more than return undefined (and document that behavior as well).

2. The factorial function

Your inputs have been checked already, so I think that you should keep this function as simple as possible, e.g.

function factorial(n) {
  if (n <= 1) {
    return 1;
  }
  return n * factorial (n - 1);  
}

... or using the ternary operator (less readable in a recursive algorithm, but some people prefer that form), e.g.

function factorial(n) {
   return n <= 1 ? 1 : n * factorial (n - 1);  
}

3. The algorithm

This is where, I believe, lies the real point of the exercise. The provided formula C(n,k) = n! / [ k! (n - k)! ], if implemented "as is", has duplications. After all, n! contains both k! and (n - k)!, so you'd be calculating k! or (n - k)! twice, which can be quite expensive. You should therefore remove one of them from n! (the most expensive one), depending on k being superior or inferior to n / 2.

4. The tests

The test named "example" should be removed. Either C is a function, and the following tests are enough, or it is not, and their subsequent execution will lead to a runtime error anyway.

The message property is intended as the name of the test, so there is no need to check the value of the pass variable - and so, there's no need for that variable either.

Finally, I believe that the statement tests[test].apply(undefined) was provided to you by the company. This is... not pretty, and quite unnecessary.

\$\endgroup\$
4
\$\begingroup\$

Some notes on function factorial(number):

var result = 1; // not needed

if (number < 0)
    return; // return Number.NaN

else if (number <= 1) // no need for 'else'
    return  result; // simply return 1

else // no need for 'else'
    result = number * factorial(number-1); // replace 'result =' with 'return'

return result; // not needed

A more efficient implementation of function C(n,k):

var result = 1;
if (k > n-k)
    k = n-k;
for (var i=0; i<k; i++)
{
    result *= n-i;
    result /= 1+i;
}
return result;
\$\endgroup\$
  • \$\begingroup\$ the task specifically said: Use a recursive solution. I agree with your comments on the original version though. \$\endgroup\$ – tim Mar 18 '15 at 20:26

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.