Re:Why 37signals Doesn't Hire Programmers Based on Brainteasers
by diego on Thursday January 05, 2012 @04:56PM
(#3430737)
Here's my naive Ruby version for what it's worth. It took me way too long, perhaps because I have a nasty cold. I've been programming since 1983. If I showed up for a code interview today, I'd probably fail miserably.
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)
Re:Why 37signals Doesn't Hire Programmers Based on Brainteasers
by mbernstein on Thursday January 05, 2012 @06:33PM
(#3431133)
Couple minutes in ruby without using the knowledge of the binomial theorem or coefficients.
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
Re:Why 37signals Doesn't Hire Programmers Based on Brainteasers
by nileshtrivedi on Friday January 06, 2012 @01:24AM
(#3432265)
Here is my version. Took me less than 5 minutes and worked the first time:
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
Re:Why 37signals Doesn't Hire Programmers Based on Brainteasers
by mbernstein on Friday January 06, 2012 @02:03AM
(#3432358)
Recursion in this case - generally in ruby as well - is not a great idea. Also, you have quite high memory requirements: O(n^2)
O(n) is quite easy in this problem.
Re:Why 37signals Doesn't Hire Programmers Based on Brainteasers
by spartango on Tuesday January 10, 2012 @05:56PM
(#3449525)
Interesting observation about Sun: I got hired into Sun (in the 2000s), not by a brainteaser puzzle or bureaucratic game but with a bit of cleverness and discussion.
Yes, Sun was big and not totally uniform, but I'll say that Sun got some seriously good talent without having to pull some of the stunts recruiters do today.
Re:Why 37signals Doesn't Hire Programmers Based on Brainteasers
by z324werwer on Thursday January 05, 2012 @03:29PM
(#3430352)
u mad bro? your solution looks quite ugly
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
Re:Why 37signals Doesn't Hire Programmers Based on Brainteasers
by haberman on Thursday January 05, 2012 @03:35PM
(#3430382)
Yes, using the binomial coefficient formula is another solution that is shorter, but I downvoted you for not being civil. Please read: http://ycombinator.com/newsguidelines.html
Re:Why 37signals Doesn't Hire Programmers Based on Brainteasers
by dxbydt on Thursday January 05, 2012 @03:57PM
(#3430485)
Just an asie: Printing Pascal's triangle for upto 10 rows is trivial. The factorials don't get big enough so you can simply use binomial coefficients (like in your ruby solution). But if you want Pascal's triangle for the 10,000th row => You can use what I wrote. If you have an easier implementation, I'd be very interested.
Re:Why 37signals Doesn't Hire Programmers Based on Brainteasers
by it on Thursday January 05, 2012 @05:36PM
(#3430911)
Here's a way to do it in Haskell:
let step row = zipWith (+) (0:row) (row++[0])
let triangle = iterate step [1]
take 10 triangle
Re:Why 37signals Doesn't Hire Programmers Based on Brainteasers
by martininmelb on Thursday January 05, 2012 @07:22PM
(#3431289)
1. I notice your solution uses recursion (at least I assume it uses recursion - I am not a ruby programmer). I think this would be an issue for large values of n (stack overflow).
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.
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=>{
})}
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 :-)