Hacker News Reader

Comment by reagan83 | Hacker News Reader

Cletus - I had never coded (or even thought) of this problem before, but your post intrigued me enough to try it out.

I put something out in Java in about 20 minutes and 50 lines using a PT class, a newRow() method that swaps the current row with the previous row and sets up the new current off of the previous (prev[element] + prev[element -1]), and a printRow() method.

My solution works well, but I'm curious how you would assess this solution during an interview. Would my language choice be a pro/con? What is the avg time you see it take an interviewee to complete this problem and how many LOC is it usually accomplished in under the pressure of an interview?

View on HN

This kind of problem has really short solutions when you have access to collection-at-a-time operations. For example, in Haskell:

    pascal 1 = [1]
    pascal i = zipWith (+) ([0] ++ pascal (i - 1)) (pascal (i - 1) ++ [0])

I'm not answering your question but just wanted to pique your interest in this because you were asking about language choice and had mentioned that your solution took 50 lines.

The above solution expresses the recursive solution as the sum of two earlier rows after appending some zeros. There is very little room for errors to hide and it provides you with a kind of 'definitional' starting point to begin optimizing if you want.

Beginner Haskell Solution:

pascal 1 = [1]

pascal 2 = [1,1]

pascal n = [1] ++ sum' (pascal (n - 1))

sum' [] = []

sum' [1] = [1]

sum' (x:xs) = [x + head' xs] ++ sum' xs

head' [] = 0

head' xs = head xs

1) When you're writing a function on integers or lists using explicit recursion, usually there's need for only one base case. Do you really need a separate definition for pascal 2? What about sum' [1]?

2) Often it's better to use fold instead of explicit recursion. If you wonder whether you can rewrite your function in terms of fold...

"A tutorial on the universality and expressiveness of fold" http://www.cs.nott.ac.uk/~gmh/fold.pdf

Your solution is less important than your process for getting there. The interviewer wants to determine how you think about problem solving. He wants to make sure that you do not just hack at the code until it seems to work. The amount of time required is generally not important unless it becomes excessive. For a problem like this 10 to 15 minutes is probably reasonable, 30 minutes might be a red flag and 45 minutes might end the interview (these times are very rough estimates and might be longer depending on the amount of discussion that takes place). Once a working solution is developed it is common (in general, I do not work at Google) to ask an applicant how they might improve or optimize it without actually having them do the additional work.

Reply on news.ycombinator.com