13 ms·

You know what? I just tried implementing the Pascal's Triangle function. I implemented the general algorithm, recursively, but I had a bunch of logic errors tha

You know what? I just tried implementing the Pascal's Triangle function. I implemented the general algorithm, recursively, but I had a bunch of logic errors that took me about 25 minutes to fix (one was obvious and embarrassing) - in the privacy of my own office and with a debugger. I have over 10 years of programming experience and I probably would have miserably failed your "litmus test", especially if it were in an interview situation in front of a whiteboard. Maybe this just means I'm a bad programmer, but I tend to think that problems like "Pascal's Triangle" don't represent what we work on day-to-day.

jemfinch 15y ago
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.
- LVB 15y ago
  Anyone can write it in Python. I think fragsworth did his in J: (-@|. |."_1 [: ":@-.&0"1 !~/~)@i. 5
  - Bootvis 15y ago
    I'm just surprised nobody has mentioned calculating the solution directly using factorials or some builtin n choose k function.
    - dspeyer 15y ago
      Factorials risk integer overflow in the intermediate calculations, though something similar can work.
      - Bootvis 15y ago
        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.
    - derefr 15y ago
      Or the even-less-computationally-intensive algorithm: http://en.wikipedia.org/wiki/Pascals_triangle#Calculating_an_individual_row_or_diagonal_by_itself http://en.wikipedia.org/wiki/Pascals_triangle#Calculating_an...
      - Bootvis 15y ago
        Very nice but expecting the candidate to know that much about Pascals triangle upfront seems a bit too much ;)
      - lightcatcher 15y ago
        Thats what dspeyer did here: http://news.ycombinator.com/item?id=3431687 http://news.ycombinator.com/item?id=3431687 . 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)
  - enceladus 15y ago
    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) )
- rdtsc 15y ago
  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.
  - ori_b 15y ago
    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.
    - bad_user 15y ago
      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.
- z324werwer 15y ago
  u mad bro, that u had to write so many lines, and yet your code couldn't print out pascal(5000) u mad? in ruby, def fact(n) n == 0 ? 1 : n.downto(1).inject(:*) end def pascal(n) 0.upto(n) {|r| print "#{fact(n)/(fact(r)*fact(n - r))} "} end
- jlarocco 15y ago
  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.
  - ori_b 15y ago
    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: typedef struct Abc { Abc *n; Abc *p; void *d; } Abc; Abc *foo(Abc *p, void *x) { Abc *n; n = malloc(sizeof(Abc*)); n->p = NULL; n->n = p; n->d = x; p->p = n; return p; } 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.
    - peterhunt 15y ago
      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.
      - ori_b 15y ago
        1) Right. 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. Pretty good, though :)
- jes5199 15y ago
  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.
- fragsworth 15y ago
  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.
  - dxbydt 15y ago
    >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 )
    - dekz 15y ago
      > 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?
    - deleted 15y ago
      [deleted]
    - jemfinch 15y ago
      > 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.
- deleted 15y ago
  [deleted]
- kunqiana 15y ago
  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)) ))))
  - rayval 15y ago
    Here's my version in C: int main(int argc, char ** argv) { long *n1,*n2; int row,i; row=0; N1[0]=1L; print_row(row,N1); while(row++ < MAX_ROWS) { for(i=0, n1 = N1, n2=N2; i<MAX_BUF && *n1; i++) { if (i==0 ) n2[i] = 0 + n1[i]; else if(n1[i]==0) n2[i] = n1[i-1] + 0; else n2[i] = n1[i-1] + n1[i]; } print_row(row,N2); for(n1=N1,n2=N2; *n2; ) *n1++ = *n2++; } } void print_row(int row,long*n) { printf("row #%d",row); while(*n) { printf(" %ld ", *n++);} printf("\n"); } This works through the size of long int (at least 50 rows).
    - haberman 15y ago
      I think some of your code is missing (like where N1 and MAX_ROWS are defined). Here's mine: #include <stdio.h> #include <stdlib.h> long *pascal(int row) { long *ret = (row == 1 ? NULL : pascal(row - 1)); ret = realloc(ret, sizeof(long) * row); ret[row - 1] = 1; for (int i = row - 2; i > 0; i--) ret[i] += ret[i - 1]; return ret; } int main(int argc, char *argv[]) { int row = atoi(argv[1]); long *data = pascal(row); for (int i = 0; i < row; i++) printf("%ld ", data[i]); printf("\n"); free(data); return 0; }
      - jiggy2011 15y ago
        upvoted for realloc trick
        haberman 15y ago
- dspeyer 15y ago
  def pascal(i): o=[1] for j in xrange(1,i): o.append(o[-1] * (i - j) / j) return o Recursion's nice, but this isn't really the place for it. Especially since python has a maximum stack depth.
  - haberman 15y ago
    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).
    - bermanoid 15y ago
      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...
- kamaal 15y ago
  You didn't test how well he can code, what you tested is how easily he can represent mathematical theorems in a programming language. That is definitely not what 99.999% of the programmers do every day. Professors in colleges, may be. But not programmers.
  - noarchy 15y ago
    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.
- ramblerman 15y ago
  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.
- the_tubes 15y ago
  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."
- zyzzy 15y ago
  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 these are the times I get ruby-1.9.2-p290 :037 > timeA('pascal2',40000) "Time elapased 949.9490000000001 milliseconds" => "Time elapased 949.9490000000001 milliseconds" ruby-1.9.2-p290 :038 > timeA('pascal',40000) "Time elapased 470.48699999999997 milliseconds" => "Time elapased 470.48699999999997 milliseconds" ruby-1.9.2-p290 :039 > timeA('pascal',80000) "Time elapased 1776.224 milliseconds" => "Time elapased 1776.224 milliseconds" ruby-1.9.2-p290 :040 > timeA('pascal2',80000) "Time elapased 5722.419000000001 milliseconds" => "Time elapased 5722.419000000001 milliseconds" ruby-1.9.2-p290 :041 > timeA('pascal',200000) "Time elapased 160416.34199999998 milliseconds" => "Time elapased 160416.34199999998 milliseconds" ruby-1.9.2-p290 :042 > timeA('pascal2',200000) "Time elapased 235113.38 milliseconds" => "Time elapased 235113.38 milliseconds"
- ricardobeat 15y ago
  five-minute coffee, am I hired? getRow = (n) -> rows = [[1]] for i in [1...n] prev = rows[i-1] rows[i] = [] for j in [0..i] rows[i][j] = (prev[j-1] or 0) + (prev[j] or 0) rows[n-1] and a one-liner for those who appreciate: (n) -> [[1]..n].reduce (p, c, i) -> ~~p[j-1] + ~~p[j] for j in [0..i]
- dennisgorelik 15y ago
  Two minutes? That's about 9 seconds per line. Unless you are typing a program that you memorized - you cannot get such speed.
rhizome 15y ago
It's probably more likely that it means you didn't graduate in CS within the past couplefew years, which I suspect is really the purpose of these filters. Would you rather be tested on your ability to comprehend a multi-kloc codebase and make correctness-preserving modifications to it? That depends on how rigorous and well-maintained the existing test suite is, or even worse, that it is only half done. Which half? Guess, I think you'll be surprised.
- ajross 15y ago
  I think that's more cynical than is appropriate. You're assuming that every successful candidate is regurgitating this from memory. Solving Pascal's Triangle is a straightforward yet not-completely-trivial logic exercise. It's the kind of algorithm design task that "serious programmers"[1] need to do, successfully, every day. Goofed logic bugs in algorithms are Very Expensive bugs. People who can avoid them are very desirable. This particular problem can be solved in just a few lines of code with no edge cases, which makes it a great candidate for a test to detect those developers. [1] And yes, of course one can be a "successful software engineer" without being a "serious programmer". Writing CRUD logic and the like may be its own skill (and one not helped by algorithmic reasoning), but CRUD developers are cheap and plentiful. Tests like this give you a marker for the people who are hard to find.
  - rhizome 15y ago
    You're assuming that every successful candidate is regurgitating this from memory. By the same token, you appear to be assuming that successful candidates aren't. But I'm not trying to polarize. Wouldn't it be better to invent a scenario for which a solution/algo must be constructed, during which the interviewer and interviewee can bounce their relative expertises? Is it too much to ask for the questions not to be rote(-ish) Pascal's Triangle stuff?
    - ajross 15y ago
      Not to get meta on you, but you're assuming that I'm assuming. I assure you I'm not assuming anything. I tried it myself, successfully, having never done it before, and it's not that hard to solve. Someone else posted their solution here. Good programmers can come up with that kind of code routinely, mediocre programmers can't. And this is a test to distinguish the classes. Talking about software design methodology cannot tell me whether someone can write new algorithms correctly. If I have a job that requires people to correctly design algorithms, I think asking questions about algorithm design is entirely appropriate.
VBprogrammer 15y ago
I don't want to put words in the OPs mouth, but in my experience knowing that you should use a recursive solution probably puts you ahead of the curve. Being able to produce a solution which has the correct general form possibly after a little prompting would count as a reasonable pass.
- phillmv 15y ago
  I think it depends on what you're hiring for. For 90% of engineering tasks, you're just plugging together different technologies other people put together. Oh hey yeah, Unix + HTTP + Rails + Javascript + Some Dude's API. The amount of SHEER INTELLIGENCE necessary to untangle the above is, I think, not very high. It's a low threshold of competence. So, for that range of problems, fumbling around for fifteen minutes in front of a whiteboard will display the necessary grasp of logic. The hard part in interviewing (and what people usually screw up), in my opinion, is almost entirely finding someone with a can do attitude who you can get along with for 40hrs every week. Almost anyone can string stuff together; finding people that you can trust is way harder.
yason 15y ago
Coding takes time. It's more cost-effective to ask the interviewee code a non-trivial task at home and review his results before inviting him in. Then you already know if he can code and you can walk through his thinking on a whiteboard, with a more specialized case.
- lutorm 15y ago
  Except that there's a difference between what people can produce and what they can google up. When you let people out of the room to do something, you have no way of knowing if they did it themselves. Or if it took them 12h to do it.
  - kd5bjo 15y ago
    When I was giving interviews, I'd have the candidate bring up the code sample that they submitted on their own laptop, and start making changes. If I found any bugs, I'd ask them to fix them; otherwise, I'd extend the problem in some way that their existing code didn't anticipate and ask them to change their code to meet the new spec. Not only did I find this very helpful in evaluating prospective employees, several people that we hired told me later that it was the most fun they'd ever had in an interview. That is, of course, a biased sample; some of the people that I interviewed obviously did not find my interview style entertaining. The litmus test that I generally used was whether they were able to, given an erroneous output of their own creation, they could reason about why it happened and fix it before the hour-long interview slot was over. Also, if I (watching over their shoulder) couldn't spot the cause of the bug, I considered that it was probably unreasonable to expect them to be able to find and correct it during the interview. While I encountered a lot of candidates that froze in the face of compiler errors or started making changes without stopping to think about what the cause of the error might be, I never once got the feeling that anyone was less familiar with the code that they submitted than someone who had written it themselves.
mikeash 15y ago
I think this response generally mischaracterizes the whole technique of whiteboard testing. If you got the general algorithm implemented recursively quickly, you're done. A bunch of logic errors? Oh well. The interviewer may point them out, at which point you can discuss them. You do not have to create perfect code on the whiteboard. You just need to demonstrate that you can code. Sounds like you would have been fine.
sethg 15y ago
In my experience, interviewers who give whiteboard problems are not expecting perfect answers or even syntactically correct answers, although if the interviewer sees a bug (e.g., missing some corner case), you may be prompted to look for it. The goal is to have a basis for follow-up questions like “how would you change it if the input was type Y instead of type X?” or “what’s the time/space complexity of that algorithm?” or “how would you write a test for that function?”
spdy 15y ago
I did the same experiment. Got a sheet of paper and figured out the concept behind this problem within a minute but i took me quite some time to put it into code. Wrong logic / not perfectly concentrated / choosing the wrong way for a moment etc. Am i a bad programmer now if i cant get a running program in less than 5 minutes ? I would rather let people apply with code they are proud of like in every design job than solving litmus tests/puzzles
Bjartr 15y ago
You only fail the 'litmus test' if the interviewer were looking for you to write working code. Whiteboard coding, done right, isn't about writing bug free code, it's about observing the thought process that goes into solving programming problems.
- kls 15y ago
  I always write working code (at least after debugging), I have a hard time understanding why people cant see the logical fallacy here. Have a programmer write code that may or may not work to test their ability as a developer. When their ability as a developer is measured by being able to write working code. I personally would rather see working code and an explanation of what they have done. I can garner someones ability to write code from that.
- rimantas 15y ago
  The problem is: I don't do thinking by writing code. I do thinking by thinking. Often away from the computer (and even farther away from whiteboards).
watmough 15y ago
Here's a 5 - 10 minute iterative version in C. https://gist.github.com/1567842 https://gist.github.com/1567842 I tend to like to rough code out Lispishly, but if I'm actually running stuff I'll often do it in C.
deleted 15y ago
[deleted]
vorg 15y ago
Just use a spreadsheet, that's programming isn't it? Type 1 into cells A1 and B1, then copy them by dragging down to the required row. In cell B2, type =A1+B1 but use the cursor keys to select the 2 cells. Drag-copy B2 down to the required row, then drag-copy rightwards until the rightmost column is only zeroes. The nth row of Pascal's triangle is corresponds to the nth row of the spreadsheet, ignoring trailing zeroes. It takes a fair bit to explain it in English, and probably in most programming languages, but to actually do it in a spreadsheet took me 10 seconds. Though admittedly I've done it before when spreadsheets first came out, doodling while I was waiting for the Cobol punchcards to go through the reader. Spreadsheets were a sudden productivity boost in their time, too bad they've since been massively abused by wannabe-programmer office workers taking their first step onto the Excel-Access-VB-SQLserver-Csharp ladder. Those of us who've been around a while know businesses don't hire programmers based on brainteasers. People invited to do brainteasers have already been filtered, selecting for under-30's willing to work copious overtime without complaining.
mvgoogler 15y ago
'but I tend to think that problems like "Pascal's Triangle" don't represent what we work on day-to-day' There are plenty of software jobs where that statement is absolutely true. I am not interviewing people for those jobs. Taking a well-defined problem such as "write code to print the Nth row of pascal's triangle" is substantially easier than most of what we deal with on a day to day basis. The hard part is discovering and defining the problem well enough to get the point where it is as easy as "here is what we need to do, write some code to do it". Once you get there, whipping out the code needs to be second nature. As cletus said in his post - a problem like this is a negative filter. If someone has a hard time whipping out the code for a well-defined problem like that, they will have a very hard time here. If they can't, it doesn't mean they are a bad programmer. It doesn't mean they can't be successful in the industry. It is simply a strong signal that they would not be successful at Google. And since I'm interviewing people for jobs at Google that's what I care about :-)
dspeyer 15y ago
What is it you've been doing for 10 years? It does sound like your basic coding skills are pretty atrophied.
kamaal 15y ago
Maybe this just means I'm a bad programmer, but I tend to think that problems like "Pascal's Triangle" don't represent what we work on day-to-day. You are right! In fact I seriously doubt any serious software project that is solving business problems ever works on these sort of problems. These problems are basically more of testing mathematical knowledge through programming. They may make a great interview to hire professors but not programmers.
- gbog 15y ago
  I don't know what you code, but what I code, which classic web apps, requires very often the kind of thinking that solving Pascal triangle requires. I often need to choose how to model my data, how to have it glued together in different forms, etc. I'd say a simple array display with border is similar, even.

jemfinch 15y ago

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.

LVB 15y ago
Anyone can write it in Python. I think fragsworth did his in J: (-@|. |."_1 [: ":@-.&0"1 !~/~)@i. 5
- Bootvis 15y ago
  I'm just surprised nobody has mentioned calculating the solution directly using factorials or some builtin n choose k function.
  - dspeyer 15y ago
    Factorials risk integer overflow in the intermediate calculations, though something similar can work.
    - Bootvis 15y ago
      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.
  - derefr 15y ago
    Or the even-less-computationally-intensive algorithm: http://en.wikipedia.org/wiki/Pascals_triangle#Calculating_an_individual_row_or_diagonal_by_itself http://en.wikipedia.org/wiki/Pascals_triangle#Calculating_an...
    - Bootvis 15y ago
      Very nice but expecting the candidate to know that much about Pascals triangle upfront seems a bit too much ;)
    - lightcatcher 15y ago
      Thats what dspeyer did here: http://news.ycombinator.com/item?id=3431687 http://news.ycombinator.com/item?id=3431687 . 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)
- enceladus 15y ago
  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) )
rdtsc 15y ago
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.
- ori_b 15y ago
  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.
  - bad_user 15y ago
    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.
z324werwer 15y ago
u mad bro, that u had to write so many lines, and yet your code couldn't print out pascal(5000) u mad? in ruby, def fact(n) n == 0 ? 1 : n.downto(1).inject(:*) end def pascal(n) 0.upto(n) {|r| print "#{fact(n)/(fact(r)*fact(n - r))} "} end
jlarocco 15y ago
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.
- ori_b 15y ago
  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: typedef struct Abc { Abc *n; Abc *p; void *d; } Abc; Abc *foo(Abc *p, void *x) { Abc *n; n = malloc(sizeof(Abc*)); n->p = NULL; n->n = p; n->d = x; p->p = n; return p; } 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.
  - peterhunt 15y ago
    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.
    - ori_b 15y ago
      1) Right. 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. Pretty good, though :)
jes5199 15y ago
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.
fragsworth 15y ago
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.
- dxbydt 15y ago
  >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 )
  - dekz 15y ago
    > 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?
  - deleted 15y ago
    [deleted]
  - jemfinch 15y ago
    > 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.
deleted 15y ago
[deleted]
kunqiana 15y ago
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)) ))))
- rayval 15y ago
  Here's my version in C: int main(int argc, char ** argv) { long *n1,*n2; int row,i; row=0; N1[0]=1L; print_row(row,N1); while(row++ < MAX_ROWS) { for(i=0, n1 = N1, n2=N2; i<MAX_BUF && *n1; i++) { if (i==0 ) n2[i] = 0 + n1[i]; else if(n1[i]==0) n2[i] = n1[i-1] + 0; else n2[i] = n1[i-1] + n1[i]; } print_row(row,N2); for(n1=N1,n2=N2; *n2; ) *n1++ = *n2++; } } void print_row(int row,long*n) { printf("row #%d",row); while(*n) { printf(" %ld ", *n++);} printf("\n"); } This works through the size of long int (at least 50 rows).
  - haberman 15y ago
    I think some of your code is missing (like where N1 and MAX_ROWS are defined). Here's mine: #include <stdio.h> #include <stdlib.h> long *pascal(int row) { long *ret = (row == 1 ? NULL : pascal(row - 1)); ret = realloc(ret, sizeof(long) * row); ret[row - 1] = 1; for (int i = row - 2; i > 0; i--) ret[i] += ret[i - 1]; return ret; } int main(int argc, char *argv[]) { int row = atoi(argv[1]); long *data = pascal(row); for (int i = 0; i < row; i++) printf("%ld ", data[i]); printf("\n"); free(data); return 0; }
    - jiggy2011 15y ago
      upvoted for realloc trick
      - haberman 15y ago
dspeyer 15y ago
def pascal(i): o=[1] for j in xrange(1,i): o.append(o[-1] * (i - j) / j) return o Recursion's nice, but this isn't really the place for it. Especially since python has a maximum stack depth.
- haberman 15y ago
  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).
  - bermanoid 15y ago
    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...
kamaal 15y ago
You didn't test how well he can code, what you tested is how easily he can represent mathematical theorems in a programming language. That is definitely not what 99.999% of the programmers do every day. Professors in colleges, may be. But not programmers.
- noarchy 15y ago
  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.
ramblerman 15y ago
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.
the_tubes 15y ago
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."
zyzzy 15y ago
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 these are the times I get ruby-1.9.2-p290 :037 > timeA('pascal2',40000) "Time elapased 949.9490000000001 milliseconds" => "Time elapased 949.9490000000001 milliseconds" ruby-1.9.2-p290 :038 > timeA('pascal',40000) "Time elapased 470.48699999999997 milliseconds" => "Time elapased 470.48699999999997 milliseconds" ruby-1.9.2-p290 :039 > timeA('pascal',80000) "Time elapased 1776.224 milliseconds" => "Time elapased 1776.224 milliseconds" ruby-1.9.2-p290 :040 > timeA('pascal2',80000) "Time elapased 5722.419000000001 milliseconds" => "Time elapased 5722.419000000001 milliseconds" ruby-1.9.2-p290 :041 > timeA('pascal',200000) "Time elapased 160416.34199999998 milliseconds" => "Time elapased 160416.34199999998 milliseconds" ruby-1.9.2-p290 :042 > timeA('pascal2',200000) "Time elapased 235113.38 milliseconds" => "Time elapased 235113.38 milliseconds"
ricardobeat 15y ago
five-minute coffee, am I hired? getRow = (n) -> rows = [[1]] for i in [1...n] prev = rows[i-1] rows[i] = [] for j in [0..i] rows[i][j] = (prev[j-1] or 0) + (prev[j] or 0) rows[n-1] and a one-liner for those who appreciate: (n) -> [[1]..n].reduce (p, c, i) -> ~~p[j-1] + ~~p[j] for j in [0..i]
dennisgorelik 15y ago
Two minutes? That's about 9 seconds per line. Unless you are typing a program that you memorized - you cannot get such speed.

rhizome 15y ago

It's probably more likely that it means you didn't graduate in CS within the past couplefew years, which I suspect is really the purpose of these filters. Would you rather be tested on your ability to comprehend a multi-kloc codebase and make correctness-preserving modifications to it? That depends on how rigorous and well-maintained the existing test suite is, or even worse, that it is only half done. Which half? Guess, I think you'll be surprised.

ajross 15y ago
I think that's more cynical than is appropriate. You're assuming that every successful candidate is regurgitating this from memory. Solving Pascal's Triangle is a straightforward yet not-completely-trivial logic exercise. It's the kind of algorithm design task that "serious programmers"[1] need to do, successfully, every day. Goofed logic bugs in algorithms are Very Expensive bugs. People who can avoid them are very desirable. This particular problem can be solved in just a few lines of code with no edge cases, which makes it a great candidate for a test to detect those developers. [1] And yes, of course one can be a "successful software engineer" without being a "serious programmer". Writing CRUD logic and the like may be its own skill (and one not helped by algorithmic reasoning), but CRUD developers are cheap and plentiful. Tests like this give you a marker for the people who are hard to find.
- rhizome 15y ago
  You're assuming that every successful candidate is regurgitating this from memory. By the same token, you appear to be assuming that successful candidates aren't. But I'm not trying to polarize. Wouldn't it be better to invent a scenario for which a solution/algo must be constructed, during which the interviewer and interviewee can bounce their relative expertises? Is it too much to ask for the questions not to be rote(-ish) Pascal's Triangle stuff?
  - ajross 15y ago
    Not to get meta on you, but you're assuming that I'm assuming. I assure you I'm not assuming anything. I tried it myself, successfully, having never done it before, and it's not that hard to solve. Someone else posted their solution here. Good programmers can come up with that kind of code routinely, mediocre programmers can't. And this is a test to distinguish the classes. Talking about software design methodology cannot tell me whether someone can write new algorithms correctly. If I have a job that requires people to correctly design algorithms, I think asking questions about algorithm design is entirely appropriate.

VBprogrammer 15y ago

I don't want to put words in the OPs mouth, but in my experience knowing that you should use a recursive solution probably puts you ahead of the curve. Being able to produce a solution which has the correct general form possibly after a little prompting would count as a reasonable pass.

phillmv 15y ago
I think it depends on what you're hiring for. For 90% of engineering tasks, you're just plugging together different technologies other people put together. Oh hey yeah, Unix + HTTP + Rails + Javascript + Some Dude's API. The amount of SHEER INTELLIGENCE necessary to untangle the above is, I think, not very high. It's a low threshold of competence. So, for that range of problems, fumbling around for fifteen minutes in front of a whiteboard will display the necessary grasp of logic. The hard part in interviewing (and what people usually screw up), in my opinion, is almost entirely finding someone with a can do attitude who you can get along with for 40hrs every week. Almost anyone can string stuff together; finding people that you can trust is way harder.

yason 15y ago

Coding takes time. It's more cost-effective to ask the interviewee code a non-trivial task at home and review his results before inviting him in. Then you already know if he can code and you can walk through his thinking on a whiteboard, with a more specialized case.

lutorm 15y ago
Except that there's a difference between what people can produce and what they can google up. When you let people out of the room to do something, you have no way of knowing if they did it themselves. Or if it took them 12h to do it.
- kd5bjo 15y ago
  When I was giving interviews, I'd have the candidate bring up the code sample that they submitted on their own laptop, and start making changes. If I found any bugs, I'd ask them to fix them; otherwise, I'd extend the problem in some way that their existing code didn't anticipate and ask them to change their code to meet the new spec. Not only did I find this very helpful in evaluating prospective employees, several people that we hired told me later that it was the most fun they'd ever had in an interview. That is, of course, a biased sample; some of the people that I interviewed obviously did not find my interview style entertaining. The litmus test that I generally used was whether they were able to, given an erroneous output of their own creation, they could reason about why it happened and fix it before the hour-long interview slot was over. Also, if I (watching over their shoulder) couldn't spot the cause of the bug, I considered that it was probably unreasonable to expect them to be able to find and correct it during the interview. While I encountered a lot of candidates that froze in the face of compiler errors or started making changes without stopping to think about what the cause of the error might be, I never once got the feeling that anyone was less familiar with the code that they submitted than someone who had written it themselves.

mikeash 15y ago

I think this response generally mischaracterizes the whole technique of whiteboard testing. If you got the general algorithm implemented recursively quickly, you're done. A bunch of logic errors? Oh well. The interviewer may point them out, at which point you can discuss them. You do not have to create perfect code on the whiteboard. You just need to demonstrate that you can code. Sounds like you would have been fine.

sethg 15y ago

In my experience, interviewers who give whiteboard problems are not expecting perfect answers or even syntactically correct answers, although if the interviewer sees a bug (e.g., missing some corner case), you may be prompted to look for it. The goal is to have a basis for follow-up questions like “how would you change it if the input was type Y instead of type X?” or “what’s the time/space complexity of that algorithm?” or “how would you write a test for that function?”

spdy 15y ago

I did the same experiment. Got a sheet of paper and figured out the concept behind this problem within a minute but i took me quite some time to put it into code. Wrong logic / not perfectly concentrated / choosing the wrong way for a moment etc. Am i a bad programmer now if i cant get a running program in less than 5 minutes ? I would rather let people apply with code they are proud of like in every design job than solving litmus tests/puzzles

Bjartr 15y ago

You only fail the 'litmus test' if the interviewer were looking for you to write working code. Whiteboard coding, done right, isn't about writing bug free code, it's about observing the thought process that goes into solving programming problems.

kls 15y ago
I always write working code (at least after debugging), I have a hard time understanding why people cant see the logical fallacy here. Have a programmer write code that may or may not work to test their ability as a developer. When their ability as a developer is measured by being able to write working code. I personally would rather see working code and an explanation of what they have done. I can garner someones ability to write code from that.
rimantas 15y ago
The problem is: I don't do thinking by writing code. I do thinking by thinking. Often away from the computer (and even farther away from whiteboards).

watmough 15y ago

Here's a 5 - 10 minute iterative version in C. https://gist.github.com/1567842 https://gist.github.com/1567842 I tend to like to rough code out Lispishly, but if I'm actually running stuff I'll often do it in C.

deleted 15y ago

[deleted]

vorg 15y ago

Just use a spreadsheet, that's programming isn't it? Type 1 into cells A1 and B1, then copy them by dragging down to the required row. In cell B2, type =A1+B1 but use the cursor keys to select the 2 cells. Drag-copy B2 down to the required row, then drag-copy rightwards until the rightmost column is only zeroes. The nth row of Pascal's triangle is corresponds to the nth row of the spreadsheet, ignoring trailing zeroes. It takes a fair bit to explain it in English, and probably in most programming languages, but to actually do it in a spreadsheet took me 10 seconds. Though admittedly I've done it before when spreadsheets first came out, doodling while I was waiting for the Cobol punchcards to go through the reader. Spreadsheets were a sudden productivity boost in their time, too bad they've since been massively abused by wannabe-programmer office workers taking their first step onto the Excel-Access-VB-SQLserver-Csharp ladder. Those of us who've been around a while know businesses don't hire programmers based on brainteasers. People invited to do brainteasers have already been filtered, selecting for under-30's willing to work copious overtime without complaining.

mvgoogler 15y ago

'but I tend to think that problems like "Pascal's Triangle" don't represent what we work on day-to-day' There are plenty of software jobs where that statement is absolutely true. I am not interviewing people for those jobs. Taking a well-defined problem such as "write code to print the Nth row of pascal's triangle" is substantially easier than most of what we deal with on a day to day basis. The hard part is discovering and defining the problem well enough to get the point where it is as easy as "here is what we need to do, write some code to do it". Once you get there, whipping out the code needs to be second nature. As cletus said in his post - a problem like this is a negative filter. If someone has a hard time whipping out the code for a well-defined problem like that, they will have a very hard time here. If they can't, it doesn't mean they are a bad programmer. It doesn't mean they can't be successful in the industry. It is simply a strong signal that they would not be successful at Google. And since I'm interviewing people for jobs at Google that's what I care about :-)

dspeyer 15y ago

What is it you've been doing for 10 years? It does sound like your basic coding skills are pretty atrophied.

kamaal 15y ago

Maybe this just means I'm a bad programmer, but I tend to think that problems like "Pascal's Triangle" don't represent what we work on day-to-day. You are right! In fact I seriously doubt any serious software project that is solving business problems ever works on these sort of problems. These problems are basically more of testing mathematical knowledge through programming. They may make a great interview to hire professors but not programmers.

gbog 15y ago
I don't know what you code, but what I code, which classic web apps, requires very often the kind of thinking that solving Pascal triangle requires. I often need to choose how to model my data, how to have it glued together in different forms, etc. I'd say a simple array display with border is similar, even.