5 ms·
(So I had 10 minutes to kill) ----- import scala.collection.mutable.HashMap import scala.math.BigInt val pascals = HashMap[Int,List[BigInt]]() def pascal(ro
by dxbydt 15y ago
(So I had 10 minutes to kill)
-----
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 :-)
- z324werwer 15y agou 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
- haberman 15y agoYes, 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 http://ycombinator.com/newsguidelines.html
- dxbydt 15y agoJust 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.
- it 15y agoHere's a way to do it in Haskell: let step row = zipWith (+) (0:row) (row++[0]) let triangle = iterate step [1] take 10 triangle
- martininmelb 15y ago1. 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.
- z324werwer 15y agoit's iterative bro.
- diego 15y agoHere'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)
- mbernstein 15y agoCouple 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 edit: fixed formatting, sorry :(
- nileshtrivedi 15y agoHere 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
- mbernstein 15y agoRecursion 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.
- spartango 15y agoInteresting 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.