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]))
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/
Closest I can come is square minus the other two which gives:
1 5 9 15 20 28...
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.
(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)))))
(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;
}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.
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.
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.
(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) )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.
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...
That is definitely not what 99.999% of the programmers do every day. Professors in colleges, may be. But not programmers.
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