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