Hacker News Reader

Comment by fragsworth | Hacker News Reader

I didn't prefix or append 1 to each row, like you did. Instead I added the edges of the previous row as special conditions and this caused a lot of trouble.

Realizing and taking advantage of this property of Pascal's Triangle significantly simplifies the problem. I guess it should be obvious, but I didn't consider using it. I don't think it's because I'm stupid (though I might be, I'm not sure) - I think it's because these kinds of problems are far removed from what I work on day-to-day.

View on HN

>these kinds of problems are far removed from what I work on day-to-day.

Exactly! The OP says he "clarified" the problem, but I can clarify tons of math problems for you where the solution is staring you right in the face yet its impossible to solve if you haven't seen it previously.

example:

We all know 2,3,5,7,11,... are the primes

So the next guy is 13.

We all know 4,9,16,25,36 are the squares

So the next guy is 49

We all know 1,1,2,3,5 are the fibonacci numbers

So the next guy is 8

So, what's the next guy in 1,5,7, 15, 20 ?

( Remember the solution is right in front of you, but 90% of people on average won't figure it out. These are called convolution series. The solution is 28, if you haven't figured it out yet. )

(edit: provided solution and fixed a simple numerical error: dekz, thank you for spotting that )

That's a really bad question, and I'm not just saying that because I don't know what the answer is. The first three sequences are very ordinary mathematical series, suggesting that the fourth would be the same. But the sequence 1, 5, 7, 15, 20 doesn't appear in OEIS[1], let alone 1, 5, 7, 15, 20, 28. I feel comfortable in announcing that if a sequence doesn't appear in OEIS, it isn't mathematically significant. Likewise, "convolution series" doesn't appear to have a well-defined mathematical interpretation.

What sequence is this and what is the justification for 28 being the next number?

[1] http://oeis.org/

Apparently the solution is

(1) correct an error in the question which renders it unsolvable (a_3 should be 9, not 7)

(2) guess that the invented term "convolution series" doesn't have anything to do with the mathematical concept of convolution[1]

(3) a_n = nth square number minus nth prime minus nth Fibonacci number.

Staring you right in the face!

[1] https://en.wikipedia.org/wiki/Convolution#Definition

Dude. Relax. I said convolution series and not convolution integral ( the one you've linked to ). The "invented term" as you call it appears in Melzak's textbook ( companion to concrete math ). Finally, I actually "invented" a sequence that appears in OEIS ( https://oeis.org/A160138 ) , so I'm well aware that there are infinite sequences you can manufacture by simply changing the op in a convolution series. I just throw these questions into the mix to have some fun and games, otherwise doing interviews becomes very tedious and boring. Nobody is being judged on whether they can figure out that the number of moves for a legitimate tower of hanoi ie. 1,3,7,15, comes from the 2^n-1 sequence ( there's an entire chapter of D.E.Knuth's "concrete math" devoted to just that very topic, and it was my text in undergrad, so I like to have some fun with it. )

Forgive the non-10%er but do you mind explaining the solution?

Closest I can come is square minus the other two which gives:

1 5 9 15 20 28...

> Closest I can come is square minus the other two which gives:

Yep, you got it! That is the solution. There is a method to the madness. Given series S squares, F fibonaccis, P primes, with an op of minus, the convolution series

C = S op F op P = S op P op F

gives you 1 5 9 15 20 28... ( ps the third term is 9 and not 7 as stated in the original problem. In my defense, it was 7pm and I was drowsy when I posted that, so I must have looked at my watch, seen the 7 on the dial and then wrote 7 instead of 9. Apologies )

Funny, that's a question my friend asked me the other day because he couldn't figure it out in an interview. Took me half an hour to solve this thing. Would definitely have failed the interview question myself, imagine doing it when someone was watching your every move!?

The convolution series question is bad 'cos you don't give enough terms to even see it. The next term is 28 only if the first four numbers are 1,5,7,15 and you assume that what precedes 1 is 0. If you give two or three terms more (28, 48, 75), I'm sure more people will have success figuring it out. The number of terms given is like saying "1 1 2 ?" and saying the missing one is 3 because this is the Fibonacci series.

In any case, even if the candidate didn't figure out the convolution series, but vocally tried calculating differences or tried to look at the numbers in a different base than 10 or even complained that she can cook up an arbitrary rule for the remainder of the series, that kind of thought process is certainly interesting and playful interview material .... if the post calls to a keen eye for patterns. The key is that the answer is not what you're interested in, ever. It's always the thought process.

> We all know 4,9,25,36,49 are the squares

2^2, 3^2, 5^2, 6^2, 7^2

4^2? Did I miss something there?

> I can clarify tons of math problems for you where the solution is staring you right in the face yet its impossible to solve if you haven't seen it previously.

Are you seriously contending that Pascal's triangle is such a problem?

We all know that "Aha!" problems exist, that there are algorithms that are simple in hindsight despite being anything but obvious before we were told the answer. I don't think anyone here is proposing that such questions are good for interviews. But do you really believe that producing rows of Pascal's triangle, when the triangle has already been explained, is actually one of those "Aha!" questions?

If you aren't contending that, I'm not sure what point you're trying to make above.

For my solution, after Jemfinch posted about this topic on G+ - I had to remember what Pascal's Triangle essentially was (it's been awhile since I've reviewed the binomial theorem, etc). No big deal.

Once one understands the actual problem (wikipedia has a rather nice graphical pyramid showing a few rows being generated), it should be a rather simple task to implement a naive version of it in any modern language. Is my ruby version the best performing? Of course not. However, it demonstrates some obvious insights into it such that the first and last members of a row are always 1's.

If I were hiring engineers, I'd be slightly wary if they couldn't at least make basic insights such as that and get darn close within a few minutes. Obviously, there are nerves and other things that can cause issues during an interview process - but one should arrive at a general solution rather quickly, even if it's not the most beautiful.

I don't think anyone is trying to be condescending - but the quick naive approach using an array and calculating some sort of offset to get your values is simply bread and butter in our profession.

Reply on news.ycombinator.com