Log in

No account? Create an account
entries friends calendar profile Elf Sternberg's Pendorwright Projects Previous Previous Next Next
Interview Question - Elf M. Sternberg
Interview Question

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.
        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.


Leave a comment