Basic programming like Pascal's triangle represents the easiest stuff we do on a day-to-day basis. We write code. Pascal's triangle is code. Would you rather be tested on your ability to comprehend a multi-kloc codebase and make correctness-preserving modifications to it? Would you rather be tested on your ability to integrate or upgrade third-party libraries in a massive existing codebase? Coding is the easiest thing we do on a day-to-day basis; if it's not representative of what we work on day-to-day, it's because it's easier than what we do, not because it's harder.
I was astonished at the 25 minutes you claimed this took you, so I did it myself. It took me about two minutes to write this, which worked the first time I tried it:
#!/usr/bin/env python
def pascal(i):
if i == 0:
return [1]
else:
L = pascal(i-1)
ret = [1]
for i in xrange(len(L)-1):
ret.append(L[i] + L[i+1])
ret.append(1)
return ret
if __name__ == '__main__':
import sys
print pascal(int(sys.argv[1]))
What problems did you encounter that required you to use a debugger? I'm genuinely curious, because it seems like such a simple problem.
After 15 years of programming one doesn't really remember what the heck Pascal's triangle looks like. You know why? Because knowing about Pascal's triangle doesn't bring in a paycheck.
If you program for a living, ask yourself in the last 5 years how many times did you have to write Pascal's triangle? How many times did you have to solve a brain teaser at work? I'll answer for me -- 0 times.
So I am advocate of posing a relevant problem and taking the candidate on the whiteboard through that problem. Not "let's imagine you have 100 horses, now one dies, blah blah..." but "Here is what we are working on. We have 1000 concurrent users, there is an open TCP connection to each, help us solve this particular latency problem". Yeah they might not know about Pascal's triangle but they if they can understand and show an ability to solve your particular problem then they are a candidate for you.
After 15 years of programming, one would hope that seeing the definition of it would be enough to let you implement it in short order. Expecting to have it memorized? Of course not. Expecting you to be able to code it up after a good explanation of what it is? I wouldn't expect you to have any serious issues.
I honestly had forgotten the definition of it (the last time I saw it was in high school algebra), but I was able to get a working solution in about 10 minutes, including looking at the definition on Wikipedia. I'd say I'm a rather average coder (I'm certainly surrounded by people far better than I am, in any case).
If you had never seen or heard of Pascal's triangle before, I'd say maybe 20 minutes to code it would be reasonable.
Well, if the Pascal triangle question is not a question of what is a Pascal triangle and the problem is properly explained, then it is easy to come up with a solution.
However, this doesn't highlight good engineers. You know why? Because in the real world finding out the problem is many times a lot harder than coming up with a solution.
Here's a sample:
If I say to you that "I want these and these people classified / sorted, such that I want to find the people that have the best probability of being a good hire" ... I haven't actually told you the problem. I don't really know the problem myself. All I know is maybe that the hiring process is broken for some reason and I'd like to fix it, but I don't know the reasons (I can't put my finger on it).
And that's not a properly defined problem. We don't even know how to measure properly if a hire was good or not. And in the real world, that's how most problems are described to engineers - i.e. I have this pain, solve it somehow.
> Your company doesn't do performance reviews for employees?
Every performance review I ever attended was a bad joke, for the same reasons companies have problems filtering between candidates.
Seriously, if there's a problem with the hiring process (it was just an example btw, I'm not saying there is one at your company), then why do you think performance reviews work out well?
Right. I would hope that implementing something like the Pascal triangle is not the only question you would ask. It indicates if someone can't turn specs into code, but not much more.
> After 15 years of programming one doesn't really remember what the heck Pascal's triangle looks like. You know why? Because knowing about Pascal's triangle doesn't bring in a paycheck.
No, it certainly doesn't. I've never had to write Pascal's triangle, for sure, and I doubt I ever will need to. But on a daily basis I'm solving myriad little problems just like Pascal's triangle. Complicated? Of course not, especially with the libraries my programming environment makes available. But it's the bread and butter of what a software engineer does a daily basis.
If your objection is to make any sense at all, you must be contending that there exist--in the real world--people who can effectively implement solutions for complex problems but who can't code up Pascal's triangle on a whiteboard in a few short minutes. Where are these people? Pascal's triangle isn't a positive filter. It's not like we're hiring anyone who can implement it. It's a negative filter: if you can't do it, why should I believe that you can solve the much more complex problems software engineers regularly face?
Well... unless you did a good job explaining the algorithm for generating Pascal's triangle in simple terms I'd probably fail given the pressure. Otherwise, my initial response would be a visit to Wikipedia where my eyes would promptly glaze over at the text talking about "binomial coefficients" and I'd decide your job advertisement was misleading and it probably isn't a good job anyway.
Assuming you terminated the interview first, I'd go home and come to resent you for asking such a deceptive question. A simple coding test does not invite someone to conceptualize a solution to an unknown problem in terms of rows when the interviewer expects a recursive solution. I'd find solace in noting that the recursive solution is far less efficient than simply building the table manually (pop quiz: calculate exactly how much less efficient in 30 seconds!), and assume that you didn't realize this or you would have asked a more clever brainteaser.
Either way, I'd leave the interview irritated you didn't want to talk about the real problems you needed to solve and upset you didn't look at any of the code I made available before you scheduled our interview. I'd eventually feel grateful things didn't work out, but I'd steer friends away from working with your company, out of the conviction the people interviewing and managing the programming staff don't understand how to judge programmer value, and that it isn't a good place for people who get things done.
>Well... unless you did a good job explaining the algorithm for generating Pascal's triangle in simple terms I'd probably fail given the pressure.
How's this for simple terms? http://en.wikipedia.org/wiki/File:PascalTriangleAnimated2.gi... It's on Wikipedia's page for Pascal's triangle. If your response to that page is to have your eyes 'glaze over' to the point where you can't find the animation (which has a simply-worded caption explaining the triangle), why should someone want to hire you?
I'll tell you why anyone would hire me if you can answer my simple question about the relative efficiencies of the top-down versus recursive solutions. You've already had an hour and claim to be familiar with the problem space, so I think it's a fair measure of your suitability in this space.
I'm going to go for coffee, but there's a whiteboard right there. Shouldn't take more than a minute or two.
Otherwise, my initial response would be a visit to Wikipedia where my eyes would promptly glaze over at the text talking about "binomial coefficients" and I'd decide your job advertisement was misleading and it probably isn't a good job anyway.
You would be right in deciding that. Over the years I've seen all these puzzle and math kids have the least productivity in delivering business software.
And besides if you spend say 30 minutes a day reading these interview puzzles online, you can game the system and get your way through. Without you even being tested on some basic skills required to win in the real world.
You may know all the algorithms from the book by heart. But what's the whole point if you don't how to use a couple of unix text processing utilities? Puzzle kids generally answer that by saying something like sed can be learn't by reading a manual.
If you can learn and work with sed by reading a manual on the job, then you can also learn and work with algorithms by reading manuals on the job too!
> How many times did you have to solve a brain teaser at work?
There is a fine line between brain teasers and the difficult problems that are our bread and butter. To answer your question: I would categorize many particularly subtle problems I've solved at work as brain teasers, so my number is high.
Relevant problems are a great way to judge someone's problem solving skills, but any problem that gives a glimpse into the way a person thinks is sufficient. I am probably not willing to give a candidate the amount of context to describe, let alone time to solve, the exact problem that I happen to be in the middle of on the day of an interview, but rather one we have already solved and determined to be interview-worthy. This means I certainly don't care about the solution, but rather the path to the solution. If you believe, as I do, that people tend to walk similar paths through every problem they solve, and that the path is important and the solution worthless, then the relevance of the problem is irrelevant.
Bingo. So much of what people are doing these days is throwing together APIs and frameworks, and reading documentation on the same. If the candidate has experience with the technologies you're using, and can show that they've completed some real projects with them, they may actually be of more use than the guy who can perform mental acrobatics with brainteasers.
I got a job once by diving into a multi-kloc codebase and fixing bugs (it was open source and they had a bugtracker)
They didn't ask me to do this - I just wanted to impress them.
That was a very satisfying way to get a job, I'd be happy to do it again.
I would rather be tested by making changes to the the multi-kloc codebase. It's more similar to what I actually spend my time doing at work. And it's a good chance to see the code I'd be working on.
As for coding Pascal's triangle? It took me <30 seconds to Google it and find code I could copy/paste.
I've had interviews where I've been asked to take a moderately obfuscated code sample, find out and describe to the interviewer what it does, and then find all the bugs in it.
To be honest, seeing about 200 lines that looked like this:
Note, there are at least 3 (edit: at least 4) bugs in the above code. None should be syntax errors.
Sorting it out was a bit of a challenge. I think the specific question that I was looking at deobfuscated into reading words and definitions in from the command line and maintaining them in a sorted list, then looking up the words and printing their definitions.
And I agree, it was a great interview question. I even had the ability to sit in front of the computer and test my fixes to make sure it worked.
Let me try (I do not often write production C code)
1. You need to malloc 3 words, and you're only allocating one (you want sizeof(Abc))
2. Abc in the struct will not resolve (change to struct _Abc and the struct name to _Abc)
3. You should cast the result of malloc/check for failure
4. This is bad memory management practice, I think.
2) No, 'struct Foo' is in a different namespace from the typedef'ed name. 'typedef struct Foo Foo' is perfectly valid.
3) Yes, absolutely.
4) Not sure what you mean.
Here's a hint: You'll likely miss one of them unless you realize what the algorithm is trying to do. It's an algorithmic error. The other one is findable from looking at the code without context, but the correct fix isn't entirely obvious without realizing the way the code works.
I think function foo is supposed to insert a new node (n) into the list before node p, but it's not done properly (while n points to p and p points to n, n does not point back to the item before p).
I was going for foo as 'dlist_prepend()', not dlist_insert(), but figuring out that it's putting a node into a list is good enough for me. (Edit: to me, 'prepend' implies that there are no nodes before the head of the list you're prepending to)
That should be enough for you to figure the last 2 errors, in any case.
Yes, it should be returning `n`. And the final one I was thinking of was a segfault on an empty list
prepend(NULL, &something);
would die if you don't do;
if (p != NULL)
p->p = n;
I think, this would be easier in a larger problem where you had context that gave you usage examples. I probably wouldn't ask someone to debug a function floating an a vacuum like I did here. I'd use a trivial but full working program.
I don't think I'd expect everyone to get every bug without a little bit of prodding in the right direction. Being able to step through the code and show what it's doing to the data structures would be a first step that would make me happy. Recognizing that the data structure looked like it's a linked list, and finding and and fixing a couple of the bugs, and I'd be very happy.
Casting the result of malloc isn't a good idea in C because it can hide the lack of a prototype if you forget to #include <stdlib.h>. It's also a redundant mention of the type name in question, making for more work / noisy diffs under code change.
I agree that the real test is how well you do on the real codebase. But (as an interviewer) I'm not going to let you see that codebase or spend time describing its architecture to you until I'm convinced you are worthwhile. Hence, walk me through the steps to generate something programmatically; Pascal's triangle or anything else. I don't give a shit that you found code for it on Google, I'm not looking for a solution - I'm looking to understand how well you can solve problems.
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.
>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?
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. )
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!?
> 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 )
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.
> 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.
That is a very clever solution that appears to rely on some mathematical property of Pascal's triangle that is not at all obvious from its definition. You've basically derived a formula for deriving binomial(n, k) given binomial(n, k-1).
While no interviewer would reasonably expect anyone to come up with that as a first solution (well, unless it was a very mathy job, and even there they'd give you some leeway), it would be reasonable to have a conversation about the structure that eventually lead there.
Some of the best interviewers I've seen approach interviewing almost like teaching, in that they'll ask you questions that lead you towards the answer, just to keep the conversation flowing so they can see how (and whether) you think.
For instance, in this case, after providing a correct recursive implementation you'd hopefully add the caveat that it might not be the best way to do it because of maximum stack depth, and you could talk about that a bit, as well as workarounds. You'd likely be able to easily offer an improved version that iteratively updated a (properly sized) row in-place, [1,0,0,...,0] -> [1,1,0,...,0] -> [1,2,1,...,0], etc., until the last digit became 1, in which case you're done.
Then you'd have a conversation about the time and space complexity of that method, you'd hopefully be able to figure out that it's O(N^2) in time and O(N) in space, and the interviewer would ask you whether you could do better. You'd tell him that it's optimal re: space, but that there could possibly be an implementation in O(N) time, and then you'd think for a moment.
From there, the interviewer would give you a gentle prod (after all, this isn't a math interview and we don't have all day) by suggesting you look at the ratio between neighboring elements, and then it's easy to, say, look at the eighth row and see that the ratios are 8/1, 7/2, 6/3, 5/4, 4/5, 3/6, 2/7, 1/8 and figure out dspeyer's formula from there.
The nice thing about interviews in this format are that they don't require any specific prior knowledge; in fact, they work much better when the candidate has never seen the problem before, because you actually get to talk through it with them for the first time.
I realize that algorithms aren't everything, but at a place like Google, at least, they're a lot more important than at a typical Java-shop, so I think questions like this are perfectly fair. If someone can't make it through an interview like that, they're going to have a lot more trouble on the job when they need to cast a complicated machine learning algorithm that's just been invented by the guy down the hall into map-reduce form and get it running well enough so that it can run in real time and actually be tested...
My comment wasn't complaining about interviews or these questions (I'm at Google now and was at Amazon before, so I've made it through these loops before and I've got no bone to pick).
I was meaning to comment on how dspeyer was portraying his solution as a simple iterative alternative to jemfinch's recursive one, when in fact it was an entirely different algorithm that calculated the results in a different way. I thought it was strange that he did not mention this.
For an algorithms heavy job, I would hope a candidate would be able to derive this equation with a little guidance (ie, reminding them about n choose k and how to write that with factorials)
Yes, it seems a number of optimizations are possible. At least it is not necessary to calculate n!. Depending on the job discussing these strategies and whether they are worthwhile for some real world problem can be quite interesting.
True, but could just anyone write it as offensively as the below Python one-liner?
(Were one to ever write such code in production, he should be escorted from the building immediately!)
from itertools import tee, izip, chain
pascal = lambda rows: reduce(lambda acc,n: acc+[(lambda it: [sum(x) for x in (lambda it,n=2: izip(*((lambda it,n: ([next(it) for _ in xrange(n)],it)[-1])(it,pos) for pos,it in enumerate(tee(it,n)))))(chain((0,),it,(0,)))])(acc[-1])], xrange(rows), [[1]])
num_rows = 10
print '\n'.join( ' '.join(map(str,row)) for row in pascal(num_rows) )
I tried to recode what you did in scheme for practice
(define (pascal n)
(if (= n 0) (list 1)
(begin
(let ((L (pascal (- n 1)))
(ret (list 1)))
(do ((i 0 (+ i 1)))
((= i (- (length L) 1)))
(begin (set! ret (append ret (list (+ (list-ref L i) (list-ref L (+ i 1))))))))
(append ret (list 1))
))))
Thanks for the tip, but when I tried to run it under mzscheme I got the error: map: all lists must have same size; arguments were: #<procedure:+> () (1). Also could you explain why set! and list-ref are bad?
You are doing yourself a great service by learning Scheme - that can fundamentally change how you think about programming. Reading the first chapter of SICP[0] will change you forever. Yet right now you're using Scheme as a Python/C/Ruby with a strange syntax, while it's a totally different language with its own idioms. You should learn them to master Scheme.
As for your particular questions:
1. map yields an error under mzscheme
I'm at work, and didn't have access to a proper scheme, so I used an online REPL[1], which apparently is more forgiving. Regardless, you can write your own map (a good exercise!) that stops as soon as one of the arguments is exhausted. Make it tail-recursive[2] as well!
2. list-ref is bad
Lists are beautiful data structures designed for recursive algorithms. If you are using lists and not using recursion (or a hidden recursion in the form of map), you're doing something wrong. list-ref uses list as a vector, which has a performance implications - your algorithm is O(n^3) while mine is O(n^2).
3. set! is bad
Margins are too small for a proper explanation :), but basically set! has side-effects[3], and functional programming should avoid having them.
Using (map + (cdr L) L) doesn't work since they're different sizes (with DrRacket that I used, I see that it worked for you in your other comment, it is a very nice solution!). I'm not sure of an easy constant time way to append a zero to the end of (cdr L). The way I did it is similar to how you did it without map:
What if I wanted an exact precision. Could I use a custom data type to get better precision? If I used a custom data type, how could I make the code work for a distributed system to get parallel behavior?
If someone had some experience with pascal triangle, they could come up with a very efficient solution, that might put them at a advantage. If the interviewer valued efficient solutions.
So far
dspeyer, has one of the most efficient algorithms.
def pascal(i):
o=[1]
for j in xrange(1,i):
o.append(o[-1] * (i - j) / j)
return o
in ruby this could be
def pascal2(i)
o=[1]
i += 1
for j in 1.upto(i - 1 )
o << o[-1] * (i - j)/j
end
o
end
we could make it even more efficient if we remember a there is symmetry in a pascal triangle. So that we don't have to calculate all the values in a row, maybe just half of the values. We have to calculate the row a little different if it is even or odd in number.
def pascal(i)
o=[1]
i += 1
if i == 1 then
return o
end
i.even? ? d = i / 2 - 1 : d = i / 2
for j in 1.upto(d )
o << o[-1] * (i - j)/j
end
o[0..i/2] + o[0..i/2 - 1].reverse
end
So far it up to 2x as fast. I wrote this method in Ruby to time the different methods, pascal, pascal2.
def timeA(m,n)
begin_time = Time.now
send(m,n)
end_time = Time.now
p "Time elapased #{(end_time - begin_time)*1000} milliseconds"
end
I agree that the code should be simple enough to write in one go.
But that is under the (large) assumption that a suitable recursive algorithm has been found. The programming or coding is not the issue here. It's understanding the problem well enough and then identifying a recursive strategy.
Your code sucks dude ;)
Actually I don't know python so I don't know what's going on. Here is a real man's program in c++, it didn't take long to write but it did take long to figure out how to calculate it correctly.
#include <iostream>
using namespace std;
int main()
{
int max;
cout << "How big do you like it?\n";
cin >> max;
if(max<0||max>30)
return 0;
for(int row=0; row<=max; row++)
{
cout << 1 << " ";
unsigned int out=1;
unsigned int last;
unsigned int next=row;
for(int i=1; i<=row; i++)
{
last=out;
out=last*next/i;
next--;
cout << out << " ";
}
cout << endl;
}
return 0;
}
EDIT: there we go :D small errors corrected
For those that are just brainfucked with wikipedia's explanation
1. Wikipedia sucks as explaining math. Never use it to look something up that deals with math.
2. The best explanation is like in the middle of the article, "Calculating an individual row or diagonal by itself"... "For example, to calculate row 5, r = 6. The first value is 1. The next value is 1 × 5/1 = 5. The numerator decreases by one, and the denominator increases by one with each step. So 5 × 4/2 = 10. Then 10 × 3/3 = 10. Then 10 × 2/4 = 5. Then 5 × 1/5 = 1."
I was astonished at the 25 minutes you claimed this took you, so I did it myself. It took me about two minutes to write this, which worked the first time I tried it:
What problems did you encounter that required you to use a debugger? I'm genuinely curious, because it seems like such a simple problem.