11 ms·

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

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) )
- nazar 15y ago
  PHP Version I came up with. Took more than 10 minutes tho... for ($i=0; $i<=10; $i++) { if ($i== 0) $row[$i] = array(0, 1, 0); else { $row[$i] = array(); array_push($row[$i], 0); for($j = 0; $j<count($row[$i-1]); $j++) { $someval = $row[$i-1][$j]+$row[$i-1][$j+1]; array_push($row[$i], $someval); } } for($k = 1; $k<count($row[$i])-1; $k++) { echo $row[$i][$k]; } echo "<br />"; }
  - deleted 15y ago
    [deleted]
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.

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) )
nazar 15y ago
PHP Version I came up with. Took more than 10 minutes tho... for ($i=0; $i<=10; $i++) { if ($i== 0) $row[$i] = array(0, 1, 0); else { $row[$i] = array(); array_push($row[$i], 0); for($j = 0; $j<count($row[$i-1]); $j++) { $someval = $row[$i-1][$j]+$row[$i-1][$j+1]; array_push($row[$i], $someval); } } for($k = 1; $k<count($row[$i])-1; $k++) { echo $row[$i][$k]; } echo "<br />"; }
- deleted 15y ago
  [deleted]

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.