Pascal’s Triangle And The Developer Interview
I’ve been grateful for the many problem submissions to the Typescript Programming Test Problems repo. It’s been a fun exercise and hopefully useful to new programmers as well as veterans interested in Typescript. Some of the problems come with a story and the story associated with the problem discussed in this post seems to be all too common. Since I just finished watching one of the original Twilight Zone episodes, allow me to assume my best Rod Serling imitation (programmer and company name are not real).
Consider the case of Katie, a ReactJS programmer who applied for a junior programmer job at company XYZ in Somewhere, USA. Katie had several React projects online, one of which was in Typescript, a relatively new language for her. During her phone interview, Katie was asked about React component life cycle, general programming concepts, and other things such as version control.
To her delight, Katie was invited for an on-site interview. After arriving, she was ushered to a conference room with a large white board. Several other developers came into the room and sat at one end of the table. One of the developers went to the board, and wrote a sequence of numbers,
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1
Katie was then asked to write the pseudocode to compute the n-th row in this progression. Katie was not very strong in math and asked what this had to do with React or the position. She was told in a very stern voice that she would not be able to move forward in consideration for the position without coding the solution to this problem. Katie did not receive an offer.
So, now Pascal’s Triangle is a programming test problem? I did look at her React portfolio and although my ReactJS is quite rusty, my belief is that Company XYZ lost out on a good junior programmer that would likely have been a very good long-term choice for them. All for the sake of developer ego and naivety.
Before I discuss the solution and my specific Typescript implementation, I suppose it’s natural to ask if I would have used this problem and if so, how would I have conducted the same interview. I bring this up since I’ve been involved in over a hundred developer interviews during my career and admit that a conducting a good interview is a constant learning process.
Since Katie is a junior developer, I’d be interested in the following during the course of a face-to-face interview.
– How much mentoring is Katie likely to need for tasks outside her direct experience?
– Can Katie help in brainstorming solutions to problems presented to our group?
– Does Katie grasp life-cycle concepts and how to implement solutions in an environment where multiple devs are working on a project?
– How well does Katie seem to ‘fit’ with the group?
If I have nothing else to work with (i.e. I know someone who worked with Katie or a detailed discussion with references), then I tend to prefer a combination of discussion problems and pair programming exercises for junior and intermediate-level positions. So, I might approach the interview as a simulation of our actual work environment where a customer presented a change request that requires Katie and myself to collaborate on solving the Pascal’s triangle problem. If there is interest, I might do another post on the sequence of questions I would ask and what I’m looking for in the answer and discussion resulting from each question. The bottom line is that there is no ‘me vs. Katie or us vs. the candidate vibe.’ I want to see how a junior person performs in a collaborative exercise since that is the exact environment in which they would be expected to work.
In the mean time, here is my solution to the Pascal’s triangle problem. My first attempt at this problem was in a computational geometry class in the 1980’s. I had to compute the n-th row to obtain the binomial coefficients needed to implement a n-th order Bezier curve. While we may deduce the forward recursion that allows row n to be generated from row n-1, it helps to have a proof that such a relationship always holds. Suppose we know nothing other than the arrangement of numbers, as presented. If we take it as axiomatic that each row begins and ends with a 1, then it is possible to create a proof by induction that the forward recurrence relation holds.
It helps, of course, to understand exactly what numbers comprise Pascal’s triangle, namely binomial coefficients. If (n k) represents the k-th element in the n-th row, then (n k) = n! / k!(n-k)! . This is the number of combinations of n items taken k at a time. The individual numbers in a row are coefficients in the expansion of (x+y)n.
Since 0! = 1! = 1, all rows begin and end with a one, by definition. Proof of the forward recurrence (sometimes called Pascal’s rule) can be found elsewhere but is included here for completeness:
Show that (n k) = (n-1 k-1) + (n-1 k)
(n-1 k-1) = (n-1)! / (k-1)!(n-1-(k-1))! = (n-1)! / (k-1)!(n-k)!
(n-1 k) = (n-1)! / k!(n-1-k)!
Multiply the first expression by (k/k) and the second by (n-k)/(n-k)
(n-1 k-1) + (n-1 k) = (n-1)![k + (n-k) / k!(n-k)!] = [n(n-1)!] / [k!(n-k)!] = n! / k!(n-k)! = (n k)
for k in the closed interval [1,n-1]
This shows that the forward recurrence (i.e. computing row n from row n-1) holds. For convenience, we can hardcode the return for n = 0, 1, and 2 and then use Pascal’s rule for successive rows. The symmetry relationship follows directly from the definition of binomial coefficients, i.e. (n k) = (n n-k) for appropriate k.
This is essentially what I coded in Fortran in a first-semester computational geometry course.
In the early 2000’s, I had a business application that required frequent sampling of binomial coefficients for varying values of n and k. I modified the algorithm to cache the most recently computed row and then recurse forward from the beginning or the most recently computed row. If the next-requested value of n is the same as the cached version, then the appropriate coefficient can be returned from the cached row.
What is not generally seen in most discussions of Pascal’s triangle is that it is possible to recurse backwards, i.e. compute row n-1 from row n. The expression is
(n k) = (n+1 k) – (n k-1) and the corresponding code is easier if the leading 1 is maintained in the cached half-row.
To prove, expand the terms on the right-hand side of the equation and then multiply the second one by k/k. Then, factor out n! There should be an (n+1-k) term that cancels in numerator and denominator. I’m kind of skimming over this since I know most people will not be interested in this level of detail.
This leads to a very interesting algorithm where the recursion may be implemented from an initial row (2, for example) forward or from the currently cached row forward or backwards. This is the idea behind the Actionscript code I wrote way back in the day that was subsequently ported to JS and is now in the Typescript Math Toolkit.
You may deconstruct the implementation from the shared folder in the Typescript Programming Test Problems repo.
Enjoy, and the next time you are asked this problem in a programming test, ask the interviewer if they even know what those numbers are