15Sep

Interview Question

Posted by Elf Sternberg as Uncategorized

I won’t reveal where or when I got this question, but it always amused me.  At the time, I answered it using Underscore and Coffeescript, which the interviewers allowed I was going to have access to… but here’s a pure ES6 solution.

The problem, simply stated, was “write a function that sums two polynomial equations and prints the results.”  They defined the format for the input this way:

// 5x^4 + 4x^2 + 7 
// 3x^2 + 9x - 7
var e1 = [{x: 4, c: 5}, {x: 2, c: 4}, {x: 0, c: 7}];
var e2 = [{x: 2, c: 3}, {x: 1, c: 9}, {x: 0, c: -7}];

They were kind enough to let me code on my keyboard.  My answer is rather dramatic.

// Reduce any list of equations into an array of maps of exponent:coefficient
var eqns = [e1, e2].map((a) => a.reduce((m, t) => { m[t.x] = t.c; return m; }, new Object(null)));

// Find the largest exponent among all the equations
var maxe = Math.max.apply(null, eqns.map((a) => Math.max.apply(null, Object.keys(a))));

// For the range (maxe ... 0), for all equations, sum all the coefficients of that exponent, 
// filter out the zeros, sort highest to lowest, create string representations, and print.
console.log(
        Array.from(new Array(maxe + 1), (x,i) => i)
        .map((exp) => [exp, eqns.reduce(((memo, eqn) => memo + (eqn.hasOwnProperty(exp) ? eqn[exp] : 0)), 0)])
        .filter((e) => e[1] != 0)
        .sort((e) => e[0])
        .map((e) => e[1] + (e[0] > 1 ? 'x^' + e[0] : (e[0] == 1 ? 'x' : '')))
        .join(' + '));

The interviewer just stared at it, and stared at it, and said, “I’ve never seen anyone solve that in three lines.  Or that fast.”

I shrugged.  “It’s a straightforward map/reduce of the relationship between exponents and coefficients, removing any factors that had a coefficient of zero.  This seemed the least buggy way to do it.  The riskiest part of this equation is the mapping back to string representation.  The nice feature of this function is that if we generalize the first line over an arguments array, it works for any number of equations, not just two.”

He agreed.  They ultimately didn’t hire me.  I had a friend there, and he said, “They really liked you, but it was pretty clear you were already bored where you were and moving from one infrastructure job to another wasn’t going to change that.”  Sad but true.

 

Comment Form

Subscribe to Feed

Categories

Calendar

September 2015
M T W T F S S
« Aug   Jan »
 123456
78910111213
14151617181920
21222324252627
282930