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.

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]))

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.

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.

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.

It's not intended to. It's highlighting bad engineers, not good ones. It's a negative filter, not a positive one.

> We don't even know how to measure properly if a hire was good or not.

Your company doesn't do performance reviews for employees?

Every performance review I ever attended was a bad joke, for the same reasons companies have problems filtering between candidates.

Seriously, if there's a problem with the hiring process (it was just an example btw, I'm not saying there is one at your company), then why do you think performance reviews work out well?

No, it certainly doesn't. I've never had to write Pascal's triangle, for sure, and I doubt I ever will need to. But on a daily basis I'm solving myriad little problems just like Pascal's triangle. Complicated? Of course not, especially with the libraries my programming environment makes available. But it's the bread and butter of what a software engineer does a daily basis.

If your objection is to make any sense at all, you must be contending that there exist--in the real world--people who can effectively implement solutions for complex problems but who can't code up Pascal's triangle on a whiteboard in a few short minutes. Where are these people? Pascal's triangle isn't a positive filter. It's not like we're hiring anyone who can implement it. It's a negative filter: if you can't do it, why should I believe that you can solve the much more complex problems software engineers regularly face?

Assuming you terminated the interview first, I'd go home and come to resent you for asking such a deceptive question. A simple coding test does not invite someone to conceptualize a solution to an unknown problem in terms of rows when the interviewer expects a recursive solution. I'd find solace in noting that the recursive solution is far less efficient than simply building the table manually (pop quiz: calculate exactly how much less efficient in 30 seconds!), and assume that you didn't realize this or you would have asked a more clever brainteaser.

Either way, I'd leave the interview irritated you didn't want to talk about the real problems you needed to solve and upset you didn't look at any of the code I made available before you scheduled our interview. I'd eventually feel grateful things didn't work out, but I'd steer friends away from working with your company, out of the conviction the people interviewing and managing the programming staff don't understand how to judge programmer value, and that it isn't a good place for people who get things done.

How's this for simple terms? http://en.wikipedia.org/wiki/File:PascalTriangleAnimated2.gi... It's on Wikipedia's page for Pascal's triangle. If your response to that page is to have your eyes 'glaze over' to the point where you can't find the animation (which has a simply-worded caption explaining the triangle), why should someone want to hire you?

I'm going to go for coffee, but there's a whiteboard right there. Shouldn't take more than a minute or two.

You would be right in deciding that. Over the years I've seen all these puzzle and math kids have the least productivity in delivering business software.

And besides if you spend say 30 minutes a day reading these interview puzzles online, you can game the system and get your way through. Without you even being tested on some basic skills required to win in the real world.

You may know all the algorithms from the book by heart. But what's the whole point if you don't how to use a couple of unix text processing utilities? Puzzle kids generally answer that by saying something like sed can be learn't by reading a manual.

If you can learn and work with sed by reading a manual on the job, then you can also learn and work with algorithms by reading manuals on the job too!

There is a fine line between brain teasers and the difficult problems that are our bread and butter. To answer your question: I would categorize many particularly subtle problems I've solved at work as brain teasers, so my number is high.

Relevant problems are a great way to judge someone's problem solving skills, but any problem that gives a glimpse into the way a person thinks is sufficient. I am probably not willing to give a candidate the amount of context to describe, let alone time to solve, the exact problem that I happen to be in the middle of on the day of an interview, but rather one we have already solved and determined to be interview-worthy. This means I certainly don't care about the solution, but rather the path to the solution. If you believe, as I do, that people tend to walk similar paths through every problem they solve, and that the path is important and the solution worthless, then the relevance of the problem is irrelevant.

That is definitely not what 99.999% of the programmers do every day. Professors in colleges, may be. But not programmers.

As for coding Pascal's triangle? It took me <30 seconds to Google it and find code I could copy/paste.

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;
    }

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.

1. You need to malloc 3 words, and you're only allocating one (you want sizeof(Abc)) 2. Abc in the struct will not resolve (change to struct _Abc and the struct name to _Abc) 3. You should cast the result of malloc/check for failure 4. This is bad memory management practice, I think.

2) No, 'struct Foo' is in a different namespace from the typedef'ed name. 'typedef struct Foo Foo' is perfectly valid.

3) Yes, absolutely.

4) Not sure what you mean.

Here's a hint: You'll likely miss one of them unless you realize what the algorithm is trying to do. It's an algorithmic error. The other one is findable from looking at the code without context, but the correct fix isn't entirely obvious without realizing the way the code works.

Pretty good, though :)

I think function foo is supposed to insert a new node (n) into the list before node p, but it's not done properly (while n points to p and p points to n, n does not point back to the item before p).

That should be enough for you to figure the last 2 errors, in any case.

n->p = p->p

I don't see the last one - unless foo should be returning n?

     prepend(NULL, &something);

     if (p != NULL)
         p->p = n;

I don't think I'd expect everyone to get every bug without a little bit of prodding in the right direction. Being able to step through the code and show what it's doing to the data structures would be a first step that would make me happy. Recognizing that the data structure looked like it's a linked list, and finding and and fixing a couple of the bugs, and I'd be very happy.

Unfortunately C++ requires the cast.

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.

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 )

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

[1] http://oeis.org/

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

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

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

Staring you right in the face!

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

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

1 5 9 15 20 28...

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

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

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

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

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

4^2? Did I miss something there?

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.

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

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

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

   def pascal(i):
        o=[1]
        for j in xrange(1,i):
           o.append(o[-1] * (i - j) / j)
        return o

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...

I was meaning to comment on how dspeyer was portraying his solution as a simple iterative alternative to jemfinch's recursive one, when in fact it was an entirely different algorithm that calculated the results in a different way. I thought it was strange that he did not mention this.

For an algorithms heavy job, I would hope a candidate would be able to derive this equation with a little guidance (ie, reminding them about n choose k and how to write that with factorials)

(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) )

    (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))
        ))))

This is better scheme:

(define (pascal n) (if (= n 0) (list 1) (let ((L (pascal (- n 1)))) (append (list 1) (map + (cdr L) L) (list 1)))))

As for your particular questions:

1. map yields an error under mzscheme

I'm at work, and didn't have access to a proper scheme, so I used an online REPL[1], which apparently is more forgiving. Regardless, you can write your own map (a good exercise!) that stops as soon as one of the arguments is exhausted. Make it tail-recursive[2] as well!

2. list-ref is bad

Lists are beautiful data structures designed for recursive algorithms. If you are using lists and not using recursion (or a hidden recursion in the form of map), you're doing something wrong. list-ref uses list as a vector, which has a performance implications - your algorithm is O(n^3) while mine is O(n^2).

3. set! is bad

Margins are too small for a proper explanation :), but basically set! has side-effects[3], and functional programming should avoid having them.

Have fun learning Scheme!

[0] http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-9.html#... [1] http://www.bluishcoder.co.nz/jsscheme/ [2] http://en.wikipedia.org/wiki/Tail_call [3] http://en.wikipedia.org/wiki/Side_effect_(computer_science)

(define next (lambda (l) (if (null? (cdr l)) '(1) (cons (+ (car l) (cadr l)) (next (cdr l))))))

(define pascal (lambda (n) (cond ((< n 1) '()) ((= n 1) '(1)) (else (cons 1 (next (pascal (- n 1))))))))

    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");
    }

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;
  }

I ran your code and it does run well. However fails for large cases such as pascal(200000).

You mentioned you worked for Google and Amazon, how can you modify the code to get an answer for pascal(200000)

  1. use double to get approximately-correct answers
  2. use an abitrary-precision library like GMP

  #include <stdio.h>
  #include <stdlib.h>

  int main(int argc, char *argv[]) {
    int row = atoi(argv[1]);
    long data[row];
    for (int i = 0; i < row; i++) {
      data[i] = 1;
      for (int j = i - 1; j > 0; j--) data[j] += data[j - 1];
    }
    for (int i = 0; i < row; i++) printf("%ld ", data[i]);
    printf("\n");
    return 0;
  }

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

  def pascal2(i)
    o=[1]
    i += 1
    for j in 1.upto(i - 1 )
       o << o[-1] * (i - j)/j
    end
    o
   end

  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

  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

  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"

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.

    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]

    (n) -> [[1]..n].reduce (p, c, i) -> ~~p[j-1] + ~~p[j] for j in [0..i]

That's about 9 seconds per line.

Unless you are typing a program that you memorized - you cannot get such speed.

  #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;
  }

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."

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

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

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 :-)

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.

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.

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?

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.

Are you seriously suggesting that anyone has code for a line of pascal's triangle memorized? Why would they? Just in case they got asked for it in an interview?

This is one of the advantages of this over something like quicksort: it's obscure enough that the candidate won't be able to recite it.

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.

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.

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.

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.

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.

I've developed high-performance medical imaging applications. I've build large distributed financial systems. I've built 2D/3D games. I've done a ton of stuff. Hell, I'm a software engineering hiring manager at my company. Yet I have no idea what a Pascall's triangle is, or how to give you a row of them.

I consider questions like that to be as useless as brainteasers in determining whether or not to hire someone. Sure, it can help give clues about a candidate, but if you're seriously considering rejecting a candidate on that point alone, I think you've got a problem in your hiring process.

Pascal's triangle is simple a triangle which starts at 1 and where each number in the next row is the sum of the two numbers above it, with 0 being assumed for numbers on the edge.

A program to produce one is nothing more than a couple for-loops, printf, and some basic logic.

All I'm saying is that there needs to be a multi-faceted look at a candidate. Some candidates are going to be so obviously poor that they do merit instant rejection. However, in my experience, that is the exception rather than the rule.

And yes - trivial programming questions do weed out a fair number of candidates. However... it's tricky. A trivial programming question can look different to many different people, especially if they have varying skill levels and depending on their level of comfort in interviews.

I try to give people the benefit of the doubt. If one question stumps them, I'll try to gauge their understanding with another similar (but different enough) question. If that doesn't work... sometimes I'll give them another shot, but usually I'll start winding the interview down.

I would ask you to explain, you would smirk inside, I will be rejected.

I am sure google should have enough data by now to see if there is correlation between knowing this problem and performance of hired programmer. I will be suprized if it has any relation.

I'm sure cletus or any other interviewer would explain what Pascal's Triangle is to you, and provide a couple rows of example output if you asked.

EDIT: Find/replace "Pascal's Triangle" with "FizzBuzz" and reread the comment. You'll get the same insight without getting hung up on seeing a term you didn't know.

"Candidates might get hung up on the gotcha part of it: the actual snip calculation. That's not something we care about, but that the candidates will likely think we care about. We should consider just giving them the formula (or letting them use a pre-defined "snip" method)."

It's useful as a very early screening because it eliminates a lot of people who are wasting your time and is so simple as to have almost to false negatives. It has no complexity, no algorithm or concepts you might be unfamiliar with- just the for loop, the conditional, and the modulo operator. No one who claims to be a professional developer should fail it.

For reference: http://www.codinghorror.com/blog/2007/02/why-cant-programmer...

Write a program that prints the numbers 1 to 100. However, for multiples of 3 print "Fizz" and for multiples of 5 print "Buzz". For multiples of both 3 and 5, print "FizzBuzz".

No point to this, I guess, other than that even something as simplistic as this is open to interpretation.

show' :: Int -> String show' x

|((rem x 3 == 0) && (rem x 5 == 0)) = "FizzBuzz"

|rem x 3 == 0 = "Fizz"

|rem x 5 == 0 = "Buzz"

|otherwise = show x

main :: IO ()

main = putStrLn $ foldl (\acc x -> acc ++"\n" ++ show' x) "" [1..100]

     x `rem` 3

Instead of folding, just map putStrLn over the list:

    mapM_ (putStrLn . show') [1..100]

Finally, I think this site lets you format code by putting four spaces in front of each line. I hope :)

Edit: One other thing. You don't need all those parentheses in the first line.

    rem x 3 == 0 && rem x 5 == 0 = "FizzBuzz"
    x `rem` 3 == 0 && x `rem` 5 == 0 = "FizzBuzz"

  fizzbuzz x | x `mod` 3 == 0 && x `mod` 5 == 0 = "FizzBuzz"
             | x `mod` 3 == 0 = "Fizz"
             | x `mod` 5 == 0 = "Buzz"
             | otherwise = show x

  main = putStr $ unlines $ map fizzbuzz [1..100]

    int main(int argc, char ** argv) 
    { 
    	int i;
    	for (i=0; i< 100; i++)
    	{
    		if( (i%3==0)&&(i%5==0)) printf("FizzBuzz");
    		else if(i%3==0)         printf ("Fizz");
    		else if(i%5==0)         printf ("Buzz");
    		else                    printf("%d",i);
    		printf("\n");
    	}
    }

   Write a program that prints the numbers from 1 to 100. But for multiples 
   of three print "Fizz" instead of the number and for the multiples of five
   print "Buzz". For numbers which are multiples of both three and five print
   "FizzBuzz".

  (dotimes (n 100)
	   (cond ((= 0 n))
		 ((and (= 0 (mod n 3))(= 0 (mod n 5)))
		  (format t "~a: Fizz Buzz!~%" n))
		 ((= 0 (mod n 3))
		  (format t "~a: Fizz!~%" n))
		 ((= 0 (mod n 5))
		  (format t "~a: Buzz!~%" n))
		 (t (format t "~a~%" n))))

    (fizzbuzz-eval
     100
     '(((3 5) (print "FizzBuzz"))
       ((3)   (print "Fizz"))
       ((5)   (print "Buzz"))
       (()    print-number)))

The call is

  (fizzbuzz (100 (((3 5) "fizzbuzz")(3 "fizz")(5 "buzz"))))

  (defun make-cond (item)
  (let ((divisors (first item))
	(exclamation (second item)))
    (if (listp divisors)
	(let ((div1 (first divisors))
	      (div2 (second divisors)))
	  `((and (= 0 (mod n ,div1)) (= 0 (mod n ,div2)))
	    (format t "~a: ~a~%" n ,exclamation)))
      `((= 0 (mod n ,divisors)) ;else
	(format t "~a: ~a~%" n ,exclamation)))))

  (defmacro fizzbuzz (params-list)
  (destructuring-bind (num-to req-list) params-list
    (let ((cond-list '(((= 0 n)))))
      (loop for item in req-list do
	    (push (make-cond item) cond-list))
      `(dotimes (n ,num-to)
	 (cond ,@(reverse
		  (push '(t (format t "~a~%" n))
			cond-list)))))))

1. Use loop instead of dotimes so you can make the index range over 1-100 instead of 0-99.

2. Factor out the string calculation so you only need one print statement.

3. Maybe use zerop.

4. Don't write ")(". Use a space in between.

Example:

    (loop for n from 1 to 100
          do (format t "~a~%"
                     (cond
                      ((and (zerop (mod n 3))
                            (zerop (mod n 5)))
                       "FizzBuzz")
                      ((zerop (mod n 3)) "Fizz")
                      ((zerop (mod n 5)) "Buzz")
                      (t (format nil "~a" n)))))

With the macro you can use arbitrary divisors though ;)

Any desire to refactor that beast?

I have to ask the parent poster if they truly feel that people need to know this http://en.wikipedia.org/wiki/Pascal%27s_triangle to deliver web or mobile solutions? You are highlighting the issue that the article is talking about.

Further, a whiteboard is like giving a mechanic a drawing of a car and a hammer and saying fix the head gasket. If creating a row from a Pascal Triangle was a real issue that crossed my desk the first thing I would do is hit Google to find the mathematical formula and explanation of what it does then I would see if there is a standard library and finally I would write it if one does not exist. Your whiteboard does not have search capabilities on it, so how are you expecting someone to show you how they work when you have provided them with any semblance of an environment that they would work in.

Pascal's Triangle is not some obscure and difficult mathematical formula you are expected to have memorized...This is not "construct Pascals Triangle and if you don't know what that is, too bad..."

It's a very simple concept and doesn't require the knowledge of anything other than simple arithmetic; any competent programmer should be able to write a program to construct one once the concept is explained to them...it's just a couple of for loops, some printfs, and straightforward logic.

That's the whole point the poster was making...really simple programming problems like fizzbuzz etc are useful at quickly weeding out people who lack very basic programming ability.

Constructing Pascals Triangle is obviously not a part of normal programming, but the ability to take an algorithm that has been described to you verbally and translate it into code is at the heart of all programming...that's what programming is basically.

If you can't do it, you are ipso facto not a real programmer.

I still contend that you are not gaining much insight and are producing an unnecessary filter that can do you more damage than good. I was on a project once that was cursed, we had a developer have a stroke, I had to have my heart restarted due to SVT from sleep deprivation etc. etc. We literally lost everyone that knew the technology except for me and I was not in good shape, and there was this one guy Tom Marra, he was an artist, but the kid had passion he had never coded in his life, but we where in a really bad situation, once he found out that with source control he could hack the crap out of the code and then just re-pull to fix his mistakes, he set out to teach himself JavaScript, on his own initiative. In less than a month he was contributing code to source control and in 2 months you could not tell his code from a seasoned pro's. The one quality this kid had was passion. You can't identify Tom Marra's by making them solve trivia on a whiteboard.

None of those things are necessary to solve the problem. There's no need to search for information...all the information you need is contained in the problem. It's an exceedingly simple algorithm, and if you can't take the verbal explanation and translate it into code, you are simply not a programmer.

What would you search for, how to make a for-loop? If you don't know such basics as flow control and basic logic, you probably need to go back to school. If you can't remember the usage of printf then you either picked the wrong language, or ask for help, or simple explain you'll fudge it a little and a good interviewer wouldn't penalize you. I'd note if you are interviewing for a language-specific position and said you are fluent in it, not knowing such a basic API might count against you though...

I think the important thing you are missing is that generally in "whiteboard" type situations, you are not expected to produce a completely correct/compilable program. Generally pseudo-code or whatever language you please is accepted and if you make some small syntax or logic error it's not a big deal. In light of that, a compiler/IDE/computer is not necessary unless you have some other reason to require them...such as a disability.

The important part is to see how one reasons through the process of taking a described algorithm and translating it into code...that is the essence of programming. If you can't do it, you are ipso facto not a programmer.

Your analogy is false...in your example the person is not being tested on the actual job they are expected to perform. Obviously that's not a good test.

In this case the programmer is being tested on precisely what their day to day job is: taking a verbal description of a process and translating it into code....so an accurate analogy would be to ask an architect to sketch a simple truss structure and discuss it, which is not unreasonable.

The entire point here is to give a drop dead simple problem to weed out the people who are fundamentally unfit for the position.

Do you think this accurately reflects the working conditions of a developer? Do you think that they jump into problems and that small errors are OK to them? do you think that they will be comfortable making those small errors in front of people, given that they A) generally would not accept them for themselves, and B) how critical some people can be of code that is not their own? Do you think they will be able to put there best foot forward in such an unnatural situation? They may blank, they may freeze and they may just be the type of person that reflects on an issue for a while before the set out to code.

What would you search for

I personally would search for the mathematical formula and a text description that I could put on my second monitor as reference. But first I would search for a standard library and avoid the effort all together.

taking a verbal description of a process and translating it into code

I personally never work from verbal descriptions, I document the issue, and place it into a ticket system in which I work the tickets based on priority.

Do you think this accurately reflects the working conditions of a developer?

Who said anything about trying to simulate a normal development day? This is about finding out some of their thought processes and if they can solve an exceedingly simple coding problem.

They may blank, they may freeze and they may just be the type of person that reflects on an issue for a while before the set out to code.

Where did they say you can't reflect on the issue? That's exactly what they want is you reflecting on the problem and describing how you'd go about solving it.

If someone tells you to write a function that takes a number N and prints out 1..N in pseudo code(Which is basically what the pascal problem asks when they provide the formula for a row) and you can't even talk your way through a possible solution you're not going to be able to complete any interview process, no matter how gentle.

I personally would search for the mathematical formula and a text description that I could put on my second monitor as reference.

So you're complaining that you can't search for something that the interviewer is already providing?

I personally never work from verbal descriptions, I document the issue, and place it into a ticket system in which I work the tickets based on priority.

If you are this incapable of listening to a two or three sentence problem description, ask the interviewer to print it out for you and write "ticket #1" on it? I mean is your nitpick really "They told me the problem out loud instead of writing it down?"

This is even ignoring the fact that taking verbal problem descriptions is an incredibly useful skill as a software engineer. I mean I guess I could tell people to file another ticket and I could have the joy of e-mail tag as I have to send off clarifying questions further delaying the task.

I assure you I am not trying to be argumentative, I am trying to help people understand why I and the author of the article believe that it is a flawed hiring practice. I have raised some good points, you can reflect on them and utilize them or you can discard them as rubbish. But I can tell you this, I have a lot of success in recruiting and I have learned by committing some of the very mistakes that I now advocate against. I used to buy into the Cargo Cult hiring practices, until someone smarter than me taught me how to truly identify talented individuals.

That's not the goal of the exercise however, nor is it a desirable one. The point is to a very loose test of basic ability. You can test the basic ability of a runner by asking them to do a quick sprint; the fact that this is not an accurate simulation of a race is irrelevant.

> do you think that they will be comfortable making those small errors in front of peopl

They should be. Any programmer should be comfortable making errors and owning up to them.

> Do you think that they jump into problems and that small errors are OK to them In this situation it is. In a "real world" situation, those would be caught by the compiler or unit tests. Of course really bad mistakes in this test would count against you.

> They may blank, they may freeze

Of course, this can happen in any type of interview. The point of interviews is to try and get the best balance of weeding out unsuitable people and finding the best ones. No matter what process you use, you will occasionally discard perfectly viable candidates...however this is preferable to accepting unsuitable ones.

> just be the type of person that reflects on an issue for a while before the set out to code.

...and that's fine...I'm not sure why you think this is some sort of "gotcha" test. It's perfectly fine to take some time...nobody is timing you. Again, this is a basic test to make sure you have the simplest skills and to get a little insight into your thinking/working. If you are uncomfortable with some aspect of the test, it is fine to say "well usually I take some time to think" or "I don't like writing on whiteboards"...etc.

You seem to be fundamentally misunderstanding the nature and point of the exercise. Errors are ok and expected because it's a simple test of reasoning and logic ability...likewise jumping in is ok because it's a simple problem.

Do you as a programmer spend a lot of time considering a simple if/else statement? Of course not...you jump in and write it. Again, we are talking about a simple algorithm here...given the description it basically writes itself for anyone with a modicum or programming experience.

The point here is to get a basic assessment of raw ability. The rest of the interview is to determine how well they might fit in the company, and any other gaps can be filled in with training.

> I personally would search for the mathematical formula and a text description that I could put on my second monitor as reference

That's the point you're missing. You don't need to search for that, it's been given to you. The description of the triangle contains the algorithm for constructing it. It's also so simple that you should be able to hold it in memory for the short time necessary, but if needed you could ask for a refresher.

> But first I would search for a standard library and avoid the effort all together.

That would negate the purpose of the test. Again, this is the most basic of basic programming tasks. It tests your ability to write simple logic and flow controls...something fundamental to writing computer programs.

Even if you solve a problem using mostly library functions, you still will need a few simple loops and logic to tie them together, and that's what this is testing.

> I personally never work from verbal descriptions

The verbal here is incidental...the point is you're working form some description or set of requirements. In this instance it's so simple that a verbal description will suffice, perhaps with one or two reminders. If you really can't hold such a simple description in your mind for 20 minutes I'd say you're not suited for any sort of mental work and might need to see a neurologist.

It seems your objections are based on a flawed premise, a fundamental misunderstanding of what the test is, how simple and easy it is, and what it is supposed to be testing.

If you look at want ads for day labor and other physical tasks it will often say something like "must be able to lift 50 lbs". When you went to the job site, they might ask you to lift a bag of concrete weighing 50 pounds. This is an exceedingly simple task and anyone fit for the job will be able to do it easily. It will quickly weed out anyone who is simply unfit for the work required, anyone who is fit will be able to do it easily.

More specific to your answers I understand your position, and I truly believe that you use it in this manner, the problem I have is that for every one of you there are 20 of the former me's who get so wound up in code tricks and trivia that we create unfair and useless interview filters. As such there is a perception among developers about code test, and that perception can be summed up that I am going to be tested on what the company thinks I should know, not what I know. For some of us, this creates a horrible and humiliating interview experience. In which a developer stands in front of a whiteboard analyzing their every move. No matter how much someone reassures them, they still have everything but logic running through their mind. It only takes one interviewer with an ego to permanently affect a developer in this manner and no amount of reassurance from a person they just met will help someone believe that their every move is not being judged.

Many people with Asperger syndrome fail tech interviews horribly but a good deal of them turn out to be wonderful developers. My best friend is affected by it, and I know from experience that he would never land a job if it where not for me. In spite of that, he is always the star developer at every organization that I bring him into. Now if someone sat him down and said, show me something you built and walk me through a routine, like the article suggest, they would be fascinated by his depth of knowledge.

If you don't know the formula and they haven't volunteered it, you can simulate this search simply by asking, and any interviewer using this for a proper purpose will happily write it on the whiteboard for you and walk you through it if anything is still unclear. It's not what's being tested.

What is being tested is that you know enough about programming to understand pretty much nothing more than basic flow control, basic arithmetic and perhaps trivial IO.

A use of a question like this checks that you've at least read "programming for dummies", and roughly understand the overall concepts of programming not whether or not you're proficient enough to even fill an entry level position. It weeds out the candidates that are completely unable to program at all.

> Do you think they will be able to put there best foot forward in such an unnatural situation? They may blank, they may freeze and they may just be the type of person that reflects on an issue for a while before the set out to code.

I've had smart candidates blank on trivial problems, but there's a very noticeable difference between people who blank and people who just have no clue. With people who blank, you get them to calm down, you ask probing questions to get them talking, even if it's about the weather, and they will eventually start offering up small bits and pieces of an answer that makes sense and gets them to "unfreeze" and start solving the problem. Whereas with the type of candidates this type of interviewing should be used to get rid of, you get absolutely nothing and/or total bullshit.

> But first I would search for a standard library and avoid the effort all together.

That's something you might say as a "by the way", but it isn't what the interviewer will be looking for.

> I personally never work from verbal descriptions, I document the issue, and place it into a ticket system in which I work the tickets based on priority.

Fine, so consider the description on the whiteboard the ticket with your highest priority would be my response to that if a candidate were to raise this objection (though be honest, if they did alarm bells would already be going off in my head).

Once in a while i have to look on how to format a string and how to use map, reduce, etc..

do i have to go to school because of that? heck i dont even remember what i had for breakfast yesterday

For this sort of test, all that is necessary is that you understand the basic idea of a for-loop...the basic idea of how to format a string...remember there's a good chance you're writing in pseudo-code.

Presumably however if you are a programmer, there is at least one language where you should be able to complete this task without looking anything up. It requires only the simplest of language constructs/library functions.

The exception of course is if this is a job for say, a Python programmer...and on your resume you say you are a "Python expert". The fact that you have to look up the syntax for basic constructs in Python would suggest you were lying on your resume. That's one of the things this exercise tests for.

If you said in your resume "I have experience with other languages, but I can learn Python"...then just being able to do this exercise in pseudo-code or any language of your choice would show you have basic programming skills and should be able to pick up Python.

If you really have to remind yourself what a for-loop is then yes, maybe you do have to go back to school/hit the books and study harder.

You see that's the crux of the issue, I can be a JavaScript expert and deliver massive JavaScript applications without having to resort to the arguments array to figure out how many parameters where passed into a function. Also, if I ever had a use case for it, I would look up the API and probably mentally discard it shortly afterwards. The interviewer thought that it was a perfectly reasonable filter, but yet I am one of the top JavaScript talents in my market. It did not work for them, because they assumed that knowledge of the arguments array was basic knowledge and any developer worth their salt would know it. Yet in my time working with some great JavaScript developers not a one of us ever used it. Further it harmed them because I now believe they are as incompetent as they believe me to be, as such if someone in my peer group asked about a position with them, I would relay my story. Not to be indignant but to be truthful, as such they lost access to valuable resources in a constrained market.

That being said, one can be an expert in say Java and not know the JDBC API, maybe all of their work revolved around JPA. Many in Java would argue that JDBC is fundamental and should be known to be an expert but a new crop of developers have never know anything but ORM. But we older developers assume that JDBC is a fundamental prerequisite because it was in our time. They cant see anything but the progression from JDBC to JPA because it is the life experience that they had. As such it's flawed and irrelevant. You have to be very careful to not bring interviewer bias into an interview and test are loaded with them. Even the simplest of test.

Does it not strike you that quite a few HN'ers openly admit that they would not pass the filter? Some of them long time contributors and members, some of them very respected? To me, I would question the viability of my assumptions if HN'ers where openly saying no your filter would eliminate me. I mean we have some of the best of the best lurking here. 37 has been complaining about it for a long time, I have had my own threads about it, and everyone agrees that hiring is flawed. Maybe it's time we reevaluate our assumptions based on what guys like the crew at 37 are doing since they seem to be improving on candidate selection over the rest of us.

The point I am making is what you are trying to garner, can be identified by asking a candidate to show you something they built and walk you through the routine they are most proud of. There are going to be functions, loops, if statement etc. in that code, if they can't explain what they built, then you should be suspect. Giving them a test just introduces bias of what the interviewer thinks they should know, and does nothing to tell the interviewer what they know.

To be quite honest, this thread is having the opposite effect. I'm questioning the quality of HN contributors based on their inability to either comprehend the question or code a simple algorithm.

I passed similar coding questions in interviews before I'd ever written a line of code in my life (in a Microsoft PM internship interview). No one cared if I wrote a semicolon or not - the interview was asking if I understood basic concepts like loops and logic.

I have yet to see someone who says that they would not pass the filter. Every single example I've seen in this thread is someone making up a different filter and saying that they would not pass that. I see people saying that they took a long time to debug subtle bugs in it, that they don't know the definition of the problem, or that in general they need documentation to code, all of which is completely irrelevant to the filter as given. Subtle bugs are allowed, the definition is given to you, the solution doesn't need any documentation (and if it does, you can just make up whatever API call you expect would be present in a sane standard library)

I'd be shocked to find any good programmer who, given the definition of Pascal's triangle, couldn't produce some decent, possibly buggy, incomplete, and syntactically incorrect, code on a whiteboard to print out a row from it.

I've yet to see anyone give an argument for how a good programmer could fail this test that doesn't rest on some feature of the test that doesn't actually exist.

You are now hitting at the core of the issue, to most developers bugs, bad code, correct API's matter, you are asking them to look past something that is engrained in their work ethic, personality, and quality as a developer to measure their worth as a developer. It does not matter what the filter truly is, their is a perception on the developers part of what they are being tested for, because they attribute what makes them of value to the test. As such the correct solution is what makes them valuable. You can't tell them to give you what they perceive to be the incorrect solution and expect it to accurately reflect what they value in themselves as a developer, that the interviewers bias. The fact that the filter is being misinterpreted is irrelevant or very relevant depending on your perspective. To the interviewee, they are going to perceive the task just as many on HN have and no amount of prodding to give up their nature is going to make them perform well, conversely they are going to perform worse. I have neglected the fact that the filter is being misunderstood for the very fact that, it will be misunderstood and for that alone it sets people up to fail.

This is one of the point that I am getting at, you are right it's not just the code that is being judged, candidates know that too, so when they are standing at the whiteboard a million things about being judge may be going through their mind. It has nothing to do with being stodgy or honorable or above the effort and everything to do, with some people just cannot perform in such an environment. People hold out that it is a negative filter, that if you can't pass it, you are a definite negative and observations on a lot of peoples parts are not confirming that assumption. I side with the author of the article that there is an all inclusive way to identify good candidates that fall into this category as well as candidates that would pass the whiteboard test without resorting to the whiteboard. I am not arguing that people should not be able to code, rather I side with the author that there is a better way to identify the people that can and receive more positive hits in the process. Thus reducing the interviewing cycle and identify more talent in a constrained market.

I see where you're coming from. I think the issue is that 99% (100%?) of all HNers would likely be great hires for most companies, so they see these questions as trivial, dumb, and not representative. Just the fact that someone thinks about these types of questions and reads programming blogs probably puts them ahead of most of the programming population.

The problem is that many of us have really never seen the mythical horrible programmer. The person that really can't even start a solution to FizzBuzz. The one that leaves the interviewer wondering how the person got jobs at other companies. I have seen and interviewed them before and it's frightening and uncomfortable for everyone involved. I've had candidates break down crying when I asked them to write a simple sql select statement on the board because their resume said expert in sql. For many, it's hard to fathom these people are out there, but they do exist.

FizzBuzz style questions are really important (eg. create an array with 4 numbers: 1, 2, 3 and 4 and output the values. Oh a "Java and Python 'expert'?". Please in both languages then!). Although I agree that home tasks and trick-algorithm questions are useless.

I don't think home tasks are useless, but they have to used properly. A home task geared to 1-2 hours seems reasonable for an exercise between the first and second interview. Some may say they'll just look up the answer (it's encouraged!), and that's why during the second interview the employer should discuss their answer. If the candidate can explain why they made particular decisions on the take home piece and have an intelligent discussion about the trade offs they took then who cares if they looked up the answer. In fact, the home test is probably closer to real programming since I don't know anyone who codes without Google nearby.

So, my preferred method is to use FizzBuzz as a first cut on the first interview and then give a take home quiz that should take the candidate 1-2 hours or less if they are good.

Any programmer I want to work with will be able to walk up to a whiteboard and write a program to print a row of Pascal's triangle or a function that determines whether one string contains another. Simple programming problems like this are the tiny problems we solve on a daily basis; if you can't implement such trivial functions without bugs, how can you expect to design or implement multi-kloc systems without bugs?

Until I get a keyboard with a tappety tap tap under my fingers my brain is at all stop.

Tom Marra's don't get hired at these big web co's kind of places.

This is probably the reason why there aren't many Tom Marra's at these big web firms and why don't seem to make any thing awesome anymore, than their first initial offering.

The job these algorithm kids in these big companies seems to do is to some ensure the wheels are rolling and they don't punctured. If they do, fix them by some fancy hackery!

Besides will you hire a novelist on how well he can solve crosswords?

I don't think the point is that you would be expected to know every historical abstract concept, but rather that given the basics of one, you could write code to implement a data structure around it.

If someone genuinely has never seen a problem before, and then figures it out in 45 mins, this person may look worse than someone who memorized the answer, and solves it in 10 mins.

The best solution is to give a previously unknown question to both the interviewee and the interviewer, and have them work out the solution together. It doesn't have to be a coding question, but the interviewer should be good enough to assess whether or not the person they are interviewing is good, not from how quickly they spit out an answer, but through how they work to get the answer.

1) I don't program on a whiteboard. It's 2012, I have tools, and they beat the whiteboard setup every time.

2) I will never implement something that I have not implemented before without at least first consulting with a search engine. You see, I am not a genius that will come up with the best algorithm for a calculation every time I am put up to the challenge. My amateur attempts will be no where near as good as what others have collectively accomplished over the years that the problem existed.

For example, in this particular case (I have never had to implement a function that generates Pascal's triangle before), I can guarantee you that anything I came up with at a whiteboard right now would be completely inferior to what the result would be if I was allowed to do a search first. So unless you're trying to see if I am capable of writing any old crappy code so long as the result is correct, your test isn't adequate.

3) Interviews still make me nervous, doesn't matter how many times I have them, I never feel comfortable going through the process. This often leads me to simply draw blanks when given a whiteboard assignment of this nature. You may think this means I am just incapable of solving your problem, or that I perform poorly under pressure, but I can tell you that this type of "put you on the spot" pressure is much different from the type one generally feels in a work environment.

2) Nobody cares how good your solution is, they care about seeing your thought process while solving it. They are likely waiting breathlessly to ask you follow up questions about your poor implementation that will further enlighten them about the way you think. It would be a downright shame to disappoint them by writing a great solution right away.

3) This is a legitimately big problem. Everyone responds to the pressure of interviews differently and it is definitely not necessarily correlated to their response to the pressures of the workplace. Ideally you would notify the interviewer(s) of your anxiety beforehand and they would be willing to work with you on either a short take-home (which a lot of people also hate for other reasons), or some type of working interview (which is often infeasible).

The original article was about a specific-language whiteboard problem, which is open to arguments about tooling and internet access, but many people ask these sorts of questions in terms of pseudocode, structured written english, or even discourse out-loud, and the goal is not to determine programming language or algorithm knowledge, but problem solving skills.

edit: phrasing

I got an interview in 2006 for Microsoft. I typed my C solution with Notepad via share screen over DSL. The code is "to find out the depth of leaf nodes in a binary tree and find out which leaf node is the shallowest/deepest" or something like that. I did that in 20 minutes and return solution to find out depths for all leaf nodes and sorted them by depth. And the interviewer saw how I worked during the session and laughed I was the first one to solve the problem in that way and much better than what they expect.

At the other hand, I got interviewed in Amazon around the same time. I completely choked on whiteboard because I did not prepare for session before like that and I still had a jet lag due to lack of sleep during flight in previous night. Then I got another interview in Bloomberg and I complete couldn't write code with pencil and paper.

My mind flows when I typed but chokes when I worked on paper/whiteboard. I guess the fluidity of editor is the key.

Later when I interview software engineers. I tried to let them to have a computer so they can write code during the session. I feel much better grasp for their potential and habit during the session than whiteboard and pencil paper test.

1. Writing down pseudo code for solutions. 2. Diagrams for architectures. 3. Flow charts for possible actions during problem solving.

But if you ask me to write down a real program in whiteboard, I find myself starting to got interrupted by thoughts about erase lines, moving blocks around and worrying about my writing is too big and board is too small for my code.

I think shared whiteboard is definitely a very good tool for discussions. But for me, even a rudimentary editor like notepad, vi helps me more in handling all rewriting/visualizing/pondering process. Probably I am not those programmers who can write down code without worrying about rewriting them. For me, write a program is like oil painting involving constant changes.

It's almost like Google has some sort of informal process for throwing away old interview questions this way, just for laughs...

This also makes me think I may spend too much time lurking on HN.

Well, I can assure you that as a kernel programmer, I think it IS indeed a waste of time. It's also astonishing that the moment the interviewer asks me something like this, my enthusiasm and interest in the interview drops by more than 50%. When I apply for a kernel programming a job at Google, I am dying to talk about my system internals knowledge, device driver programming experience, subtle differences between the AMD/Intel arch and what not. Instead, what do I get ? The recruiter asks me to recite by heart problems from a popular algorithms book for the pre-screening. It's like the prospective employer is telling me : I don't care what you did in the last three years. Let's start from scratch!

What also bothers me is the the test for coding skills. When a company hires a Linux kernel developer, the best possible way to test for coding skills is to look at my contributions. Instead, I am asked to write code and implement malloc so that the interviewer gets a taste of my coding knowledge. I think this is a huge waste of time.

My point being that the job interview at Google is incredibly generic. I believe that just like you should have a different resume for each job you apply to, the same applies to the interview process too.

More Info: This is very specific to my interview experience at Google. The two times that I applied at Google for Linux kernel development positions, overall I had the same experience as described above.

Some more Info : I also don't understand the idea of the algorithms test during the prescreen. If you go through the algorithms book the recruiter suggests and look up on glassdoor for interview questions, there's a very fair chance that you already know the answer to the question that's being asked!

Most of the supposed brilliant Algorithm and Math brains are basically people who crawl internet forums for puzzle questions by spending around 30 minutes everyday.

They don't know a jack about algorithms or math. Its just they know enough to game the interview.

  -module(pascal).
  -export([tri/1]).

  tri(Depth) ->
    tri(Depth,[[1]]).

  calc_row_rest([_]) ->
    [1];
  calc_row_rest([X,Y | Rest]) ->
    [X + Y | calc_row_rest([Y | Rest])].

  calc_row(Acc) ->
    [1 | calc_row_rest(Acc)].

  tri(X,_) when X =< 0 ->
    [];
  tri(1,Acc) ->
    lists:reverse(Acc);
  tri(Depth,Acc) ->
    NewRow = calc_row(hd(Acc)),
    tri(Depth-1,[NewRow | Acc]).

  > pascal:tri(10).
  [[1],
  [1,1],
  [1,2,1],
  [1,3,3,1],
  [1,4,6,4,1],
  [1,5,10,10,5,1],
  [1,6,15,20,15,6,1],
  [1,7,21,35,35,21,7,1],
  [1,8,28,56,70,56,28,8,1],
  [1,9,36,84,126,126,84,36,9,1]]

1. It falls on the interviewer to be helpful and clear enough to help a candidate understand what is being asked. Often, a brainteaser of any sort explained poorly can be a death knell for anybody, no matter how smart they are. It's imperative that the interviewer is able to thoughtfully analyze a person's line of thinking moreso than whether or not they can get to a right answer.

2. Which brings me to the second point... The issue with a lot of brainteasers for poor interviewers is that it's a binary outcome. Either the candidate already knows the answer and comes off looking like a genius, or the candidate stumbles around in no man's land with no clue what you're talking about. Again, it's key here that the interviewer is able to guide a candidate through the thinking instead of sitting back and enjoying the show (which is admittedly sometimes fun).

I definitely think there is space for brainteasers, but it really requires an interviewer with the right training to get it right (which a company like Google does not have to worry about, but a start-up may). What I've actually heard is an interesting approach for start-ups recruiting is to just have the candidate sit and try to tackle a recent problem the company has faced with the interviewer.

We did not actually give people tests to take home. :)

Interviewing is a numbers game. Your goal is to come up with a process that balances time spent by the interviewer with finding a suitable candidate.

You have to admit that this is biased towards a company, like Google, that must hire many more people per unit time than most companies do. (And the Google process seems to work remarkably well for Google.)

A more useful example was when I asked my high school AP Computer Science class years ago to test if an array of integers contained a poker straight without using a parser, assuming ace=1, jack=11, queen=12, king=13. The key was to see if they knew how to think about algorithms. I wanted them to perform a sort and iterate across the array, but was interested in what they came up with. It tested a lot of important concepts in thinking about problems, which is more important to me than correct syntax on a whiteboard or implementing valid recursion on the fly.

I watch them work and help them out as they go; I'd get a ton less info if I just looked at the finished product.

We do also have a couple of "off line" coding tasks, which are even more informative (if I had to ditch one, I'd ditch the live one).

import scala.collection.mutable.HashMap

import scala.math.BigInt

val pascals = HashMap[Int,List[BigInt]]()

def pascal(row:Int):List[BigInt] = {

val result:List[BigInt] = row match {

case 1 =>List(1)

case 2 =>List(1,1)

case n =>List.tabulate[BigInt](n)(x=>{

  if( x == 0 || x == n-1 ) 1

  else pascals(n-1)(x-1)+pascals(n-1)(x)

}

pascals+=(row->result)

result

}

(1 to 100).foreach(row=>println(pascal(row)))

------

Results: ---- List(1)

List(1, 1)

List(1, 2, 1)

List(1, 3, 3, 1)

List(1, 4, 6, 4, 1)

List(1, 5, 10, 10, 5, 1)

List(1, 6, 15, 20, 15, 6, 1)

List(1, 7, 21, 35, 35, 21, 7, 1)

List(1, 8, 28, 56, 70, 56, 28, 8, 1)

List(1, 9, 36, 84, 126, 126, 84, 36, 9, 1)

List(1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1)

...and 90 more rows -------

Prints Pascal triangles some 10,000 rows & beyond. So where's my Google job ?:)

Kidding aside, In 1999,I got hired at Sun Microsystems based on a 1-hour written exam. Chap gave me a pencil, paper & few programming problems & left me alone in a room. No laptop, no books, nothing. After 1 hour, he grabbed my paper, looked through the work & said "You are hired". Then we went for coffee.

otoh, I didn't get hired at 2 quant firms in 2011 based on this Whiteboard style interviewing. I got the first puzzle right & then halfway through the 2nd puzzle the chap said "There's an easier solution" & then they upped the ante ( Stirling numbers & then convolution integral & then I think they decided I wasn't a good fit because I couldn't work out every single theorem right there and then. I can do any number of problems, but if you could please write them down on a piece of paper & leave me alone for an hour...I can't quite think and write in front of you while you are passing snide comments on my thought process. Most of my professors when faced with a problem they haven't seen before typically say "I'll get back to you", and then in an hour or two, they call me to their office and show me their work. They don't try to work out a solution right in front of a classroom of 100 gawking students. They do so in the privacy of their office. No offence ( cause I still want that google job :-)

  def print_pascal(rows)
    row=[1, 0]
    (1..rows).each do |r|
      next_row = Array.new(r + 1)
      next_row[0] = 1 
      (1..row.length-1).each do |i|
        next_row[i] = row[i] + row[i-1]
      end
      print row[0..-2], "\n"
      row = next_row << 0 
    end
  end

  print_pascal(100)

  def p(row)
    [1,Range.new(0, row.length - 2).map {|l|     
      row[l] + row[l+1] 
      }, 1].flatten
  end

  a = [1]
  while true
    a = p(a)
    puts a.inspect
  end

  def pascal(num)
    return [1] if num == 1
    res = []
    prev = [0] + pascal(num-1) + [0]
    (1..num).to_a.each { |i| res << (prev[i-1] + prev[i]) }
    return res
  end

O(n) is quite easy in this problem.

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

let step row = zipWith (+) (0:row) (row++[0])

let triangle = iterate step [1]

take 10 triangle

2. I think an iterative function for fact would be more efficient.

3. I notice you do not memoize the result of fact even though you are calculating it twice for each call.

I suspect that you are trying to show how compact a solution can be, but in an interview situation, I would probably be more impressed by someone who is aware of the issues above.

Not that anyone will ever read this... I thought I'd managed to escape this time, but then I thought it might be some good practice, so I timed myself...

  nitrogen@n2:~ $ time bash
  nitrogen@n2:~ $ vim /tmp/pascal.c
  nitrogen@n2:~ $ cd /tmp
  nitrogen@n2:/tmp $ gcc -std=c99 -Wall -Wextra pascal.c -o pascal
  pascal.c: In function ‘main’:
  pascal.c:15:21: error: expected ‘;’ before ‘)’ token
  pascal.c:15:21: error: expected statement before ‘)’ token
  pascal.c:16:2: error: too few arguments to function ‘calloc’
  nitrogen@n2:/tmp $ vim pascal.c
  nitrogen@n2:/tmp $ vim pascal.c
  nitrogen@n2:/tmp $ ./pas^C
  nitrogen@n2:/tmp $ gcc -std=c99 -Wall -Wextra pascal.c -o pascal
  nitrogen@n2:/tmp $ ./pascal 1
  1 
  nitrogen@n2:/tmp $ ./pascal 2
  1 1 
  nitrogen@n2:/tmp $ ./pascal 3
  1 2 1 
  nitrogen@n2:/tmp $ ./pascal 4
  1 3 3 1 
  nitrogen@n2:/tmp $ ./pascal 5
  1 4 6 4 1 
  nitrogen@n2:/tmp $ ./pascal 6
  1 5 10 10 5 1 
  nitrogen@n2:/tmp $ ./pascal 7
  1 6 15 20 15 6 1 
  nitrogen@n2:/tmp $ exit
  exit
  
  real	4m5.621s
  user	0m0.928s
  sys	0m0.136s

  #include <stdio.h>
  #include <stdlib.h>
  
  int main(int argc, char *argv[])
  {
  	int row;
  	int *data;
  	int i, j;
  
  	if(argc != 2) {
  		printf("Usage: %s <row>\n", argv[0]);
  		return -1;
  	}
  
  	row = atoi(argv[1]);
  	data = calloc(row, sizeof(int));
  
  	data[0] = 1;
  
  	for(i = 1; i < row; i++) {
  		for(j = i; j > 0; j--) {
  			data[j] = data[j] + data[j - 1];
  		}
  	}
  
  	for(i = 0; i < row; i++) {
  		printf("%d ", data[i]);
  	}
  	printf("\n");
  
  	return 0;
  }

public class Pascal

{

      public static long[]  getRow(int rowNum)

      {
		long[]  thisRow = new long[rowNum];
		if(rowNum == 1)
		{
			thisRow[0] = 1;
		}

		else
		{
			long[]  lastRow = getRow(rowNum - 1);
			thisRow[0] = 1;
			thisRow[rowNum - 1] = 1;

			for(int i = 1; i < rowNum - 1; i++)
			{
				thisRow[i] = lastRow[i - 1] + lastRow[i];
			}
		}

		return thisRow;
	}
	public static void main(String args[])
	{
		int getRowNum = Integer.parseInt(args[0]);
		long[]  pasc = Pascal.getRow(getRowNum);
		for(int i = 0; i < pasc.length; i++)
		{
			System.out.print(pasc[i] + " ");
		}
		System.out.print("\n");
	}

Edit, cleaned up code:

How do I paste into here whilst preserving line breaks?

   function printPascal(x, triangle) {
      var row = [];
      while (x) {
         var next = clone(row);
         next.push(1);
         for (var i = 0; i < row.length - 1; i++)
            next[i + 1] = row[i] + row[i + 1];
         row = next;
         x--;
         if (triangle)
            print(whitespace(x) + row);
      }
      if (!triangle)
         print(row);
   }

   function clone(list) {
      var clone = [];
      for (i in list)
         clone.push(list[i]);
      return clone;
   }

   function whitespace(x) {
      var white = " ";
      while (x) {
         white += " ";
         x--;
      }
      return white;
   }

   printPascal(10);

    pascal = iterate (\xs -> zipWith (+) ([0] ++ xs) (xs ++ [0])) [1]

    void pascal(int n, int *buf)
    {
        for (int row = 0; row < n; row++) {
            for (int prev = 0, col = 0; col < row; col++) {
                int curr = buf[col];
                buf[col] += prev;
                prev = curr;
            }
            buf[row] = 1;
        }
    }

Looking at the C version, I wondered if it could be done without temporaries curr and prev. My no-temporaries version is not really any nicer, though it does shave off a few lines. :P

    void pascal(int n, int *buf)
    {
        for (int i = 0; i < n; i++) {
            buf[i] = 1;
            for (int j = i - 1; j > 0; j--)
                buf[j] += buf[j - 1];
        }
    }

    for i in range(n):
        p = 0
        for j in range(i):
            buf[j], p = buf[j] + p, buf[j]
        buf[i] = 1

    let rec iterate f value = seq {
        yield value
        yield! iterate f (f value) }

    let pascal = iterate (fun xs -> List.map2 (+) (0::xs) (xs @ [0])) [1]

    gimli> pascal <- local {
    gimli+   loop <- function(n, xs) {
    gimli+     if n > 0 then do
    gimli+       print(xs);
    gimli+       loop(n - 1, [0, xs] + [xs, 0]);
    gimli+     end
    gimli+   };
    gimli+   function(n) loop(n, [1])
    gimli+ }
    func(n) loop(n,[1])

    gimli> pascal(0)
    F

    gimli> pascal(1)
    1
    F

    gimli> pascal(9)
    1
    [1,1]
    [1,2,1]
    [1,3,3,1]
    [1,4,6,4,1]
    [1,5,10,10,5,1]
    [1,6,15,20,15,6,1]
    [1,7,21,35,35,21,7,1]
    [1,8,28,56,70,56,28,8,1]
    F

    gimli> xs <- [1]
    1

    gimli> xs <- [0, xs] + [xs, 0]
    [1,1]

    gimli> xs <- [0, xs] + [xs, 0]
    [1,2,1]

http://news.ycombinator.com/item?id=3431107

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

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

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

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

pascal 1 = [1]

pascal 2 = [1,1]

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

sum' [] = []

sum' [1] = [1]

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

head' [] = 0

head' xs = head xs

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

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

My implementation in 15 min using javascript. BTW I'm a freshmen CS major.

function row(len){

    if (len==1){
        return [1]
    }else{
        var p = row(len-1),
            arr = [];
        for (var i=0; i<len; i++){
            if (i==0){
                arr.push(p[0]);
            } else if (i == len-1){
                arr.push(p[i-1]);                
            } else {
                arr.push(p[i]+p[i-1]);                
            }
        }  
        return arr;
    }        
}

Or as we say in the medical field, this test has high "sensitivity" :)

http://en.wikipedia.org/wiki/Sensitivity_and_specificity#Sen...

Now I've seen them I'll keep them in mind if I ever have a need for them.

Although, in my research it was stated that these were extensions to the ECMA-262 standard and may not work everywhere. Therefore you would have to write up your own Array.prototype.map and Array.prototype.reduce to make them work. Is that true? If so, wouldn't seem simple to me unless you use them on a daily basis.

It's implicit in all of these that the concept is explained to you. Nobody would ask you to "implement a X" expecting you to know what X was (be it Pascals triangle, fizzbuzz, map, etc) unless X happened to be a fundamental concept in the field you are working in (not the case for any of the examples so far)

> Therefore you would have to write up your own Array.prototype.map and Array.prototype.reduce to make them work. Is that true?

Yes, that's sort of the point here. Javascript has these functions as methods of arrays (in some implementations), but the idea of the test is to write your own. They're both pretty simple, basically a for-loop and some logic.

On another note I have a hard time believing you work in JavaScript on a day to day basis and are not working with arrays. If you use jQuery or a similar library, you are working with arrays all the time and also using map-like functionality even if you don't know it by that name.

$(".foo").click(function(){})

Takes an array of elements and maps over them.

    (fn [r]
      (reduce #(cons
        (* (first %1)
           (/ (- r %2) %2))
      %1) [1] (range 1 r)))

# print a row of pascal's triangle

print "1\n";

:)